You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Evaluate smaller sorts for unique query metadata #795
Follow-up to #772. The audit found small stable-sort specializations for metadata whose keys are intended to be unique:
query/datalog/prepared.rs::collect_slot_names: sort names collected from a HashSet.
query/engine/plan.rs::Builder::or: sort branch variable names collected from a map.
query/engine/plan.rs::Builder::sub: sort imported (name, slot) pairs by slot.
At baseline 3d19abbce5dd8d5244641ff0d7ba8bad5424d07f, Rust 1.99.1 with the audit lock and unchanged release profile, the first two changes together independently reduced the CLI from 1,263,592 to 1,263,240 bytes (352 saved). The import-sort prototype independently produced 1,262,936 bytes (656 saved). These savings are not additive; measure any combination.
The standalone string-sort probe at 100K elements was 24.2% faster for random unique names and within 2.3% for ascending/descending input across four paired socket-swapped rounds. It removes stable-sort scratch space, but this is not an end-to-end query-planning benchmark. Small query-sized lists and complete prepare/plan costs need measurement.
Scope:
Confirm every equal-key tie is indistinguishable. In particular, prove the import-slot invariant (including duplicate join-variable inputs and aliases) before changing the import sort; omit that change if stable ties matter.
Keep optimizer selectivity/cost sorts and legacy transaction replay sorts stable.
Preserve prepared slot order, branch variable order, plan behavior and errors using existing differential tests plus any missing tie case.
Remeasure independently and combined on native, browser and WASI; run relevant plan/prepared/disjunction tests, MSRV and normal coverage gates on the bench.
Keep public API, format, size cap and coverage floors unchanged.
Done in #799 (merged into v3): all three sorts are unstable; import-slot invariant proved and tested. Sizes: native −1,008, WASI −1,752, browser −1,886 bytes; planning time unchanged within noise.
Activity
Merge pull request #799 from project-minigraf/perf/795-unique-sorts
adityamukho commentedon Oct 30, 2026
Done in #799 (merged into v3): all three sorts are unstable; import-slot invariant proved and tested. Sizes: native −1,008, WASI −1,752, browser −1,886 bytes; planning time unchanged within noise.
Merge origin/v3 into perf/794-set-sort-unstable