interface dispatch

Thu Oct 21 21:44:00 GMT 1999

 Hi,
I just looked at Per's mail where he discusses his design to speed up
interface dispatch in JVMs. See
http://sourceware.cygnus.com/ml/java-discuss/1999-q3/msg00377.html
I compared it to what I'd implemented in kaffe, and noticed that
it's very similar; except that I didn't have the ioffset tables that link
interfaces back to the classes implementing them. As a result, 
I didn't have constant lookup time, but a lookup time linear in the
number of interfaces a class implements (which is very small, see 
Per's statistics.)
So I implemented the ioffsets tables as well, and while doing that I wondered 
about a few things I'd like to comment on.
First, I should note that the interface dispatch (i.e., the code that
invokes an interface on a given run-time object) cannot be as simple
as the proposed LOOKUP_INTERFACE macro:
>> #define LOOKUP_INTERFACE(CL, IFACE, IMETODINDEX) \
> (CLASS_ITABLE(CL)[CLASS_IOFFSETS(IFACE)[CLASS_IINDEX(CL)] + IMETHODINDEX])
>
This code only reliably looks up the interface if the run-time object 
indeed implements the interface, which cannot be determined at compile-time.
(You could have an option --assume-perfect-interface-dispatch, similar to
--nobound-checks, of course.)
Otherwise, it must be coupled with the test that the object indeed
implements the interface.
Per proposes this test:
> #define OBJECT_INSTANCEOF_INTERFACE(OBJ, IFACE) \
> CLASS_INSTANCEOF_INTERFACE(OBJECT_CLASS(OBJ), IFACE)
>> #define CLASS_INSTANCEOF_INTERFACE(CL, IFACE) \
> (CLASS_IINDEX(CL) <= CLASS_IOFFSETS_LENGTH(IFACE) \
> && ({unsigned short __offset = CLASS_IOFFSETS(IFACE)[CLASS_IINDEX(CL)]; \
> __offset < CLASS_ITABLE_LENGTH(CL) \
> && CLASS_ITABLE(CL)[__offset]] == IFACE}))

What I don't understand here is the "CLASS_ITABLE(CL)[__offset]] == IFACE"
part: CLASS_ITABLE(CL)[__offset] is a methodptr, IFACE is an interface.
Let's assume for a sec that methodptr is a pointer to a "method" struct
describing the method.
I think you'll have to store a field "iface" in each "method" struct and 
then test whether this method is part of this class because the class 
implements that interface. 
So the test would then be CLASS_ITABLE(CL)[__offset].iface == IFACE
or some such, where methods "m" implementing interface "i" have their 
m.iface field set to "i". 
However, Per defined methodptr as void*.
I think what he meant, and what I did for kaffe, is for methodptr to be
the actual PC to which to jump when the method is invoked.
You'd like to be able to simply test CLASS_ITABLE(CL)[__offset]
for NULL to know that the class implements the interface method.
In other words, it would be faster to omit the check that the interface
dispatch table index you found via the interface's ioffset is indeed a 
valid offset for a method defined in that very interface.
This, however, seems possible only by assigning such iindex values to 
classes that are unique among all classes. Note that Per's suggested
find_iindex function only finds those iindices for a class that are suitable
for use considering the interfaces a class implements. There is no guarantee
that two classes who implement disjoint sets of interfaces do not end up
with the same iindex. In fact, to keep the ioffset tables small, this
is desirable. (Unique iindex values, on the other hand,
make the interface ioffset tables much more sparse and bigger in size.
Again, another space-for-time trade-off.)
However, I do not see how you can make sure that a class implements 
an interface without either assuming globally unique iindices or by
introducing a check that the indexes method is indeed one that corresponds
to the interface being dispatched.
For the globally unique case, a time-for-space (slower, less space) tradeoff 
might be to store the first used index 'u' in the ioffset array for each 
interface as part of the interface, and to only store the elements including 
and following 'u', and to adjust every array access by 'u', i.e.:
unsigned short __offset = CLASS_IOFFSETS(IFACE)[CLASS_IINDEX(CL)-'u'];
	- Godmar