bugConcurrent Versions System - Bugs: bug #17560, merge code in rcs.c is O(n^2)

 
 

bug #17560: merge code in rcs.c is O(n^2)

Submitted by:  None
Submitted on:  Mon 28 Aug 2006 08:37:53 PM UTC  
Votes:  5  
 
Category:  Bug Fix (patch attached) Severity:  3 - Normal
Item Group:  None Status:  Fixed
Privacy:  Public Assigned to:  None
Open/Closed:  Closed Release:  1.11.23
Fixed Release:  1.11.23 Fixed Feature Release:  1.12.14

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Fri 08 Sep 2006 01:26:09 PM UTC, comment #18: 

Larry added some touch ups to my touch ups, then I touched that up.  Now I've merge the last of these touch ups into stable, I hope.  Closing.

Derek Robert Price <dprice>
Project Administrator
Wed 06 Sep 2006 06:36:34 PM UTC, comment #17: 

What Mark said but, if anyone is trying to benchmark the change, it should be possible to contrive the worst case scenario using a really long file with one byte per line and checking in a bunch of revisions, each time changing every other line of the file.  Then check out 1.1.  Starting with a file several kB in size and creating a few thousand revisions, I will be suprised if you don't see some significant improvement with the new algorithm over the old.

Derek Robert Price <dprice>
Project Administrator
Wed 06 Sep 2006 06:29:02 PM UTC, comment #16: 

Probably a longish file could help show the differences too, since part of what the improved algorithm was doing was shifting portions of an array forward and backwards (using memcpy) as sections were deleted and other sections were inserted into the array (once per RCS change text chunk).  The more lines in the file, the more lines would need to be shifted in memory for each RCS change chunk.

The new algorithm is simply careful to build a second array in order rather than shifting the first in place.

So really, I think the new algorithm is more exactly O(C + L), where C is the number of RCS change chunks to be processed and L is the total number of lines in the head revision, whereas it was previously approximately O(C * L / 2).

Derek Robert Price <dprice>
Project Administrator
Wed 06 Sep 2006 06:21:01 PM UTC, comment #15: 

I would expect that users of binary files and some kinds of
auto-generated files which have lots of RCS change chunks
will see the most improvement when checking out very old
revisions. (Of course, it would be better if CVS were not
used for such files in the first place as it is intended
more for sources than binaries.)

Mark D. Baushke <mdb>
Project Administrator
Wed 06 Sep 2006 06:07:16 PM UTC, comment #14: 

Excuse me - I misstated that.  The improved algorithm was O(n^2) dependent on the number of RCS change chunks in each revision but only linearly dependent on the number of revisions.  The rest of what I said should still stand.

Cheers,

Derek Robert Price <dprice>
Project Administrator
Wed 06 Sep 2006 06:03:40 PM UTC, comment #13: 

This patch should only affect checkout, and should reduce an O(n^2) dependency on the number of revisions behind the head to O(n).

Of course, many commands (e.g. diff, annotate) can check out at least one old revision of the file before running, so those commands should be affected most.

In other words, using the exact same file, `cvs checkout -rHEAD' should show little to no improvement, whereas `cvs checkout -r1.1' should show improvement exponentially proportional to the number of non-branch revisions in the file.

Since the other overhead, like network transfer, should take more time than even the O(n^2) application of RCS change texts unless the size and number of revisions in the file are both very large, if you don't hold most variables constant then the improvement should be fairly hard to detect.

Cheers,

Derek Robert Price <dprice>
Project Administrator
Wed 06 Sep 2006 05:48:23 PM UTC, comment #12: 

I retried that patch today on a other 16 CPU Linux machine, and did not see the huge differences as reported yesterday. With this machine I see speed enhancements for my project in the order of 33% time savings. Very nice but not HUGE, i.e. the impact of the patch seems to be varying a lot with the file size, repository access method, percentage of diffs between versions of the file.

Peter Toft <petoft>
Wed 06 Sep 2006 12:40:51 PM UTC, comment #11: 

