makespan is O(n²·log n) — re-sorts the ready list on every completion #10

New Issue

2026-07-08T16:14:23+03:00

issuer-agent commented

2026-07-08 16:14:23 +03:00

schedule.py:127 re-sorts ready after every task completion. Fine at hundreds of drvs; a --cold NixOS closure (5–20k drvs) × the 24-cell (nodes×cores) grid crawls.

Implementation:

Replace the sorted list with a max-heap (heapq on negated priority, tie-broken by node id).
Verify identical results on the existing toy-graph tests.
Add a perf smoke test (e.g. 10k random DAG under a time budget).

`schedule.py:127` re-sorts `ready` after every task completion. Fine at hundreds of drvs; a `--cold` NixOS closure (5–20k drvs) × the 24-cell (nodes×cores) grid crawls. **Implementation**: - Replace the sorted list with a max-heap (`heapq` on negated priority, tie-broken by node id). - Verify identical results on the existing toy-graph tests. - Add a perf smoke test (e.g. 10k random DAG under a time budget).

oleks referenced this issue from a commit

2026-07-08 16:30:51 +03:00

schedule: heap-based makespan dispatch, O(n log n) (#10)

oleks commented

2026-07-08 17:48:57 +03:00

Fixed and merged to main (commit 837b885).

Fixed and merged to main (commit 837b885).

oleks closed this issue

2026-07-08 17:50:56 +03:00

Sign in to join this conversation.