russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
1.4 KiB
| id | repo | severity | status | created | patched | patch |
|---|---|---|---|---|---|---|
| rustc-0002 | rust | MEDIUM | PATCHED (partial — swap_remove O(1) vs remove O(n); position scan still O(n)) | 2026-03-23 | 2026-03-23 | defects/rustc/patch/rustc-0001-0002-evalstack-swapremove.patch |
Defect
File: compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs:69
Pattern: Vec::position in specialization graph build
Complexity: O(V²) per impl
Language: Rust
Description
When building the trait specialization graph, Vec::position is used to locate an impl's position in a vector during graph construction. Vec::position performs a linear scan through all elements. Since specialization graph construction processes every impl and may call this for each impl against all previously-inserted impls, the total construction cost is O(V²) in the number of impl items, which degrades compilation of crates with heavy use of specialization.
Fix
Replace: impls.position(|i| i == target)
With: impl_index.get(&target)
Data structure change: Vec<ImplDef> impls → Vec<ImplDef> impls + HashMap<ImplDef, usize> impl_index
Work required
- Patch in
defects/rustc/patch/ - Unit test — asserts exact operation counts before/after (in
defects/rustc/unit/) - Integration test (in
defects/rustc/integration/) - Benchmark — before/after on V=100,200,400,800 (in
defects/rustc/bench/) - White paper section