konsti/dev/incompat-tracker - Branch - pubgrub-rs/pubgrub

Return and track affected and culprit on conflicts

#298Merged

Comparing

konsti/dev/incompat-tracker

(

ec324e8

) with

dev

(

ffef172

)

-17%

Improvements: 1

Regressions: 1
(
1
)

Untouched: 4

Benchmarks

Improved

sudoku-hard

benches/sudoku.rs::benches::bench_solve

+6%

4.2 ms4 ms

Passed

backtracking_ranges

benches/backtracking.rs::benches::bench_group

2 s2 s

backtracking_disjoint_versions

benches/backtracking.rs::benches::bench_group

-1%

2.3 s2.4 s

sudoku-easy

benches/sudoku.rs::benches::bench_solve

-1%

3.8 ms3.9 ms

backtracking_singletons

benches/backtracking.rs::benches::bench_group

-2%

4.3 s4.4 s

large_case_u16_NumberVersion.ron

benches/large_case.rs::benches::bench_nested::large_cases

Regression

-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

Home Terms Privacy Docs