Repository navigation
Reduce set-encoding size by reusing the unstable byte-vector sort #794
Description
Follow-up to #772. On v3 baseline 3d19abbce5dd8d5244641ff0d7ba8bad5424d07f, src/storage/keys.rs::set_elements uses a stable Vec<Vec<u8>> sort even though equal encoded elements are identical and immediately deduplicated. An unstable specialization is already linked elsewhere.
The isolated one-line prototype encoded.sort() → encoded.sort_unstable() measured with Rust 1.99.1, the audit dependency lock, and the existing release profile:
| Artifact | Before | After | Saved |
|---|---|---|---|
| Native CLI | 1,263,592 | 1,260,568 | 3,024 |
| Thin-LTO dist CLI | 1,502,888 | 1,498,776 | 4,112 |
| WASI | 879,785 | 878,835 | 950 |
| Packaged browser Wasm | 994,445 | 993,569 | 876 |
| Stripped opt-level-3 library consumer | 2,161,280 | 2,157,120 | 4,160 |
On the idle bench machine, four socket-swapped algorithm-probe rounds at 100K byte vectors gave median changes of -27.3% random, -22.0% repeated, -2.1% descending and +0.8% ascending time. These are sort timings, not end-to-end database claims. The change also removes stable-sort scratch allocation.
The prototype passed all 23 key codec tests, all 10 set integration tests on disk, native/browser/WASI builds and Rust 1.89 all-features checking.
Scope and shipping gates:
- Make this a focused v3 change, preserving exact encoded bytes, deduplication, signed-zero/NaN handling and all errors.
- Add or strengthen meaningful equivalence coverage for permuted, duplicate, long and mixed-type sets as needed; use existing tests where they already establish it.
- Measure complete set ingest/checkpoint/query workloads on the bench, including sorted and reverse input, before accepting the runtime tradeoff.
- Run normal correctness/coverage/platform gates and remeasure at the implementation head.
- Keep the current size cap, coverage floors, API, file format and MSRV unchanged.
Activity
Merge origin/v3 into perf/794-set-sort-unstable
Merge pull request #800 from project-minigraf/perf/794-set-sort-unstable
adityamukho commentedon Oct 30, 2026
Fixed on v3 by #800.