Weak task order constraints

Tasks that are known to take a lot of time may be launched first to improve the build times. The general problem of finding an optimal order for launching tasks in parallel and with constraints is called Job Shop. In practice this problem can often be reduced to a critical path problem (approximation).

The following pictures illustrate the difference in scheduling a build with different independent tasks, in which a slow task is clearly identified, and launched first:

Waf provides a function for reordering the tasks before they are launched in the module Runner, the default reordering may be changed by dynamic method replacement in Python:

import Runner
def get_next(self):
	# reorder the task list by a random function
	self.outstanding.sort()
	# return the next task
	return self.outstanding.pop()
Runner.Parallel.get_next = get_next
			

If the reordering is not to be performed each time a task is retrieved, the list of task may be reordered when the next group is retrieved:

import Runner
old_refill = Runner.Parallel.refill_task_list
def refill_task_list(self):
	old_refill(self)
	self.outstanding.sort()
Runner.Parallel.refill_task_list = refill_task_list
			

It is possible to measure the task execution times by intercepting the function calls. The task execution times may be re-used for optimizing the schedule for subsequent builds:

import time
import Task
old_call_run = Task.TaskBase.call_run
def new_call_run(self):
	t1 = time.time()
	ret = old_call_run(self)
	t2 = time.time()
	if not ret: print "execution time %r" % (t2 - t1)
	return ret
Task.TaskBase.call_run = new_call_run