svn commit: r1224655 - in /subversion/trunk/subversion/libsvn_delta: delta.h text_delta.c xdelta.c

[st...@apache.org]

Author: stefan2
Date: Sun Dec 25 23:01:15 2011
New Revision: 1224655

URL: http://svn.apache.org/viewvc?rev=1224655&view=rev
Log:
Optimize the delta windows generated by our xdelta algorithm:
Since our algo is greedy, it prefers short, frequent sequences
as matches over longer unique ones. Unique matches will eventually
be found and, therefore, can be used to remove the less efficient
matches after the fact.

* subversion/libsvn_delta/delta.h
  (svn_txdelta__remove_copy): declare new private API function
* subversion/libsvn_delta/text_delta.c
  (svn_txdelta__remove_copy): implement it
* subversion/libsvn_delta/xdelta.c
  (compute_delta): use the new function to optimize the delta ops

Modified:
    subversion/trunk/subversion/libsvn_delta/delta.h
    subversion/trunk/subversion/libsvn_delta/text_delta.c
    subversion/trunk/subversion/libsvn_delta/xdelta.c

Modified: subversion/trunk/subversion/libsvn_delta/delta.h
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_delta/delta.h?rev=1224655&r1=1224654&r2=1224655&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_delta/delta.h (original)
+++ subversion/trunk/subversion/libsvn_delta/delta.h Sun Dec 25 23:01:15 2011
@@ -68,6 +68,12 @@ void svn_txdelta__insert_op(svn_txdelta_
                             const char *new_data,
                             apr_pool_t *pool);
 
+/* Remove / truncate the last delta ops spanning the last MAX_LEN bytes
+   from the delta window being built via BUILD_BATON starting.  Return the
+   number of bytes that were actually removed. */
+apr_size_t
+svn_txdelta__remove_copy(svn_txdelta__ops_baton_t *build_baton,
+                         apr_size_t max_len);
 
 /* Allocate a delta window from POOL. */
 svn_txdelta_window_t *

Modified: subversion/trunk/subversion/libsvn_delta/text_delta.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_delta/text_delta.c?rev=1224655&r1=1224654&r2=1224655&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_delta/text_delta.c (original)
+++ subversion/trunk/subversion/libsvn_delta/text_delta.c Sun Dec 25 23:01:15 2011
@@ -276,6 +276,48 @@ svn_txdelta__insert_op(svn_txdelta__ops_
   ++build_baton->num_ops;
 }
 
+apr_size_t
+svn_txdelta__remove_copy(svn_txdelta__ops_baton_t *build_baton,
+                         apr_size_t max_len)
+{
+  svn_txdelta_op_t *op;
+  apr_size_t len = 0;
+
+  /* remove ops back to front */
+  while (build_baton->num_ops > 0)
+    {
+      op = &build_baton->ops[build_baton->num_ops-1];
+
+      /*  we can't modify svn_txdelta_target ops -> stop there */
+      if (op->action_code == svn_txdelta_target)
+        break;
+      
+      /*  handle the case that we cannot remove the op entirely */
+      if (op->length + len > max_len)
+        {
+          /* truncate only insertions. Copies don't benefit
+             from being truncated. */
+          if (op->action_code == svn_txdelta_new)
+            {
+               build_baton->new_data->len -= max_len - len;
+               op->length -= max_len - len;
+               len = max_len;
+            }
+          
+          break;
+        }
+        
+      /* drop the op entirely */
+      if (op->action_code == svn_txdelta_new)
+        build_baton->new_data->len -= op->length;
+      
+      len += op->length;
+      --build_baton->num_ops;
+    }
+    
+  return len;
+}
+
 
 
 /* Generic delta stream functions. */

Modified: subversion/trunk/subversion/libsvn_delta/xdelta.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_delta/xdelta.c?rev=1224655&r1=1224654&r2=1224655&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_delta/xdelta.c (original)
+++ subversion/trunk/subversion/libsvn_delta/xdelta.c Sun Dec 25 23:01:15 2011
@@ -437,6 +437,19 @@ compute_delta(svn_txdelta__ops_baton_t *
             svn_txdelta__insert_op(build_baton, svn_txdelta_new,
                                    0, lo - pending_insert_start,
                                    b + pending_insert_start, pool);
+          else 
+            {
+              /* the match borders on the previous op. Maybe, we found a
+               * match that is better than / overlapping the previous one. */
+              apr_size_t len = reverse_match_length(a + apos, b + lo, apos < lo ? apos : lo);
+              if (len > 0)
+                {
+                  len = svn_txdelta__remove_copy(build_baton, len);
+                  apos -= len;
+                  matchlen += len;
+                  lo -= len;
+                }
+            }
 
           /* Reset the pending insert start to immediately after the
              match. */