1) summary of current state
MMD (multi method dispatch) is used to find a method for binary operations like "add" or "cmp" depending on the classes (or types) of the left and right operand. The current implementation utilizes a quadratic table per function. Entries can be added dynamically with the mmdvtregister opcode.
For the MMD_ADD function of two Integer PMCs:
add Px, P.Integer, P.Integer
a different slot is used as for adding an Integer and a PerlInt
add Px, P.Integer, P.PerlInt
(the P.type notation indicates the PMC class)
We have already a native Integer PMC and PyInt, PerlInt, and TclInt variants in the Parrot tree. At least the first three are doing basically the same. They should just inherit the functionality of Integer. The same is true for other Parrot core types.
But creating even a static setup of MMD functions for all permutations of Integer PMCs is almost impossible, the more that another HLL can easily be added at runtime. Creating MMD slots for this type would need the knowledge of other existing types including their behavior. And there are of course more permuations: add P.Float, P.int ...
E.g.
$P0 = new "PyInt" # or "PerlInt", "TclInt", Integer, ... $P1 = new Integer # or "PerlInt", "TclInt", ... $P2 = add $P0, $P1
If Parrot should be able to run code originating from different HLLs the core implementation has to provide a common and reasonable subset of functionality. [1]
Currently even above mixed types "add" operation isn't working (The Integer could be the result of a Parrot library call).
2) n-dimensional MMD
Perl6 supports a more general form of MMD:
multi sub foo(ClassA $a, ClassB $b, ClassC $c : ...) { ... }which dispatches on the types of three invocants. Extending the static two-dimensional table to even just one more dimension would already occupy more memory then most computers have (yes, I know that tables can be compressed - just add one more dimension ...:-)
3) 1-dimensional method lookup
This is handled by VTABLE_find_method. A new method can easily be installed by calling VTABLE_add_method. Both are under control of the class that implements these two VTABLEs.
4) Proposed changes:
a) All method lookup goes through VTABLE_find_method. To achieve MMD functionality, two arguments are added to the find_method signature:
PMC* find_method(STRING* meth_name, INTVAL mmd_nr, INTVAL* mmd_flag)
mmd_nr is the MMD invocant number:
0 := first (or only invocant) 1 := second invocant (e.g. right argument of 2-dim MMD) ...
mmd_flag is a pointer to an integer, indicating the desired behavior:
The caller sets:
mmd_flag := NULL ... no MMD, plain method lookup
mmd_flag := &depth ... return the next matching method starting
at the given parent search depth depth := 0 this class
:= 1 first parent in search order
:= n n-th pareht ...The called class returns either NULL (if method wasn't found) or a pointer to the method function. C< *mmd_flag > is set to the search depth of the found method.
Additionally the class can set C< *mmd_flag > to -1 if no further MMD lookup should be performed, i.e. the returned function (if any) should be used.
A 2-dimensional MMD search for a method looks similar to this:
mmd_flag = 0
do
meth = left.find_method(left, "name", 0, &mmd_flag)
if mmd_flag == -1
return meth
if (meth)
push(found, (meth, mmd_flag, 0))
mmd_flag ++
else
break
mmd_flag = 0
do
meth = right.find_method(right, "name", 1, &mmd_flag)
if (meth)
push(found, (meth, mmd_flag, 1))
mmd_flag ++
else
break
if ! found.elements
return NULL
sort { distance_func } found
return found[0].meth
b) the C<add_method> vtable is extended with one argument:
void add_method(STRING* meth_name, INTVAL mmd_nr)
The default implementation uses a store_global like the opcode:
store_global "class_name_right\0__1", "meth_name", func
c) Parrot objects have a dedicated parent_search_array of classes. Plain PMCs have "self_name" and their parent names in the C<isa_str>. To simplify and unify both schemes, we move the functionality into the vtable:
vtable->mro ... array of classes for method resolution order
5) Performance considerations
As these scheme obviously needs several lookups to find a matching MMD function the result should be cached. This caching can be efficiently done at the opcode level in predereferenced run loops (including JIT) with a PIC (polymorphic inline cache). [2]
A PIC scheme outperforms the current static MMD table lookup by 30% up to 70% for overloaded operations.
A cache invalidation function is called from add_method (and remove_method) which resets entries for the passed class.
Method lookups called from inside Parrot aren't really very common. Inside a PMC method wrapper the involved types and the inheritance is known so that the super() method can be called statically.
One remarkable exception is C<sort>, where a 2-dimensional MMD compare function is called. But normally you would sort homogeneous types so that a caching similar to the PIC can be done.
Additionally we already have a method cache which is quite efficient.
Further related mails
[1] Subject: "overloaded operator calling conventions"
The common subset of all current target languages is that a new left-hand side PMC is created.
[2] Subject: "PIC for more MOPS but not only"
Subject: "PIC again"Shows some performane timings and more usage of PIC.
and Subject: "MMD dispatch"
A warnocked variant of this mail.
Comments welcome, leo
