bugmake - Bugs: bug #15533, Double-colon lines are inserted...

 
 

bug #15533: Double-colon lines are inserted O(n^2). VERY long make startup time

Submitter:  None
Submitted:  Thu 26 Jan 2006 01:22:52 AM UTC
   
 
Severity:  3 - Normal Item Group:  Enhancement
Status:  Fixed Privacy:  Public
Assigned to:  psmith Open/Closed:  Closed
Component Version:  3.80 Operating System:  Any
Fixed Release:  3.81 Triage Status:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Sun 05 Feb 2006 04:36:50 PM UTC, comment #2: 

OK, I added a pointer to keep track of the last item in the list.

Paul D. Smith <psmith>
Group administrator
Thu 26 Jan 2006 01:27:00 AM UTC, comment #1: 

The 3.81beta4 code runs in 2059.64s, so that's 20% faster than the 3.79.1 code.

Attached is the diff to get this down to 187s (10x)

I understand that this is probably not a common problem (lots of double colons) but it is a dramatic speed improvement when you do have them

Anonymous
Thu 26 Jan 2006 01:22:52 AM UTC, original submission:  

% grep :: Makefile | wc -l
91348

% time ./make-3.79.1 foo
2540.26s user 9.99s system 94% cpu 45:00.78 total

% time ./make-3.81beta4 foo


A little instrumentation in file.c shows that this code:

  else
    {
      /* There is already a double-colon entry for this file.  */
      new->double_colon = f;
      while (f->prev != 0)
        f = f->prev;
      f->prev = new;
    }

Gets run about 1.5M times with my test makefile, with each run going around the "while" loop about 13k times, for a total of 19,000,000,000 executions of "f = f->prev".

SOLUTION:
Add a "tail" pointer to the linked list that hangs of the file struct. This pointer points to the last element in the linked list at all times, making insertion O(1) instead of O(n).

ATTACHMENT:
measurement data from before and after the patch.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #2131:  diff added by None (1KiB - application/octet-stream - Diff from 3.81beta4 to remove O(n^2) insertion for double-colon lines)
file #2130:  measurements added by None (2KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

Only logged-in users can vote.

 

Follow 7 latest changes.

Date Changed by Updated Field Previous Value => Replaced by
2006-04-01 psmith Fixed Release4.0 3.81
2006-02-05 psmith StatusNone Fixed
    Assigned toNone psmith
    Open/ClosedOpen Closed
    Fixed ReleaseNone 4.0
2006-01-26 None Attached File- Added diff, #3313
2006-01-26 None Attached File- Added measurements, #3312

Back to the top

Powered by Savane 3.13-3230.
Corresponding source code