[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: anonymous
Subject: [bug #17560] merge code in rcs.c is O(n^2)
Date: Mon, 28 Aug 2006 20:37:54 +0000
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.13) Gecko/20060724 Firefox/1.0.8 (Ubuntu package 1.0.8)


                 Summary: merge code in rcs.c is O(n^2)
                 Project: Concurrent Versions System
            Submitted by: None
            Submitted on: Monday 08/28/2006 at 20:37 UTC
                Category: Bug Fix (patch attached)
                Severity: 3 - Normal
              Item Group: None
                  Status: None
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open
           Fixed Release: None
   Fixed Feature Release: None



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

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.


File Attachments:

Date: Monday 08/28/2006 at 20:37 UTC  Name:
cvs-1.12.12.rcs.c-patch-slow-patch-issue.txt  Size: 4.62KB   By: None
rcs.c patch of 1.12.12 to fix large merge fragment merge issue


Reply to this item at:


  Message sent via/by Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]