Re: Best multimethods/multiple dispatch implementations?

On Mon, 22 Sep 2008 04:17:41 -0700 (PDT), Christoffer Lernv
<lerno@dragonascendant.com> wrote:


>On Sep 19, 12:12 pm, George Neuner <gneun...@comcast.net> wrote:
>> <le...@dragonascendant.com> wrote:
>> >On Sep 16, 1:17 am, George Neuner <gneun...@comcast.net> wrote:
>>>> CLOS dispatch is typically implemented as an inline coded minimum
>>>> depth discrimination tree - a series of IF-THEN tests on the argument
>>>> types - ordered by the partitioning value of the function arguments.
>>>> Lisp tries to order the tests so as to most efficiently partition the
>>>> virtual search tree at each step.
>>
>>> The best case scenarios of this ought to be really fast and easy to
>>> inline, but what about methods that are frequently overridden?
>>> Wouldn't worst case be pretty bad?
>>
>> The worst case is linear in the number of overloads - that requires
>> every overload of the function to have a unique argument type
>> signature.
>
>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.


Even so, single dispatch is better done by table or hash.




>> Tables make sense for single dispatch, but there is a lot of overhead
>> associated with using them for multiple dispatch. With MD the naked
>> table is very sparse - some arguments may have no discrimination value
>> at all and the ones that do will have entries for only a very few of
>> the possible data types in the program. So an MD table will
>> necessarily be compressed and there must be a mapping from each
>> argument's potential type to an index legal for that argument's
>> dimension.
>>
>> Once you factor in the type->index mapping (which most likely will be
>> implemented by conditional chain even if the dispatch source uses a
>> tabular construct like switch" or "case"), you've lost most or all of
>> the speed advantage of using the table over just using conditional
>> chains in the first place.
>
>Won't dispatch be implemented something like this?
>
>public Object dispatch(Objekt... objekts)
>{
> int index = 0;
> for (int i = 0; i < objekts.length; i++)
> {
> index += m_poleMult[i] *
>m_poleTable[i].getPoleForClass(objects[i].getClassId());
> }
> return m_dispatchArray[index].call(objects);
>}


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. Java has the additional problem that the type checker won't
let this mess work unless the arguments are passed through as a
generic list of objects. Although, at the lowest level, this is true
no matter what the implementation language, Java's type checker is no
help when a call to the generic function has incompatible types.


Lisp (in general) also could construct the dispatch tables at run time
and then generate and JIT compile a dispatch function that indexes on
the arguments types and indirectly invokes the overload function. It
would, in fact, look very similar to the corresponding Java solution.


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, and there are no manifest pointers in the language, so unless
there is some implementation dependent language extension that allows
to create and jump through a table of raw function pointers, it is
more performant to code a conditional tree that calls the functions
directly.


That, in fact, is the original reason for using discrimination trees.
Although CLOS is considered part of Common Lisp and is built into some
implementations, it is really a standardized extension library. CLOS
began life as a set of semi-portable macros and still is a separate
loadable library in many implementations - so it had to do things as
portably as possible without sacrificing too much in performance.


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.


George

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