Ready-set tracker

Hands out the tasks of a graph without cycles as soon as every task they depend on is done, so a slow task holds up only the tasks that wait for it.

Time complexity O(V+E), gograph function dag.NewTracker.

How it works

A Tracker runs a dependency graph the way a build system does. Ready returns the tasks that can start, and Done marks tasks as finished, which makes ready every task that was waiting only on them. An edge from A to B means B depends on A, so Ready returns B once A is done.

Levels split the same graph into rounds, and each round waits for its slowest task. The tracker starts a task the moment its own dependencies finish, so a long task in one round doesn't hold up the tasks of the next round that never waited for it.

The tracker leaves running the tasks to the caller, and with them how many run at once. This page uses two workers that take the ready tasks first in, first out, and each task takes its weight in time. NewTracker copies the graph in O(V+E), and all the Ready and Done calls of a run add up to O(V+E) too. It returns ErrDAGHasCycle for a graph with a cycle, and Done returns ErrNotReady for a task Ready hasn't returned.

Monorepo build

One hundred build targets, T1 to T100, in the repository of an online shop. T1 to T32 are shared libraries, T33 to T41 the code generator and API definitions, T42 to T58 services, T59 to T63 batch jobs, T64 to T71 the API client and UI packages, T72 to T76 apps, T77 to T95 container images, and T96 to T100 the deploys and the contract and end-to-end tests. A target takes 1 to 20 minutes to build. Each edge points from a target to a target that builds on it.

A directed graph with 100 vertices and 266 edges.

With two build machines, each target building as soon as the targets it builds on are done, how many minutes does the whole build take?

With 2 workers, the last of the 100 tasks finishes at time 184. Running the levels one after another on the same workers takes 194, since each level waits for its slowest task. One task at a time would take 337.

Step by step

The tracker hands out a task once every task it depends on is done, and 2 workers take the ready tasks in the order it returns them. Each task takes its weight in time, and the time it ends shows next to its name once it starts. The first call to Ready returns the 8 tasks that depend on nothing: T1, T2, T3, T33, T65, T66, T67 and T77.
At time 0, T1 and T2 start, to end at 2 and 2. Every worker is busy, so 6 ready tasks wait for one to come free.
At time 2, T1 and T2 finish. Done makes T4, T5, T10, T11, T14, T15, T16 and T8 ready. T3 and T33 start, to end at 4 and 5. Every worker is busy, so 12 ready tasks wait for one to come free.
At time 4, T3 finishes. Done makes no new task ready. T65 starts and takes 2, so it ends at 6. Every worker is busy, so 11 ready tasks wait for one to come free.
At time 5, T33 finishes. Done makes T34 ready. T66 starts and takes 2, so it ends at 7. Every worker is busy, so 11 ready tasks wait for one to come free.
At time 6, T65 finishes. Done makes T70 ready. T67 starts and takes 2, so it ends at 8. Every worker is busy, so 11 ready tasks wait for one to come free.

76 more steps lead to the last one:

Done. At time 184, T100 finishes, the last of the 100 tasks. Running the levels one after another on 2 workers would take 194, and one task at a time 337.

Use it in Go

t, err := dag.NewTracker(g)
if err != nil {
	return err
}
workers := make(chan struct{}, 2)
finished := make(chan string, g.Order())
for t.Remaining() > 0 {
	for _, task := range t.Ready() {
		go func() {
			workers <- struct{}{}
			run(task) // task.Weight() is how long it takes
			<-workers
			finished <- task.Label()
		}()
	}
	if err := t.Done(<-finished); err != nil {
		return err
	}
}

Example graphs

Build pipeline, 7 vertices and 9 edges
Course prerequisites, 14 vertices and 18 edges
Spreadsheet formulas, 25 vertices and 41 edges
Monorepo build, 100 vertices and 266 edges