All the changes sound correct to me.  I know the linevector_add is still used, but I didn't check if the linevector_delete function has no further references.  If so, I would think it should be fine to remove.

Attribution of "Michael J. Smith<msmith@ideorlando.org>" would be preferred.  My name is common enough even with the middle initial.

Anonymous
Wed 06 Sep 2006 04:00:36 AM UTC, comment #10: 

I have made a few changes in the code from the
rcs.diff.3 patch:

 + Avoid C99/C++ "//" style comments.
   Use C89 "/* ... */" style comments.

 + Use white space to separate operators.

 + Put curly braces on their own lines.

 + Use xnmalloc (qty, size) instead of
   xnrealloc (NULL, qty, size)

 + Do not mix 'int' and and 'unsigned long' in comparisons.

It appears that the linevector_delete function is
no longer used. Should it be deleted?

I have started a 'make check on this revised patch.
If all goes well, I'll hope to commit tomorrow.
What attribution do you wish for the patch?
Maybe <msmith@ideorlando.org> would be okay?

Mark D. Baushke <mdb>
Project Administrator
Tue 05 Sep 2006 07:50:23 PM UTC, comment #9: 

I just tried CVS 1.12.13 including the most recent patch.
It has a dramatic (positive) impact to some of my major projects.
I measure the time to do "cvs update -r SOMETAG" recursively
and find a speed-up of more than a factor of 3 - for ~1000 files.
If the patch is sound, then this is a major advance to cvs.
I look forward to the next release!

Peter Toft <petoft>
Tue 05 Sep 2006 01:10:56 PM UTC, comment #8: 

I checked the changes from the original source and removed all of the formating related differences I could spot.  See the attached diff. 

As a side note for anyone refactoring this addition, the code under the FRAG_ADD could be refactored into a separate procedure, but I didn't see any real local benefit to this.  This code segment was based on the linevector_add which is used in several other locations.  To limit the extent of this change I did not change the commonly used linevector_add function.

Anonymous
Tue 05 Sep 2006 03:39:41 AM UTC, comment #7: 

Looks like we are almost there.  Could you please regenerate the patch one more time without other extraneous changes.  In particular, please do not include any formatting changes or other changes which do not affect the operation of the code.  For instance, please do not delete comments which still apply, please don't move the open-brackets which open blocks onto the line with their control structure, and please don't move the err = 0 initializer without effect.

If you would like to make a case for removing the comments or moving the initializer, you may submit a separate patch.  Moving the brackets will not be considered - please see the HACKING file distributed with CVS for more on CVS coding conventions.

Thanks,

Derek Robert Price <dprice>
Project Administrator
Tue 29 Aug 2006 02:29:07 PM UTC, comment #6: 

I had missed what you were referencing.  I have re-run with the -w option.  I have to admit I am not too familiar with this the -u diff so was not sure exactly what to expect.

Anonymous
Tue 29 Aug 2006 02:00:50 PM UTC, comment #5: 

> I think my point was i removed the white space and extra DEBUG lines that
> were in my source rcs.c file before the diff -u (I had removed those from the
> original diff by hand a long while back).
>
> I do not believe there are any spurious WS in the diff i attached.


I did not basemy statement on yours.  I looked at the diff.  Reading up through halfway through the second chunk, I see nothing but white space changes.  For example:

