Spread problem with > 10 arguments
John.Rose at Sun.COM
Mon Jul 6 17:17:05 PDT 2009
On Jul 6, 2009, at 7:40 AM, Fredrik Öhrström wrote:
> Because in the source code for JavaMethodHandle you will
> see an example of the combinatorial explosion of possible
> method types that I am flagging as a serious problem
> unless generic invocation is supported.
Yes, it is a serious problem. If you look at the Reference
Implementation code, you'll see places where bytecode generation is
stubbed out, and that is some cause for concern.
I should point out that the R.I. uses signature normalization in
several ways to mitigate the explosion you predict.
Many of the combinators (those with the word "Generic" in their class
names) either convert from or to an all-Object calling sequence. This
cuts the space of calling sequences to O(N) (where N is the maximum
argument list length).
The combinators which convert to and from arbitrary calling sequences
manage primitive values by first retyping them to long or int (with no
data change) and then managing boxing and value conversion with little
plugins. This would bring the space of "raw" calling sequences to
O(N**3), but further normalizations (sorting by kind, and then
lengthening all ints to long if there are any longs) makes the space
A final point about the explosion: It is almost certain to trail off
after 10 arguments, because of the relative scarcity of signatures
with N>10 in actual code. There is no plausible scenario (that I know
of) where we'll actually experience N**2 (or even linear) growth in
the complexity of argument signatures. Java programs are not that
This is still too many little classes, and in any case requires
dynamic bytecode weaving and/or some sort of fully polymorphic calling
mechanism. The solution I am proposing is to use the hardwired
"little classes" up to a few arguments (say N = 5 to 10) and back off
to full polymorphism using flyby adapters. This solution has no
effect on the public API, except perhaps exposing the flyby type
ArgumentList as an option (alternative to Object) with
spreadArguments, collectArguments, etc. At any rate, I'd like to
allow List where Object is allowed already for varargs processing.
As an internal implementation tactic, I think this is better for
HotSpot than using varargs Object arrays, because it puts less "magic"
in the JVM; you can implement the varargs mechanisms on top of it, but
the code complexity is lower (I think) than putting varargs processing
directly into the runtime.
> Even with the clever compression scheme already in place,
> it seems to me (please correct me if I am wrong) that
> JavaMethodHandle requires 180 methods to handle up to 5 arguments.
The most complex adapter module in the R.I. is ToGeneric, which builds
adapters that can take any calling sequence, and convert it to (non-
varargs) Object arguments and return value. There is one "little
class" per number of arguments; those classes A0..A5 extend JMH and
contain a total of 140 "invoke" methods.
> With up to 10 arguments it would have to implement 605 methods
> and with up to 20 arguments it would have to implement 2205 methods.
Yes A0..A10 contain 275 "invoke" methods. So your estimates are a
little high, but only by a small factor.
> I think this signifies more than just a tricky implementation matter.
> It is a clear indication that managing all possible signatures is
> that should be inside the JVM and not implemented in bytecode.
> Also, since the performance question for smaller JVMs is often
> I would like to compare the situation with closures. Apparently a lot
> of people would like to see closures in the Java.
> It is indeed possible to compile a closuresq for loop as efficiently
> as a
> standard Java for loop. However the optimizations needed to do this
> approximately: inlining, escape-analysis, object explosion.
> These are the same optimizations needed to optimize MethodHandle
> generic invocation efficiently!
At the JVM implementation level, this is really the same conversation
as closures. You are right that there is no significant difference
between method handles and closures. (At the *JVM* *level*! But
closures are essentially a language feature with a likely set of
implementation tactics, whereas method handles are not a language
feature, except for minimal punch-through in Java's type system.)
> But no one complains that closures should
> not be added to Java because non-optimizing JVMs will not execute
> them as
Here's an alternate and more likely cause for that silence: No one
complains about this with closures because the people arguing about
closures are language and applications people, and they rarely think
in great detail about JVM implementation. This conversation right
here and now is likely to be a cutting edge conversation about JVM
implications of function pointers and the like.
> I think that any reasonable JVM that is interested in any sort of
> performance will have some sort of optimizer. Heck, even the JVM
> inside the SIM card in a modern GSM/3G phone can now execute at a
> couple of
> hundred MHz and have 1 GB of memory! :-)
Good point. Counter-points: It is risky to declare a minimum size
for a JVM. Also, cycles on a small device drain power, which is the
real limited resource. So those 100's of MHz are only a peak rate.
Running more frequent GCs or a complex JIT could warm up your handset
more than the system designers will permit. As for deeply optimizing
background compilers (like HotSpot's), only on big power-guzzling
multi-core machines is there a concept of pre-paid cycles, which a JIT
can soak up almost "for free". I'm not familiar with the efficiency
characteristics of JRockit's eager JIT, but even if runs 1000
instructions to generate one instruction (which would be very good, if
combined with optimization), that's still a pretty big power spike to
start up an application.
More information about the mlvm-dev