[PATCH] single-file-merge optimization (was: svn commit: r31504 - trunk/subversion/libsvn_client)

C. Michael Pilato wrote:
> Karl Fogel wrote:
>> Do we really have to loop over (on average) half of changed_revs each
>> time to evaluate whether or not the range in question is operative?
>> After all, changed_revs is in sorted order already -- I don't know which
>> way, but svn_ra_get_log2()'s doc string has details on that. So instead
>> of looping every time, we could just compare
>> APR_ARRAY_IDX(changed_revs, 0, svn_revnum_t *)
>> APR_ARRAY_IDX(changed_revs, changed_revs->nelts, svn_revnum_t *)
>
> changed_revs->nelts-1 here, but yes, I see what you're saying.

Attaching a patch which should do this, for extra eyes and backup purposes.

-- 
C. Michael Pilato <cmpilato_at_collab.net>
CollabNet   <>   www.collab.net   <>   Distributed Development On Demand

More optimizations for the single-file merge case.

* subversion/libsvn_client/merge.c
  (remove_noop_merge_ranges): Avoid a linear trampse through the array
    of operative revisions if the entire range fails to overlap with the
    requested merge range.

Suggested by: kfogel

Index: subversion/libsvn_client/merge.c
===================================================================
--- subversion/libsvn_client/merge.c (revision 31930)
+++ subversion/libsvn_client/merge.c (working copy)
@@ -3920,6 +3920,7 @@
   int i;
   svn_revnum_t oldest_rev = SVN_INVALID_REVNUM;
   svn_revnum_t youngest_rev = SVN_INVALID_REVNUM;
+ svn_revnum_t oldest_changed_rev, youngest_changed_rev;
   apr_array_header_t *changed_revs =
     apr_array_make(pool, ranges->nelts, sizeof(svn_revnum_t *));
   apr_array_header_t *operative_ranges =
@@ -3948,20 +3949,36 @@
                           apr_array_make(pool, 0, sizeof(const char *)),
                           log_changed_revs, changed_revs, pool));
 
+ /* Our list of changed revisions should be in youngest-to-oldest order. */
+ youngest_changed_rev = *(APR_ARRAY_IDX(changed_revs,
+ 0, svn_revnum_t *));
+ oldest_changed_rev = *(APR_ARRAY_IDX(changed_revs,
+ changed_revs->nelts - 1,
+ svn_revnum_t *));
+
   /* Now, copy from RANGES to *OPERATIVE_RANGES, filtering out ranges
      that aren't operative (by virtue of not having any revisions
      represented in the CHANGED_REVS array). */
   for (i = 0; i < ranges->nelts; i++)
     {
       svn_merge_range_t *range = APR_ARRAY_IDX(ranges, i, svn_merge_range_t *);
+ svn_revnum_t range_min = MIN(range->start, range->end) + 1;
+ svn_revnum_t range_max = MAX(range->start, range->end);
       int j;
 
+ /* If the merge range is entirely outside the range of changed
+ revisions, we've no use for it. */
+ if ((range_min > youngest_changed_rev)
+ || (range_max < oldest_changed_rev))
+ continue;
+
+ /* Walk through the changed_revs to see if any of them fall
+ inside our current range. */
       for (j = 0; j < changed_revs->nelts; j++)
         {
           svn_revnum_t *changed_rev =
             APR_ARRAY_IDX(changed_revs, j, svn_revnum_t *);
- if ((*changed_rev > MIN(range->start, range->end))
- && (*changed_rev <= MAX(range->start, range->end)))
+ if ((*changed_rev >= range_min) && (*changed_rev <= range_max))
             {
               APR_ARRAY_PUSH(operative_ranges, svn_merge_range_t *) = range;
               break;