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

[anonymous]

URL:
  <http://savannah.nongnu.org/bugs/?17560>

                 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
                 Release: 
           Fixed Release: None
   Fixed Feature Release: None

    _______________________________________________________

Details:

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.







    _______________________________________________________

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
<http://savannah.nongnu.org/bugs/download.php?file_id=10623>

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/bugs/?17560>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/