Login | Register
My pages Projects Community openCollabNet

Discussions > SCons Development (OBSOLETE) > [scons-dev] Scons Build Time

Project highlights:

03 Nov 2016: Release 2.5.1 is now available at the download page.

09 Apr 2016: Release 2.5.0 is now available at the download page.

07 Nov 2015: Release 2.4.1 is now available at the download page.

Discussion topic

Back to topic list

[scons-dev] Scons Build Time

Author anirishduck
Full name Frank Murphy
Date 2010-03-08 14:30:43 PST
Message Hello,

If you don't know already, scons's performance on large builds has
been reddited (http://www.reddit.co​m/r/programming/comm​ents/barcc/how_scala​ble_is_scons/).
I like scons, and naturally this information disturbed me. So I
started doing some investigation, and finally discovered this from the
wiki (http://www.scons.org​/wiki/DeveloperGuide​/TaskMaster):

> It's worth noting that the Jobs module calls the Taskmaster once for each node to be processed (i.e., it's O(n)) and the Taskmaster has an amortized performance of O(n) each time it's called. Thus, the overall time is O(n^2). It takes a pathological DAG to achieve the worst-case performance, but it occasionally happens in practice.

It seems fairly clear that the build from reddit article reduces to
one of these "pathological DAGs". The question I have is this: after
looking at the source code of both Taskmaster.py and Job.py, the above
statement from the wiki seems incorrect. When running, Job.py calls
the Taskmaster function next_task to get the next task to run. After
looking over _find_next_ready_node for a bit, it seems to me that its
performance should be amortized O(1), not O(n). After a couple runs,
most nodes on the candidate list should be DAG nodes with no
dependencies. Then, the top of the candidates list will always have a
ready node, and no more looping will be necessary. However, the
performance reported in the prior article seems to suggest otherwise.

Furthermore, if the function isn't amortized O(1), it should be. After
all, there are well known algorithms to topologically sort a DAG, and
all of them are O(n). So it seems that sorting a DAG once and then
finding the next item in a topologically sorted order n times should
be O(1) amortized (and O(n) worst-case).

So, this leads me back to my original question. What is causing the
O(n^2) performance, and how can it be fixed?

Frank Murphy

PS: The codebase for your project is well commented and coherently
laid out. This made my initial inquiry a lot easier, and is something
you guys should be proud of.

« Previous message in topic | 1 of 4 | Next message in topic »


Show all messages in topic

[scons-dev] Scons Build Time anirishduck Frank Murphy 2010-03-08 14:30:43 PST
     Re: [scons-dev] Scons Build Time gregnoel Greg Noel 2010-03-08 18:03:35 PST
         RE: Re: [scons-dev] Scons Build Time webpost at tigris dot org webpost at tigris dot org 2010-03-09 11:41:47 PST
             Re: [scons-dev] Scons Build Time gregnoel Greg Noel 2010-03-09 16:37:23 PST
Messages per page: