From 7c368acc20fcd68544e0c8358f9522ff2e46896c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 30 Oct 2026 11:25:33 +0530 Subject: [PATCH] perf: sort set element encodings with sort_unstable (#794) 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 Claude-Session: https://claude.ai/code/session_01H2a7QjqyDrSDo1LKTK619q --- CHANGELOG.md | 2 ++ CLAUDE.md | 2 +- docs/TEST_COVERAGE.md | 8 +++++--- src/storage/keys.rs | 40 +++++++++++++++++++++++++++++++++++++++- 4 files changed, 47 insertions(+), 5 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 474a2eeae9..63ae481101 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -26,6 +26,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Performance +- **Sort set element encodings without a stable sort** (#794). `set_elements` sorts its elements' byte encodings with `sort_unstable`: equal encodings are identical bytes and deduplicated straight after, so the encoded bytes are unchanged, and the stable sort's scratch allocation and code go. The native release binary is 3,024 bytes smaller (WASI 950, thin-LTO dist 4,112). On the bench machine, ingest, checkpoint, set-constant queries and scans of 100,000 32-element sets in seven input shapes stayed within run-to-run noise. No API, format or error change. + - **Release certified aggregate groups** (#781). Ordered aggregation now includes ordinary `sum`/`avg`, fixed-scalar `min`/`max`, and Integer/nil `sum-distinct`. Effective grouping tuples may include hidden `:with` keys, constants and repetitions when they reduce to one ascending Integer/Boolean dimension; existing single numeric/Boolean keys remain supported. Arguments are certified from constants, metadata or raw attribute history using the pinned reader, with pending/staged data and unsupported origins retaining full-input evaluation. Every `:with` Sort is retained. Limits count emitted groups after min/max drops; a retained Sort still drains its input. Completed groups are released, but one growing distinct group remains linear. Small selective grouped queries pay proof startup cost. Common result-buffer memory failures can precede later unread source failures, as on the existing ordered-count path; registered finalizers retain full-drain behavior. No aggregate semantics, syntax, public API, dependency or storage format changes. - **Resolve expression keyword literals once per operator** (#774). `=` and `!=` reuse a literal keyword's entity UUID across input rows, including nested expressions, rule bodies and prepared slots. The cache contains only literals from that expression and is discarded with the operator; dynamic operands retain the existing comparison semantics. No API, dependency or file-format change. See the [measurements](docs/benchmarks/774-expression-keywords.md). diff --git a/CLAUDE.md b/CLAUDE.md index 0dcdb0b510..28e239f0f0 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -218,7 +218,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**2056 tests** (2037 active, 19 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**2057 tests** (2038 active, 19 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. The #760 deterministic storage suite adds three native unit tests in a separate `--cfg minigraf_shuttle` build, outside the default count. Run only `graph::storage::deterministic::` with that cfg; ordinary unit tests do not enter its scheduler. `deterministic-schedules.yml` runs relevant v3 PRs on Linux/macOS/Windows plus Linux MSRV, and larger nightly/manual searches with replay artifacts. The identical main workflow activates the v3 schedule after both PRs merge. See `docs/testing/deterministic-schedules.md` for scope, controls and findings. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index f497e6f5cf..b61e75aea2 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,12 +4,14 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Active** | 2,037 | 2,072 | +| **Active** | 2,038 | 2,073 | | **Ignored** | 19 | 20 | -| **Total** | 2,056 | 2,092 | +| **Total** | 2,057 | 2,093 | Counts above are the current Cargo test inventory (active versus ignored), -including #777, #789 and #781. Verification results below identify which suites ran. +including #777, #789, #781 and #794. Verification results below identify which suites ran. + +**#794 verification (2026-10-30)**: one added `storage::keys` unit test checks that a set's element encoding equals its elements' encodings, ordered and deduplicated by a `BTreeSet`, over 2,000 random sets of up to about 60 elements with duplicates, signed zeros, NaNs and strings up to 300 bytes, in shuffled, sorted and reversed order. It passes with both the old stable sort and the new unstable sort. The full default suite passes (2,038 active, 19 ignored). CI-equivalent native, browser and WASI clippy pass on Rust 1.99.1, and Rust 1.89 checks all features. The release binary is 1,260,568 bytes (3,024 smaller), below the unchanged 1,263,616-byte cap. **#781 verification (2026-10-29)**: 24 active tests and two ignored measurement probes are added. On implementation `90cb88924`, the complete default suite diff --git a/src/storage/keys.rs b/src/storage/keys.rs index af93648201..bc977411cf 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -525,7 +525,7 @@ pub fn set_elements(elements: &[KeyValue]) -> Vec { b }) .collect(); - encoded.sort(); + encoded.sort_unstable(); encoded.dedup(); encoded.concat() } @@ -1391,6 +1391,44 @@ mod tests { } } + #[test] + fn set_element_encoding_is_the_sorted_distinct_encodings() { + // The reference: each element's encoding, ordered and deduplicated by + // a BTreeSet. Elements repeat (copies, -0.0/0.0, NaNs) and run past 64 + // bytes, in shuffled, sorted and reversed order (#794). + let mut rng = Rng(794); + for round in 0..2000 { + let mut elements: Vec = (0..rng.below(40)) + .map(|_| match rng.below(10) { + 0 => KeyValue::Str(random_string(&mut rng, 300)), + _ => random_value(&mut rng), + }) + .filter(|v| !matches!(v, KeyValue::LongStr { .. })) + .collect(); + for i in 0..elements.len() / 2 { + let j = usize::try_from(rng.below(elements.len() as u64)).unwrap(); + elements.push(elements[j].clone()); + elements.swap(i, j); + } + match round % 3 { + 0 => {} + 1 => elements.sort_by_key(enc_value), + _ => { + elements.sort_by_key(enc_value); + elements.reverse(); + } + } + let want: Vec = elements + .iter() + .map(enc_value) + .collect::>() + .into_iter() + .flatten() + .collect(); + assert_eq!(set_elements(&elements), want, "sorted distinct encodings"); + } + } + #[test] fn sets_inline_up_to_64_element_bytes() { // One string element of n bytes encodes as n + 3.