svn commit: r1495256 - /subversion/trunk/subversion/libsvn_fs_fs/tree.c

[st...@apache.org]

Author: stefan2
Date: Fri Jun 21 00:36:48 2013
New Revision: 1495256

URL: http://svn.apache.org/r1495256
Log:
Effectively revert r1495209 and r1495214.  Tune and document the remainder.

* subversion/libsvn_fs_fs/tree.c
  (cache_lookup): turn magic number into a constant;
                  fine-tune iteration latencies; add commentary

Modified:
    subversion/trunk/subversion/libsvn_fs_fs/tree.c

Modified: subversion/trunk/subversion/libsvn_fs_fs/tree.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/tree.c?rev=1495256&r1=1495255&r2=1495256&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/tree.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/tree.c Fri Jun 21 00:36:48 2013
@@ -40,8 +40,6 @@
 #include <assert.h>
 #include <apr_pools.h>
 #include <apr_hash.h>
-#define APR_WANT_BYTEFUNC
-#include <apr_want.h>
 
 #include "svn_hash.h"
 #include "svn_private_config.h"
@@ -344,6 +342,9 @@ cache_lookup( fs_fs_dag_cache_t *cache
   apr_size_t path_len = strlen(path);
   long int hash_value = revision;
 
+  /* "randomizing" / distributing factor used in our hash function */
+  enum { factor = 0xd1f3da69 };
+
   /* optimistic lookup: hit the same bucket again? */
   cache_entry_t *result = &cache->buckets[cache->last_hit];
   if (   (result->revision == revision)
@@ -355,24 +356,40 @@ cache_lookup( fs_fs_dag_cache_t *cache
 
   /* need to do a full lookup.  Calculate the hash value
      (HASH_VALUE has been initialized to REVISION). */
-  for (i = 0; i + 4 <= path_len; i += 4)
+  i = 0;
 #if SVN_UNALIGNED_ACCESS_IS_OK
-    hash_value = hash_value * 0xd1f3da69
-               + ntohl(*(const apr_uint32_t*)(path + i));
+  /* We relax the dependency chain between iterations by processing
+     two chunks from the input per hash_value self-multiplication.
+     The HASH_VALUE update latency is now 1 MUL latency + 1 ADD latency
+     per 2 chunks instead of 1 chunk.
+   */
+  for (; i + 8 <= path_len; i += 8)
+    hash_value = hash_value * factor * factor
+               + (  (long int)*(const apr_uint32_t*)(path + i) * factor
+                  + (long int)*(const apr_uint32_t*)(path + i + 4));
 #else
+  for (; i + 4 <= path_len; i += 4)
     {
+      /* read the data in BIG-ENDIAN order
+         (it's just simpler code and most of the machines in question are
+          actually big endian) */
       apr_uint32_t val = 0;
       int j;
 
+      /* most compilers will unroll this loop: */
       for (j = 0; j < 4; j++)
         val = (val << 8) + (unsigned char)path[i + j];
 
-      hash_value = hash_value * 0xd1f3da69 + val;
+      hash_value = hash_value * factor + val;
     }
 #endif
 
   for (; i < path_len; ++i)
-    hash_value = hash_value * 33 + (unsigned char)path[i];
+    /* Help GCC to minimize the HASH_VALUE update latency by splitting the
+       MUL 33 of the naive implementation: h = h * 33 + path[i].  This
+       shortens the dependency chain from 1 shift + 2 ADDs to 1 shift + 1 ADD.
+     */
+    hash_value = hash_value * 32 + (hash_value + (unsigned char)path[i]);
 
   bucket_index = hash_value + (hash_value >> 16);
   bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;