Spread problem with > 10 arguments

[John Rose]

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.

Hi Fredrik!

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  
size O(N**2).

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  
complex.

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  
> something
> that should be inside the JVM and not implemented in bytecode.

Yes!

> Also, since the performance question for smaller JVMs is often  
> mentioned,
> 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  
> are
> 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
> efficiently.

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  
> running
> 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.

-- John