[or-cvs] r11700: From little acorns: redo our string and digest hashing code (in tor/trunk: . src/common)

[nickm@xxxxxxxx]

Author: nickm
Date: 2007-09-28 15:23:54 -0400 (Fri, 28 Sep 2007)
New Revision: 11700

Modified:
   tor/trunk/
   tor/trunk/ChangeLog
   tor/trunk/src/common/container.c
   tor/trunk/src/common/ht.h
Log:
 r14682@Kushana:  nickm | 2007-09-28 15:23:38 -0400
 From little acorns: redo our string and digest hashing code to be faster, since this stuff may be critical-path.



Property changes on: tor/trunk
___________________________________________________________________
 svk:merge ticket from /tor/trunk [r14682] on c95137ef-5f19-0410-b913-86e773d04f59

Modified: tor/trunk/ChangeLog
===================================================================
--- tor/trunk/ChangeLog	2007-09-28 17:36:47 UTC (rev 11699)
+++ tor/trunk/ChangeLog	2007-09-28 19:23:54 UTC (rev 11700)
@@ -21,6 +21,13 @@
     - Fix logic to look up a cert by its signing key digest.  Bugfix on
       0.2.0.7-alpha.
 
+  o Minor bugfixes (performance):
+    - Use a slightly simpler string hashing algorithm (copying Python's
+      instead of Java's) and optimize our digest hashing algorithm to take
+      advantage of 64-bit platforms and to remove some possibly-costly
+      voodoo.
+
+
 Changes in version 0.2.0.7-alpha - 2007-09-21
   o New directory authorities:
     - Set up moria1 and tor26 as the first v3 directory authorities. See

Modified: tor/trunk/src/common/container.c
===================================================================
--- tor/trunk/src/common/container.c	2007-09-28 17:36:47 UTC (rev 11699)
+++ tor/trunk/src/common/container.c	2007-09-28 19:23:54 UTC (rev 11700)
@@ -694,8 +694,13 @@
 static INLINE unsigned int
 digestmap_entry_hash(const digestmap_entry_t *a)
 {
-  uint32_t *p = (uint32_t*)a->key;
-  return ht_improve_hash(p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]);
+#if SIZEOF_INT != 8
+  const uint32_t *p = (const uint32_t*)a->key;
+  return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
+#else
+  const uint64_t *p = (const uint64_t*)a->key;
+  return p[0] ^ p[1];
+#endif
 }
 
 HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,

Modified: tor/trunk/src/common/ht.h
===================================================================
--- tor/trunk/src/common/ht.h	2007-09-28 17:36:47 UTC (rev 11699)
+++ tor/trunk/src/common/ht.h	2007-09-28 19:23:54 UTC (rev 11700)
@@ -65,6 +65,7 @@
   return h;
 }
 
+#if 0
 /** Basic string hash function, from Java standard String.hashCode(). */
 static INLINE unsigned
 ht_string_hash(const char *s)
@@ -77,7 +78,22 @@
   }
   return h;
 }
+#endif
 
+/** Basic string hash function, from Python's str.__hash__() */
+static INLINE unsigned
+ht_string_hash(const char *s)
+{
+  unsigned h;
+  const unsigned char *cp = (const unsigned char *)s;
+  h = *cp << 7;
+  while (*cp) {
+    h = (1000003*h) ^ *cp++;
+  }
+  h ^= (cp-(const unsigned char*)s);
+  return h;
+}
+
 #define _HT_SET_HASH(elm, field, hashfn)        \
     (elm)->field.hte_hash = hashfn(elm)