_loader: Optimize loading by keeping the dependencies sortedbschubert/optimize-loader-sorting

A sizeable amount of time is spent in sorting the dependencies when
loading elements. We can instead keep the list sorted at all time,
which reduces the number of time we need to call sort.

3 files changed, 30 insertions, 46 deletions

diff --git a/src/buildstream/_loader/loadelement.pyx b/src/buildstream/_loader/loadelement.pyx
index 867de6f29..694380b4f 100644
--- a/src/buildstream/_loader/loadelement.pyx
+++ b/src/buildstream/_loader/loadelement.pyx
@@ -116,6 +116,30 @@ cdef class LoadElement:
     def junction(self):
         return self._loader.project.junction
 
+    # add_dependency()
+    #
+    # Add a dependency to the current element.
+    #
+    # This helper functions keeps the underlying list sorted at all times to remove the need for filtering.
+    #
+    # Args:
+    #   dep (Dependency): the dependency to add to the list
+    #
+    def add_dependency(self, Dependency dep not None):
+        cdef int low = 0
+        cdef int high = len(self.dependencies)
+        cdef int mid
+
+        while low < high:
+            mid = (low + high) // 2
+
+            if _dependency_cmp(<Dependency> self.dependencies[mid], dep) < 0:
+                low = mid + 1
+            else:
+                high = mid
+
+        self.dependencies.insert(low, dep)
+
     # depends():
     #
     # Checks if this element depends on another element, directly
@@ -195,34 +219,3 @@ def _dependency_cmp(Dependency dep_a, Dependency dep_b):
 
     # This wont ever happen
     return 0
-
-
-# sort_dependencies():
-#
-# Sort dependencies of each element by their dependencies,
-# so that direct dependencies which depend on other direct
-# dependencies (directly or indirectly) appear later in the
-# list.
-#
-# This avoids the need for performing multiple topological
-# sorts throughout the build process.
-#
-# Args:
-#    element (LoadElement): The element to sort
-#
-def sort_dependencies(LoadElement element):
-    cdef list working_elements = [element]
-    cdef set visited = set(working_elements)
-    cdef Dependency dep
-
-    # Now dependency sort, we ensure that if any direct dependency
-    # directly or indirectly depends on another direct dependency,
-    # it is found later in the list.
-    while working_elements:
-        element = working_elements.pop()
-        for dep in element.dependencies:
-            if dep.element not in visited:
-                visited.add(dep.element)
-                working_elements.append(dep.element)
-
-        element.dependencies.sort(key=cmp_to_key(_dependency_cmp))
diff --git a/src/buildstream/_loader/loader.py b/src/buildstream/_loader/loader.py
index 061d28bf0..9c7add0b0 100644
--- a/src/buildstream/_loader/loader.py
+++ b/src/buildstream/_loader/loader.py
@@ -131,18 +131,12 @@ class Loader():
         with PROFILER.profile(Topics.CIRCULAR_CHECK, "_".join(targets)):
             self._check_circular_deps(dummy_target)
 
-        ret = []
+        # Finally, wrap what we have into LoadElements and return the target
         #
-        # Sort direct dependencies of elements by their dependency ordering
-        #
-        for element in target_elements:
-            loader = element._loader
-            with PROFILER.profile(Topics.SORT_DEPENDENCIES, element.name):
-                loadelement.sort_dependencies(element)
-
-            # Finally, wrap what we have into LoadElements and return the target
-            #
-            ret.append(loader._collect_element(element, task))
+        ret = [
+            element._loader._collect_element(element, task)
+            for element in target_elements
+        ]
 
         self._clean_caches()
 
@@ -342,9 +336,7 @@ class Loader():
                                             LoadErrorReason.INVALID_DATA)
 
                 # All is well, push the dependency onto the LoadElement
-                # Pylint is not very happy with Cython and can't understand 'dependencies' is a list
-                current_element[0].dependencies.append(  # pylint: disable=no-member
-                    Dependency(dep_element, dep.dep_type))
+                current_element[0].add_dependency(Dependency(dep_element, dep.dep_type))
             else:
                 # We do not have any more dependencies to load for this
                 # element on the queue, report any invalid dep names
diff --git a/src/buildstream/_profile.py b/src/buildstream/_profile.py
index b17215d0e..e41cd7706 100644
--- a/src/buildstream/_profile.py
+++ b/src/buildstream/_profile.py
@@ -41,7 +41,6 @@ import time
 # The special 'all' value will enable all profiles.
 class Topics():
     CIRCULAR_CHECK = 'circ-dep-check'
-    SORT_DEPENDENCIES = 'sort-deps'
     LOAD_CONTEXT = 'load-context'
     LOAD_PROJECT = 'load-project'
     LOAD_PIPELINE = 'load-pipeline'