Re: Best multimethods/multiple dispatch implementations?

=?ISO-8859-1?Q?Christoffer_Lern=F6?= <lerno@dragonascendant.com>
Mon, 22 Sep 2008 04:17:41 -0700 (PDT)

          From comp.compilers

Related articles
[5 earlier articles]
Re: Best multimethods/multiple dispatch implementations? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2008-09-15)
Re: Best multimethods/multiple dispatch implementations? gneuner2@comcast.net (George Neuner) (2008-09-15)
Re: Best multimethods/multiple dispatch implementations? sh006d3592@blueyonder.co.uk (Stephen Horne) (2008-09-17)
Re: Best multimethods/multiple dispatch implementations? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2008-09-18)
Re: Best multimethods/multiple dispatch implementations? bettini@dsi.unifi.it (Lorenzo Bettini) (2008-09-18)
Re: Best multimethods/multiple dispatch implementations? gneuner2@comcast.net (George Neuner) (2008-09-19)
Re: Best multimethods/multiple dispatch implementations? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2008-09-22)
Re: Best multimethods/multiple dispatch implementations? gneuner2@comcast.net (George Neuner) (2008-09-24)
Re: Best multimethods/multiple dispatch implementations? armelasselin@hotmail.com (Armel) (2008-09-24)
Re: Best multimethods/multiple dispatch implementations? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2008-09-25)
Re: Best multimethods/multiple dispatch implementations? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2008-09-25)
Re: Best multimethods/multiple dispatch implementations? gneuner2@comcast.net (George Neuner) (2008-09-28)
Re: Best multimethods/multiple dispatch implementations? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2008-09-29)
[4 later articles]
| List of all articles for this month |

From: =?ISO-8859-1?Q?Christoffer_Lern=F6?= <lerno@dragonascendant.com>
Newsgroups: comp.compilers
Date: Mon, 22 Sep 2008 04:17:41 -0700 (PDT)
Organization: Compilers Central
References: 08-09-026 08-09-069 08-09-093 08-09-100
Keywords: OOP, performance
Posted-Date: 23 Sep 2008 14:13:31 EDT

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?


> 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);
}


I realize this is a lot longer than a simple if-then, but I was mainly
thinking about commonly overridden functions, such as class creation
or the "toString()" I already brought up.



Post a followup to this message

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