Re: [PATCH] Implement premature termination of compareseq.

[Bruno Haible]

Hi Ralf,

Both of your optimization ideas are excellent. A 4x speedup for msgmerge
is not something that I'm seeing every day!!

Let me start by committing the diffseq.h change. I'm changing the macro
to not include the 'return' statement, just the condition expression. And
when the condition has evaluated to true, it does not need to be evaluated
again at every 'compareseq' recursion level. Also, I prefer to not force
every user of the module to define the macro: the majority of the users
is like 'diffutils' and will not desire an early abort.

2008-09-14  Ralf Wildenhues  <address@hidden>

        * lib/diffseq.h (EARLY_ABORT): New macro.
        (compareseq): Change return type to bool. Return true when EARLY_ABORT
        evaluates to true.

*** lib/diffseq.h.orig  2008-09-14 17:52:29.000000000 +0200
--- lib/diffseq.h       2008-09-14 17:52:04.000000000 +0200
***************
*** 49,54 ****
--- 49,56 ----
       EXTRA_CONTEXT_FIELDS    Declarations of fields for 'struct context'.
       NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff].
       NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff].
+      EARLY_ABORT(ctxt)       (Optional) A boolean expression that triggers an
+                              early abort of the computation.
       USE_HEURISTIC           (Optional) Define if you want to support the
                               heuristic for large vectors.
     Before including this file, you also need to include:
***************
*** 61,66 ****
--- 63,73 ----
  #define OFFSET_MAX \
    ((((OFFSET)1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1)
  
+ /* Default to no early abort.  */
+ #ifndef EARLY_ABORT
+ # define EARLY_ABORT(ctxt) false
+ #endif
+ 
  /* Use this to suppress gcc's `...may be used before initialized' warnings. */
  #ifndef IF_LINT
  # ifdef lint
***************
*** 407,415 ****
     If FIND_MINIMAL, find a minimal difference no matter how
     expensive it is.
  
!    The results are recorded by invoking NOTE_DELETE and NOTE_INSERT.  */
  
! static void
  compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
            bool find_minimal, struct context *ctxt)
  {
--- 414,425 ----
     If FIND_MINIMAL, find a minimal difference no matter how
     expensive it is.
  
!    The results are recorded by invoking NOTE_DELETE and NOTE_INSERT.
  
!    Return false if terminated normally, or true if terminated through early
!    abort.  */
! 
! static bool
  compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
            bool find_minimal, struct context *ctxt)
  {
***************
*** 435,446 ****
--- 445,460 ----
      while (yoff < ylim)
        {
        NOTE_INSERT (ctxt, yoff);
+       if (EARLY_ABORT (ctxt))
+         return true;
        yoff++;
        }
    else if (yoff == ylim)
      while (xoff < xlim)
        {
        NOTE_DELETE (ctxt, xoff);
+       if (EARLY_ABORT (ctxt))
+         return true;
        xoff++;
        }
    else
***************
*** 451,459 ****
        diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
  
        /* Use the partitions to split this problem into subproblems.  */
!       compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt);
!       compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt);
      }
  }
  
  #undef ELEMENT
--- 465,477 ----
        diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
  
        /* Use the partitions to split this problem into subproblems.  */
!       if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, 
ctxt))
!       return true;
!       if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, 
ctxt))
!       return true;
      }
+ 
+   return false;
  }
  
  #undef ELEMENT
***************
*** 462,466 ****
--- 480,485 ----
  #undef EXTRA_CONTEXT_FIELDS
  #undef NOTE_DELETE
  #undef NOTE_INSERT
+ #undef EARLY_ABORT
  #undef USE_HEURISTIC
  #undef OFFSET_MAX