Performance Update

[Per Bothner]

On 07/13/2009 01:38 PM, John Rose wrote:
> 3. Make some cases of boxing/unboxing optimizable, by including strong
> escape analysis in the JIT, including Integer.valueOf.   This point
> only applies to JVMs with full-power JITs, and requires some special
> pleading for Integer.valueOf, because of its interning behavior.

I think a good start would be escape *annotations*.  The idea is that
either a library writer (human) or a compiler can emit @NonEscape
annotates on certain method parameters.  Verifying @NonEscape can
be done locally, and hence much more cheaply - even potentially
by less powerful VMs, as on a mobile device.

Here is a strawman proposal I wrote up:

It seems much simpler if @NonEscape is an annotation that the
(library) programmer *explicitly* adds.  That makes it part of the
actual ABI of a method, which means a VM can throw a link-time
exception if the annotation "lies".  This should be much simpler
so that even a relatively simple VM can implement it.

For the sake of discussion, I'll use @NonEscape as a new anotation
which may be applied to method parameters.  It means that the
parameter *may* refer to a stack-allocated object.  It can also be
applied to a non-static method, in which case it applies to the
implicit 'this' parameter.

@NonEscape put certain (enforced) restrictions on how a variable is
used.  A field can be selected from it.  It can be passed as a
parameter, but only if the parameter is @NonEscape.  Methods can be
called, but only methods where the 'this' parameter has the @NonEscape
property.  No other use of a NonEscape variable is allowed.  You
cannot compare it using ==, only by calling (non-default) equals.
You cannot store the variable in a field, nor in an array.

For simplicity, @NonEscape is only allowed on variables that have a
final class type.  This allows the object header to be elided, since
we know statically the class of the referenced object.

These restrictions should be easy to check by javac
(or other static compilers), and also the run-time
verifier.  (Ideally we want to do both, but the javac
changes are less urgent.)

Consider a local variable:

   Complex z = new Complex();

If z satisfies the requirements of a @NonEscape
variable, then we can stack-allocate the
constructed Complex.  Or allocate its various
fields in separate registers.

We can explicitly annotate z:

   @NonEscape Complex z = new Complex();

This can allow javac to check the programmer's intent.  However, note
that (unless I'm missing something) annotations on local variables are
not (in Java6) written to the class files.  Hence, unless we extend
the class file format with a new attribute, the VM can't count on this
annotation.  But that's probably OK: It more convenient for
programmers to not have to annotate local variables, and it seems
fairly easy for the VM to infer whether a local variable is
non-escaping.  That way applications writers don't have to write
@NonEscape annotative, but can still get the performance benefit of
libraries using @NonEscape annotations.

This allows for efficient but verbose code.  For example:

public final class Complex {
   double re, im;
   public static void negate(@NonEscape Complex arg, @NonEscape Complex 
result) {
     result.re = -arg.re;
     result.un = -arg.im;
   }
   ...
}

Using it:

   Complex z = new Complex();
   ...;
   Complex zneg = new Complex();
   Complex.negate(z, zneg);

Ultimately, we'd like:
   zneg = - z;

but just getting rid of the explicit temporaries would help:
   Complex zneg = Complex.negate(z);

We can do that with a simple convention.  Change the
definition of Complex to:

public final class Complex {
   double re, im;
   public static void negate$F(@Result Complex result, @NonEscape 
Complex arg) {
     result.re = -arg.re;
     result.un = -arg.im;
   }
   ...
}

Note the "$F" suffix, which is used for new "calling convention".

Note also the new @Result annotation, which extends (subsumes)
@NonEscape, but indicates the "function result".  (The @Result
parameter is first, so we can handle varargs methods.)

Now the compiler can translate:
   Complex zneg = Complex.negate(z);
to:
   Complex zneg = new Complex();
   Complex.negate$F(zneg, z);

This gets more interesting with compound expressions:

   Complex r = Complex.add(Compile.mul(a, b), c)

would be syntactic sugar for:
   @NonEscape Complex temp1 = new Complex();
   Complex.mul$F(temp1, a, b);
   Complex r = new Complex();
   Complex.mul$F(r, temp1, c);

Note that the generated .class files would be
portable even to "legacy" JVMs.  However, JVMs
that  make use of @NonEscape annotations can
compile the methods to more efficient code.

Clearly, this isn't a precise enough design, but
perhaps it can  be the start of something workable.
I think it's important to try it. If this is a dead
end that has been explored and found unworkable or
too difficult, I'd like to know that.

Possible extensions to consider beyond the basic idea:
* Infix operators: 'x + y' is sugar for 'x.add(y)'.
* Non-escaping stack-allocated arrays, especially
useful for varargs.
* "inlining" structs in other classes.  I.e. something
like @NonEscape for fields. Such a field could only
be passed to method as a @NonEscape parameter.
-- 
	--Per Bothner
per at bothner.com   http://per.bothner.com/