Patch: Interface Dispatch optimization, version 2

[Bryce McKinlay <mckinlay at redhat dot com>]

This is an updated patch for optimizing the interface dispatch tables. 
The previous patch would allocate too much memory for ioffsets, since it 
would add the size of _Jv_IDispatchTable when calculating the size for 
ioffsets in an interface.

This fixes that problem, and also simplifies some code, by making 
_Jv_IDispatchTable a struct which is used only for classes, and putting 
this in an anonymous union with ioffsets (used only by interfaces) in 
java::lang::Class.

I'm checking this in to the trunk.

Bryce


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

	* java/lang/Class.h (_Jv_IDispatchTable): Make it a struct. Put 
	'itable' inline, instead of as a pointer.
	(java::lang::Class): Put 'idt' in anonymous union with 'ioffsets'.
	* link.cc (null_idt): Update definition.
	(_Jv_Linker::prepare_constant_time_tables): Allocate klass->idt
	as a single struct. Use _Jv_AllocBytes, not _Jv_AllocRawObj.
	(_Jv_Linker::generate_itable): Update to use 'ioffsets'.
	(_Jv_Linker::find_iindex): Likewise. Update comment.
	* java/lang/natClass.cc	(_Jv_LookupInterfaceMethodIdx): Update for
	_Jv_IDispatchTable change.
	(_Jv_IsAssignableFrom): Likewise.

Index: link.cc
===================================================================
--- link.cc	(revision 110815)
+++ 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,9 +622,10 @@
     {
       // 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 *));
-      klass->idt->cls.itable_length = itable_size;
+      int idt_bytes = sizeof (_Jv_IDispatchTable) + (itable_size 
+						     * sizeof (void *));
+      klass->idt = (_Jv_IDispatchTable *) _Jv_AllocBytes (idt_bytes);
+      klass->idt->itable_length = itable_size;
 
       jshort *itable_offsets = 
 	(jshort *) _Jv_Malloc (ifaces.count * sizeof (jshort));
@@ -639,18 +637,17 @@
 
       for (int i = 0; i < ifaces.count; i++)
 	{
-	  ifaces.list[i]->idt->iface.ioffsets[cls_iindex] =
-	    itable_offsets[i];
+	  ifaces.list[i]->ioffsets[cls_iindex] = itable_offsets[i];
 	}
 
-      klass->idt->cls.iindex = cls_iindex;	    
+      klass->idt->iindex = cls_iindex;	    
 
       _Jv_Free (ifaces.list);
       _Jv_Free (itable_offsets);
     }
   else 
     {
-      klass->idt->cls.iindex = SHRT_MAX;
+      klass->idt->iindex = SHRT_MAX;
     }
 }
 
@@ -713,7 +710,7 @@
 _Jv_Linker::generate_itable (jclass klass, _Jv_ifaces *ifaces,
 			       jshort *itable_offsets)
 {
-  void **itable = klass->idt->cls.itable;
+  void **itable = klass->idt->itable;
   jshort itable_pos = 0;
 
   for (int i = 0; i < ifaces->count; i++)
@@ -722,12 +719,9 @@
       itable_offsets[i] = itable_pos;
       itable_pos = append_partial_itable (klass, iface, itable, itable_pos);
 
-      /* Create interface dispatch table for iface */
-      if (iface->idt == NULL)
+      /* Create ioffsets table for iface */
+      if (iface->ioffsets == NULL)
 	{
-	  iface->idt
-	    = (_Jv_IDispatchTable *) _Jv_AllocRawObj (sizeof (_Jv_IDispatchTable));
-
 	  // The first element of ioffsets is its length (itself included).
 	  jshort *ioffsets = (jshort *) _Jv_AllocBytes (INITIAL_IOFFSETS_LEN
 							* sizeof (jshort));
@@ -735,7 +729,7 @@
 	  for (int i = 1; i < INITIAL_IOFFSETS_LEN; i++)
 	    ioffsets[i] = -1;
 
-	  iface->idt->iface.ioffsets = ioffsets;	    
+	  iface->ioffsets = ioffsets;
 	}
     }
 }
@@ -881,8 +875,8 @@
 // Interface Dispatch Table, we just compare the first element to see if it 
 // matches the desired interface. So how can we find the correct offset?  
 // Our solution is to keep a vector of candiate offsets in each interface 
-// (idt->iface.ioffsets), and in each class we have an index 
-// (idt->cls.iindex) used to select the correct offset from ioffsets.
+// (ioffsets), and in each class we have an index (idt->iindex) used to
+// select the correct offset from ioffsets.
 //
 // Calculate and return iindex for a new class. 
 // ifaces is a vector of num interfaces that the class implements.
