Patch: Interface dispatch table optimization

Patch: Interface dispatch table optimization

[Bryce McKinlay]

[-- Attachment #1: Type: text/plain, Size: 499 bytes --]

It turns out that we can allocate interface dispatch (jclass->idt) 
tables as a single struct, rather than a struct that contains a pointer 
to another table. This means that only one idt allocation is required 
for each class/interface, and _Jv_AllocBytes can be used to reduce the 
memory that needs to be scanned by the GC.

In addition, this means that two less pointer dereferences are required 
for every interface call!

I'm going to test this a bit more, then check it in to trunk.

Bryce



[-- Attachment #2: libjava-idt-optimization.patch --]
[-- Type: text/x-patch, Size: 3712 bytes --]

2006-02-09  Bryce McKinlay  <mckinlay@redhat.com>

	* java/lang/Class.h (_Jv_IDispatchTable): Put cls.itable and
	iface.ioffsets inline, instead of as pointers.
	* link.cc (null_idt): Update definition.
	(_Jv_Linker::prepare_constant_time_tables): Allocate klass->idt and
	as a single struct. Use _Jv_AllocBytes, not _Jv_AllocRawObj.
	(_Jv_Linker::generate_itable): Likewise, for iface->idt.
	(_Jv_Linker::find_iindex): Assign new iface->idt when resizing
	ioffsets.

Index: link.cc
===================================================================
--- link.cc	(revision 110767)
+++ link.cc	(working copy)
@@ -552,7 +552,7 @@
 #define INITIAL_IOFFSETS_LEN 4
 #define INITIAL_IFACES_LEN 4
 
-static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, NULL} };
+static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, {}} };
 
 // Generate tables for constant-time assignment testing and interface
 // method lookup. This implements the technique described by Per Bothner
@@ -611,9 +611,6 @@
       return;
     }
 
-  klass->idt = 
-    (_Jv_IDispatchTable *) _Jv_AllocRawObj (sizeof (_Jv_IDispatchTable));
-
   _Jv_ifaces ifaces;
   ifaces.count = 0;
   ifaces.len = INITIAL_IFACES_LEN;
@@ -625,8 +622,9 @@
     {
       // The classes pointed to by the itable will always be reachable
       // via other paths.
-      klass->idt->cls.itable = 
-	(void **) _Jv_AllocBytes (itable_size * sizeof (void *));
+      int idt_bytes = sizeof (_Jv_IDispatchTable) 
+	+ (itable_size * sizeof (void *));
+      klass->idt = (_Jv_IDispatchTable *) _Jv_AllocBytes (idt_bytes);
       klass->idt->cls.itable_length = itable_size;
 
       jshort *itable_offsets = 
@@ -725,17 +723,15 @@
       /* Create interface dispatch table for iface */
       if (iface->idt == NULL)
 	{
-	  iface->idt
-	    = (_Jv_IDispatchTable *) _Jv_AllocRawObj (sizeof (_Jv_IDispatchTable));
+	  int idt_bytes = sizeof (_Jv_IDispatchTable)
+	    + INITIAL_IOFFSETS_LEN * sizeof (jshort);
 
-	  // The first element of ioffsets is its length (itself included).
-	  jshort *ioffsets = (jshort *) _Jv_AllocBytes (INITIAL_IOFFSETS_LEN
-							* sizeof (jshort));
+	  iface->idt = (_Jv_IDispatchTable *) _Jv_AllocBytes (idt_bytes);
+
+	  jshort *ioffsets = &iface->idt->iface.ioffsets[0];
 	  ioffsets[0] = INITIAL_IOFFSETS_LEN;
 	  for (int i = 1; i < INITIAL_IOFFSETS_LEN; i++)
 	    ioffsets[i] = -1;
-
-	  iface->idt->iface.ioffsets = ioffsets;	    
 	}
     }
 }
@@ -931,9 +927,16 @@
 	  int newlen = 2 * len;
 	  if (i >= newlen)
 	    newlen = i + 3;
+
+	  int idt_bytes = sizeof (_Jv_IDispatchTable) 
+	    + (newlen * sizeof (jshort));
+	    
+	  _Jv_IDispatchTable *new_idt 
+	    = (_Jv_IDispatchTable *) _Jv_AllocBytes (idt_bytes);
+
 	  jshort *old_ioffsets = ifaces[j]->idt->iface.ioffsets;
-	  jshort *new_ioffsets = (jshort *) _Jv_AllocBytes (newlen
-							    * sizeof(jshort));
+	  jshort *new_ioffsets = new_idt->iface.ioffsets;
+
 	  memcpy (&new_ioffsets[1], &old_ioffsets[1],
 		  (len - 1) * sizeof (jshort));
 	  new_ioffsets[0] = newlen;
@@ -941,7 +944,7 @@
 	  while (len < newlen)
 	    new_ioffsets[len++] = -1;
 	  
-	  ifaces[j]->idt->iface.ioffsets = new_ioffsets;
+	  ifaces[j]->idt = new_idt;
 	}
       ifaces[j]->idt->iface.ioffsets[i] = offsets[j];
     }
