You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2013/06/29 22:04:42 UTC

svn commit: r1498017 - /subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/reps.c

Author: stefan2
Date: Sat Jun 29 20:04:42 2013
New Revision: 1498017

URL: http://svn.apache.org/r1498017
Log:
On the fsfs-format7 branch: improve the representation container's match hash
efficiency by reducing the number of rehashing operations (fewer chances for
collisions) and replacing entries only if they belong to different reps.

* subversion/libsvn_fs_fs/reps.c
  (grow_hash): allow for specifying a minimum bucket count
  (add_new_text): expand hash only once;
                  ignore hash conflicts inside the same rep

Modified:
    subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/reps.c

Modified: subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/reps.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/reps.c?rev=1498017&r1=1498016&r2=1498017&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/reps.c (original)
+++ subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/reps.c Sat Jun 29 20:04:42 2013
@@ -324,30 +324,46 @@ init_hash(hash_t *hash,
   allocate_hash_members(hash, 1 << twoPower, pool);
 }
 
-/* Double the number of buckets in HASH by rehashing it based TEXT.
+/* Make HASH have at least MIN_SIZE buckets but at least double the number
+ * of buckets in HASH by rehashing it based TEXT.
  */
 static void
 grow_hash(hash_t *hash,
-          svn_stringbuf_t *text)
+          svn_stringbuf_t *text,
+          apr_size_t min_size)
 {
   hash_t copy;
   apr_size_t i;
 
-  allocate_hash_members(&copy, hash->size * 2, hash->pool);
-  copy.used = hash->used;
-  copy.shift = hash->shift - 1;
+  /* determine the new hash size */
+  apr_size_t new_size = hash->size * 2;
+  apr_size_t new_shift = hash->shift - 1;
+  while (new_size < min_size)
+    {
+      new_size *= 2;
+      --new_shift;
+    }
 
+  /* allocate new hash */
+  allocate_hash_members(&copy, new_size, hash->pool);
+  copy.used = 0;
+  copy.shift = new_shift;
+
+  /* copy / translate data */
   for (i = 0; i < hash->size; ++i)
     {
       apr_uint32_t offset = hash->offsets[i];
       if (offset != NO_OFFSET)
         {
           hash_key_t key = hash_key(text->data + offset);
-          size_t idx =  hash_to_index(&copy, key);
+          size_t idx = hash_to_index(&copy, key);
+
+          if (copy.offsets[idx] == NO_OFFSET)
+            copy.used++;
 
           copy.prefixes[idx] = hash->prefixes[i];
           copy.offsets[idx] = offset;
-          copy.last_matches[idx] = hash->last_matches[idx];
+          copy.last_matches[idx] = hash->last_matches[i];
         }
     }
 
@@ -406,7 +422,9 @@ add_new_text(svn_fs_fs__reps_builder_t *
              apr_size_t len)
 {
   instruction_t instruction;
-  size_t offset;
+  apr_size_t offset;
+  apr_size_t buckets_required;
+
   if (len == 0)
     return;
 
@@ -418,6 +436,11 @@ add_new_text(svn_fs_fs__reps_builder_t *
   /* add to text corpus */
   svn_stringbuf_appendbytes(builder->text, data, len);
 
+  /* expand the hash upfront to minimize the chances of collisions */
+  buckets_required = builder->hash.used + len / MATCH_BLOCKSIZE;
+  if (buckets_required * 3 >= builder->hash.size * 2)
+    grow_hash(&builder->hash, builder->text, 2 * buckets_required);
+
   /* add hash entries for the new sequence */
   for (offset = instruction.offset;
        offset + MATCH_BLOCKSIZE <= builder->text->len;
@@ -426,10 +449,15 @@ add_new_text(svn_fs_fs__reps_builder_t *
       hash_key_t key = hash_key(builder->text->data + offset);
       size_t idx = hash_to_index(&builder->hash, key);
 
+      /* Don't replace hash entries that stem from the current text.
+       * This makes early matches more likely. */
+      if (builder->hash.offsets[idx] == NO_OFFSET)
+        ++builder->hash.used;
+      else if (builder->hash.offsets[idx] >= instruction.offset)
+        continue;
+
       builder->hash.offsets[idx] = offset;
       builder->hash.prefixes[idx] = builder->text->data[offset];
-      if (++builder->hash.used * 3 >= builder->hash.size * 2)
-        grow_hash(&builder->hash, builder->text);
     }
 }