Merge pull request #3490 from chasinglogic/less-list-manipulation-in-DAG-walk

Improve DAG walk performance by preventing unnecessary list manipulation

2 files changed, 6 insertions, 2 deletions

diff --git a/src/CHANGES.txt b/src/CHANGES.txt
index 47b63ee..c837157 100755
--- a/src/CHANGES.txt
+++ b/src/CHANGES.txt
@@ -46,6 +46,8 @@ RELEASE  VERSION/DATE TO BE FILLED IN LATER
     - Improved threading performance by ensuring NodeInfo is shared
       across threads. Results in ~13% improvement for parallel builds
       (-j# > 1) with many shared nodes.
+    - Improved DAG walk performance by reducing unnecessary work when
+      there are no un-visited children.
 
   From Mats Wichmann
     - Replace instances of string find method with "in" checks where
diff --git a/src/engine/SCons/Taskmaster.py b/src/engine/SCons/Taskmaster.py
index 4892026..06fc94c 100644
--- a/src/engine/SCons/Taskmaster.py
+++ b/src/engine/SCons/Taskmaster.py
@@ -874,8 +874,10 @@ class Taskmaster(object):
             # These nodes have not even been visited yet.  Add
             # them to the list so that on some next pass we can
             # take a stab at evaluating them (or their children).
-            children_not_visited.reverse()
-            self.candidates.extend(self.order(children_not_visited))
+            if children_not_visited:
+                if len(children_not_visited) > 1:
+                    children_not_visited.reverse()
+                self.candidates.extend(self.order(children_not_visited))
 
             # if T and children_not_visited:
             #    T.write(self.trace_message('     adding to candidates: %s' % map(str, children_not_visited)))