[Notes] [Git][BuildStream/buildstream][bschubert/rework-circular-check]

Benjamin Schubert pushed to branch bschubert/rework-circular-check at BuildStream / buildstream

Commits:

a39c4767

by Daniel Silverstone at 2019-02-12T15:12:30Z

_yaml.py: Only retrieve provenance in node_get() when needed

We were indiscriminately retrieving the node's provenance data in the
`node_get()` function which was accounting for approximately a third of
the total runtime of `node_get()` which dominates pre-scheduler time in
`bst build`.  This change ameliorates that situation by only retrieving
the provenance data when it's actually needed.

Signed-off-by: Daniel Silverstone <daniel silverstone codethink co uk>

cda03313

by Daniel Silverstone at 2019-02-12T15:12:30Z

_yaml.py: Reduce use of `isinstance()` in `node_sanitize()`

We know that nodes are typically one of:
str, list, dict, bool, tuple, NoneType or our ChainMap
Of these, dict and ChainMap are Mapping, only list is list
and the rest are returned unchanged.  We can reduce/defer our use
of isinstance here, dramatically, improving performance.

Signed-off-by: Daniel Silverstone <daniel silverstone codethink co uk>

b6f08e1b

by Daniel Silverstone at 2019-02-12T15:12:30Z

_yaml.py: Remove use of isinstance() in `{node,list}_{chain_,}copy`

A non-trivial proportion of time pre-scheduler in `bst build` is spent
copying (or chain-copying) nodes.  Approximately a quarter of the time
spent in that effort is in `isinstance()`.  This removes that CPU load.

Signed-off-by: Daniel Silverstone <daniel silverstone codethink co uk>

69ee11c6

by Daniel Silverstone at 2019-02-12T15:12:30Z

_yaml.py: Reduce cost of node_final_assertions

By re-using the isinstance replacements from earlier commits and
using a tuple of the string constants for checking for composition
markers, we reduce the cost of node_final_assertions by two thirds
in basic testing.

Signed-off-by: Daniel Silverstone <daniel silverstone codethink co uk>

0928e570

by Daniel Silverstone at 2019-02-12T15:12:30Z

_context.py: Cache result of get_strict()

While get_strict() doesn't look expensive per-se, it is called so many
times that it is valuable to cache the result once computed.  Since I
don't think it can change once it is computable, cache it immediately
that becomes possible and we save 20s in my test case.

Signed-off-by: Daniel Silverstone <daniel silverstone codethink co uk>

022a59f0

by Benjamin Schubert at 2019-02-12T16:14:05Z

Merge branch 'danielsilverstone-ct/further-optimisations' into 'master'

Further optimisations

See merge request BuildStream/buildstream!1131

ae1663f4

by Benjamin Schubert at 2019-02-12T17:00:18Z

Build dependency cache eagerly

We can update the cache as we build the elements, we don't need
to wait until we have built the whole graph

0c5c450e

by Benjamin Schubert at 2019-02-12T17:00:18Z

Eagerly check for circular dependencies

Whenever we finish loading a package's dependencies, we can check
if it's part of a cycle, this allows us to not have to go through
the whole graph a second time

Changes:

buildstream/_context.py

@@ -361,14 +361,17 @@ class Context():
      #    (bool): Whether or not to use strict build plan
+     #
      def get_strict(self):
 +        if self._strict_build_plan is None:
 +            # Either we're not overridden or we've never worked it out before
 +            # so work out if we should be strict, and then cache the result
 +            toplevel = self.get_toplevel_project()
 +            overrides = self.get_overrides(toplevel.name)
 +            self._strict_build_plan = _yaml.node_get(overrides, bool, 'strict', default_value=True)
          # If it was set by the CLI, it overrides any config
 -        if self._strict_build_plan is not None:
 -            return self._strict_build_plan
+-
 -        toplevel = self.get_toplevel_project()
 -        overrides = self.get_overrides(toplevel.name)
 -        return _yaml.node_get(overrides, bool, 'strict', default_value=True)
 +        # Ditto if we've already computed this, then we return the computed
 +        # value which we cache here too.
 +        return self._strict_build_plan
      # get_cache_key():
