[PATCH] Speed-up of libsvn_diff by reworking fp argument

[Morten Kloster]

[[[
Faster LCS algorithm in libsvn_diff by reworking fp argument

* subversion/libsvn_diff/lcs.c
  (svn_diff__snake): fp and k arguments are added by caller
]]]

Calling svn_diff__snake with fp+k as argument instead of both as
separate arguments reduces running time for the lcs algorithm
substantially; by more than 20% on my system. Combining this
patch with the idx one gives a slight additional speed
improvement, but not nearly the sum of each separate
improvement (on my system, at least).

Patched version produces identical diff results and passes
all libsvn_diff tests.

Should I maybe change the name of fp in svn_diff__snake?


Morten

Index: subversion/libsvn_diff/lcs.c
===================================================================
--- subversion/libsvn_diff/lcs.c        (revision 1128318)
+++ subversion/libsvn_diff/lcs.c        (working copy)
@@ -48,8 +48,7 @@
 };
 
 static APR_INLINE void
-svn_diff__snake(apr_off_t k,
-                svn_diff__snake_t *fp,
+svn_diff__snake(svn_diff__snake_t *fp,
                 int idx,
                 svn_diff__lcs_t **freelist,
                 apr_pool_t *pool)
@@ -63,7 +62,7 @@
    * can mark that lcs node for reuse, because the sequence up to this
    * point was a dead end.
    */
-  lcs = fp[k].lcs;
+  lcs = fp[0].lcs;
   while (lcs)
     {
       lcs->refcount--;
@@ -76,19 +75,19 @@
       lcs = previous_lcs;
     }
 
-  if (fp[k - 1].y + 1 > fp[k + 1].y)
+  if (fp[-1].y + 1 > fp[1].y)
     {
-      start_position[0] = fp[k - 1].position[0];
-      start_position[1] = fp[k - 1].position[1]->next;
+      start_position[0] = fp[-1].position[0];
+      start_position[1] = fp[-1].position[1]->next;
 
-      previous_lcs = fp[k - 1].lcs;
+      previous_lcs = fp[-1].lcs;
     }
   else
     {
-      start_position[0] = fp[k + 1].position[0]->next;
-      start_position[1] = fp[k + 1].position[1];
+      start_position[0] = fp[1].position[0]->next;
+      start_position[1] = fp[1].position[1];
 
-      previous_lcs = fp[k + 1].lcs;
+      previous_lcs = fp[1].lcs;
     }
 
 
@@ -122,11 +121,11 @@
       lcs->length = position[1]->offset - start_position[1]->offset;
       lcs->next = previous_lcs;
       lcs->refcount = 1;
-      fp[k].lcs = lcs;
+      fp[0].lcs = lcs;
     }
   else
     {
-      fp[k].lcs = previous_lcs;
+      fp[0].lcs = previous_lcs;
     }
 
   if (previous_lcs)
@@ -134,10 +133,10 @@
       previous_lcs->refcount++;
     }
 
-  fp[k].position[0] = position[0];
-  fp[k].position[1] = position[1];
+  fp[0].position[0] = position[0];
+  fp[0].position[1] = position[1];
 
-  fp[k].y = position[1]->offset;
+  fp[0].y = position[1]->offset;
 }
 
 
@@ -272,12 +271,12 @@
       /* Forward */
       for (k = -p; k < d; k++)
         {
-          svn_diff__snake(k, fp, idx, &lcs_freelist, pool);
+          svn_diff__snake(fp + k, idx, &lcs_freelist, pool);
         }
 
       for (k = d + p; k >= d; k--)
         {
-          svn_diff__snake(k, fp, idx, &lcs_freelist, pool);
+          svn_diff__snake(fp + k, idx, &lcs_freelist, pool);
         }
 
       p++;