Re: Best multimethods/multiple dispatch implementations?

On Thu, 18 Sep 2008 01:50:16 -0700 (PDT), Christoffer Lernv
<lerno@dragonascendant.com> wrote:


>On Sep 16, 1:17 am, George Neuner <gneun...@comcast.net> wrote:
>>> I know Dylan and CLOS also has implementations, but I heard CLOS'
>>> might be pretty slow.
>>
>> 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. But remember that the dispatch is optimized and tailored
to the type signatures of the overloads - if a particular argument has
the same type in several overloads, it is only useful to identify the
set and does not need to be checked individually for each overload.
If a particular argument has the same type in every overload, a good
CLOS implementation won't even check it.


Even the worst case is typically not bad. Most generic function
overloads in CLOS correspond directly to object methods in other OO
languages. Since most real world object hierarchies are fairly
shallow, most worst case generic functions have only a small number of
overloads.


If the object hierarchy and the set of function overloads are fixed at
compile time, then CLOS usually does a pretty good job with them. If
the programmer (ab)uses Lisp's power to change the object hierarchy or
generate new functions at run time, then performance will suffer.




>> It is quite feasible to have both object bound methods and separate
>> generic MD functions in the same language. You could use the same MD
>> dispatch method for each, but method tables are more efficient for
>> single dispatch. MD tables can get very large but they are mostly
>> sparse and so can be compressed effectively. However, compressing the
>> tables slows lookup at run time. This is ok if few MD dispatches are
>> expected, but if you anticipate a lot of use, using discrimination
>> trees like CLOS may be a better bet.
>
>Aren't there some languages with hybrid dispatch using tables or trees
>depending on the tree depth?


There may be, but I'm not aware of any. Most languages don't even
have multiple dispatch. Hashing is another to go for single dispatch
but I've not yet seen it used for multiple dispatch.


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.




>With even rudimentary type inference I suppose one would be able to
>cut away a lot of branching.


Basically, what you need to figure out how is which arguments are
discriminating (ie. the same argument has a different type in
different overloads) and how many different types each argument can
assume. An argument's discriminating value is proportional to the
number of different types it could have - an argument with only one
type has no discriminating value.


ex:
  f( X, A, I, I )
  f( X, A, I, R )
  f( X, C, I, I )
  f( Y, A, I, I )
  f( Y, B, I, I )
  f( Y, C, I, I )


where X,Y,A,B,C,I & R are potential argument types.


You don't need to test arg3 at all because it is always type I and so
has no discriminating value. You only need to test arg4 when arg1 is
type X and arg2 is type A. And when arg2 is type B there is only one
choice of overload. So the dispatch pseudo code could look something
like:


      if (arg2 = B) ...
      else
      if (arg2 = A)
            if (arg1 = X)
                  if (arg4 = I) ...
                  else
                  if (arg4 = R) ...
                  else
                        error
            else
            if (arg1 = Y) ...
            else
                  error
      else
      if (arg2 = C)
            if (arg1 = X) ...
            else
            if (arg1 = Y) ...
            else
                  error


And, of course, if the test for argument type is heavy, you'd want to
do it only once per argument and cache the result.




>Do you know of any papers on CLOS dispatch implementations?


I don't know of any CLOS-specific papers. Much of the development of
Lisp predates the web ... although Common Lisp and CLOS date to the
early 80's they are based on older implementations. CLOS is mostly
based on an early Lisp extension called LOOPS, but it borrows ideas
from a number of other early OO languages as well.


I don't know when the discrimination tree implementation became the
preferred dispatch method or if there are papers online regarding any
of the older languages.


However, there are a fair number of papers on multimethod and generic
function implementation as well as papers on optimizing discrimination
networks so I imagine it shouldn't be too hard to find something
useful.


George

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