kaffe just got faster again

Date view Thread view Subject view Author view

From: Godmar Back (gback@cs.utah.edu)
Date: Sat Dec 19 1998 - 15:48:19 EST


 I implemented a faster interface lookup scheme.
Previously, every INVOKEINTERFACE instruction would invoke findMethod
to search through all methods of a class and its superclasses to find
the method that the interface invocation asked for. Utterly silly.

What I did is to precompute and store the indices in the method dispatch
table where a given interface method sits (if it's there).
This is stored in the itable2dtable array.

soft_lookupmethod, instead of taking name and signature of the
interface method, simply takes the interface itself and the index of the
method in the interface class as parameters.
I will scan the interface table to see whether the class implements that
interface, and will then consult the if2itable to find the offset in
the itable2dtable array where the indices for that particular interface
are stored. It will then add the interface method index (which I compute
in buildInterfaceDispatchTable) and retrieve the corresponding entry
in the method dispatch table.

While this may sound expensive, it's a lot less expensive than performing
a linear search through the method table using equalsUtf8Const. (even
if they were interned, I'd would think.)

The complexity of the new implementation is
O(number of interfaces implemented by that class) plus a constant.

This means, btw, that you should put the most frequently used interface
first when you write your implements clause. So put Serializable and
Cloneable last.

The results very much depend on how many interfaces an application
uses. Frequently used interfaces are HashtableEnumeration/Enumeration.
For my favorite unscientific benchmark --- compiling the class libraries
with pizza, I'm getting an improvement from an average of 18.217950 to
17.850900 user seconds over 20 runs each. This is a 2% speedup.
This was with -ms 32M -mx 96M to minimize the impact of garbage
collection. Nevertheless, I expect the speedup to be bigger with
applications that make use of more interfaces (and where the classes
that implement the interfaces have more methods, since the
complexity of the old invokeinterface implementation depended on the
number of methods in that class. This is why Alexandre's "performance.java"
is somewhat bogus, since it perform invokeinterface on a class with only
one or two methods.)

A potential opportunity to optimize this further would be to merge the
interfaces arrays and if2itable arrays in an array of the form
struct {
        Hjava_lang_Class *interface;
        short itablestart;
} [];
This would save the separate allocation and collection of the
if2itable array.

Enjoy,

        Godmar


Date view Thread view Subject view Author view

This archive was generated by hypermail 2b29 : Sat Sep 23 2000 - 19:57:24 EDT