+     #

buildstream/_loader/loadelement.py

@@ -67,14 +67,14 @@ class LoadElement():
          self.node = node       # The YAML node
          self.name = filename   # The element name
          self.full_name = None  # The element full name (with associated junction)
 -        self.deps = None       # The list of Dependency objects
 -        self.node_id = next(self._counter)
 +        self.dependencies = []
+         #
          # Private members
+         #
          self._loader = loader   # The Loader object
 -        self._dep_cache = None  # The dependency cache, to speed up depends()
 +        self._dep_cache = BitMap()  # The dependency cache, to speed up depends()
 +        self._node_id = next(self._counter)
+         #
          # Initialization
@@ -94,12 +94,27 @@ class LoadElement():
              'build-depends', 'runtime-depends',
          ])
 -        self.dependencies = []
+-
      @property
      def junction(self):
          return self._loader.project.junction
 +    # _add_dependency()
 +    #
 +    # Add an element as a dependency of the current element
 +    #
 +    # Args:
 +    #     dependency (LoadElement): element to add as a dependency
 +    #     dep_type (str): type of dependency to add
 +    #
 +    # Raises:
 +    #     LoadError: if adding the current dependency would create a circular
 +    #                dependency
 +    #
 +    def _add_dependency(self, dependency, dep_type):
 +        self.dependencies.append(LoadElement.Dependency(dependency, dep_type))
 +        self._dep_cache.update(dependency._dep_cache)
 +        self._dep_cache.add(dependency._node_id)
++
      # depends():
+     #
      # Checks if this element depends on another element, directly
@@ -112,32 +127,59 @@ class LoadElement():
      #    (bool): True if this LoadElement depends on 'other'
+     #
      def depends(self, other):
 -        self._ensure_depends_cache()
 -        return other.node_id in self._dep_cache
 +        return other._node_id in self._dep_cache
 -    ###########################################
 -    #            Private Methods              #
 -    ###########################################
 -    def _ensure_depends_cache(self):
 +    # _ensure_no_circular_deps()
 +    #
 +    # Ensure the node is not part of a dependency cycle
 +    #
 +    # Raises:
 +    #   (LoadError): In case there was a circular dependency
 +    #
 +    def _ensure_no_circular_deps(self):
 +        if self._node_id in self._dep_cache:
 +            self._find_circular_deps(set(), set(), [])
 -        if self._dep_cache:
 +    # _find_circular_deps():
 +    #
 +    # Detect circular dependencies on LoadElements with
 +    # dependencies already resolved.
 +    #
 +    # Args:
 +    #    check_elements (set[LoadElement]): The elements in the chain being checked
 +    #    validated (set[LoadElement]): The elements already validated to not have
 +    #                                  circular dependencies
 +    #    sequence (list[Element]): current sequence of elements that is checked
 +    #
 +    # Raises:
 +    #    (LoadError): In case there was a circular dependency error
 +    #
 +    def _find_circular_deps(self, check_elements, validated, sequence):
 +        # Skip already validated branches
 +        if self in validated:
              return
 -        self._dep_cache = BitMap()
+-
 +        if self in check_elements:
 +            # Create `chain`, the loop of element dependencies from this
 +            # element back to itself, by trimming everything before this
 +            # element from the sequence under consideration.
 +            chain = sequence[sequence.index(self.full_name):]
 +            chain.append(self.full_name)
 +            raise LoadError(LoadErrorReason.CIRCULAR_DEPENDENCY,
 +                            ("Circular dependency detected at element: {}\n" +
 +                             "Dependency chain: {}")
 +                            .format(self.full_name, " -> ".join(chain)))
++
 +        # Push / Check each dependency / Pop
 +        check_elements.add(self)
 +        sequence.append(self.full_name)
          for dep in self.dependencies:
 -            elt = dep.element
+-
 -            # Ensure the cache of the element we depend on
 -            elt._ensure_depends_cache()
+-
 -            # We depend on this element
 -            self._dep_cache.add(elt.node_id)
+-
 -            # And we depend on everything this element depends on
 -            self._dep_cache.update(elt._dep_cache)
 +            dep.element._check_circular_deps(check_elements, validated, sequence)
 +        check_elements.remove(self)
 +        sequence.pop()
 -        self._dep_cache = FrozenBitMap(self._dep_cache)
 +        # Eliminate duplicate paths
 +        validated.add(self)
  # _extract_depends_from_node():

buildstream/_loader/loader.py

@@ -127,23 +127,6 @@ class Loader():
                  target_elements.append(element)
                  profile_end(Topics.LOAD_PROJECT, target)
 -        #
 -        # Now that we've resolve the dependencies, scan them for circular dependencies
 -        #
+-
 -        # Set up a dummy element that depends on all top-level targets
 -        # to resolve potential circular dependencies between them
 -        dummy_target = LoadElement("", "", self)
 -        dummy_target.dependencies.extend(
 -            LoadElement.Dependency(element, Symbol.RUNTIME)
 -            for element in target_elements
 -        )
+-
 -        profile_key = "_".join(t for t in targets)
 -        profile_start(Topics.CIRCULAR_CHECK, profile_key)
 -        self._check_circular_deps(dummy_target)
 -        profile_end(Topics.CIRCULAR_CHECK, profile_key)
+-
          ret = []
+         #
          # Sort direct dependencies of elements by their dependency ordering
@@ -273,58 +256,14 @@ class Loader():
                                  "{}: Cannot depend on junction"
                                  .format(dep.provenance))
 -            element.dependencies.append(LoadElement.Dependency(dep_element, dep.dep_type))
 +            element._add_dependency(dep_element, dep.dep_type)
          deps_names = [dep.name for dep in dependencies]
          self._warn_invalid_elements(deps_names)
 -        return element
 +        element._ensure_no_circular_deps()
 -    # _check_circular_deps():
 -    #
 -    # Detect circular dependencies on LoadElements with
 -    # dependencies already resolved.
 -    #
 -    # Args:
 -    #    element (str): The element to check
 -    #
 -    # Raises:
 -    #    (LoadError): In case there was a circular dependency error
 -    #
 -    def _check_circular_deps(self, element, check_elements=None, validated=None, sequence=None):
+-
 -        if check_elements is None:
 -            check_elements = {}
 -        if validated is None:
 -            validated = {}
 -        if sequence is None:
 -            sequence = []
+-
 -        # Skip already validated branches
 -        if validated.get(element) is not None:
 -            return
+-
 -        if check_elements.get(element) is not None:
 -            # Create `chain`, the loop of element dependencies from this
 -            # element back to itself, by trimming everything before this
 -            # element from the sequence under consideration.
 -            chain = sequence[sequence.index(element.full_name):]
 -            chain.append(element.full_name)
 -            raise LoadError(LoadErrorReason.CIRCULAR_DEPENDENCY,
 -                            ("Circular dependency detected at element: {}\n" +
 -                             "Dependency chain: {}")
 -                            .format(element.full_name, " -> ".join(chain)))
+-
 -        # Push / Check each dependency / Pop
 -        check_elements[element] = True
 -        sequence.append(element.full_name)
 -        for dep in element.dependencies:
 -            dep.element._loader._check_circular_deps(dep.element, check_elements, validated, sequence)
 -        del check_elements[element]
 -        sequence.pop()
+-
 -        # Eliminate duplicate paths
 -        validated[element] = True
 +        return element
      # _sort_dependencies():
+     #

buildstream/_profile.py

@@ -42,7 +42,6 @@ initialized = False
+ #
  # The special 'all' value will enable all profiles.
  class Topics():
 -    CIRCULAR_CHECK = 'circ-dep-check'
      SORT_DEPENDENCIES = 'sort-deps'
      LOAD_LOADER = 'load-loader'
      LOAD_CONTEXT = 'load-context'

buildstream/_yaml.py

@@ -365,8 +365,8 @@ _sentinel = object()
+ #
  def node_get(node, expected_type, key, indices=None, *, default_value=_sentinel, allow_none=False):
      value = node.get(key, default_value)
 -    provenance = node_get_provenance(node)
      if value is _sentinel:
 +        provenance = node_get_provenance(node)
          raise LoadError(LoadErrorReason.INVALID_DATA,
                          "{}: Dictionary did not contain expected key '{}'".format(provenance, key))