@@ -913,9 +907,9 @@
         {
 	  if (j >= num)
 	    goto found;
-	  if (i >= ifaces[j]->idt->iface.ioffsets[0])
+	  if (i >= ifaces[j]->ioffsets[0])
 	    continue;
-	  int ioffset = ifaces[j]->idt->iface.ioffsets[i];
+	  int ioffset = ifaces[j]->ioffsets[i];
 	  /* We can potentially share this position with another class. */
 	  if (ioffset >= 0 && ioffset != offsets[j])
 	    break; /* Nope. Try next i. */	  
@@ -924,16 +918,18 @@
   found:
   for (j = 0; j < num; j++)
     {
-      int len = ifaces[j]->idt->iface.ioffsets[0];
+      int len = ifaces[j]->ioffsets[0];
       if (i >= len) 
 	{
 	  // Resize ioffsets.
 	  int newlen = 2 * len;
 	  if (i >= newlen)
 	    newlen = i + 3;
-	  jshort *old_ioffsets = ifaces[j]->idt->iface.ioffsets;
+
+	  jshort *old_ioffsets = ifaces[j]->ioffsets;
 	  jshort *new_ioffsets = (jshort *) _Jv_AllocBytes (newlen
 							    * sizeof(jshort));
+
 	  memcpy (&new_ioffsets[1], &old_ioffsets[1],
 		  (len - 1) * sizeof (jshort));
 	  new_ioffsets[0] = newlen;
@@ -941,9 +937,9 @@
 	  while (len < newlen)
 	    new_ioffsets[len++] = -1;
 	  
-	  ifaces[j]->idt->iface.ioffsets = new_ioffsets;
+	  ifaces[j]->ioffsets = new_ioffsets;
 	}
-      ifaces[j]->idt->iface.ioffsets[i] = offsets[j];
+      ifaces[j]->ioffsets[i] = offsets[j];
     }
 
   _Jv_MutexUnlock (&iindex_mutex);
Index: java/lang/natClass.cc
===================================================================
--- java/lang/natClass.cc	(revision 110815)
+++ java/lang/natClass.cc	(working copy)
@@ -985,8 +985,8 @@
 _Jv_LookupInterfaceMethodIdx (jclass klass, jclass iface, int method_idx)
 {
   _Jv_IDispatchTable *cldt = klass->idt;
-  int idx = iface->idt->iface.ioffsets[cldt->cls.iindex] + method_idx;
-  return cldt->cls.itable[idx];
+  int idx = iface->ioffsets[cldt->iindex] + method_idx;
+  return cldt->itable[idx];
 }
 
 jboolean
@@ -1013,16 +1013,15 @@
         return _Jv_InterfaceAssignableFrom (source, target);
 
       _Jv_IDispatchTable *cl_idt = source->idt;
-      _Jv_IDispatchTable *if_idt = target->idt;
 
-      if (__builtin_expect ((if_idt == NULL), false))
+      if (__builtin_expect ((target->ioffsets == NULL), false))
 	return false; // No class implementing TARGET has been loaded.    
-      jshort cl_iindex = cl_idt->cls.iindex;
-      if (cl_iindex < if_idt->iface.ioffsets[0])
+      jshort cl_iindex = cl_idt->iindex;
+      if (cl_iindex < target->ioffsets[0])
         {
-	  jshort offset = if_idt->iface.ioffsets[cl_iindex];
-	  if (offset != -1 && offset < cl_idt->cls.itable_length
-	      && cl_idt->cls.itable[offset] == target)
+	  jshort offset = target->ioffsets[cl_iindex];
+	  if (offset != -1 && offset < cl_idt->itable_length
+	      && cl_idt->itable[offset] == target)
 	    return true;
 	}
       return false;
Index: java/lang/Class.h
===================================================================
--- java/lang/Class.h	(revision 110815)
+++ java/lang/Class.h	(working copy)
@@ -120,23 +120,14 @@
   { return this + 1; }
 };
 
-// Interface Dispatch Tables 
-union _Jv_IDispatchTable
+// The table used to resolve interface calls.
+struct _Jv_IDispatchTable
 {
-  struct
-  {
-    // Index into interface's ioffsets.
-    jshort iindex;
-    jshort itable_length;
-    // Class Interface dispatch table.
-    void **itable;
-  } cls;
-
-  struct
-  {
-    // Offsets into implementation class itables.
-    jshort *ioffsets;
-  } iface;
+  // Index into interface's ioffsets.
+  jshort iindex;
+  jshort itable_length;
+  // Class Interface dispatch table.
+  void *itable[0];
 };
 
 // Used by _Jv_Linker::get_interfaces ()
@@ -600,8 +591,13 @@
   jshort depth;
   // Vector of this class's superclasses, ordered by decreasing depth.
   jclass *ancestors;
-  // Interface Dispatch Table.
-  _Jv_IDispatchTable *idt;
+  // In a regular class, this field points to the Class Interface Dispatch 
+  // Table. In an interface, it points to the ioffsets table.
+  union 
+  {
+    _Jv_IDispatchTable *idt;
+    jshort *ioffsets;
+  };
   // Pointer to the class that represents an array of this class.
   jclass arrayclass;
   // Security Domain to which this class belongs (or null).