Re: Best multimethods/multiple dispatch implementations?

"Christoffer Lernv" <lerno@dragonascendant.com> a icrit dans le message de
news: 08-09-112@comp.compilers...
> 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?


there may be an imposing _tree_ of if-then (with good partitioning
values, you may be able to run only log2(if-count), you may also use
partitioning value so as to get some log2(if-count) + K, while
ensuring that mostly used functions uses at most K if-then, it may be
interesting if K is small and the frequency for the mostly used
functions is really higher than that of others).


e.g.
if (very_frequent_func_criteria) {
}
else if (lesser_very_frequent_func_criteria) {
}
else if (criteria_for_first_half_other_funcs) {
        if (criteria_for_first_quarter_other_funcs) {
                if (func1_criteria) {
                }
                ...
        }
        else { // second quarter
                ...
        }
}
else { // second half
        ...
}


does it make sense?
HIH
Armel

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