@@ -914,6 +914,10 @@ RoundTripRepresenter.add_representer(SanitizedDict,
                                       SafeRepresenter.represent_dict)
 +# Types we can short-circuit in node_sanitize for speed.
 +__SANITIZE_SHORT_CIRCUIT_TYPES = (int, float, str, bool, tuple)
++
++
  # node_sanitize()
+ #
  # Returnes an alphabetically ordered recursive copy
@@ -922,9 +926,21 @@ RoundTripRepresenter.add_representer(SanitizedDict,
  # Only dicts are ordered, list elements are left in order.
+ #
  def node_sanitize(node):
 +    # Short-circuit None which occurs ca. twice per element
 +    if node is None:
 +        return node
++
 +    node_type = type(node)
 +    # Next short-circuit integers, floats, strings, booleans, and tuples
 +    if node_type in __SANITIZE_SHORT_CIRCUIT_TYPES:
 +        return node
 +    # Now short-circuit lists.  Note this is only for the raw list
 +    # type, CommentedSeq and others get caught later.
 +    elif node_type is list:
 +        return [node_sanitize(elt) for elt in node]
 -    if isinstance(node, collections.abc.Mapping):
+-
 +    # Finally ChainMap and dict, and other Mappings need special handling
 +    if node_type in (dict, ChainMap) or isinstance(node, collections.Mapping):
          result = SanitizedDict()
          key_list = [key for key, _ in node_items(node)]
@@ -932,10 +948,12 @@ def node_sanitize(node):
              result[key] = node_sanitize(node[key])
          return result
+-
 +    # Catch the case of CommentedSeq and friends.  This is more rare and so
 +    # we keep complexity down by still using isinstance here.
      elif isinstance(node, list):
          return [node_sanitize(elt) for elt in node]
 +    # Everything else (such as commented scalars) just gets returned as-is.
      return node
@@ -1064,15 +1082,52 @@ class ChainMap(collections.ChainMap):
              return default
 +# Node copying
 +#
 +# Unfortunately we copy nodes a *lot* and `isinstance()` is super-slow when
 +# things from collections.abc get involved.  The result is the following
 +# intricate but substantially faster group of tuples and the use of `in`.
 +#
 +# If any of the {node,list}_{chain_,}_copy routines raise a ValueError
 +# then it's likely additional types need adding to these tuples.
++
 +# When chaining a copy, these types are skipped since the ChainMap will
 +# retrieve them from the source node when needed.  Other copiers might copy
 +# them, so we call them __QUICK_TYPES.
 +__QUICK_TYPES = (str, bool,
 +                 yaml.scalarstring.PreservedScalarString,
 +                 yaml.scalarstring.SingleQuotedScalarString,
 +                 yaml.scalarstring.DoubleQuotedScalarString)
++
 +# These types have to be iterated like a dictionary
 +__DICT_TYPES = (dict, ChainMap, yaml.comments.CommentedMap)
++
 +# These types have to be iterated like a list
 +__LIST_TYPES = (list, yaml.comments.CommentedSeq)
++
 +# These are the provenance types, which have to be cloned rather than any other
 +# copying tactic.
 +__PROVENANCE_TYPES = (Provenance, DictProvenance, MemberProvenance, ElementProvenance)
++
 +# These are the directives used to compose lists, we need this because it's
 +# slightly faster during the node_final_assertions checks
 +__NODE_ASSERT_COMPOSITION_DIRECTIVES = ('(>)', '(<)', '(=)')
++
++
  def node_chain_copy(source):
      copy = ChainMap({}, source)
      for key, value in source.items():
 -        if isinstance(value, collections.abc.Mapping):
 +        value_type = type(value)
 +        if value_type in __DICT_TYPES:
              copy[key] = node_chain_copy(value)
 -        elif isinstance(value, list):
 +        elif value_type in __LIST_TYPES:
              copy[key] = list_chain_copy(value)
 -        elif isinstance(value, Provenance):
 +        elif value_type in __PROVENANCE_TYPES:
              copy[key] = value.clone()
 +        elif value_type in __QUICK_TYPES:
 +            pass  # No need to copy these, the chainmap deals with it
 +        else:
 +            raise ValueError("Unable to be quick about node_chain_copy of {}".format(value_type))
      return copy
@@ -1080,14 +1135,17 @@ def node_chain_copy(source):
  def list_chain_copy(source):
      copy = []
      for item in source:
 -        if isinstance(item, collections.abc.Mapping):
 +        item_type = type(item)
 +        if item_type in __DICT_TYPES:
              copy.append(node_chain_copy(item))
 -        elif isinstance(item, list):
 +        elif item_type in __LIST_TYPES:
              copy.append(list_chain_copy(item))
 -        elif isinstance(item, Provenance):
 +        elif item_type in __PROVENANCE_TYPES:
              copy.append(item.clone())
 -        else:
 +        elif item_type in __QUICK_TYPES:
              copy.append(item)
 +        else:  # Fallback
 +            raise ValueError("Unable to be quick about list_chain_copy of {}".format(item_type))
      return copy
@@ -1095,14 +1153,17 @@ def list_chain_copy(source):
  def node_copy(source):
      copy = {}
      for key, value in source.items():
 -        if isinstance(value, collections.abc.Mapping):
 +        value_type = type(value)
 +        if value_type in __DICT_TYPES:
              copy[key] = node_copy(value)
 -        elif isinstance(value, list):
 +        elif value_type in __LIST_TYPES:
              copy[key] = list_copy(value)
 -        elif isinstance(value, Provenance):
 +        elif value_type in __PROVENANCE_TYPES:
              copy[key] = value.clone()
 -        else:
 +        elif value_type in __QUICK_TYPES:
              copy[key] = value
 +        else:
 +            raise ValueError("Unable to be quick about node_copy of {}".format(value_type))
      ensure_provenance(copy)
@@ -1112,14 +1173,17 @@ def node_copy(source):
  def list_copy(source):
      copy = []
      for item in source:
 -        if isinstance(item, collections.abc.Mapping):
 +        item_type = type(item)
 +        if item_type in __DICT_TYPES:
              copy.append(node_copy(item))
 -        elif isinstance(item, list):
 +        elif item_type in __LIST_TYPES:
              copy.append(list_copy(item))
 -        elif isinstance(item, Provenance):
 +        elif item_type in __PROVENANCE_TYPES:
              copy.append(item.clone())
 -        else:
 +        elif item_type in __QUICK_TYPES:
              copy.append(item)
 +        else:
 +            raise ValueError("Unable to be quick about list_copy of {}".format(item_type))
      return copy
@@ -1142,22 +1206,26 @@ def node_final_assertions(node):
          # indicates that the user intended to override a list which
          # never existed in the underlying data
+         #
 -        if key in ['(>)', '(<)', '(=)']:
 +        if key in __NODE_ASSERT_COMPOSITION_DIRECTIVES:
              provenance = node_get_provenance(node, key)
              raise LoadError(LoadErrorReason.TRAILING_LIST_DIRECTIVE,
                              "{}: Attempt to override non-existing list".format(provenance))
 -        if isinstance(value, collections.abc.Mapping):
 +        value_type = type(value)
++
 +        if value_type in __DICT_TYPES:
              node_final_assertions(value)
 -        elif isinstance(value, list):
 +        elif value_type in __LIST_TYPES:
              list_final_assertions(value)
  def list_final_assertions(values):
      for value in values:
 -        if isinstance(value, collections.abc.Mapping):
 +        value_type = type(value)
++
 +        if value_type in __DICT_TYPES:
              node_final_assertions(value)
 -        elif isinstance(value, list):
 +        elif value_type in __LIST_TYPES:
              list_final_assertions(value)

[Notes] [Git][BuildStream/buildstream][bschubert/rework-circular-check] 8 commits: _yaml.py: Only retrieve provenance in node_get() when needed

Benjamin Schubert pushed to branch bschubert/rework-circular-check at BuildStream / buildstream

Commits:

5 changed files:

Changes: