[buildstream] 01/03: element: Rewrite 'dependencies()' to be more optimal

[ro...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

root pushed a commit to branch bschubert/optimize-deps
in repository https://gitbox.apache.org/repos/asf/buildstream.git

commit 5201c2983e1fdb903027d657c63493b73f24f8a6
Author: Benjamin Schubert <be...@gmail.com>
AuthorDate: Fri Jul 12 18:05:50 2019 +0100

    element: Rewrite 'dependencies()' to be more optimal
    
    This reduces the number of comparison we need to make and reduces
    the runtime cost of this method by roughly 25%
---
 src/buildstream/element.py | 65 +++++++++++++++++++++++++---------------------
 1 file changed, 36 insertions(+), 29 deletions(-)

diff --git a/src/buildstream/element.py b/src/buildstream/element.py
index fe7d366..9239a2c 100644
--- a/src/buildstream/element.py
+++ b/src/buildstream/element.py
@@ -80,7 +80,6 @@ from collections import OrderedDict
 import contextlib
 from contextlib import contextmanager
 from functools import partial
-from itertools import chain
 import string
 from typing import cast, TYPE_CHECKING, Any, Dict, Iterator, List, Optional
 
@@ -468,46 +467,54 @@ class Element(Plugin):
             if scope in (Scope.RUN, Scope.ALL):
                 yield from self.__runtime_dependencies
         else:
+            def visit_run(element, visited):
+                visited.add(element._unique_id)
 
-            def visit(element, scope, visited):
-                if scope == Scope.ALL:
-                    visited[0].add(element._unique_id)
-                    visited[1].add(element._unique_id)
+                for dep in element.__runtime_dependencies:
+                    if dep._unique_id not in visited:
+                        yield from visit_run(dep, visited)
 
-                    for dep in chain(element.__build_dependencies, element.__runtime_dependencies):
-                        if dep._unique_id not in visited[0] and dep._unique_id not in visited[1]:
-                            yield from visit(dep, Scope.ALL, visited)
+                yield element
 
-                    yield element
-                elif scope == Scope.BUILD:
-                    visited[0].add(element._unique_id)
+            def visit_build(element, visited_build, visited_run):
+                visited_build.add(element._unique_id)
 
-                    for dep in element.__build_dependencies:
-                        if dep._unique_id not in visited[1]:
-                            yield from visit(dep, Scope.RUN, visited)
+                for dep in element.__build_dependencies:
+                    if dep._unique_id not in visited_run:
+                        yield from visit_run(dep, visited_run)
 
-                elif scope == Scope.RUN:
-                    visited[1].add(element._unique_id)
+            def visit_all(element, visited):
+                visited.add(element._unique_id)
 
-                    for dep in element.__runtime_dependencies:
-                        if dep._unique_id not in visited[1]:
-                            yield from visit(dep, Scope.RUN, visited)
+                for dep in element.__build_dependencies:
+                    if dep._unique_id not in visited:
+                        yield from visit_all(dep, visited)
 
-                    yield element
-                else:
-                    yield element
+                for dep in element.__runtime_dependencies:
+                    if dep._unique_id not in visited:
+                        yield from visit_all(dep, visited)
+
+                yield element
 
             if visited is None:
                 # Visited is of the form (Visited for Scope.BUILD, Visited for Scope.RUN)
                 visited = (BitMap(), BitMap())
-            else:
-                # We have already a visited set passed. we might be able to short-circuit
-                if scope in (Scope.BUILD, Scope.ALL) and self._unique_id in visited[0]:
-                    return
-                if scope in (Scope.RUN, Scope.ALL) and self._unique_id in visited[1]:
-                    return
 
-            yield from visit(self, scope, visited)
+            if scope == Scope.ALL:
+                # We can use only one of the sets when checking for Scope.ALL, as we would get added to
+                # both anyways.
+                # This would break if we start reusing 'visited' and mixing scopes, but that is done
+                # nowhere in the codebase.
+                if self._unique_id not in visited[0]:
+                    yield from visit_all(self, visited[0])
+            elif scope == Scope.BUILD:
+                if self._unique_id not in visited[0]:
+                    yield from visit_build(self, visited[0], visited[1])
+            elif scope == Scope.RUN:
+                if self._unique_id not in visited[1]:
+                    yield from visit_run(self, visited[1])
+            else:
+                yield self
 
     def search(self, scope: Scope, name: str) -> Optional["Element"]:
         """Search for a dependency by name