adityamukho · 8000 Oct 30, 2026 · Oct 30, 2026 · Oct 30, 2026
@@ -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.
+
 - **Unstable sorts for unique query metadata** (#795). Prepared-query slot names, an `or`'s branch variables and a subplan's imported variables sort with `sort_unstable`: their keys are unique, or, for a join variable named twice, the tied entries are identical, so order and plans are unchanged. Release builds shrink by 1,008 bytes (native CLI), 1,752 bytes (WASI) and 1,886 bytes (browser `--lib`); prepare and planning time is unchanged within noise. No API, dependency or file-format 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.

@@ -218,7 +218,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**2057 tests** (2038 active, 19 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
+**2058 tests** (2039 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.

@@ -4,12 +4,14 @@
 
 | | Default features | With `--features test-hooks` |
 |---|---|---|
-| **Active** | 2,038 | 2,073 |
+| **Active** | 2,039 | 2,074 |
 | **Ignored** | 19 | 20 |
-| **Total** | 2,057 | 2,093 |
+| **Total** | 2,058 | 2,094 |
 
 Counts above are the current Cargo test inventory (active versus ignored),
-including #777, #789, #781 and #795. Verification results below identify which suites ran.
+including #777, #789, #781, #794 and #795. 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 passed before merging #795 (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

@@ -525,7 +525,7 @@ pub fn set_elements(elements: &[KeyValue]) -> Vec<u8> {
             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<KeyValue> = (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<u8> = elements
+                .iter()
+                .map(enc_value)
+                .collect::<std::collections::BTreeSet<_>>()
+                .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.