bitbake: runqueue: Rewrite and optimize recrdepends handling

This is a performance sensitive piece of code and the shear number
of recursive loops is causing a significant and unscalable performance
pain point.

This change moves to a two step approach, firstly generating a list of recursive
dependencies for any task, then applying this to the recursive tasks, iterating
over things until no further dependencies are added.

It was noticed an optimisation is possible and the list of recursive tasks need not
contain the taskname, only the base task id. This allows a significant performance
improvement and limits the size of the resursive task lists, improving speed.

(Bitbake rev: eba738ac5672556eaab4f3374c8025c322761c4a)

Signed-off-by: Richard Purdie <richard.purdie@linuxfoundation.org>

1 files changed, 83 insertions, 51 deletions

diff --git a/bitbake/lib/bb/runqueue.py b/bitbake/lib/bb/runqueue.py
index bbfe9eeee0..d7acfabef4 100644
--- a/bitbake/lib/bb/runqueue.py
+++ b/bitbake/lib/bb/runqueue.py
@@ -74,9 +74,6 @@ def build_tid(mc, fn, taskname):
         return "multiconfig:" + mc + ":" + fn + ":" + taskname
     return fn + ":" + taskname
 
-def tid_replacetask(tid, taskname):
-    return tid.rsplit(":", 1)[0] + ":" + taskname
-
 class RunQueueStats:
     """
     Holds statistics on the tasks handled by the associated runQueue
@@ -670,71 +667,106 @@ class RunQueueData:
                             recursiveitasks[tid].append(newdep)
 
                 self.runtaskentries[tid].depends = depends
+                # Remove all self references
+                self.runtaskentries[tid].depends.discard(tid)
 
         #self.dump_data()
 
+        self.init_progress_reporter.next_stage()
+
         # Resolve recursive 'recrdeptask' dependencies (Part B)
         #
         # e.g. do_sometask[recrdeptask] = "do_someothertask"
         # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
         # We need to do this separately since we need all of runtaskentries[*].depends to be complete before this is processed
-        self.init_progress_reporter.next_stage()
-        extradeps = True
+
+        # Generating/interating recursive lists of dependencies is painful and potentially slow
+        # Precompute recursive task dependencies here by:
+        #     a) create a temp list of reverse dependencies (revdeps)
+        #     b) walk up the ends of the chains (when a given task no longer has dependencies i.e. len(deps) == 0)
+        #     c) combine the total list of dependencies in cumulativedeps
+        #     d) optimise by pre-truncating 'task' off the items in cumulativedeps (keeps items in sets lower)
+
+
+        revdeps = {}
+        deps = {}
+        cumulativedeps = {}
+        for tid in self.runtaskentries:
+            deps[tid] = set(self.runtaskentries[tid].depends)
+            revdeps[tid] = set()
+            cumulativedeps[tid] = set()
+        # Generate a temp list of reverse dependencies
+        for tid in self.runtaskentries:
+            for dep in self.runtaskentries[tid].depends:
+                revdeps[dep].add(tid)
+        # Find the dependency chain endpoints
+        endpoints = set()
+        for tid in self.runtaskentries:
+            if len(deps[tid]) == 0:
+                endpoints.add(tid)
+        # Iterate the chains collating dependencies
+        while endpoints:
+            next = set()
+            for tid in endpoints:
+                for dep in revdeps[tid]:
+                    cumulativedeps[dep].add(fn_from_tid(tid))
+                    cumulativedeps[dep].update(cumulativedeps[tid])
+                    if tid in deps[dep]:
+                        deps[dep].remove(tid)
+                    if len(deps[dep]) == 0:
+                        next.add(dep)
+            endpoints = next
+        #for tid in deps:
+        #    if len(deps[tid]) != 0:
+        #        bb.warn("Sanity test failure, dependencies left for %s (%s)" % (tid, deps[tid]))
+
         # Loop here since recrdeptasks can depend upon other recrdeptasks and we have to
         # resolve these recursively until we aren't adding any further extra dependencies
+        extradeps = True
         while extradeps:
-            extradeps = {}
-
-            for taskcounter, tid in enumerate(recursivetasks):
-                extradeps[tid] = set()
-
+            extradeps = 0
+            for tid in recursivetasks:
                 tasknames = recursivetasks[tid]
-                seendeps = set()
-                seenbasedeps = set()
-
-                def generate_recdeps(t):
-                    newdeps = set()
-                    basetid = fn_from_tid(t)
-                    if basetid not in seenbasedeps:
-                        for taskname in tasknames:
-                            newtid = tid_replacetask(t, taskname)
-                            if newtid in self.runtaskentries and newtid not in seendeps:
-                                newdeps.add(newtid)
-                                extradeps[tid].add(newtid)
-                        seenbasedeps.add(basetid)
-                    seendeps.add(t)
-                    newdeps.add(t)
-                    for i in newdeps:
-                        if i not in self.runtaskentries:
-                            # Not all recipes might have the recrdeptask task as a task
-                            continue
-                        for n in self.runtaskentries[i].depends:
-                            if n not in seendeps:
-                                 generate_recdeps(n)
-                generate_recdeps(tid)
 
+                totaldeps = set(self.runtaskentries[tid].depends)
                 if tid in recursiveitasks:
+                    totaldeps.update(recursiveitasks[tid])
                     for dep in recursiveitasks[tid]:
-                        generate_recdeps(dep)
+                        if dep not in self.runtaskentries:
+                            continue
+                        totaldeps.update(self.runtaskentries[dep].depends)
 
-            for tid in self.runtaskentries:
-                # Add in extra dependencies
-                if tid in extradeps:
-                     extradeps[tid].difference_update(self.runtaskentries[tid].depends)
-                     self.runtaskentries[tid].depends.update(extradeps[tid])
-                     # Remove circular references so that do_a[recrdeptask] = "do_a do_b" can work
-                     self.runtaskentries[tid].depends.difference_update(recursivetasksselfref)
-                     extradeps[tid].difference_update(recursivetasksselfref)
-                     if not len(extradeps[tid]):
-                         del extradeps[tid]
-                     if tid not in recursivetasks:
-                        bb.warn(tid)
-                # Remove all self references
-                if tid in self.runtaskentries[tid].depends:
-                    logger.debug(2, "Task %s contains self reference!", tid)
-                    self.runtaskentries[tid].depends.remove(tid)
+                deps = set()
+                for dep in totaldeps:
+                    if dep in cumulativedeps:
+                        deps.update(cumulativedeps[dep])
+
+                for t in deps:
+                    for taskname in tasknames:
+                        newtid = t + ":" + taskname
+                        if newtid == tid:
+                            continue
+                        if newtid in self.runtaskentries and newtid not in self.runtaskentries[tid].depends:
+                            extradeps += 1
+                            self.runtaskentries[tid].depends.add(newtid)
 
-            bb.debug(1, "Added %s recursive dependencies in this loop" % len(extradeps))
+                # Handle recursive tasks which depend upon other recursive tasks
+                deps = set()
+                for dep in self.runtaskentries[tid].depends.intersection(recursivetasks):
+                    deps.update(self.runtaskentries[dep].depends.difference(self.runtaskentries[tid].depends))
+                for newtid in deps:
+                    for taskname in tasknames:
+                        if not newtid.endswith(":" + taskname):
+                            continue
+                        if newtid in self.runtaskentries:
+                            extradeps += 1
+                            self.runtaskentries[tid].depends.add(newtid)
+
+            bb.debug(1, "Added %s recursive dependencies in this loop" % extradeps)
+
+        # Remove recrdeptask circular references so that do_a[recrdeptask] = "do_a do_b" can work
+        for tid in self.runtaskentries:
+            self.runtaskentries[tid].depends.difference_update(recursivetasksselfref)
 
         self.init_progress_reporter.next_stage()