summaryrefslogtreecommitdiffstats
path: root/bitbake/lib/bb/runqueue.py
diff options
context:
space:
mode:
authorRichard Purdie <richard.purdie@linuxfoundation.org>2013-11-25 23:12:27 +0000
committerRichard Purdie <richard.purdie@linuxfoundation.org>2013-11-26 23:01:33 +0000
commit4c69970bd379f441279fe46edd92613e80ea3dc5 (patch)
tree9bdc859bae95c32bff537946de8d742d167c9223 /bitbake/lib/bb/runqueue.py
parent3ca58c762f09047c3798ef982b4c6fcd395a5809 (diff)
downloadpoky-4c69970bd379f441279fe46edd92613e80ea3dc5.tar.gz
bitbake: runqueue: Optimise next_buildable_task()
This unlikely looking function was found to be eating a lot of CPU time since it gets called once per trip through the idle loop if we're not running a maximum number of processes. This was particularly true in world builds of 13,000 tasks. Calling the computation code is pretty pointless because until some other task finishes nothing is going to become available to build. We can know when things become available so this patch teaches the scheduler this knowledge. It also: * skips any coputation when nothing can be built * if there is only one available item to build, ignore the priority map * precomputes the stamp filenames, rather than doing it every time * saves the length of the array rather than calculating it each time (the extra function overhead is significant) Timing wise, initially, 5000 iterations through here was 20s, with the patch 200000 calls takes the same time. The end result is that builds get up and running faster. (Bitbake rev: 4841c1d37c503a366f99e3a134dca7440e3a08ea) Signed-off-by: Richard Purdie <richard.purdie@linuxfoundation.org>
Diffstat (limited to 'bitbake/lib/bb/runqueue.py')
-rw-r--r--bitbake/lib/bb/runqueue.py65
1 files changed, 48 insertions, 17 deletions
diff --git a/bitbake/lib/bb/runqueue.py b/bitbake/lib/bb/runqueue.py
index a320a649e9..f984119e87 100644
--- a/bitbake/lib/bb/runqueue.py
+++ b/bitbake/lib/bb/runqueue.py
@@ -98,26 +98,49 @@ class RunQueueScheduler(object):
98 """ 98 """
99 self.rq = runqueue 99 self.rq = runqueue
100 self.rqdata = rqdata 100 self.rqdata = rqdata
101 numTasks = len(self.rqdata.runq_fnid) 101 self.numTasks = len(self.rqdata.runq_fnid)
102 102
103 self.prio_map = [] 103 self.prio_map = []
104 self.prio_map.extend(range(numTasks)) 104 self.prio_map.extend(range(self.numTasks))
105
106 self.buildable = []
107 self.stamps = {}
108 for taskid in xrange(self.numTasks):
109 fn = self.rqdata.taskData.fn_index[self.rqdata.runq_fnid[taskid]]
110 taskname = self.rqdata.runq_task[taskid]
111 self.stamps[taskid] = bb.build.stampfile(taskname, self.rqdata.dataCache, fn)
112 if self.rq.runq_buildable[taskid] == 1:
113 self.buildable.append(taskid)
114
115 self.rev_prio_map = None
105 116
106 def next_buildable_task(self): 117 def next_buildable_task(self):
107 """ 118 """
108 Return the id of the first task we find that is buildable 119 Return the id of the first task we find that is buildable
109 """ 120 """
110 for tasknum in xrange(len(self.rqdata.runq_fnid)): 121 self.buildable = [x for x in self.buildable if not self.rq.runq_running[x] == 1]
111 taskid = self.prio_map[tasknum] 122 if not self.buildable:
112 if self.rq.runq_running[taskid] == 1: 123 return None
113 continue 124 if len(self.buildable) == 1:
114 if self.rq.runq_buildable[taskid] == 1: 125 return self.buildable[0]
115 fn = self.rqdata.taskData.fn_index[self.rqdata.runq_fnid[taskid]] 126
116 taskname = self.rqdata.runq_task[taskid] 127 if not self.rev_prio_map:
117 stamp = bb.build.stampfile(taskname, self.rqdata.dataCache, fn) 128 self.rev_prio_map = range(self.numTasks)
118 if stamp in self.rq.build_stamps.values(): 129 for taskid in xrange(self.numTasks):
130 self.rev_prio_map[self.prio_map[taskid]] = taskid
131
132 best = None
133 bestprio = None
134 for taskid in self.buildable:
135 prio = self.rev_prio_map[taskid]
136 if not bestprio or bestprio > prio:
137 stamp = self.stamps[taskid]
138 if stamp in self.rq.build_stamps.itervalues():
119 continue 139 continue
120 return taskid 140 bestprio = prio
141 best = taskid
142
143 return best
121 144
122 def next(self): 145 def next(self):
123 """ 146 """
@@ -126,6 +149,9 @@ class RunQueueScheduler(object):
126 if self.rq.stats.active < self.rq.number_tasks: 149 if self.rq.stats.active < self.rq.number_tasks:
127 return self.next_buildable_task() 150 return self.next_buildable_task()
128 151
152 def newbuilable(self, task):
153 self.buildable.append(task)
154
129class RunQueueSchedulerSpeed(RunQueueScheduler): 155class RunQueueSchedulerSpeed(RunQueueScheduler):
130 """ 156 """
131 A scheduler optimised for speed. The priority map is sorted by task weight, 157 A scheduler optimised for speed. The priority map is sorted by task weight,
@@ -137,9 +163,7 @@ class RunQueueSchedulerSpeed(RunQueueScheduler):
137 """ 163 """
138 The priority map is sorted by task weight. 164 The priority map is sorted by task weight.
139 """ 165 """
140 166 RunQueueScheduler.__init__(self, runqueue, rqdata)
141 self.rq = runqueue
142 self.rqdata = rqdata
143 167
144 sortweight = sorted(copy.deepcopy(self.rqdata.runq_weight)) 168 sortweight = sorted(copy.deepcopy(self.rqdata.runq_weight))
145 copyweight = copy.deepcopy(self.rqdata.runq_weight) 169 copyweight = copy.deepcopy(self.rqdata.runq_weight)
@@ -1116,6 +1140,7 @@ class RunQueueExecute:
1116 self.runq_complete = [] 1140 self.runq_complete = []
1117 1141
1118 self.build_stamps = {} 1142 self.build_stamps = {}
1143 self.build_stamps2 = []
1119 self.failed_fnids = [] 1144 self.failed_fnids = []
1120 1145
1121 self.stampcache = {} 1146 self.stampcache = {}
@@ -1128,6 +1153,7 @@ class RunQueueExecute:
1128 1153
1129 # self.build_stamps[pid] may not exist when use shared work directory. 1154 # self.build_stamps[pid] may not exist when use shared work directory.
1130 if task in self.build_stamps: 1155 if task in self.build_stamps:
1156 self.build_stamps2.remove(self.build_stamps[task])
1131 del self.build_stamps[task] 1157 del self.build_stamps[task]
1132 1158
1133 if status != 0: 1159 if status != 0:
@@ -1317,6 +1343,10 @@ class RunQueueExecuteTasks(RunQueueExecute):
1317 schedulers.add(getattr(module, name)) 1343 schedulers.add(getattr(module, name))
1318 return schedulers 1344 return schedulers
1319 1345
1346 def setbuildable(self, task):
1347 self.runq_buildable[task] = 1
1348 self.sched.newbuilable(task)
1349
1320 def task_completeoutright(self, task): 1350 def task_completeoutright(self, task):
1321 """ 1351 """
1322 Mark a task as completed 1352 Mark a task as completed
@@ -1334,7 +1364,7 @@ class RunQueueExecuteTasks(RunQueueExecute):
1334 if self.runq_complete[dep] != 1: 1364 if self.runq_complete[dep] != 1:
1335 alldeps = 0 1365 alldeps = 0
1336 if alldeps == 1: 1366 if alldeps == 1:
1337 self.runq_buildable[revdep] = 1 1367 self.setbuildable(revdep)
1338 fn = self.rqdata.taskData.fn_index[self.rqdata.runq_fnid[revdep]] 1368 fn = self.rqdata.taskData.fn_index[self.rqdata.runq_fnid[revdep]]
1339 taskname = self.rqdata.runq_task[revdep] 1369 taskname = self.rqdata.runq_task[revdep]
1340 logger.debug(1, "Marking task %s (%s, %s) as buildable", revdep, fn, taskname) 1370 logger.debug(1, "Marking task %s (%s, %s) as buildable", revdep, fn, taskname)
@@ -1358,7 +1388,7 @@ class RunQueueExecuteTasks(RunQueueExecute):
1358 1388
1359 def task_skip(self, task, reason): 1389 def task_skip(self, task, reason):
1360 self.runq_running[task] = 1 1390 self.runq_running[task] = 1
1361 self.runq_buildable[task] = 1 1391 self.setbuildable(task)
1362 bb.event.fire(runQueueTaskSkipped(task, self.stats, self.rq, reason), self.cfgData) 1392 bb.event.fire(runQueueTaskSkipped(task, self.stats, self.rq, reason), self.cfgData)
1363 self.task_completeoutright(task) 1393 self.task_completeoutright(task)
1364 self.stats.taskCompleted() 1394 self.stats.taskCompleted()
@@ -1418,6 +1448,7 @@ class RunQueueExecuteTasks(RunQueueExecute):
1418 self.rq.worker.stdin.flush() 1448 self.rq.worker.stdin.flush()
1419 1449
1420 self.build_stamps[task] = bb.build.stampfile(taskname, self.rqdata.dataCache, fn) 1450 self.build_stamps[task] = bb.build.stampfile(taskname, self.rqdata.dataCache, fn)
1451 self.build_stamps2.append(self.build_stamps[task])
1421 self.runq_running[task] = 1 1452 self.runq_running[task] = 1
1422 self.stats.taskActive() 1453 self.stats.taskActive()
1423 if self.stats.active < self.number_tasks: 1454 if self.stats.active < self.number_tasks: