diff mbox series

runqueue: Avoid building task set unions in next_buildable_task

Message ID 20261022225148.2195453-1-ricardo.salveti@oss.qualcomm.com
State New
Headers show
Series runqueue: Avoid building task set unions in next_buildable_task | expand

Commit Message

Ricardo Salveti Oct. 22, 2026, 10:51 p.m. UTC 
next_buildable_task() runs at least once for every task in the build,
and again on every worker wakeup while a slot is free. Each call copies
the buildable set, removes holdoff_tasks from it and intersects it with
tasks_covered | tasks_notcovered, and when a task is buildable it also
computes runq_running - runq_complete. Those sets grow to the size of
the whole runqueue, so every call costs time proportional to the build,
although only a small fraction of the tasks are buildable at any time.

Filter the buildable tasks by membership instead, and keep
runq_running - runq_complete as a set which is updated when tasks start
and complete. Tasks are never removed from runq_running or
runq_complete, so the new set always equals the difference and, as
before, includes failed tasks. Also use it for the thread count in the
pressure and load average messages. Every task has its own priority, so
the chosen task does not depend on set iteration order.

A no-op 'bitbake core-image-minimal' with OE-core goes from 7.66s to
6.64s, and a no-op build of an image with 18 layers from 46.54s to
41.59s (median of 5 runs each). Task signatures and the runqueue task
order of dry runs and of a single-threaded build from sstate are
unchanged.

AI-Generated: Uses Claude Code (Claude Opus 5.5)
Signed-off-by: Ricardo Salveti <ricardo.salveti@oss.qualcomm.com>
---
 lib/bb/runqueue.py | 27 ++++++++++++++++++---------
 1 file changed, 18 insertions(+), 9 deletions(-)

Comments

Richard Purdie Oct. 22, 2026, 11:10 p.m. UTC | #1 
On Thu, 2026-10-22 at 19:51 -0300, Ricardo Salveti via lists.openembedded.org wrote:
> next_buildable_task() runs at least once for every task in the build,
> and again on every worker wakeup while a slot is free. Each call copies
> the buildable set, removes holdoff_tasks from it and intersects it with
> tasks_covered | tasks_notcovered, and when a task is buildable it also
> computes runq_running - runq_complete. Those sets grow to the size of
> the whole runqueue, so every call costs time proportional to the build,
> although only a small fraction of the tasks are buildable at any time.
> 
> Filter the buildable tasks by membership instead, and keep
> runq_running - runq_complete as a set which is updated when tasks start
> and complete. Tasks are never removed from runq_running or
> runq_complete, so the new set always equals the difference and, as
> before, includes failed tasks. Also use it for the thread count in the
> pressure and load average messages. Every task has its own priority, so
> the chosen task does not depend on set iteration order.
> 
> A no-op 'bitbake core-image-minimal' with OE-core goes from 7.66s to
> 6.64s, and a no-op build of an image with 18 layers from 46.54s to
> 41.59s (median of 5 runs each). Task signatures and the runqueue task
> order of dry runs and of a single-threaded build from sstate are
> unchanged.
> 
> AI-Generated: Uses Claude Code (Claude Opus 5.5)
> Signed-off-by: Ricardo Salveti <ricardo.salveti@oss.qualcomm.com>
> ---
>  lib/bb/runqueue.py | 27 ++++++++++++++++++---------
>  1 file changed, 18 insertions(+), 9 deletions(-)

I'm torn. That speed up is relatively small compared to times of
overall builds and it comes at the cost of having two data structures
in parallel which need to be in sync with each other. We're tried to
avoid having duplicate data where possible due to the risks that
entails...

Is that gain really worth it?

Cheers,

Richard
diff mbox series

Patch

diff --git a/lib/bb/runqueue.py b/lib/bb/runqueue.py
index ef95eb46b..522288d63 100644
--- a/lib/bb/runqueue.py
+++ b/lib/bb/runqueue.py
@@ -237,7 +237,7 @@  class RunQueueScheduler(object):
             pressure_state = (exceeds_cpu_pressure, exceeds_io_pressure, exceeds_memory_pressure)
             pressure_values = (round(cpu_pressure,1), self.rq.max_cpu_pressure, round(io_pressure,1), self.rq.max_io_pressure, round(memory_pressure,1), self.rq.max_memory_pressure)
             if self.pressure_state is not None and pressure_state != self.pressure_state:
-                psi_logger.verbose("Pressure status changed to CPU: %s, IO: %s, Mem: %s (CPU: %s/%s, IO: %s/%s, Mem: %s/%s) - using %s/%s bitbake threads" % (pressure_state + pressure_values + (len(self.rq.runq_running.difference(self.rq.runq_complete)), self.rq.number_tasks)))
+                psi_logger.verbose("Pressure status changed to CPU: %s, IO: %s, Mem: %s (CPU: %s/%s, IO: %s/%s, Mem: %s/%s) - using %s/%s bitbake threads" % (pressure_state + pressure_values + (len(self.rq.runq_running_not_complete), self.rq.number_tasks)))
                 bb.event.fire(PSIEvent(pressure_state, pressure_values), self.rq.cfgData)
             self.pressure_state = pressure_state
             return (exceeds_cpu_pressure or exceeds_io_pressure or exceeds_memory_pressure)
@@ -248,7 +248,7 @@  class RunQueueScheduler(object):
             if loadfactor > self.rq.max_loadfactor:
                 limit = True
             if self.loadfactor_limit is not None and limit != self.loadfactor_limit:
-                bb.note("Load average limiting set to %s as load average: %s - using %s/%s bitbake threads" % (limit, loadfactor, len(self.rq.runq_running.difference(self.rq.runq_complete)), self.rq.number_tasks))
+                bb.note("Load average limiting set to %s as load average: %s - using %s/%s bitbake threads" % (limit, loadfactor, len(self.rq.runq_running_not_complete), self.rq.number_tasks))
             self.loadfactor_limit = limit
             return limit
         return False
@@ -259,9 +259,11 @@  class RunQueueScheduler(object):
         """
         # Once tasks are running we don't need to worry about them again
         self.buildable.difference_update(self.rq.runq_running)
-        buildable = set(self.buildable)
-        buildable.difference_update(self.rq.holdoff_tasks)
-        buildable.intersection_update(self.rq.tasks_covered | self.rq.tasks_notcovered)
+        holdoff = self.rq.holdoff_tasks
+        covered = self.rq.tasks_covered
+        notcovered = self.rq.tasks_notcovered
+        buildable = {t for t in self.buildable
+                     if t not in holdoff and (t in covered or t in notcovered)}
         if not buildable:
             return None
 
@@ -273,7 +275,7 @@  class RunQueueScheduler(object):
 
         # Filter out tasks that have a max number of threads that have been exceeded
         skip_buildable = {}
-        for running in self.rq.runq_running.difference(self.rq.runq_complete):
+        for running in self.rq.runq_running_not_complete:
             rtaskname = taskname_from_tid(running)
             if rtaskname not in self.skip_maxthread:
                 self.skip_maxthread[rtaskname] = self.rq.cfgData.getVarFlag(rtaskname, "number_threads")
@@ -1883,6 +1885,8 @@  class RunQueueExecute:
         self.runq_buildable = set()
         self.runq_running = set()
         self.runq_complete = set()
+        # runq_running - runq_complete, kept up to date for the scheduler
+        self.runq_running_not_complete = set()
         self.runq_tasksrun = set()
 
         self.build_stamps = {}
@@ -2082,6 +2086,10 @@  class RunQueueExecute:
         self.runq_buildable.add(task)
         self.sched.newbuildable(task)
 
+    def runq_running_add(self, task):
+        self.runq_running.add(task)
+        self.runq_running_not_complete.add(task)
+
     def task_completeoutright(self, task):
         """
         Mark a task as completed
@@ -2089,6 +2097,7 @@  class RunQueueExecute:
         completed dependencies as buildable
         """
         self.runq_complete.add(task)
+        self.runq_running_not_complete.discard(task)
         for revdep in self.rqdata.runtaskentries[task].revdeps:
             if revdep in self.runq_running:
                 continue
@@ -2152,7 +2161,7 @@  class RunQueueExecute:
             self.rq.state = RunQueueState.CLEAN_UP
 
     def task_skip(self, task, reason):
-        self.runq_running.add(task)
+        self.runq_running_add(task)
         self.setbuildable(task)
         bb.event.fire(runQueueTaskSkipped(task, self.stats, self.rq, reason), self.cfgData)
         self.task_completeoutright(task)
@@ -2381,7 +2390,7 @@  class RunQueueExecute:
                 startevent = runQueueTaskStarted(task, self.stats, self.rq,
                                                  noexec=True)
                 bb.event.fire(startevent, self.cfgData)
-                self.runq_running.add(task)
+                self.runq_running_add(task)
                 self.stats.taskActive()
                 if not (self.cooker.configuration.dry_run or self.rqdata.setscene_enforce):
                     bb.build.make_stamp_mcfn(taskname, taskfn)
@@ -2426,7 +2435,7 @@  class RunQueueExecute:
                 self.rq.worker[mc].process.stdin.flush()
 
             self.build_stamps[task] = bb.parse.siggen.stampfile_mcfn(taskname, taskfn, extrainfo=False)
-            self.runq_running.add(task)
+            self.runq_running_add(task)
             self.stats.taskActive()
             if self.can_start_task():
                 return True