Performance History
No performance history available yetOnce you have some commits, you will be able to see the performance history of your primary branch. Latest Results
Store contradicted incompatibilities in a dense Vec instead of a hash map
`State::contradicted_incompatibilities` mapped an `IncompId` to the decision
level at which the incompatibility was last found contradicted, using an
`FxHashMap`. It is read in the hot `unit_propagation` loop, which iterates the
per-package incompatibility list and, for every entry, checks whether that
incompatibility is already contradicted before doing any further work. On
conflict-heavy resolutions that check runs an enormous number of times (260M+
times for `backtracking_singletons`), so it dominated by repeated hash lookups
and, on backtrack, by `HashMap::retain` over a growing table.
Incompatibility ids are dense `u32` arena indices, so this commit replaces the
hash map with a `Vec<u32>` indexed by the raw id, using `u32::MAX` as a
"not currently contradicted" sentinel (`DecisionLevel` is a decision count and
cannot reach `u32::MAX`). `is_contradicted` becomes a bounds-checked array
load, `insert` grows the vec on demand, and the backtrack reset becomes a
single linear pass that clears entries above the target decision level.
Semantics are unchanged.
Benchmarks (criterion, `backtracking` / `large_case` / `sudoku`):
backtracking_singletons ~623 ms -> ~446 ms (-28%)
backtracking_disjoint_versions ~322 ms -> ~239 ms (-26%)
backtracking_ranges ~236 ms -> ~221 ms (-6%)
large_case_u16_NumberVersion ~6.04 ms -> ~5.69 ms (-6%)
sudoku-easy / sudoku-hard within noise
`cargo test` (incl. proptest), `cargo clippy --all-targets` clean.RyanJamesStewart:perf/contradicted-dense-vec Latest Branches
N/A
RyanJamesStewart:perf/contradicted-dense-vec N/A
N/A
© 2026 CodSpeed Technology