Speed up adding children to the various Node lists (depends, ignore, sources, implicit).

4 files changed, 74 insertions, 26 deletions

diff --git a/src/CHANGES.txt b/src/CHANGES.txt
index a066689..3283760 100644
--- a/src/CHANGES.txt
+++ b/src/CHANGES.txt
@@ -28,6 +28,12 @@ RELEASE 0.XX - XXX
 
   - Add an "sconsign" script to print the contents of .sconsign files.
 
+  - Speed up maintaining the various lists of Node children by using
+    dictionaries to avoid "x in list" searches.
+
+  - Cache the computed list of Node children minus those being Ignored
+    so it's only calculated once.
+
   From Gary Oberbrunner:
 
   - Report the target being built in error messages when building
diff --git a/src/engine/SCons/Node/FS.py b/src/engine/SCons/Node/FS.py
index c2d001e..1f88330 100644
--- a/src/engine/SCons/Node/FS.py
+++ b/src/engine/SCons/Node/FS.py
@@ -969,7 +969,11 @@ class Dir(Entry):
         else:
             return self.entries['..'].root()
 
-    def all_children(self, scan):
+    def children(self, scan=1):
+        return filter(lambda x, i=self.ignore: x not in i,
+                             self.all_children(scan))
+
+    def all_children(self, scan=1):
         keys = filter(lambda k: k != '.' and k != '..', self.entries.keys())
         kids = map(lambda x, s=self: s.entries[x], keys)
         def c(one, two):
diff --git a/src/engine/SCons/Node/NodeTests.py b/src/engine/SCons/Node/NodeTests.py
index f8593d7..103cfae 100644
--- a/src/engine/SCons/Node/NodeTests.py
+++ b/src/engine/SCons/Node/NodeTests.py
@@ -429,20 +429,23 @@ class NodeTestCase(unittest.TestCase):
         n1 = SCons.Node.Node()
         n1.builder_set(Builder())
         node.implicit = []
-        node._add_child(node.implicit, [n1])
+        node.implicit_dict = {}
+        node._add_child(node.implicit, node.implicit_dict, [n1])
 
         node.prepare()  # should not throw an exception
 
         n2 = SCons.Node.Node()
         n2.linked = 1
         node.implicit = []
-        node._add_child(node.implicit, [n2])
+        node.implicit_dict = {}
+        node._add_child(node.implicit, node.implicit_dict, [n2])
 
         node.prepare()  # should not throw an exception
 
         n3 = SCons.Node.Node()
         node.implicit = []
-        node._add_child(node.implicit, [n3])
+        node.implicit_dict = {}
+        node._add_child(node.implicit, node.implicit_dict, [n3])
 
         node.prepare()  # should not throw an exception
 
@@ -451,7 +454,8 @@ class NodeTestCase(unittest.TestCase):
                 return None
         n4 = MyNode()
         node.implicit = []
-        node._add_child(node.implicit, [n4]) 
+        node.implicit_dict = {}
+        node._add_child(node.implicit, node.implicit_dict, [n4]) 
         exc_caught = 0
         try:
             node.prepare()
@@ -650,8 +654,9 @@ class NodeTestCase(unittest.TestCase):
         node.add_source([n1, n2, n3])
         node.add_dependency([n4, n5, n6])
         node.implicit = []
-        node._add_child(node.implicit, [n7, n8, n9])
-        node._add_child(node.implicit, [n10, n11, n12])
+        node.implicit_dict = {}
+        node._add_child(node.implicit, node.implicit_dict, [n7, n8, n9])
+        node._add_child(node.implicit, node.implicit_dict, [n10, n11, n12])
         node.add_ignore([n2, n5, n8, n11])
 
         kids = node.children()
@@ -680,8 +685,9 @@ class NodeTestCase(unittest.TestCase):
         node.add_source([n1, n2, n3])
         node.add_dependency([n4, n5, n6])
         node.implicit = []
-        node._add_child(node.implicit, [n7, n8, n9])
-        node._add_child(node.implicit, [n10, n11, n12])
+        node.implicit_dict = {}
+        node._add_child(node.implicit, node.implicit_dict, [n7, n8, n9])
+        node._add_child(node.implicit, node.implicit_dict, [n10, n11, n12])
         node.add_ignore([n2, n5, n8, n11])
 
         kids = node.all_children()
@@ -717,10 +723,14 @@ class NodeTestCase(unittest.TestCase):
         n1.add_source([n2, n3])
 
         nw = SCons.Node.Walker(n1)
-        assert nw.next().name ==  "n2"
-        assert nw.next().name ==  "n3"
-        assert nw.next().name ==  "n1"
-        assert nw.next() == None
+        n = nw.next()
+        assert n.name ==  "n2", n.name
+        n = nw.next()
+        assert n.name ==  "n3", n.name
+        n = nw.next()
+        assert n.name ==  "n1", n.name
+        n = nw.next()
+        assert n == None, n
 
         n4 = MyNode("n4")
         n5 = MyNode("n5")
