Repository navigation
perf: sort set element encodings with sort_unstable (#794) - #800
Merged
Merged
Conversation
Equal element encodings are identical bytes and are deduplicated right after the sort, so stability is unobservable: the encoded bytes are unchanged. Drops the stable sort's scratch allocation and its code (native release binary 1,263,592 -> 1,260,568 bytes). Adds a reference test: the encoding equals the BTreeSet-ordered distinct encodings over random sets with duplicates, signed zeros, NaNs and long strings, in shuffled, sorted and reversed order. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01H2a7QjqyDrSDo1LKTK619q
Codecov Report✅ All modified and coverable lines are covered by tests. 📢 Thoughts on this report? Let us know! |
Keep both #794 and #795 CHANGELOG entries; combine test counts (2,058 total, 2,039 active). Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01H2a7QjqyDrSDo1LKTK619q
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Implements #794 (follow-up to the #772 audit, #798). This is the audit's
encoded-set-sort.patch(docs/audits/772/evidence/patches/) plus a reference test.Change
keys::set_elementssorts element encodings withsort_unstableinstead ofsort. Equal encodings are identical byte strings and are removed by thededupthat follows, so stability cannot be observed. Encoded bytes, deduplication, signed-zero/NaN handling and errors are unchanged. No API, file-format, error-code, MSRV, size-cap or coverage-floor change.Equivalence test
set_element_encoding_is_the_sorted_distinct_encodingscompares the encoding with aBTreeSetreference over 2,000 random sets. The sets have up to about 60 elements and mix every scalar kind, with repeated elements, ±0.0, NaNs and strings up to 300 bytes (long sets). Each set is tested in shuffled, encoding-sorted and reversed order. The test passes with both the old stable sort and the new one.Sizes (bench machine, Rust 1.99.1)
End-to-end set workload (bench machine, release profile,
taskset -c 2)100,000 entities, one 32-element set each, ingested in 500-fact transactions, then a checkpoint, 200 set-constant point queries and a full scan with
count. Seven input shapes: ints/strings/keywords in ascending and descending order, plus mixed. Base and head runs alternate, with medians over 5 rounds. Phase changes ranged from −6.3% to +2.3%, except the two outliers below, which were rerun for 10 more rounds:The mixed point-query path sorts only 200 × 32 encodings in total, so this sort cannot explain a ~5 ms gap; I read it as code layout or noise, and the ranges overlap. Every other phase was within ±4%, most slightly faster. Machine noise produced a few multi-second outliers in individual runs; medians are reported.
Verification
cargo test: 2,038 passed, 19 ignored (one new test)--all-features,wasm32-unknown-unknown --features browser,wasm32-wasip1cargo +1.89 check --all-features(MSRV)cargo fmt --checkDocs: CHANGELOG (Performance),
docs/TEST_COVERAGE.mdcounts and a #794 verification note, CLAUDE.md test count.🤖 Generated with Claude Code
https://claude.ai/code/session_01H2a7QjqyDrSDo1LKTK619q