Re: Best multimethods/multiple dispatch implementations?

On Oct 1, 10:09 am, George Neuner <gneun...@comcast.net> wrote:
> On Mon, 29 Sep 2008 05:46:30 -0700 (PDT), Christoffer Lernv
>> Would it make sense to switch between table and tree dispatch
>> depending on dispatch type?
>
> I would seriously consider switching methods not on the type of the
> dispatch but rather based on the number of functions involved ...


Oops, typo! That's what I meant - switching between tree and table
depending on function size.


I read some paper investigating dispatch for java where a straight if-
then sequence was optimal for 1-4 types, trees for approx 5-10 and
tables for anything above that. As you say, the optimal sizes will
vary by platform and implementation language.


Seeing as SmartEiffel doesn't use tables at all and still manages very
respectful benchmarks, it's apparent a pure tree approach can work
well.


On the other hand, SmartEiffel does not use partial compilation, but
compiles the full source to be able to reduce the number of branches.


My current idea is to use LLVM, and then compile each file to LLVM
bitcode with the actual generic functions generated just before
linking.


It would be nice to be able to prune the tree of the generic function
separately for each call site - i.e. inlining it for each call and
then prune the tree to optimize dispatch time.


>> But even without taking subclassing into account I can see function
>> name clashes that will increase search-depth, esp. really simple
>> function names like "add" "append"
>
>> So we get
>> add(LinkedList l, Object o)
>> add(Vector l, Object o)
>> add(Integer i1, Integer i2)
>> add(Float f1, Floar f2)
>
> I don't understand ... what "name clash" are you worried about?


I simply mean that these all map to the same dispatch-function, even
though they are totally unrelated.


So if I (hypotetically speaking) add 10 new classes, all implementing
their own "add" function, I would suddenly discover that defining new
classes made adding to my liked list slower :)


It is sort of the unexpected results one would like to avoid if
possible, but perhaps this is a necessary consequence due to the
global nature of generic functions?


>> In some languages I'd have to generate an init method that adds all my
>> classes:
>
>> C c = addClass("Object", definition);
>> addMethod(c, "someMethod", function1);
>> addMethod(c, "someOtherMetho", function2);
>> ... and so on ...
>
>> Is that what you're referring to?
>
> Not quite. You don't want to be comparing strings at dispatch time or
> using reflection (except maybe to initialize the table).


Yes I know, it was just somewhat simpler to write the example that
way. What it gained in simplicity it obviously lost in clarity.


> I can't write this in Java off the cuff - I'd need to spend some


No problem, I just write in Java because I use it often. I can read
most languages.


>> But what about supporting dynamic loading of classes? It looks like a
>> table/hash would easily support it, but it would require a runtime
>> recompilation with a tree, unless that tree is constructed during
>> runtime - in which case it seems like a table would be many times
>> faster.
>
> Unless Java provides a way for an object to be informed whenever a new
> class file is loaded, you'll probably have to accommodate that
> yourself through some kind of registration API invoked by the new
> class.


I'd like to implement the core runtime in LLVM, C or C++, so I am not
expecting to get much for free.


Right now I am a bit stuck, because it looks like the serious drawback
to the tree-approach is that it effectively prevents any modification
to function dispatch during runtime. You would not be able to add or
remove functions for example.


I know SELF optimizes the code with type prediction trees, but I
believe that was very much linked to them using a VM, where you can
JIT certain areas depending on actual runtime behaviour.


I'm going to read the papers on SELF again, but as I currently
understand it then tree-dispatch also means I will won't be able to
add many types of meta-programming.




/Christoffer

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