From 0b75e62fe83bd1a6af3e73ef3a53c5bf475e35d9 Mon Sep 17 00:00:00 2001 From: Benjamin Schubert Date: Tue, 14 Jan 2020 14:54:35 +0000 Subject: loader.py: Optimize sorting of elements when they are multiple targets Currently, with multiple targets, we would go through all the elements in the target and sort them, even though they might already be sorted. This ensures we sort every element only once. --- src/buildstream/_loader/loadelement.pyx | 13 +++++++++++-- src/buildstream/_loader/loader.py | 6 +++++- 2 files changed, 16 insertions(+), 3 deletions(-) diff --git a/src/buildstream/_loader/loadelement.pyx b/src/buildstream/_loader/loadelement.pyx index fb1dd1d15..31c3aef1a 100644 --- a/src/buildstream/_loader/loadelement.pyx +++ b/src/buildstream/_loader/loadelement.pyx @@ -212,12 +212,21 @@ def _dependency_cmp(Dependency dep_a, Dependency dep_b): # # Args: # element (LoadElement): The element to sort +# visited (set): a list of elements that should not be treated because +# because they already have been treated. +# This is useful when wanting to sort dependencies of +# multiple top level elements that might have a common +# part. # -def sort_dependencies(LoadElement element): +def sort_dependencies(LoadElement element, set visited): cdef list working_elements = [element] - cdef set visited = set(working_elements) cdef Dependency dep + if element in visited: + return + + visited.add(element) + # 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. diff --git a/src/buildstream/_loader/loader.py b/src/buildstream/_loader/loader.py index 3b18af691..0c6c725c7 100644 --- a/src/buildstream/_loader/loader.py +++ b/src/buildstream/_loader/loader.py @@ -141,10 +141,14 @@ class Loader: # # Sort direct dependencies of elements by their dependency ordering # + + # Keep a list of all visited elements, to not sort twice the same + visited_elements = set() + for element in target_elements: loader = element._loader with PROFILER.profile(Topics.SORT_DEPENDENCIES, element.name): - loadelement.sort_dependencies(element) + loadelement.sort_dependencies(element, visited_elements) # Finally, wrap what we have into LoadElements and return the target # -- cgit v1.2.1