Smarter scheduling using durations from previous runs

[ozgurakgun]

Motivation

It would be useful if nextest could optionally schedule tests in descending expected runtime order, using durations recorded from previous runs.

For test suites with a few long-running tests and many short tests, starting the longest tests first can reduce total makespan under parallel execution. This is the standard longest-processing-time-first heuristic: it helps avoid ending a run with one long test still occupying the final worker while all other workers are idle.

Proposal

nextest already records structured run data, including test outcomes and timings. A profile option or CLI flag could use historical durations from the latest comparable run to prioritise scheduling.

Add an optional scheduling mode that orders selected tests by expected duration, longest first. The expected duration could come from previous nextest run data.

For example, the interface could be a CLI flag or profile setting such as: cargo nextest run --schedule longest-first

[profile.default]
schedule = "longest-first"

Tests without historical timing data could fall back to the default ordering.

Alternatives

No response

Additional context

No response

[sunshowers]

Yes, this would be nice. There is a chunk of design work that needs to be done:

• Should there be an explicit analysis step? What should the inputs to that step be? (For example, you can imagine processing CI runs -- we may want to add a way to download runs from CI as a prerequisite.)
• Where should the results of the analysis be stored? Should they be checked into the repo?
• What order should we run tests in?
• One challenge with longest-processing-time first is that often you actually want to balance that with shortest-processing-time first -- for test runs, providing quick feedback on potentially-failing tests is quite important. End-to-end execution time matters in CI but has to be balanced with quick runs for local runs. So we may want to have different algorithms in each case.
• Something else that's worth considering is that running tests in lexicographic order with (binary-id, test name) is often quite nice when scanning results in CI. I wonder what we actually want to do is not longest-first but rather scheduling such that the predicted end time of each test lines up in order. That is a somewhat trickier algorithm to write that should actually deliver results very similar to slowest-first.

All of this is manageable and certainly worth doing -- realistically speaking though I don't quite have the time to work on this in the short or medium term. But I'd definitely encourage folks to do some prototyping and thinking about the space of possibilities here. (The first step would probably be to write a script which analyzes historical runs and spits out an estimated time taken for each test using some variant of a Kalman filter).