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

 
 

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

Submitted by:  None
Submitted on:  Thu 26 Jan 2006 01:22:52 AM UTC  
 
Severity: 3 - NormalItem Group: Enhancement
Status: FixedPrivacy: Public
Assigned to: Paul D. Smith <psmith>Open/Closed: Closed
Component Version: 3.80Operating System: Any
Fixed Release: 3.81Triage Status: None

Add a New Comment(Rich Markup)
   

You are not logged in

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

 

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>
Project AdministratorIn charge of this item.
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 File(s):
   
   
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

 

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

Only logged-in users can vote.

 

Please enter the title of George Orwell's famous dystopian book (it's a date):

 

 

Follow 7 latest changes.

Date Changed By Updated Field Previous Value => Replaced By
Sat 01 Apr 2006 07:18:44 AM UTCpsmithFixed Release4.0=>3.81
Sun 05 Feb 2006 04:36:50 PM UTCpsmithStatusNone=>Fixed
  Assigned toNone=>psmith
  Open/ClosedOpen=>Closed
  Fixed ReleaseNone=>4.0
Thu 26 Jan 2006 01:27:00 AM UTCNoneAttached File-=>Added diff, #3313
Thu 26 Jan 2006 01:22:52 AM UTCNoneAttached File-=>Added measurements, #3312

Back to the top


Powered by Savane 3.1-cleanup1