@@ -6854,9 +6855,9 @@
     {
  if (vec->lines_alloced == 0)
      vec->lines_alloced = 10;
- while (vec->nlines + nnew >= vec->lines_alloced)
-     vec->lines_alloced *= 2;
- vec->vector = xnrealloc (vec->vector,
+     while (vec->nlines + nnew >= vec->lines_alloced)
+         vec->lines_alloced *= 2;
+     vec->vector = xnrealloc (vec->vector,
  vec->lines_alloced, sizeof (*vec->vector));
     }

This is, at the least, distracting, and often causes the patch algorithm to fail.  At the least, 3/7 chunks fail applying to the trunk and 6/7 fail applying to stable.  Though I am unsure if either of these were because of white-space only changes, I would prefer to wait until I have a clean patch before potentially wasting much more time looking into it.

Derek Robert Price <dprice>
Project Administrator
Tue 29 Aug 2006 01:29:35 PM UTC, comment #4: 

I think my point was i removed the white space and extra DEBUG lines that were in my source rcs.c file before the diff -u (I had removed those from the original diff by hand a long while back).

I do not believe there are any spurious WS in the diff i attached.

Anonymous
Tue 29 Aug 2006 01:25:18 PM UTC, comment #3: 

Patches containing lines with changes to only white space (spaces, tabs, newlines...) complicate our work too and are generally not accepted.  If you think your white space only changes are important, you may try to resubmit them as a separate patch.

You may be able to fix this patch by regenerating the patch with the `-w' option (long synonym is `--ignore-all-space').  So, the complete command would now be `diff -uw'.

Thanks again.

Derek Robert Price <dprice>
Project Administrator
Tue 29 Aug 2006 01:14:06 PM UTC, comment #2: 

Here is the diff -u versus the rcs.c file from 1.12.12.

I removed some of the debug TRACE code to make the changes more clear, but the change is still rather large.

Anonymous
Tue 29 Aug 2006 11:59:51 AM UTC, comment #1: 

Michael Smith's original report and patch ate here: http://lists.nongnu.org/archive/html/bug-cvs/2005-10/msg00046.html .

Michael, could you please include a `diff -u' version of your patch?  It is much easier to deal with.

Derek Robert Price <dprice>
Project Administrator
Mon 28 Aug 2006 08:37:53 PM UTC, original submission:  

A while back (about a year) I detected that cvs slowed down dramatically under 1.12.12 for certain files.  The common issue with these files was that they had a large number of change fragments (and we were not checking out the head version any longer).  For 300K lines and roughly 300K fragments, I found that the underlying merge algorithm in rcs.c was O(n^2) instead of being O(n).

I submitted this patch to the rcs.c a while back on the mailing list, but had heard nothing since.  I would hate for this issue to be found by someone else later since I already have a solution.  This patch was applied to our cvs server and sped up the check-out to the expected amount of time.

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #10697:  rcs.c.patch added by mdb (6KiB - text/x-patch - Revised patch that conforms better to the CVS standards.)
file #10693:  rcs.diff.3 added by None (6KiB - application/octet-stream - updated changes as per Derek's request)
file #10632:  rcs.diff.no-ws added by None (4KiB - application/octet-stream - ran with diff -uw)
file #10629:  rcs.diff added by None (11KiB - text/plain - rcs diff using the -u option on the o(n) merge fix)
file #10623:  cvs-1.12.12.rcs.c-patch-slow-patch-issue.txt added by None (5KiB - text/plain - rcs.c patch of 1.12.12 to fix large merge fragment merge issue)

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

Do you think this task is very important?
If so, you can add your encouragement to it.
This task has 5 encouragements so far.

Only logged-in users can vote.

 

 

 

Follow 13 latest changes.

Date Changed by Updated Field Previous Value => Replaced by
2006-09-08 dprice StatusNeed Info => Fixed
    Open/ClosedOpen => Closed
    Fixed ReleaseNone => 1.11.23
    Fixed Feature ReleaseNone => 1.12.14
2006-09-06 mdb Attached File- => Added rcs.c.patch, #10697
2006-09-05 petoft Carbon-Copy- => Added petoft
2006-09-05 None Attached File- => Added rcs.diff.3, #10693
2006-08-29 None Attached File- => Added rcs.diff.no-ws, #10632
2006-08-29 None Attached File- => Added rcs.diff, #10629
2006-08-29 dprice StatusNone => Need Info
    Release => 1.11.23
    Carbon-Copy- => Added msmith@ideorlando.org
2006-08-28 None Attached File- => Added cvs-1.12.12.rcs.c-patch-slow-patch-issue.txt, #10623

Back to the top


Powered by Savane 3.5