Re: Best multimethods/multiple dispatch implementations?

On Thu, 25 Sep 2008 04:33:41 -0700 (PDT), Christoffer Lernv
<lerno@dragonascendant.com> wrote:


>On Sep 24, 8:00 am, George Neuner <gneun...@comcast.net> wrote:
>> On Mon, 22 Sep 2008 04:17:41 -0700 (PDT), Christoffer Lernv
>
>>> I'm thinking about something like "toString()" in Java.
>>
>>> Assuming it is implemented as a generic function, wouldn't it need to
>>> a rather imposing if-then list since there must be hundreds of
>>> versions of this function in the java libs alone?
>>
>>> Why is this not a problem?
>>
>> It could be a problem, but only if the class hierarchy is deep. That
>> is not the case in most real code ... even in enormous class
>> frameworks, studies have shown that the real world class hierarchies
>> are rarely more than about 10 levels deep.
>>
>> In Java, all the standard classes derive from Object in just a few
>> steps. Developer added hierarchies contribute little even if they
>> derive starting from existing standard classes.
>
>Does this have anything to do with hierarchy depth? Perhaps I am
>misunderstanding something.


I think you do understand, but for some reason you're hung up on
single dispatch. Discrimination trees efficiently solve *multiple*
dispatch - single dispatch is an instance of worst case behavior.




>I am assuming that to create an OO system using generic functions,
>Object#toString() is implemented as the generic function
>
>String toString(Object o) { ... }
>
>When a subclass X to Object implements an overriding function, we add
>a new function definition
>
>String toString(X o) { ... }
>
>So if we have 10 direct subclasses to Object overriding toString, we
>have 100 extra definitions of toString()


No, you get 10 extra definitions.




>So wouldn't this be independent on hierarchy depth but instead
>dependent on the number of different versions of the method?


Yes it would. I said already that discrimination's worst case is
linear in the number of overloads. I also said a table or hash is
better for single dispatch.


That said, even in large frameworks, it's unusual for a method to be
overridden by every subclass. Doing so, in fact, defeats the purpose
of using super/sub classification in the first place. Generally a
large fraction of classes will inherit a large fraction of their
functionality. So, in general, a dispatch function is likely to need
tests for only a fraction of the classes of the hierarchy.




>> The basic idea is right ... you create a dispatch table and somehow
>> index it based on the run time argument types. The problem in Java
>> (and in Lisp, see below) is that the tables have to be constructed at
>> run time.
>
>But doesn't discrimination trees mean corresponding difficulties when
>compiling the language, since a precompiled generic function will need
>to be recompiled when extended, right?


No more difficulty than any other dispatch method. If the class
hierarchy or the set of overloads changes, a table or hash also has to
be reconstructed and the code that uses it updated and recompiled.




>> In either case - table or discrimination tree - the set of type ids
>> and function overloads is known at compile time so all the tests are
>> effectively against integer constants. But in Lisp, a direct function
>> call is quite a bit faster than an indirect call via the function
>> symbol,
>
>The big win I see about discrimination trees would be that it is
>possible to merge the results of these trees to reduce them
>significantly.


The big win is in calling the function directly. The CPU, in general,
can't prefetch code through an indirect jump[*]. Almost inevitably,
the result is a pipeline stall that can take hundreds or thousands of
cycles to recover from.


Of course, there is also a penalty paid for the conditional branches
in the dispatch code, but most modern CPUs try to minimize branch
penalties using branch prediction and speculative execution. Some
high powered CPUs implement multi-way speculation - that is, at a
branch they continue executing both code paths simultaneously until
the result of the branch test is known. Some can do this through
multiple nested branches, actually following 4 or more code paths
simultaneously.


[*] Many CPUs apply branch prediction to indirect jumps, but
prediction doesn't work well with a random jump pattern, the result is
that the CPU's predictions are usually wrong, resulting in a pipeline
stall. And no CPU implements multi-way speculation for indirect jumps
- it is only done for conditional branches.




>> FWIW, I have been told off-line that some of the heavyweight Lisps do
>> now use table dispatch ... but those particular Lisps all have CLOS
>> functionality built into them rather than as a separate library so
>> they can implement the functionality however they please.
>
>Table dispatch for performance reasons or are there other reasons?


I think mostly for performance of their own object GUI frameworks.
GUI widget frameworks tend to be large and have many overloaded
methods. Under such circumstances the cumulative branch penalties of
discrimination overwhelm the prefetch penalties of indirect function
calls.


I doubt that it has much impact on user written code. OO is optional
in Lisp and 1st class functions and closures handle a lot of
situations that other languages need to use objects for. Since Lisp
programmers aren't forced to use objects, they typically use them only
when the program's data elements actually fit into a classification
hierarchy. Only rarely do CLOS hierarchies grow very large.


George

Return to the comp.compilers page.
Search the comp.compilers archives again.