Concatenative topics
Concatenative meta
Other languages
Meta
Here's my idea for how multiple dispatch could be implemented in Factor, balancing runtime and compiletime efficiency.
When a multi-generic is created and methods are added, a topologically sorted list of methods is maintained. Therefore, adding a method takes O(n) time where n is the number of methods, but the constant factor for this is small. A global cache is initialized as empty.
When the multi-generic is called, first the classes of each arguments are looked up and then the global cache is searched for the appropriate method. Maybe this would look like a tree of hashtables. If there's a cache hit, the value found will be a mapping from sets of predicate classes to methods, topologically sorted. Usually there will only be one set of predicate classes--a bunch of objects--but in general this will have to be searched through linearly.
My understanding is that this is what many Lisp systems do (or did at one point). There are some words where this would be a totally appropriate strategy to do all the time (generate-insn), and there are other words where this would make a big cache with lots of garbage, where eventually the strategy would have to be to evict old entries (like). For both like and generate-insn, the cache would probably overflow prompting the next strategy.
If the global cache grows too big (indicating that there have been lots of slow lookups, and there will probably be more in the future), then an 'automaton' (really just a dispatch DAG) is compiled (as in "Efficient Multiple and Predicate Dispatching" by Chambers and Chen) to efficiently handle all lookups, including for predicate classes, using n single dispatches if the multigeneric has n arguments.
We don't compute this immediately when methods are added, because this takes a bit of time to compute (proportional to the number of DAG nodes times the number of methods, which should be at least the number of methods squared) and it would make loading files slow. That is, unless there's some way to incrementally add to the DAG. But I don't see how to do this.
Once the DAG is computed, there is no reason to have a global cache over it, since the DAG should be just as efficient. Maybe the deploy tool should construct all possible DAGs ahead of time, so they don't have to be constructed at runtime.
The polymorphic inline cache will have to work whether a DAG has been constructed or the megamorphic global cache is being used. Multimethod PICs could be a bunch of single-dispatch PICs chained together, basically into a tree. A possible optimization is to use a DAG instead of a tree, based on the DAG for the whole dispatch. The advantage of this is that nodes could be shared instead of duplicated. Who knows which strategy is really better.
If propagation detects that arguments to a multigeneric are of restricted classes, then the dispatch might be convertible to single dispatch, or dispatch of lower arity. Here's a naive algorithm for implementing this which works efficiently with adding methods, but is O(n) in the number of methods on the multigeneric:
Maybe there's a way of organizing the methods ahead of time to make this calculation more efficient. For example, multigenerics could keep track of the partial order of the methods in a way that gives an efficient operation for finding all the methods <= a listing of classes. The other thing that needs to be efficient is testing whether a set of methods dispatches on fewer arguments.
For a given set of classes inferred by propagation, we only need one partially dispatched generic. We can reuse this. When methods are added to the multigeneric, then each partially dispatched version is checked for whether this new method is applicable. If so, it is added. This could, in general, make the specialized version dispatch on more arguments, and the surrounding machinery already handles this (see the next section).
This version of partial dispatch is agnostic about which way things are implemented; it doesn't require the DAG. It might happen that a DAG is used for the fully generic version, but a megamorphic global cache is used for the paritally dispatched version (if the original multigeneric dispatched on three or more arguments).
If a multigeneric only has methods for dispatching on a one of the arguments, then it is compiled as a GENERIC# is now. This includes when one argument is always indicated to dispatch on the same class--in this case, that only means that that has to be checked, and it won't influence dispatch. When a method is added that makes it multiple dispatch, callers have their PICs updated and the internal dispatch mechanism of the generic is changed to act like a multigeneric (its methods are topologically sorted, the megamorphic cache is initialized, etc).
Similarly, if a multigeneric requires dispatch on some, but not all, of its arguments (even if it is left being a multigeneric), it can be compiled more efficiently for this case.
A big part of the gain for these might be in the PICs. If a multigeneric doesn't dispatch on a particular argument, storing that argument's classes in PICs would be useless and pollute the cache.
I'm not sure if this would make math operations like + as efficient as they are now. Maybe the system would have to detect things that look like math, in order to compile them according to the current method. Or maybe MATH: will just stick around.
This revision created on Tue, 2 Feb 2010 20:15:12 by littledan