Re: [Boost-build] Profiling code question

From: Markus Schöpflin (markus.schoepflin_at_[hidden])
Date: 2006-07-27 10:35:35

Rene Rivera wrote:

> Vladimir Prus wrote:
>> Hi,
>> I'm still surprised by our profiling output. Here's what I see when sorted by 
>> "net" time:
>>
>>  --count--    --gross--   --net--     --name--
>>  3.56E+06     2.62E+06    2.62E+06    [OTHER]
>>  82,825.00    9.60E+05    250,000.00  FILE_DIRSCAN
>>  138,826.00   3.50E+05    230,000.00  BUILTIN_GLOB_BACK
>>
>>
>> So, most of the net time is spent in "OTHER".
>>
>> 1. What's exactly that?
> 
> It's basically the hashing. Specifically hashitem() in "hash.c".

Quite some time ago, I did some profiling for bjam and I identified hashing 
as one possible trouble spot. Unfortunately I ran out of time and never got 
around to really make something out of my findings.

Anyway, attached is a diff (against HEAD) which implements a faster hash 
function. If you're feeling adventurous, you might want to rebuild your 
bjam with the patch applied and check if it makes any difference.

The hash code was taken from http://burtleburtle.net/bob/hash/evahash.html.

Markus

Index: hash.c
===================================================================
RCS file: /cvsroot/boost/boost/tools/jam/src/hash.c,v
retrieving revision 1.5
diff -u -r1.5 hash.c
--- hash.c	3 Oct 2005 00:47:36 -0000	1.5
+++ hash.c	27 Jul 2006 14:30:30 -0000
@@ -92,6 +92,73 @@
 static void hashrehash( struct hash *hp );
 static void hashstat( struct hash *hp );
 
+/*****/
+typedef  unsigned int  u4;   /* unsigned 4-byte type */
+typedef  unsigned char u1;   /* unsigned 1-byte type */
+
+/* The mixing step */
+#define mix(a,b,c) \
+{ \
+  a=a-b;  a=a-c;  a=a^(c>>13); \
+  b=b-c;  b=b-a;  b=b^(a<<8);  \
+  c=c-a;  c=c-b;  c=c^(b>>13); \
+  a=a-b;  a=a-c;  a=a^(c>>12); \
+  b=b-c;  b=b-a;  b=b^(a<<16); \
+  c=c-a;  c=c-b;  c=c^(b>>5);  \
+  a=a-b;  a=a-c;  a=a^(c>>3);  \
+  b=b-c;  b=b-a;  b=b^(a<<10); \
+  c=c-a;  c=c-b;  c=c^(b>>15); \
+}
+
+/* The whole new hash function */
+u4 hash(
+  register u1 * k,              /* the key */
+  u4 length,                    /* the length of the key in bytes */
+  u4 initval                    /* the previous hash, or an arbitrary value */
+  )
+{
+  register u4 a,b,c;  /* the internal state */
+  u4          len;    /* how many key bytes still need mixing */
+  
+  /* Set up the internal state */
+  len = length;
+  a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
+  c = initval;         /* variable initialization of internal state */
+
+  /*---------------------------------------- handle most of the key */
+  while (len >= 12)
+  {
+    a=a+(k[0]+((u4)k[1]<<8)+((u4)k[2]<<16) +((u4)k[3]<<24));
+    b=b+(k[4]+((u4)k[5]<<8)+((u4)k[6]<<16) +((u4)k[7]<<24));
+    c=c+(k[8]+((u4)k[9]<<8)+((u4)k[10]<<16)+((u4)k[11]<<24));
+    mix(a,b,c);
+    k = k+12; len = len-12;
+  }
+
+  /*------------------------------------- handle the last 11 bytes */
+  c = c+length;
+  switch(len)              /* all the case statements fall through */
+  {
+  case 11: c=c+((u4)k[10]<<24);
+  case 10: c=c+((u4)k[9]<<16);
+  case 9 : c=c+((u4)k[8]<<8);
+      /* the first byte of c is reserved for the length */
+  case 8 : b=b+((u4)k[7]<<24);
+  case 7 : b=b+((u4)k[6]<<16);
+  case 6 : b=b+((u4)k[5]<<8);
+  case 5 : b=b+k[4];
+  case 4 : a=a+((u4)k[3]<<24);
+  case 3 : a=a+((u4)k[2]<<16);
+  case 2 : a=a+((u4)k[1]<<8);
+  case 1 : a=a+k[0];
+     /* case 0: nothing left to add */
+  }
+  mix(a,b,c);
+  /*-------------------------------------------- report the result */
+  return c;
+}
+/*****/
+
 /*
  * hash_free() - remove the given item from the table if it's there.
  * Returns 1 if found, 0 otherwise.
@@ -108,12 +175,17 @@
         unsigned char *b = (unsigned char*)data->key;
         unsigned int keyval;
 
+#if 0
         keyval = *b;
 
         while( *b )
                 keyval = keyval * 2147059363 + *b++;
+        prev = hp->tab.base + ( keyval % hp->tab.nel );
+#else
+        keyval = hash((unsigned char*)data->key, strlen((char*)data->key), 0);
+        prev = hp->tab.base + ( keyval & ( hp->tab.nel - 1 ) );
+#endif
 
-    prev = hp->tab.base + ( keyval % hp->tab.nel );
         while(*prev )
     {
         register ITEM* i = *prev;
@@ -168,13 +240,16 @@
         #endif
             return 0;
     }
-
+#if 0
         keyval = *b;
 
         while( *b )
                 keyval = keyval * 2147059363 + *b++;
-
         base = hp->tab.base + ( keyval % hp->tab.nel );
+#else
+        keyval = hash((unsigned char*)(*data)->key, strlen((char*)(*data)->key), 0);
+	base = hp->tab.base + ( keyval & (hp->tab.nel - 1) );
+#endif
 
         for( i = *base; i; i = i->hdr.next )
             if( keyval == i->hdr.keyval && 
@@ -237,8 +312,12 @@
 
         if( hp->tab.base )
                 free( (char *)hp->tab.base );
-
+#if 0
         hp->tab.nel = hp->items.nel * hp->bloat;
+#else
+	hp->tab.nel = 1;
+        while (hp->tab.nel < hp->items.nel * hp->bloat) hp->tab.nel <<= 1;
+#endif
         hp->tab.base = (ITEM **)malloc( hp->tab.nel * sizeof(ITEM **) );
 
     if ( DEBUG_PROFILE )