{"algorithm":"tracker","about":["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."],"template":{"id":"spreadsheet","name":"Spreadsheet formulas","description":"A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each cell takes 1 to 4 milliseconds to work out. Each edge points from a cell to a formula that reads it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"B2","x":41,"y":195},{"id":"C2","x":41,"y":561},{"id":"D2","x":41,"y":884},{"id":"G2","x":41,"y":714},{"id":"G3","x":41,"y":408},{"id":"G4","x":194,"y":195},{"id":"G5","x":347,"y":302},{"id":"B3","x":194,"y":348},{"id":"C3","x":194,"y":654},{"id":"D3","x":194,"y":960},{"id":"B4","x":194,"y":42},{"id":"C4","x":194,"y":501},{"id":"D4","x":194,"y":807},{"id":"B5","x":347,"y":149},{"id":"C5","x":347,"y":455},{"id":"D5","x":347,"y":608},{"id":"B6","x":500,"y":218},{"id":"C6","x":500,"y":371},{"id":"D6","x":500,"y":524},{"id":"B7","x":653,"y":242},{"id":"C7","x":653,"y":395},{"id":"D7","x":653,"y":548},{"id":"E3","x":347,"y":761},{"id":"E7","x":806,"y":418},{"id":"E8","x":959,"y":487}],"edges":[{"from":"B2","to":"B3"},{"from":"G2","to":"B3"},{"from":"C2","to":"C3"},{"from":"G2","to":"C3"},{"from":"D2","to":"D3"},{"from":"G2","to":"D3"},{"from":"B2","to":"B4"},{"from":"G3","to":"B4"},{"from":"C2","to":"C4"},{"from":"G3","to":"C4"},{"from":"D2","to":"D4"},{"from":"G3","to":"D4"},{"from":"B3","to":"B5"},{"from":"B4","to":"B5"},{"from":"G4","to":"B5"},{"from":"C3","to":"C5"},{"from":"C4","to":"C5"},{"from":"G4","to":"C5"},{"from":"D3","to":"D5"},{"from":"D4","to":"D5"},{"from":"G4","to":"D5"},{"from":"B5","to":"B6"},{"from":"G5","to":"B6"},{"from":"C5","to":"C6"},{"from":"G5","to":"C6"},{"from":"D5","to":"D6"},{"from":"G5","to":"D6"},{"from":"B5","to":"B7"},{"from":"B6","to":"B7"},{"from":"C5","to":"C7"},{"from":"C6","to":"C7"},{"from":"D5","to":"D7"},{"from":"D6","to":"D7"},{"from":"B3","to":"E3"},{"from":"C3","to":"E3"},{"from":"D3","to":"E3"},{"from":"B7","to":"E7"},{"from":"C7","to":"E7"},{"from":"D7","to":"E7"},{"from":"E7","to":"E8"},{"from":"E3","to":"E8"}],"durations":{"B2":1,"B3":2,"B4":2,"B5":1,"B6":3,"B7":1,"C2":1,"C3":2,"C4":2,"C5":1,"C6":3,"C7":1,"D2":1,"D3":2,"D4":2,"D5":1,"D6":3,"D7":1,"E3":4,"E7":4,"E8":1,"G2":1,"G3":1,"G4":1,"G5":1},"durationUnit":"milliseconds","details":{"vertices":25,"edges":41,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.06833333333333333,"inDegree":{"min":0,"avg":1.64,"max":3},"outDegree":{"min":0,"avg":1.64,"max":3},"selfLoops":0,"components":1}},"problem":"With two threads recomputing the sheet, each cell as soon as the cells it reads are up to date, how many milliseconds does a full recompute take?","params":{"workers":2},"result":{"kind":"order","vertices":["B2","C2","D2","G2","G3","G4","G5","B3","C3","D3","B4","C4","D4","E3","B5","C5","D5","B6","C6","D6","B7","C7","D7","E7","E8"]},"answer":"With 2 workers, the last of the 25 tasks finishes at time 25. Running the levels one after another on the same workers takes 28, since each level waits for its slowest task. One task at a time would take 43.","legend":{"vertex":[{"id":"idle","label":"Waiting on a task it depends on","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"Ready, waiting for a worker","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Running","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Done","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Its start is done","color":"#009E73","shape":"thick"}],"panels":[{"id":"ends","title":"Ends at","kind":"table"},{"id":"running","title":"Running","kind":"list"},{"id":"ready","title":"Ready, first in first out","kind":"list"},{"id":"order","title":"Start order","kind":"list"}]},"steps":[{"say":"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 7 tasks that depend on nothing: B2, C2, D2, G2, G3, G4 and G5.","ops":[{"v":"B2","state":"waiting"},{"v":"C2","state":"waiting"},{"v":"D2","state":"waiting"},{"v":"G2","state":"waiting"},{"v":"G3","state":"waiting"},{"v":"G4","state":"waiting"},{"v":"G5","state":"waiting"},{"panel":"ready","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"At time 0, B2 and C2 start, to end at 1 and 1. Every worker is busy, so 5 ready tasks wait for one to come free.","ops":[{"v":"B2","state":"current"},{"panel":"ends","set":{"B2":"1"}},{"v":"C2","state":"current"},{"panel":"ends","set":{"C2":"1"}},{"panel":"running","list":[{"key":"B2","note":"until 1"},{"key":"C2","note":"until 1"}]},{"panel":"ready","list":[{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"}]}]},{"say":"At time 1, B2 and C2 finish. Done makes no new task ready. D2 and G2 start, to end at 2 and 2. Every worker is busy, so 3 ready tasks wait for one to come free.","ops":[{"v":"B2","state":"done"},{"e":["B2","B3"],"state":"tree"},{"e":["B2","B4"],"state":"tree"},{"v":"C2","state":"done"},{"e":["C2","C3"],"state":"tree"},{"e":["C2","C4"],"state":"tree"},{"v":"D2","state":"current"},{"panel":"ends","set":{"D2":"2"}},{"v":"G2","state":"current"},{"panel":"ends","set":{"G2":"2"}},{"panel":"running","list":[{"key":"D2","note":"until 2"},{"key":"G2","note":"until 2"}]},{"panel":"ready","list":[{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"}]}]},{"say":"At time 2, D2 and G2 finish. Done makes B3, C3 and D3 ready. G3 and G4 start, to end at 3 and 3. Every worker is busy, so 4 ready tasks wait for one to come free.","ops":[{"v":"D2","state":"done"},{"e":["D2","D3"],"state":"tree"},{"e":["D2","D4"],"state":"tree"},{"v":"G2","state":"done"},{"e":["G2","B3"],"state":"tree"},{"e":["G2","C3"],"state":"tree"},{"e":["G2","D3"],"state":"tree"},{"v":"B3","state":"waiting"},{"v":"C3","state":"waiting"},{"v":"D3","state":"waiting"},{"v":"G3","state":"current"},{"panel":"ends","set":{"G3":"3"}},{"v":"G4","state":"current"},{"panel":"ends","set":{"G4":"3"}},{"panel":"running","list":[{"key":"G3","note":"until 3"},{"key":"G4","note":"until 3"}]},{"panel":"ready","list":[{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"}]}]},{"say":"At time 3, G3 and G4 finish. Done makes B4, C4 and D4 ready. G5 and B3 start, to end at 4 and 5. Every worker is busy, so 5 ready tasks wait for one to come free.","ops":[{"v":"G3","state":"done"},{"e":["G3","B4"],"state":"tree"},{"e":["G3","C4"],"state":"tree"},{"e":["G3","D4"],"state":"tree"},{"v":"G4","state":"done"},{"e":["G4","B5"],"state":"tree"},{"e":["G4","C5"],"state":"tree"},{"e":["G4","D5"],"state":"tree"},{"v":"B4","state":"waiting"},{"v":"C4","state":"waiting"},{"v":"D4","state":"waiting"},{"v":"G5","state":"current"},{"panel":"ends","set":{"G5":"4"}},{"v":"B3","state":"current"},{"panel":"ends","set":{"B3":"5"}},{"panel":"running","list":[{"key":"G5","note":"until 4"},{"key":"B3","note":"until 5"}]},{"panel":"ready","list":[{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"}]}]},{"say":"At time 4, G5 finishes. Done makes no new task ready. C3 starts and takes 2, so it ends at 6. Every worker is busy, so 4 ready tasks wait for one to come free.","ops":[{"v":"G5","state":"done"},{"e":["G5","B6"],"state":"tree"},{"e":["G5","C6"],"state":"tree"},{"e":["G5","D6"],"state":"tree"},{"v":"C3","state":"current"},{"panel":"ends","set":{"C3":"6"}},{"panel":"running","list":[{"key":"B3","note":"until 5"},{"key":"C3","note":"until 6"}]},{"panel":"ready","list":[{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"}]}]},{"say":"At time 5, B3 finishes. Done makes no new task ready. D3 starts and takes 2, so it ends at 7. Every worker is busy, so 3 ready tasks wait for one to come free.","ops":[{"v":"B3","state":"done"},{"e":["B3","B5"],"state":"tree"},{"e":["B3","E3"],"state":"tree"},{"v":"D3","state":"current"},{"panel":"ends","set":{"D3":"7"}},{"panel":"running","list":[{"key":"C3","note":"until 6"},{"key":"D3","note":"until 7"}]},{"panel":"ready","list":[{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"}]}]},{"say":"At time 6, C3 finishes. Done makes no new task ready. B4 starts and takes 2, so it ends at 8. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"C3","state":"done"},{"e":["C3","C5"],"state":"tree"},{"e":["C3","E3"],"state":"tree"},{"v":"B4","state":"current"},{"panel":"ends","set":{"B4":"8"}},{"panel":"running","list":[{"key":"D3","note":"until 7"},{"key":"B4","note":"until 8"}]},{"panel":"ready","list":[{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"}]}]},{"say":"At time 7, D3 finishes. Done makes E3 ready. C4 starts and takes 2, so it ends at 9. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"D3","state":"done"},{"e":["D3","D5"],"state":"tree"},{"e":["D3","E3"],"state":"tree"},{"v":"E3","state":"waiting"},{"v":"C4","state":"current"},{"panel":"ends","set":{"C4":"9"}},{"panel":"running","list":[{"key":"B4","note":"until 8"},{"key":"C4","note":"until 9"}]},{"panel":"ready","list":[{"key":"D4"},{"key":"E3"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"}]}]},{"say":"At time 8, B4 finishes. Done makes B5 ready. D4 starts and takes 2, so it ends at 10. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"B4","state":"done"},{"e":["B4","B5"],"state":"tree"},{"v":"B5","state":"waiting"},{"v":"D4","state":"current"},{"panel":"ends","set":{"D4":"10"}},{"panel":"running","list":[{"key":"C4","note":"until 9"},{"key":"D4","note":"until 10"}]},{"panel":"ready","list":[{"key":"E3"},{"key":"B5"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"}]}]},{"say":"At time 9, C4 finishes. Done makes C5 ready. E3 starts and takes 4, so it ends at 13. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"C4","state":"done"},{"e":["C4","C5"],"state":"tree"},{"v":"C5","state":"waiting"},{"v":"E3","state":"current"},{"panel":"ends","set":{"E3":"13"}},{"panel":"running","list":[{"key":"D4","note":"until 10"},{"key":"E3","note":"until 13"}]},{"panel":"ready","list":[{"key":"B5"},{"key":"C5"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"}]}]},{"say":"At time 10, D4 finishes. Done makes D5 ready. B5 starts and takes 1, so it ends at 11. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"D4","state":"done"},{"e":["D4","D5"],"state":"tree"},{"v":"D5","state":"waiting"},{"v":"B5","state":"current"},{"panel":"ends","set":{"B5":"11"}},{"panel":"running","list":[{"key":"E3","note":"until 13"},{"key":"B5","note":"until 11"}]},{"panel":"ready","list":[{"key":"C5"},{"key":"D5"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"}]}]},{"say":"At time 11, B5 finishes. Done makes B6 ready. C5 starts and takes 1, so it ends at 12. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"B5","state":"done"},{"e":["B5","B6"],"state":"tree"},{"e":["B5","B7"],"state":"tree"},{"v":"B6","state":"waiting"},{"v":"C5","state":"current"},{"panel":"ends","set":{"C5":"12"}},{"panel":"running","list":[{"key":"E3","note":"until 13"},{"key":"C5","note":"until 12"}]},{"panel":"ready","list":[{"key":"D5"},{"key":"B6"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"}]}]},{"say":"At time 12, C5 finishes. Done makes C6 ready. D5 starts and takes 1, so it ends at 13. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"C5","state":"done"},{"e":["C5","C6"],"state":"tree"},{"e":["C5","C7"],"state":"tree"},{"v":"C6","state":"waiting"},{"v":"D5","state":"current"},{"panel":"ends","set":{"D5":"13"}},{"panel":"running","list":[{"key":"E3","note":"until 13"},{"key":"D5","note":"until 13"}]},{"panel":"ready","list":[{"key":"B6"},{"key":"C6"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"},{"key":"D5","note":"at 12"}]}]},{"say":"At time 13, E3 and D5 finish. Done makes D6 ready. B6 and C6 start, to end at 16 and 16. Every worker is busy, so 1 ready task waits for one to come free.","ops":[{"v":"E3","state":"done"},{"e":["E3","E8"],"state":"tree"},{"v":"D5","state":"done"},{"e":["D5","D6"],"state":"tree"},{"e":["D5","D7"],"state":"tree"},{"v":"D6","state":"waiting"},{"v":"B6","state":"current"},{"panel":"ends","set":{"B6":"16"}},{"v":"C6","state":"current"},{"panel":"ends","set":{"C6":"16"}},{"panel":"running","list":[{"key":"B6","note":"until 16"},{"key":"C6","note":"until 16"}]},{"panel":"ready","list":[{"key":"D6"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"},{"key":"D5","note":"at 12"},{"key":"B6","note":"at 13"},{"key":"C6","note":"at 13"}]}]},{"say":"At time 16, B6 and C6 finish. Done makes B7 and C7 ready. D6 and B7 start, to end at 19 and 17. Every worker is busy, so 1 ready task waits for one to come free.","ops":[{"v":"B6","state":"done"},{"e":["B6","B7"],"state":"tree"},{"v":"C6","state":"done"},{"e":["C6","C7"],"state":"tree"},{"v":"B7","state":"waiting"},{"v":"C7","state":"waiting"},{"v":"D6","state":"current"},{"panel":"ends","set":{"D6":"19"}},{"v":"B7","state":"current"},{"panel":"ends","set":{"B7":"17"}},{"panel":"running","list":[{"key":"D6","note":"until 19"},{"key":"B7","note":"until 17"}]},{"panel":"ready","list":[{"key":"C7"}]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"},{"key":"D5","note":"at 12"},{"key":"B6","note":"at 13"},{"key":"C6","note":"at 13"},{"key":"D6","note":"at 16"},{"key":"B7","note":"at 16"}]}]},{"say":"At time 17, B7 finishes. Done makes no new task ready. C7 starts and takes 1, so it ends at 18.","ops":[{"v":"B7","state":"done"},{"e":["B7","E7"],"state":"tree"},{"v":"C7","state":"current"},{"panel":"ends","set":{"C7":"18"}},{"panel":"running","list":[{"key":"D6","note":"until 19"},{"key":"C7","note":"until 18"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"},{"key":"D5","note":"at 12"},{"key":"B6","note":"at 13"},{"key":"C6","note":"at 13"},{"key":"D6","note":"at 16"},{"key":"B7","note":"at 16"},{"key":"C7","note":"at 17"}]}]},{"say":"At time 18, C7 finishes. Done makes no new task ready. One worker has nothing to do until another task is ready.","ops":[{"v":"C7","state":"done"},{"e":["C7","E7"],"state":"tree"},{"panel":"running","list":[{"key":"D6","note":"until 19"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"},{"key":"D5","note":"at 12"},{"key":"B6","note":"at 13"},{"key":"C6","note":"at 13"},{"key":"D6","note":"at 16"},{"key":"B7","note":"at 16"},{"key":"C7","note":"at 17"}]}]},{"say":"At time 19, D6 finishes. Done makes D7 ready. D7 starts and takes 1, so it ends at 20. One worker has nothing to do until another task is ready.","ops":[{"v":"D6","state":"done"},{"e":["D6","D7"],"state":"tree"},{"v":"D7","state":"waiting"},{"v":"D7","state":"current"},{"panel":"ends","set":{"D7":"20"}},{"panel":"running","list":[{"key":"D7","note":"until 20"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"},{"key":"D5","note":"at 12"},{"key":"B6","note":"at 13"},{"key":"C6","note":"at 13"},{"key":"D6","note":"at 16"},{"key":"B7","note":"at 16"},{"key":"C7","note":"at 17"},{"key":"D7","note":"at 19"}]}]},{"say":"At time 20, D7 finishes. Done makes E7 ready. E7 starts and takes 4, so it ends at 24. One worker has nothing to do until another task is ready.","ops":[{"v":"D7","state":"done"},{"e":["D7","E7"],"state":"tree"},{"v":"E7","state":"waiting"},{"v":"E7","state":"current"},{"panel":"ends","set":{"E7":"24"}},{"panel":"running","list":[{"key":"E7","note":"until 24"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"},{"key":"D5","note":"at 12"},{"key":"B6","note":"at 13"},{"key":"C6","note":"at 13"},{"key":"D6","note":"at 16"},{"key":"B7","note":"at 16"},{"key":"C7","note":"at 17"},{"key":"D7","note":"at 19"},{"key":"E7","note":"at 20"}]}]},{"say":"At time 24, E7 finishes. Done makes E8 ready. E8 starts and takes 1, so it ends at 25. One worker has nothing to do until another task is ready.","ops":[{"v":"E7","state":"done"},{"e":["E7","E8"],"state":"tree"},{"v":"E8","state":"waiting"},{"v":"E8","state":"current"},{"panel":"ends","set":{"E8":"25"}},{"panel":"running","list":[{"key":"E8","note":"until 25"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2","note":"at 0"},{"key":"C2","note":"at 0"},{"key":"D2","note":"at 1"},{"key":"G2","note":"at 1"},{"key":"G3","note":"at 2"},{"key":"G4","note":"at 2"},{"key":"G5","note":"at 3"},{"key":"B3","note":"at 3"},{"key":"C3","note":"at 4"},{"key":"D3","note":"at 5"},{"key":"B4","note":"at 6"},{"key":"C4","note":"at 7"},{"key":"D4","note":"at 8"},{"key":"E3","note":"at 9"},{"key":"B5","note":"at 10"},{"key":"C5","note":"at 11"},{"key":"D5","note":"at 12"},{"key":"B6","note":"at 13"},{"key":"C6","note":"at 13"},{"key":"D6","note":"at 16"},{"key":"B7","note":"at 16"},{"key":"C7","note":"at 17"},{"key":"D7","note":"at 19"},{"key":"E7","note":"at 20"},{"key":"E8","note":"at 24"}]}]},{"say":"Done. At time 25, E8 finishes, the last of the 25 tasks. Running the levels one after another on 2 workers would take 28, and one task at a time 43.","ops":[{"v":"E8","state":"done"},{"panel":"running","list":[]}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"t, err := dag.NewTracker(g)\nif err != nil {\n\treturn err\n}\nworkers := make(chan struct{}, 2)\nfinished := make(chan string, g.Order())\nfor t.Remaining() > 0 {\n\tfor _, task := range t.Ready() {\n\t\tgo func() {\n\t\t\tworkers <- struct{}{}\n\t\t\trun(task) // task.Weight() is how long it takes\n\t\t\t<-workers\n\t\t\tfinished <- task.Label()\n\t\t}()\n\t}\n\tif err := t.Done(<-finished); err != nil {\n\t\treturn err\n\t}\n}"}