pubgrub-rs
pubgrub
BlogDocsChangelog

Return and track affected and culprit on conflicts

#298Merged
Comparing
konsti/dev/incompat-tracker
(
ec324e8
) with
dev
(
ffef172
)
CodSpeed Performance Gauge
-17%
Improvements
1
Regressions
1
(
1
)
Untouched
4

Benchmarks

Improved

sudoku-hard
benches/sudoku.rs::benches::bench_solve
CodSpeed Performance Gauge
+6%
4.2 ms4 ms

Passed

backtracking_ranges
benches/backtracking.rs::benches::bench_group
CodSpeed Performance Gauge
0%
2 s2 s
backtracking_disjoint_versions
benches/backtracking.rs::benches::bench_group
CodSpeed Performance Gauge
-1%
2.3 s2.4 s
sudoku-easy
benches/sudoku.rs::benches::bench_solve
CodSpeed Performance Gauge
-1%
3.8 ms3.9 ms
backtracking_singletons
benches/backtracking.rs::benches::bench_group
CodSpeed Performance Gauge
-2%
4.3 s4.4 s
large_case_u16_NumberVersion.ron
benches/large_case.rs::benches::bench_nested::large_cases
Regression
CodSpeed Performance Gauge
-17%
21.5 ms25.8 ms

Commits

Click on a commit to change the comparison range
Base
dev
ffef172
-16.58%
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
10 months ago
by konstin
-0.52%
Use smallvec for root causes
087bcdf
10 months ago
by konstin
+0.3%
Review
ec324e8
10 months ago
by konstin
© 2025 CodSpeed Technology
Home Terms Privacy Docs