Index: java/lang/Class.h
===================================================================
--- java/lang/Class.h	(revision 110783)
+++ java/lang/Class.h	(working copy)
@@ -129,13 +129,13 @@
     jshort iindex;
     jshort itable_length;
     // Class Interface dispatch table.
-    void **itable;
+    void *itable[0];
   } cls;
 
   struct
   {
     // Offsets into implementation class itables.
-    jshort *ioffsets;
+    jshort ioffsets[0];
   } iface;
 };
 

Re: Patch: Interface dispatch table optimization

[Andrew Pinski]

> It turns out that we can allocate interface dispatch (jclass->idt) 
> tables as a single struct, rather than a struct that contains a pointer 
> to another table. This means that only one idt allocation is required 
> for each class/interface, and _Jv_AllocBytes can be used to reduce the 
> memory that needs to be scanned by the GC.
> 
> In addition, this means that two less pointer dereferences are required 
> for every interface call!
> 
> I'm going to test this a bit more, then check it in to trunk.
> 
> Bryce
> 
> -static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, NULL} };
> +static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, {}} };

I cannot remember if {} is valid C++, I think it is but I am not sure.
I know it is invalid C.

-- Pinski

Re: Patch: Interface dispatch table optimization

[Bryce McKinlay]

Andrew Pinski wrote:
>> It turns out that we can allocate interface dispatch (jclass->idt) 
>> tables as a single struct, rather than a struct that contains a pointer 
>> to another table. This means that only one idt allocation is required 
>> for each class/interface, and _Jv_AllocBytes can be used to reduce the 
>> memory that needs to be scanned by the GC.
>>
>> In addition, this means that two less pointer dereferences are required 
>> for every interface call!
>>
>> I'm going to test this a bit more, then check it in to trunk.
>>
>> Bryce
>>
>> -static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, NULL} };
>> +static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, {}} };
>>     
>
> I cannot remember if {} is valid C++, I think it is but I am not sure.
> I know it is invalid C.
>   

Is there an alternative? It seems to accept it without any complaints.

Bryce

Re: Patch: Interface dispatch table optimization

[Andrew Pinski]

> 
> Andrew Pinski wrote:
> >> It turns out that we can allocate interface dispatch (jclass->idt) 
> >> tables as a single struct, rather than a struct that contains a pointer 
> >> to another table. This means that only one idt allocation is required 
> >> for each class/interface, and _Jv_AllocBytes can be used to reduce the 
> >> memory that needs to be scanned by the GC.
> >>
> >> In addition, this means that two less pointer dereferences are required 
> >> for every interface call!
> >>
> >> I'm going to test this a bit more, then check it in to trunk.
> >>
> >> Bryce
> >>
> >> -static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, NULL} };
> >> +static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, {}} };
> >>     
> >
> > I cannot remember if {} is valid C++, I think it is but I am not sure.
> > I know it is invalid C.
> >   
> 
> Is there an alternative? It seems to accept it without any complaints.

Actually it is valid C++, I forgot that in C++ there are empty structs
unlike C.

Thanks,
Andrew Pinski

Re: Patch: Interface dispatch table optimization

[Gabriel Dos Reis]

Bryce McKinlay <mckinlay@redhat.com> writes:

[...]

| >> -static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, NULL} };
| >> +static _Jv_IDispatchTable null_idt = { {SHRT_MAX, 0, {}} };
| >>
| >
| > I cannot remember if {} is valid C++, I think it is but I am not sure.
| > I know it is invalid C.
| >
| 
| Is there an alternative?

It is valid C++.

-- Gaby

Re: Patch: Interface dispatch table optimization

[Per Bothner]

Bryce McKinlay wrote:
> It turns out that we can allocate interface dispatch (jclass->idt) 
> tables as a single struct, rather than a struct that contains a pointer 
> to another table. This means that only one idt allocation is required 
> for each class/interface, and _Jv_AllocBytes can be used to reduce the 
> memory that needs to be scanned by the GC.

We need a writeup of how interface dispatch works, either in the
internals manual or the wiki.  I don't find it.  Is there one?  If so,
could you update it?  If since you have this fresh in your mind, could
you do a write-up?

Not only for documentation, but it should also be done in a way that
counts as "publication" in terms of patent prior-art.
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/

Re: Patch: Interface dispatch table optimization

[Tom Tromey]

>>>>> "Per" == Per Bothner <per@bothner.com> writes:

Per> We need a writeup of how interface dispatch works, either in the
Per> internals manual or the wiki.  I don't find it.  Is there one?

A comment in the code points to your original spec:

http://gcc.gnu.org/ml/java/1999-q3/msg00377.html

There's also some longish comments in link.cc, but nothing really
tying it all together.

Tom

Re: Patch: Interface dispatch table optimization

[Bryce McKinlay]

Per Bothner wrote:
> We need a writeup of how interface dispatch works, either in the
> internals manual or the wiki.  I don't find it.  Is there one?  If so,
> could you update it?  If since you have this fresh in your mind, could
> you do a write-up?

It would certainly be good to have this. I'll try and add something to 
the wiki tomorrow, based on the existing documents.

Bryce