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

[Morten Kloster]

On Fri, May 27, 2011 at 8:41 PM, Morten Kloster <mor...@gmail.com> wrote:
> [[[
> 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
>

Why yes, I certainly should! What an excellent idea!

New name "fp_k" (being fp+k).

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_k,
                 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_k[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_k[-1].y + 1 > fp_k[1].y)
     {
-      start_position[0] = fp[k - 1].position[0];
-      start_position[1] = fp[k - 1].position[1]->next;
+      start_position[0] = fp_k[-1].position[0];
+      start_position[1] = fp_k[-1].position[1]->next;
 
-      previous_lcs = fp[k - 1].lcs;
+      previous_lcs = fp_k[-1].lcs;
     }
   else
     {
-      start_position[0] = fp[k + 1].position[0]->next;
-      start_position[1] = fp[k + 1].position[1];
+      start_position[0] = fp_k[1].position[0]->next;
+      start_position[1] = fp_k[1].position[1];
 
-      previous_lcs = fp[k + 1].lcs;
+      previous_lcs = fp_k[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_k[0].lcs = lcs;
     }
   else
     {
-      fp[k].lcs = previous_lcs;
+      fp_k[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_k[0].position[0] = position[0];
+  fp_k[0].position[1] = position[1];
 
-  fp[k].y = position[1]->offset;
+  fp_k[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++;