Changeset 1920 in kBuild

Timestamp:

Oct 24, 2008 12:00:27 AM (16 years ago)

Author:

bird

Message:

strcache2: don't hash strings that aren't small (experimental).

File:

• trunk/src/kmk/strcache2.c (modified) (14 diffs)

trunk/src/kmk/strcache2.c

@@ -77 +77 @@
 #endif
 
+# if defined(__amd64__) || defined(__x86_64__) || defined(__AMD64__) || defined(_M_X64) || defined(__amd64) \
+ || defined(__i386__) || defined(__x86__) || defined(__X86__) || defined(_M_IX86) || defined(__i386)
+#  define strcache2_get_unaligned_16bits(ptr)   ( *((const uint16_t *)(ptr)))
+# else
+   /* (endian doesn't matter) */
+#  define strcache2_get_unaligned_16bits(ptr)   (   (((const uint8_t *)(ptr))[0] << 8) \
+                                                  | (((const uint8_t *)(ptr))[1]) )
+# endif
+
 
 /*******************************************************************************
@@ -117 +126 @@
 }
 
+/* The following is a bit experiment. It produces longer chains, i.e. worse
+   distribution of the strings in the table, however the actual make
+   performances is better (<time).  The explanation is probably that the
+   collisions only really increase for entries that aren't looked up that
+   much and that it actually improoves the situation for those that is. Or
+   that we spend so much less time hashing that it makes up (and more) for
+   the pentalty we suffer from the longer chains and worse distribution.
+
+   XXX: Check how this works out with different path lengths. I suspect it
+        might depend on the length of PATH_ROOT and the depth of the files
+        in the project as well. If it does, this might make matters worse
+        for some and better for others which isn't very cool...  */
+
+#define BIG_HASH_SIZE   32
+#define BIG_HASH_TAIL   12
+#define BIG_HASH_HEAD   16
+
+#ifdef BIG_HASH_SIZE
+/* long string: hash head and tail, drop the middle. */
 MY_INLINE unsigned int
-strcache2_case_sensitive_hash_1 (const char *str, unsigned int len)
+strcache2_case_sensitive_hash_big (const char *str, unsigned int len)
+{
+  uint32_t hash = len;
+  uint32_t tmp;
+  unsigned int head;
+
+  /* head BIG_HASH_HEAD bytes */
+  head = (BIG_HASH_HEAD >> 2);
+  while (head-- > 0)
+    {
+      hash += strcache2_get_unaligned_16bits (str);
+      tmp   = (strcache2_get_unaligned_16bits (str + 2) << 11) ^ hash;
+      hash  = (hash << 16) ^ tmp;
+      str  += 2 * sizeof (uint16_t);
+      hash += hash >> 11;
+    }
+
+  /* tail BIG_HASH_TAIL bytes (minus the odd ones) */
+  str += (len - BIG_HASH_HEAD - BIG_HASH_TAIL) & ~3U;
+  head = (BIG_HASH_TAIL >> 2);
+  while (head-- > 0)
+    {
+      hash += strcache2_get_unaligned_16bits (str);
+      tmp   = (strcache2_get_unaligned_16bits (str + 2) << 11) ^ hash;
+      hash  = (hash << 16) ^ tmp;
+      str  += 2 * sizeof (uint16_t);
+      hash += hash >> 11;
+    }
+
+  /* force "avalanching" of final 127 bits. */
+  hash ^= hash << 3;
+  hash += hash >> 5;
+  hash ^= hash << 4;
+  hash += hash >> 17;
+  hash ^= hash << 25;
+  hash += hash >> 6;
+
+  return hash;
+}
+#endif /* BIG_HASH_SIZE */
+
+MY_INLINE unsigned int
+strcache2_case_sensitive_hash (const char *str, unsigned int len)
 {
 #if 1
@@ -134 +204 @@
      FIXME: A path for well aligned data should be added to speed up
             execution on alignment sensitive systems.  */
-
-# if defined(__amd64__) || defined(__x86_64__) || defined(__AMD64__) || defined(_M_X64) || defined(__amd64) \
- || defined(__i386__) || defined(__x86__) || defined(__X86__) || defined(_M_IX86) || defined(__i386)
-#  define strcache2_get_unaligned_16bits(ptr)   ( *((const uint16_t *)(ptr)))
-# else
-   /* (endian doesn't matter) */
-#  define strcache2_get_unaligned_16bits(ptr)   (   (((const uint8_t *)(ptr))[0] << 8) \
-                                                  | (((const uint8_t *)(ptr))[1]) )
+  unsigned int rem;
+  uint32_t hash;
+  uint32_t tmp;
+
+  assert (sizeof (uint8_t) == sizeof (char));
+
+# ifdef BIG_HASH_SIZE
+  /* long string? */
+  if (len >= BIG_HASH_SIZE)
+    return strcache2_case_sensitive_hash_big (str, len);
 # endif