diff --git a/src/engine/SCons/Node/__init__.py b/src/engine/SCons/Node/__init__.py
index 0fc2365..6947c93 100644
--- a/src/engine/SCons/Node/__init__.py
+++ b/src/engine/SCons/Node/__init__.py
@@ -95,10 +95,20 @@ class Node:
         # canonical example being a builder to fetch a file from a
         # source code system like CVS or Subversion).
 
+        # Each list of children that we maintain is accompanied by a
+        # dictionary used to look up quickly whether a node is already
+        # present in the list.  Empirical tests showed that it was
+        # fastest to maintain them as side-by-side Node attributes in
+        # this way, instead of wrapping up each list+dictionary pair in
+        # a class.  (Of course, we could always still do that in the
+        # future if we had a good reason to...).
         self.sources = []       # source files used to build node
+        self.sources_dict = {}
         self.depends = []       # explicit dependencies (from Depends)
-        self.implicit = None    # implicit (scanned) dependencies (None means not scanned yet)
+        self.depends_dict = {}
         self.ignore = []        # dependencies to ignore
+        self.ignore_dict = {}
+        self.implicit = None    # implicit (scanned) dependencies (None means not scanned yet)
         self.parents = {}
         self.wkids = None       # Kids yet to walk, when it's an array
         self.source_scanner = None      # implicit scanner from scanner map
@@ -349,6 +359,7 @@ class Node:
         if not self.implicit is None:
             return
         self.implicit = []
+        self.implicit_dict = {}
         if not self.has_builder():
             return
 
@@ -356,7 +367,7 @@ class Node:
             implicit = self.get_stored_implicit()
             if implicit is not None:
                 implicit = map(self.implicit_factory, implicit)
-                self._add_child(self.implicit, implicit)
+                self._add_child(self.implicit, self.implicit_dict, implicit)
                 calc = SCons.Sig.default_calc
                 if implicit_deps_unchanged or calc.current(self, calc.bsig(self)):
                     return
@@ -365,18 +376,21 @@ class Node:
                     # we need to recalculate the implicit deps,
                     # and the bsig:
                     self.implicit = []
+                    self.implicit_dict = {}
                     self.del_bsig()
 
         build_env = self.get_build_env()
 
         for child in self.children(scan=0):
             self._add_child(self.implicit,
+                            self.implicit_dict,
                             child.get_implicit_deps(build_env,
                                                     child.source_scanner,
                                                     self))
 
         # scan this node itself for implicit dependencies
         self._add_child(self.implicit,
+                        self.implicit_dict,
                         self.get_implicit_deps(build_env,
                                                self.target_scanner,
                                                self))
@@ -557,26 +571,33 @@ class Node:
 
     def add_dependency(self, depend):
         """Adds dependencies. The depend argument must be a list."""
-        self._add_child(self.depends, depend)
+        self._add_child(self.depends, self.depends_dict, depend)
 
     def add_ignore(self, depend):
         """Adds dependencies to ignore. The depend argument must be a list."""
-        self._add_child(self.ignore, depend)
+        self._add_child(self.ignore, self.ignore_dict, depend)
 
     def add_source(self, source):
         """Adds sources. The source argument must be a list."""
-        self._add_child(self.sources, source)
+        self._add_child(self.sources, self.sources_dict, source)
 
-    def _add_child(self, collection, child):
-        """Adds 'child' to 'collection'. The 'child' argument must be a list"""
+    def _add_child(self, collection, dict, child):
+        """Adds 'child' to 'collection', first checking 'dict' to see if
+        it's already present. The 'child' argument must be a list"""
         if type(child) is not type([]):
             raise TypeError("child must be a list")
-        child = filter(lambda x, s=collection: x not in s, child)
-        if child:
-            collection.extend(child)
-
+        added = None
         for c in child:
+            if not dict.has_key(c):
+                collection.append(c)
+                dict[c] = 1
+                added = 1
             c.parents[self] = 1
+        if added:
+            try:
+                delattr(self, '_children')
+            except AttributeError:
+                pass
 
     def add_wkid(self, wkid):
         """Add a node to the list of kids waiting to be evaluated"""
@@ -586,8 +607,15 @@ class Node:
     def children(self, scan=1):
         """Return a list of the node's direct children, minus those
         that are ignored by this node."""
-        return filter(lambda x, i=self.ignore: x not in i,
-                      self.all_children(scan))
+        if scan:
+            self.scan()
+        try:
+            return self._children
+        except AttributeError:
+            c = filter(lambda x, i=self.ignore: x not in i,
+                              self.all_children(scan=0))
+            self._children = c
+            return c
 
     def all_children(self, scan=1):
         """Return a list of all the node's direct children."""