diff options
author | Benjamin Schubert <ben.c.schubert@gmail.com> | 2019-02-05 15:45:37 +0000 |
---|---|---|
committer | Benjamin Schubert <ben.c.schubert@gmail.com> | 2019-02-05 15:45:37 +0000 |
commit | 0e47114402511680420156c066f6861d1b30a7f4 (patch) | |
tree | 39cd32e743e8809d109ab1f6f1cc74951a86eaeb | |
parent | a46650d0ebbe255cbd635a67d5c359dae429e2f2 (diff) | |
parent | 7682ef4910c5e5615da4565becc4d06bcb38b80e (diff) | |
download | buildstream-0e47114402511680420156c066f6861d1b30a7f4.tar.gz |
Merge branch 'danielsilverstone-ct/roaring-bitmaps' into 'master'
Switch to roaring bitmaps for the loader dependency caches
See merge request BuildStream/buildstream!1128
-rw-r--r-- | buildstream/_loader/loadelement.py | 15 | ||||
-rw-r--r-- | requirements/requirements.in | 3 | ||||
-rw-r--r-- | requirements/requirements.txt | 3 |
3 files changed, 18 insertions, 3 deletions
diff --git a/buildstream/_loader/loadelement.py b/buildstream/_loader/loadelement.py index 7dd4237fa..465d97f2c 100644 --- a/buildstream/_loader/loadelement.py +++ b/buildstream/_loader/loadelement.py @@ -19,6 +19,9 @@ # System imports from collections.abc import Mapping +from itertools import count + +from roaringbitmap import RoaringBitmap, ImmutableRoaringBitmap # pylint: disable=no-name-in-module # BuildStream toplevel imports from .._exceptions import LoadError, LoadErrorReason @@ -54,6 +57,8 @@ class LoadElement(): self.element = element self.dep_type = dep_type + _counter = count() + def __init__(self, node, filename, loader): # @@ -63,6 +68,7 @@ class LoadElement(): 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) # # Private members @@ -107,7 +113,7 @@ class LoadElement(): # def depends(self, other): self._ensure_depends_cache() - return self._dep_cache.get(other.full_name) is not None + return other.node_id in self._dep_cache ########################################### # Private Methods # @@ -117,7 +123,8 @@ class LoadElement(): if self._dep_cache: return - self._dep_cache = {} + self._dep_cache = RoaringBitmap() + for dep in self.dependencies: elt = dep.element @@ -125,11 +132,13 @@ class LoadElement(): elt._ensure_depends_cache() # We depend on this element - self._dep_cache[elt.full_name] = True + self._dep_cache.add(elt.node_id) # And we depend on everything this element depends on self._dep_cache.update(elt._dep_cache) + self._dep_cache = ImmutableRoaringBitmap(self._dep_cache) + # _extract_depends_from_node(): # diff --git a/requirements/requirements.in b/requirements/requirements.in index 18ebb5fdc..9e55084dc 100644 --- a/requirements/requirements.in +++ b/requirements/requirements.in @@ -13,3 +13,6 @@ psutil # See issues #571 and #790. ruamel.yaml >= 0.15.41, < 0.15.52 setuptools +# (Potentially) short-term need for roaring bitmaps for the +# loader dependency sorting +roaringbitmap diff --git a/requirements/requirements.txt b/requirements/requirements.txt index 7bf3205f7..fa21c48b7 100644 --- a/requirements/requirements.txt +++ b/requirements/requirements.txt @@ -13,6 +13,9 @@ psutil==5.4.8 # See issues #571 and #790. ruamel.yaml==0.15.51 setuptools==39.0.1 +# (Potentially) short-term need for roaring bitmaps for the +# loader dependency sorting +roaringbitmap==0.6 ## The following requirements were added by pip freeze: MarkupSafe==1.1.0 six==1.12.0 |