-  uint32_t hash = len;
-  uint32_t tmp;
-  int rem;
-
-  assert (sizeof (uint8_t) == sizeof (char));
-  if (len == 0)
-    return 0;
-
-  /* main loop, walking on 2 x uint16_t */
+
+  /* short string: main loop, walking on 2 x uint16_t */
+  hash = len;
   rem = len & 3;
   len >>= 2;
@@ -164 +230 @@
     }
 
-  /* the remainer */
+  /* the remainder */
   switch (rem)
     {
@@ -290 +356 @@
 
 MY_INLINE unsigned int
-strcache2_case_insensitive_hash_1 (const char *str, unsigned int len)
+strcache2_case_insensitive_hash (const char *str, unsigned int len)
 {
   unsigned int hash = 0;
@@ -684 +750 @@
 {
   struct strcache2_entry const *entry;
-  unsigned int hash = strcache2_case_sensitive_hash_1 (str, length);
+  unsigned int hash = strcache2_case_sensitive_hash (str, length);
   unsigned int idx;
 
@@ -733 +799 @@
 
   assert (!cache->case_insensitive);
-  correct_hash = strcache2_case_sensitive_hash_1 (str, length);
+  correct_hash = strcache2_case_sensitive_hash (str, length);
   MY_ASSERT_MSG (hash == correct_hash, ("%#x != %#x\n", hash, correct_hash));
 #endif /* NDEBUG */
@@ -774 +840 @@
 {
   struct strcache2_entry const *entry;
-  unsigned int hash = strcache2_case_sensitive_hash_1 (str, length);
+  unsigned int hash = strcache2_case_sensitive_hash (str, length);
   unsigned int idx;
 
@@ -818 +884 @@
 {
   struct strcache2_entry const *entry;
-  unsigned int hash = strcache2_case_insensitive_hash_1 (str, length);
+  unsigned int hash = strcache2_case_insensitive_hash (str, length);
   unsigned int idx;
 
@@ -867 +933 @@
 
   assert (!cache->case_insensitive);
-  correct_hash = strcache2_case_insensitive_hash_1 (str, length);
+  correct_hash = strcache2_case_insensitive_hash (str, length);
   MY_ASSERT_MSG (hash == correct_hash, ("%#x != %#x\n", hash, correct_hash));
 #endif /* NDEBUG */
@@ -908 +974 @@
 {
   struct strcache2_entry const *entry;
-  unsigned int hash = strcache2_case_insensitive_hash_1 (str, length);
+  unsigned int hash = strcache2_case_insensitive_hash (str, length);
   unsigned int idx;
 
@@ -993 +1059 @@
 
   hash = cache->case_insensitive
-    ? strcache2_case_insensitive_hash_1 (str, entry->length)
-    : strcache2_case_sensitive_hash_1 (str, entry->length);
+    ? strcache2_case_insensitive_hash (str, entry->length)
+    : strcache2_case_sensitive_hash (str, entry->length);
   if (hash != entry->hash)
     {
@@ -1012 +1078 @@
 {
   *hash2p = 1;
-  return    strcache2_case_sensitive_hash_1 (str, length);
+  return    strcache2_case_sensitive_hash (str, length);
 }
 
@@ -1020 +1086 @@
 {
   *hash2p = 1;
-  return    strcache2_case_insensitive_hash_1 (str, length);
+  return    strcache2_case_insensitive_hash (str, length);
 }