Mailing-List: contact commits-help@subversion.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@subversion.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1224836 - in /subversion/trunk: notes/knobs
 subversion/libsvn_fs_fs/fs_fs.c
Date: Mon, 26 Dec 2011 23:37:25 -0000
To: commits@subversion.apache.org
From: stefan2@apache.org
Message-Id: <20111226233725.EC15C23888D2@eris.apache.org>

Author: stefan2
Date: Mon Dec 26 23:37:25 2011
New Revision: 1224836

URL: http://svn.apache.org/viewvc?rev=1224836&view=rev
Log:
Tune FSFS deltification stratey: Use linear deltification on the very top of the
deltification history and skip-delta only for larger distances.  Most of the runtime
overhead is being counterbalanced by reduced I/O and masked by our membuffer
caching.
OTOH, we examine skip delta ranges linearly during commit. Therefore, runtime
becomes an issue when committing nodes with very deep change histories.
This patch simply limits the deltification history to some reasonable length.

* subversion/libsvn_fs_fs/fs_fs.c
  (SVN_FS_FS_MAX_LINEAR_DELTIFICATION,
   SVN_FS_FS_MAX_DELTIFICATION_WALK): new tuning parameters
  (choose_delta_base): implement the new deltification strategy
* notes/knobs
  document the new defines

Modified:
    subversion/trunk/notes/knobs
    subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c

Modified: subversion/trunk/notes/knobs
URL: http://svn.apache.org/viewvc/subversion/trunk/notes/knobs?rev=1224836&r1=1224835&r2=1224836&view=diff
==============================================================================
--- subversion/trunk/notes/knobs (original)
+++ subversion/trunk/notes/knobs Mon Dec 26 23:37:25 2011
@@ -33,6 +33,8 @@ DEFAULT_HTTP_LIBRARY
 MAX_SECS_TO_LINGER
 SUFFIX_LINES_TO_KEEP
 SVN_FS_FS_DEFAULT_MAX_FILES_PER_DIR
+SVN_FS_FS_MAX_LINEAR_DELTIFICATION
+SVN_FS_FS_MAX_DELTIFICATION_WALK
 SVN_UNALIGNED_ACCESS_IS_OK
 
 2.2 Features
@@ -125,7 +127,25 @@ SVN_I_LIKE_LATENCY_SO_IGNORE_HTTPV2
   Range:     natural integers
   Suggested: 1, 2, 3, 4, 5, 7, 11
 
-3.6 SVN_UNALIGNED_ACCESS_IS_OK
+3.6 SVN_FS_FS_MAX_LINEAR_DELTIFICATION
+
+  Scope:     libsvn_fs_fs
+  Purpose:   max length + 1 of the linear deltification history
+             before skip-deltification kicks in
+  Default:   16
+  Range:     natural integers
+  Suggested: 2, 4, 8, 16, 32, 64
+
+3.7 SVN_FS_FS_MAX_DELTIFICATION_WALK
+
+  Scope:     libsvn_fs_fs
+  Purpose:   max skip deltification range. Change histories
+             longer than that will be restarted with a fulltext.
+  Default:   1023
+  Range:     natural integers
+  Suggested: 1, 2, 3, 4, 5, 7, 11
+
+3.8 SVN_UNALIGNED_ACCESS_IS_OK
 
   Scope:     (global)
   Purpose:   enable data accesss optimizations.

Modified: subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c?rev=1224836&r1=1224835&r2=1224836&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c Mon Dec 26 23:37:25 2011
@@ -78,6 +78,20 @@
 #define SVN_FS_FS_DEFAULT_MAX_FILES_PER_DIR 1000
 #endif
 
+/* Begin deltification after a node history exceeded this this limit.
+   Useful values are 4 to 64 with 16 being a good compromise between
+   computational overhead and pository size savings.
+   Should be a power of 2.  
+   Values < 2 will result in standard skip-delta behavior. */
+#define SVN_FS_FS_MAX_LINEAR_DELTIFICATION 16
+
+/* Finding a deltification base takes operations proportional to the
+   number of changes being skipped. To prevent exploding runtime
+   during commits, limit the deltification range to this value.
+   Should be a power of 2 minus one.
+   Values < 1 disable deltification. */
+#define SVN_FS_FS_MAX_DELTIFICATION_WALK 1023
+
 /* Following are defines that specify the textual elements of the
    native filesystem directories and revision files. */
 
@@ -5186,6 +5200,7 @@ choose_delta_base(representation_t **rep
                   apr_pool_t *pool)
 {
   int count;
+  int walk;
   node_revision_t *base;
 
   /* If we have no predecessors, then use the empty stream as a
@@ -5203,6 +5218,23 @@ choose_delta_base(representation_t **rep
   count = noderev->predecessor_count;
   count = count & (count - 1);
 
+  /* We use skip delta for limiting the number of delta operations 
+     along very long node histories.  Close to HEAD however, we create
+     a linear history to minimize delta size.  */
+  walk = noderev->predecessor_count - count;
+  if (walk < SVN_FS_FS_MAX_LINEAR_DELTIFICATION)
+    count = noderev->predecessor_count - 1;
+
+  /* Finding the delta base over a very long distance can become extremely
+     expensive for very deep histories, possibly causing client timeouts etc.
+     OTOH, this is a rare operation and its gains are minimal. Lets simply
+     start deltification anew close every other 1000 changes or so.  */
+  if (walk > SVN_FS_FS_MAX_DELTIFICATION_WALK)
+    {
+      *rep = NULL;
+      return SVN_NO_ERROR;
+    }
+
   /* Walk back a number of predecessors equal to the difference
      between count and the original predecessor count.  (For example,
      if noderev has ten predecessors and we want the eighth file rev,