On 08/05/2012 04:54 PM, Rob N wrote:
Thanks. It will take me a while to understand that code. Once I do,
maybe I can write a performance test. I'd like to see a comparison
between invokedynamic with guarded/chained method handles, as you
described, vs calling the dispatch logic the old fashioned way.
Rob
Hi Rob,
I'm the guy that write this piece of code an because I'm stuck in Salt
Lake City airport for the next three hours,
I suppose I can write something about this code.
The implementation is based on two papers, [1] and [2] and
yes, I've written my Phd thesis on multi-method in Java a long time ago.
The first paper describes a way to do the multi-dispatch using a table
based approach
(like a vtable dispatch but more complex), so it provides a way to
'cover your ass', i.e.
a way to have if no optimization tricks work to fallback to a dispatch
algorithm which is linear to the number of parameter
(so it doesn't depend on the number of implementations of the
multi-method which is something important).
It works like this, let say we have two methods with B extends A,
void foo(A a, A a2) { ... } // impl1
void foo(A a, B b) { ... } // impl2
the algorithm first sort the methods using their types, here because B
is more specific that A,
impl2 is more specific than impl1, so the method array is { impl2, impl1 }.
Then for each parameter index, you record in a hashmap for each
available type,
if a method implementation is applicable (can be called).
Here, the hashmap for the first parameter contains only one key, A, and
the corresponding
bitset is 11 because impl2 and impl1 can be called if A is the first
parameter.
Using the same algorithm for the second parameters you get:
hash1 = { A -> 11 },
hash2 = { A -> 01, B -> 11 }
now when the multi-dispatch is called, let say with an object of class B
and another of class A,
call.foo(B,A),
the first hashmap, hash1, doesn't contains B, in that case, follow the
supertype hierarchy and
try to find a supertype which is a key, here because B inherits from A,
B will act as A,
so you can cache (for the next call) that B -> 11 in hash1.
the second parameter is A, so the hash entry is A -> 01,
The result is
call.foo(B,A) = {11 } & { 01} = 01, so method implementation at index
1 should be called -> impl1
so calling a multi-method should never be slower than accessing to the
hashmap for each arguments,
do a bitwise-and and get the lower bit set (the more specific).
The real algorithm is more convoluted because you can have interfaces,
so you can have more than
one bitset for a class at runtime, when the array is sorted, you may
have to introduce new implementation
by example, for foo(A,B) and foo(B,A) the Java semantics require to
include a third method foo(B,B)
that will just throw an exception because foo(A,B) and foo(B,A) are not
comparable.
Moreover, there is a bunch of special case that can be used to faster
the algorithm.
If there is only one implementation, multi-dispatch is not necessary, if
there is several implementation
but only one is ever call for a callsite (the callsite is monomorphic) a
guard with test will be faster,
(maybe it's also the case for bi-morphic, and so on if only the receiver
class changed)
Also, if the language you want to implement is object oriented, then the
number method applicables
depends on the receiver class, you can use a GuardWithTest for this or
consider the receiver class
as a parameter too.
Also, maybe for a parameter, there is only one possible class, for foo
of our running example,
the first parameter is always an A, in that case, it's better to not
process a bitset for it but
just do an instanceof check (or no check at all if you know that for a
callsite the first parameter
is always an A.
Also, if you have only one parameter (one that can changed), in that
case, it's better to not
compute the set but directly store the method handle in the hash.
For foo, it will be
hash2 = { A -> impl1, B -> impl2 }
and to use the result of hashmap.get() with a fold + exactInvoker.
Also, for a specific callsite, you can have primitive type in the
signature, in that case,
you can pre-process the bitset that will be used and insert it as a
constant (with a insertArguments).
Also, depending on your CPU, some provide an instruction for the highest
bit, some for the number
of trailing zeroes (latest AMD), so if the corresponding intrinsic
exists in hotspot
(I don't think it's true now but it may change) so you may have to sort
the method in one order or
in reverse order.
So currently, as far as I remember, I've implemented the bitset
algorithm but only
if there is less than 32 implementation, so store the bitset on an int.
The hash is thread-safe but it use a splay-tree to avoid to consume to
much memory
but it may be better for performance to use a hashmap (without a
volatile access
if there is no cache miss).
Note that there is two flavor of the hash, one if there is no interface,
so calling getSuperclass()
is enough and a second one works with interfaces.
And I've also implemented all the tricks listed above.
cheers,
Rémi
[1] http://webdocs.cs.ualberta.ca/~paullu/Papers/COOTS2001-HTML/mdj.html
[2] http://www.jot.fm/issues/issue_2005_12/article3/
On Aug 5, 3:18 am, Charles Oliver Nutter <head...@headius.com> wrote:
A simple way to do what you want might be sketched out like this:
* The bootstrap method returns a CallSite + handle for your
multi-dispatch logic contained in another method.
* The multi-dispatch logic receives the actual arguments for that first call.
* Based on those arguments, you build a guarded chain of method
handles that calls the right target for the incoming types, and falls
back on the multi-dispatch lookup logic again if new types come in.
From here, you can do various combinations of guards, multiple
targets, mechanisms for quickly calculating whether the incoming types
have already been negotiated, and so on.
You want to look at the bootstrap as your way to point future calls
toward your own specialized logic; the bootstrap does not necessarily
contain that logic.
There's an example implementation of multi-dispatch
here:http://code.google.com/p/jsr292-cookbook/source/browse/trunk/multi-di...
- Charlie
On Sat, Aug 4, 2012 at 11:26 PM, Rob N <rob.nikan...@gmail.com> wrote:
Hi,
I'm trying to learn about invokedynamic and the supporting classes,
and I don't yet see how they help implement the dynamically typed
language I have in mind. From what I've read so far, when you emit an
invokedynamic instruction, you specify a bootstrap method in your
language's runtime, but that is only run once, and it must return a
MethodHandle for the CallSite. Lets say I wanted to emit something
for a CLOS-like multiple dispatch method (foo x y), that will select
an implementation method based on the classes of x and y. Would I not
have to return, from the bootstrap method, a handle to a method that
did that dispatch? So why not just emit an invokevirtual or
invokestatic directly to that method? What is the advantage of
invokedynamic here?
thanks,
Rob
--
You received this message because you are subscribed to the Google Groups "JVM
Languages" group.
To post to this group, send email to jvm-languages@googlegroups.com.
To unsubscribe from this group, send email to
jvm-languages+unsubscr...@googlegroups.com.
For more options, visit this group
athttp://groups.google.com/group/jvm-languages?hl=en.
--
You received this message because you are subscribed to the Google Groups "JVM
Languages" group.
To post to this group, send email to jvm-languages@googlegroups.com.
To unsubscribe from this group, send email to
jvm-languages+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/jvm-languages?hl=en.
