CFP: USENIX Java Virtual Machine Symposium

[Bryce McKinlay]

Godmar Back wrote:

> Isn't the algorithm gcj uses basically selector indexed dispatch
> tables (STI) which is pretty standard for multiple inheritance
> dispatch?  (Except that you don't spend any time trying to
> compress the selector tables?)
>
> How is it different?

I took a look at the Vitek & Horspool paper you referenced.

The basic "STI" technique as described there appears to be vtable
dispatch adapted for dynamically typed languages (eg Smalltalk/Self). In
those languages there is no concept of a ClassCastException or
incompatible type assignment: any object can be assigned to any
variable.
For that reason the basic "STI" table would get very large very quickly,
because you need CxM entries in the table, where C is the number of
classes and M is the number of unique method declarations (messages) in
the system. Most of the entries in such a table are typically
"not-understood" entries, so a lot of space is wasted and there is a lot
of opportunity for optimization. The rest of the paper is about
alternative dispatch techniques and ways to compress these tables down
to
realistic levels.


> It seems to me that you get the advantage of dense
> partial interface dispatch tables simply by virtue of
> Java's simply inheritance scheme.

Right. The only time that empty entries appear in the itables is when a
class implements an interface but does not define all its methods. This
happens if an interface is changed and recompiled but the class
implementing it is not. Its also the major problem with the way this is
implemented in gcj: new methods can only safely be added to the end of
an
existing interface if you want to maintain binary compatibility. If
methods are removed or inserted, the offsets compiled into existing call
sites will be wrong. Of course, this is also a problem with gcc's
current
C++ vtable dispatch also. Is it solved by the new ABI? I don't know.

It should be noted that the index problem is a problem with gcj's
implementation and not the technique in general. It would work just fine
in a JIT, because the method offset used at the call site is calculated
at runtime.


> Compacting the per interface vectors would require some of
> the optimizations you proposed; I don't know if Bryce did any
> of these.

We do try to conserve entries in the ioffset tables by sharing an entry
between multiple classes when possible - see _Jv_FindIIndex(). I'm not
sure how well this works in practice - its easy enough to modify libgcj
to dump out a few stats when building the tables, but I havn't tried any
sufficiently large applications to generate useful data. Its possible
that a smarter algorithm for calculating the iindex could get better
results, but I doubt the ioffsets tables are going to get unreasonably
large. Serializable and Cloneable would be the ones to watch, I guess.

I definitely still think that a paper on this would be interesting, and
I do hope to finally get around to writing it one day soon. Although the
design is perhaps not a radical departure from existing techniques, I
think it is interesting because it specific to Java (interfaces). It
would be interesting to compare it to C++ MI dispatch of pure virtual
bases under the new ABI, something that I'll admit I don't know much
about. The paper would certainly make interesting reading for people
developing VMs and JITs: even if our technique has been used already in
a
Java implementation (maybe in Hotspot or IBM's compiler), it hasn't been
documented, AFAIK. I took a quick look at the ORP compiler and although
it has interface vtables in each class, similar to our class interface
dispatch tables (itables), it does not have the ioffset tables and must
loop to find the correct vtable. It also does not incorporate type
checking information into the tables, so its "instanceof" implementation
is not constant-time. (thats another advantage of our approach that has
yet to be exploited - the type checks and interface dispatches are
efficient enough that they could conceivably be inlined by the compiler)

regards

  [ bryce ]