Merge branch 'danielsilverstone-ct/roaring-bitmaps' into 'master'

Switch to roaring bitmaps for the loader dependency caches

See merge request BuildStream/buildstream!1128

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