Comparing
konsti/dev/incompat-tracker
(ec324e8
) withdev
(ffef172
)-17%
- Improvements
- 1
- Regressions
- 1
- Untouched
- 4
- New
- 0
- Dropped
- 0
- Ignored
- 0
Benchmarks
Improved
sudoku-hard
benches/sudoku.rs::benches::bench_solve::sudoku-hard+6%
4.2 ms
4 ms
Passed
backtracking_ranges
benches/backtracking.rs::benches::bench_group::backtracking_ranges0%
2 s
2 s
backtracking_disjoint_versions
benches/backtracking.rs::benches::bench_group::backtracking_disjoint_versions-1%
2.3 s
2.4 s
sudoku-easy
benches/sudoku.rs::benches::bench_solve::sudoku-easy-1%
3.8 ms
3.9 ms
backtracking_singletons
benches/backtracking.rs::benches::bench_group::backtracking_singletons-2%
4.3 s
4.4 s
large_case_u16_NumberVersion.ronRegression
benches/large_case.rs::benches::bench_nested::large_cases::large_case_u16_NumberVersion.ron-17%
21.5 ms
25.8 ms
Commits
Click on a commit to change the comparison rangeBase
dev
ffef172
-17%
Return and track affected and culprit on conflicts
Whenever we either discard a version due to its dependencies or perform conflict resolution, we return the last conflict that led to discarding them.
In cargo, we use this information for prioritization, which speeds up resolution (`cargo run -r -- -m pub --with-solana --filter solana-archiver-lib -t 16` goes from 90s to 20s on my machine).
Configurations that are noticeably slower for the solana test case:
* All incompatibilities unit propagation
* Only the last root cause in unit propagation
* No incompatibilities from unit propagation
* No incompatibilities from `add_version`
* Only affect counts (without culprit counts)
* Backtracking with the same heuristic as https://github.com/astral-sh/uv/pull/9843 (backtracking once after affected hits 5)
In uv, we use this to re-prioritize and backtrack when a package decision accumulated to many conflicts. Since we have our own solver loop, we add the incompatibility to our own tracking instead.
Built on https://github.com/pubgrub-rs/pubgrub/pull/291
## Benchmarks
Main:
```
index commit hash: 82086e46740d7a9303216bfac093e7268a95121f
index commit time: 2024-11-30T18:18:14Z
index size: 32
solana in index: 32
Pub CPU time: 1215.49s == 20.26min
Cargo CPU time: skipped
Cargo check lock CPU time: skipped
Pub check lock CPU time: skipped
Wall time: 80.58s == 1.34min
```
With https://github.com/pubgrub-rs/pubgrub/pull/291:
```
index commit hash: 82086e46740d7a9303216bfac093e7268a95121f
index commit time: 2024-11-30T18:18:14Z
index size: 32
solana in index: 32
Pub CPU time: 467.73s == 7.80min
Cargo CPU time: skipped
Cargo check lock CPU time: skipped
Pub check lock CPU time: skipped
Wall time: 34.76s == 0.58min
```
This PR:
```
index commit hash: 82086e46740d7a9303216bfac093e7268a95121f
index commit time: 2024-11-30T18:18:14Z
index size: 32
solana in index: 32
Pub CPU time: 271.79s == 4.53min
Cargo CPU time: skipped
Cargo check lock CPU time: skipped
Pub check lock CPU time: skipped
Wall time: 20.17s == 0.34min
```
d839d70
14 days ago
by konstin-1%
Use smallvec for root causes
087bcdf
10 days ago
by konstin0%
Review
ec324e8
8 days ago
by konstin