Release v0.9.0 · orieg/expanse

0.9.0 is a breaking release. Under Cargo's 0.x rule, ^0.8 does not match 0.9.0, so a dependent upgrades deliberately. The Rust API loses five items and changes one signature to unsafe, and the C header marks six string-map navigation functions deprecated. The concurrent Sync* wrappers no longer reach undefined behaviour from safe code on either width (#1086), and that fix costs instructions on the shared paths, and writer throughput on the 32-bit SyncExpanseMap32. The costs are listed under Disclosed costs.

Breaking changes

Checked against git diff v0.8.2 f4d1da2e -- .github/public-api/ include/.

SlotTag::Tombstone is removed (#1180). Nothing produced or consumed it. The byte 0xFE now decodes as SlotTag::RawWord. The binary image format is unchanged (EXPANSE_FORMAT_VERSION stays 2).
Migration: delete matches on SlotTag::Tombstone. SlotTag is #[non_exhaustive], so a wildcard arm already covers it.
ExpanseMap::range_filtered and ExpanseMap::scan_filtered are removed (#1181). They decoded bits 63:40 of every value as blob-map metadata without checking the tag. On a plain map that is part of the caller's value, and on a blob map's index it is inline payload bytes. No C symbol or binding called them.
Migration: on a plain map, use map.range(r).filter(..). For blob metadata, use ExpanseBlobMap::scan_filtered, which checks the tag.
slot::filter_slots_range and slot::filter_slots_predicate read metadata only from ArenaMeta slots (#1179). The signatures are unchanged but results change: any other slot reads as metadata 0, as the rustdoc already said. Before, an inline slot reported its payload bytes as metadata.
Migration: none, unless you depended on the old results. A range that excludes 0 no longer matches inline or raw slots.
with_locked_mut is replaced by with_exclusive on SyncExpanseStrMap and SyncExpanseBytesMap (#1196, Refs #1188). The old method gave its closure a &mut map while optimistic readers ran, so a store through a returned slot raced them. with_exclusive passes a StrExclusive / BytesExclusive handle with get, contains_key, insert, remove, update, len and is_empty. The operations in one section still apply as one step.
Migration: rewrite w.with_locked_mut(|m| { … m.insert(k, v); … }) as w.with_exclusive(|x| { … x.insert(k, v); … }). Code that needs a slot pointer or the whole map has no replacement yet; the operation gaps are tracked in #1194. Read-only scans move to with_locked, because the string map's cursors now take &self (see below).
occ::Collector::retire is an unsafe fn (#1173, Refs #1145). It frees a pointer the caller passes in, so safe code could free a dangling pointer. Its # Safety section states the contract.
Migration: wrap each call in unsafe { } and document why the pointer meets the contract. No binding, bench or example called it.
Four unused occ32 functions are removed (#1198): node_validate, node_version_begin, node_version_end and try_node_sample. Nothing in the workspace called them.
Migration: none inside this workspace. External callers must drop them.
occ_stats gains Stat::BranchSplitDemoteU (index 48, #1204). NAMES is now [&str; 49] and snapshot() returns [u64; 49].
Migration: code that names the array length 48 must use 49. This only applies with the occ-stats feature. Stat is #[non_exhaustive].
BRANCHU_TO_B_DOWN is now 160, not 191 (#1221). The type is unchanged, so the API snapshot does not move, but the value and the node form it selects do. After removals, a branch keeps its BranchU form down to 161 digits, where it used to demote to a BranchB at 191. This applies on plain trees as well as shared ones. The memory cost is under Disclosed costs.
Migration: none needed for correctness. Code that reads the constant sees the new value.
C: six string-map navigation functions are deprecated (#1159): expanse_strmap_first, _last, _next_at_or_after, _next_after, _prev_at_or_before and _prev_before. include/expanse.h now tags them EXPANSE_DEPRECATED (deprecated on GCC/Clang, __declspec(deprecated) on MSVC). A build with -Werror (or -Werror=deprecated-declarations, or /WX) now fails at each call.
Migration: call the _ex variants (expanse_strmap_first_ex, …), which were already in 0.8.2. They return expanse_str_nav_status, which separates truncation from a missing key. The header has no macro to turn the attribute off.
C: EXPANSE_NONNULL(1) on expanse_map_insert, expanse_bytesmap_insert and expanse_strmap_insert (#1159). The compiler may now warn when the handle argument is a literal NULL, and with -Werror that warning fails the build.
Migration: do not pass a NULL handle to these three functions.

Two other changes do not break source code:

ExpanseStrMap::first, last, next_after, next_at_or_after, prev_at_or_before, prev_before, cursor and cursor_at_or_after now take &self instead of &mut self (#1196, #1159). Existing calls still compile. StrCursor is now UnwindSafe.
Several C functions now take const handles (#1159): expanse_strmap_slot, expanse_bytesmap_slot, and the string-map navigation functions with their _ex variants. Callers compile unchanged. Code that stores these functions in function-pointer variables typed with the old signatures must update those types.

Added

compact() on the 64-bit ExpanseSet and ExpanseMap (#1199). It rebuilds the surviving keys into a new allocator, which returns the slab pages that live nodes keep pinned after bulk deletes. shrink_to_fit() cannot return those pages, because it never moves a node. Every node moves, so compact() invalidates every value pointer. The transient peak is the old tree, the new tree and a key buffer. On a tree shared through a collector it does nothing. Its pre-registered result is INTERMEDIATE:
- The retained-bytes gate is met on all 42 cells. Held bytes relative to a fresh build are 0.5770–0.9982 (measured: Apple M1, c953ea80; workload: example_remove_retention; docs/benchmarks/remove_retention/results/compact_retention.json).
- The no-side-effect instruction gate is not met: three from_sorted_iter arms moved down, by 1.6% to 7.2%, and the gate counts either direction.
- The Sync* wrappers, the 32-bit engine, the other container types and the C ABI do not have compact().
Public optimistic ordered reads on the 64-bit map readers (#1172, Refs #900). first, last, next_at_or_after, next_after, prev_at_or_before and prev_before are now public on MapReader, OwnedMapReader and DetachedMapReader. Each call is linearizable on its own. A sequence of calls is not a snapshot. The C ABI already exported these reads. The sync32 ordered reads stay #[doc(hidden)].
ExpanseStrMap::cursor_prefix and StrPrefixCursor (#1151, Refs #1096). The cursor walks exactly the keys that start with a prefix.
ExpanseStrMap::contains_key and get_slot_ptr; ExpanseBytesMap::get_slot_ptr and try_for_each (#1159).
mem_held() / shrink_to_fit(), extended across the remaining types (Refs #1135):
- the 32-bit ExpanseMap32 / ExpanseSet32, their C symbols in the 32-bit library, and WasmExpanseMap32 / WasmExpanseSet32 (#1146);
- all five concurrent wrappers: SyncExpanseMap, SyncExpanseSet and SyncExpanseStrMap (#1148), SyncExpanseBytesMap and SyncExpanseBlobMap (#1153). On a wrapper, mem_held() counts the collector's freelists and its blocks still in their grace period. shrink_to_fit(&self) releases the freelists without excluding readers or writers.
- the C ABI and the C++, Java, .NET, Go, Python, Node and PHP bindings for the concurrent map and set (#1153).
12 new C symbols in include/expanse.h. The 64-bit std library now exports 170 symbols, up from 158 (docs/COMPAT.md):
- expanse_sync_map_mem_held, expanse_sync_map_shrink_to_fit, expanse_sync_set_mem_held and expanse_sync_set_shrink_to_fit (#1153);
- expanse_map_contains, expanse_bytesmap_contains, expanse_bytesmap_for_each, expanse_strmap_contains and expanse_blob_map_contains (#1159);
- expanse_set_validate, expanse_map_validate and expanse_map_validate_explain (#1159). These three are 64-bit only.
- The 32-bit library now exports 67 symbols, up from 62: the four expanse_{map,set}_{mem_held,shrink_to_fit} symbols (#1146) and expanse_map_contains (#1159).
- The new symbols are wrapped in the Java, .NET, Python, Node and Go bindings (#1159). The C++ header gains validate(), bytesmap::for_each, blob_map::get_into, and exception propagation out of callbacks.
JUDY_STRICT_MACROS (#1159). Define it before including Judy.h to expand the J1* / JL* / JSL* / JHS* convenience macros as do { … } while (0). The default expansion is unchanged, for drop-in compatibility.
occ_stats::Stat::BranchSplitDemoteU (#1204). It counts shared removals that fall back instead of dropping a BranchU below its demotion floor.

Fixed

The Sync* wrappers no longer reach undefined behaviour from safe code, on 64-bit or 32-bit (Refs #1086, present since v0.6.0). Two classes were closed:
- optimistic readers racing a writer's plain stores;
- &T / &mut aliasing over the engine.
The 64-bit fixes:
- word-atomic root-leaf loads and stores on the map and set (#1133) and on the string map's sub-maps (#1138, #1157);
- bitmap reads through shared_bitmap in the ordered walks (#1163);
- atomic shared accesses to every word a reader loads: edges, branch headers, subarray pointers, value words and packed leaf keys. Covered writers now reach published nodes only through raw pointers (#1175).
- with_exclusive in place of with_locked_mut, and compile-time checks that each walk is used in the right sharing mode (#1196).
The 32-bit fixes, for sync32:
- readers stop borrowing the engine and read through a published slot table (#1198);
- branch nodes are read and written through raw pointers and word stores (#1203);
- the shared writer copies a leaf before editing it (#1209).
Every entry in the Miri undefined-behaviour census (.github/miri-ub-sites.json) is now recorded clean. A clean entry is an observation over the census's seed range, not a proof. Deterministic checks that every optimistic-reader answer is validated came with #1219 (Refs #1189). Fail-then-pass records for each class-2 fix came with #1196 and #1220 (Refs #1190).
Optimistic removals no longer leave a BranchU below its demotion floor (#1204, Refs #1079). Before, validate() could reject a tree shared through SyncExpanseMap, SyncExpanseSet, SyncExpanseBytesMap or a SyncExpanseStrMap sub-map after concurrent removals. A removal that would reach the floor now falls back (BranchSplitDemoteU). The follow-up in #1221 widened the U↔B band (see Performance).
SyncExpanseStrMap frees sub-maps that optimistic removes drain through a BranchU (#1184, Refs #1182). Before, such a node stayed linked until clear or drop.
Dropping a Sync* wrapper returns its tree while the writer thread lives (#1206). The wrapper drained the collector and only then dropped the tree, whose nodes went back into the collector's bins. Each writer thread's cached reader held that collector alive until the thread's next cache miss or its exit. In the PR's measurement, a dropped 10⁶-key random-order map left 10,232,856 B allocated on a live thread (#1206). The tree is now dropped first.
SyncExpanseStrMap ascending-order inserts are no longer O(N) each (#1167, Refs #1162). The deferred insert paths refolded the whole sub-map population after every fallback. At N = 20,000 sorted UUIDs, a load folded 460,996 edges before the fix and 0 after (#1167, sync::fold_edges test counter).
JudyLGet, JudySLGet and JudyHSGet no longer mutate the array on a lookup (#1159). They now use a non-mutating slot lookup. ExpanseBytesMap::get_slot_ptr projects the slot pointer through raw pointers, as Stacked and Tree Borrows require.
occ::Collector::retire is unsafe (#1173, Refs #1145); see Breaking changes.
The blob-metadata filters check the slot tag (#1179, #1181); see Breaking changes.
sync::tests::stale_locator_window_during_compact_fallback no longer hangs on a many-core x86 host (#1224). The test now paces its compactor; it is a blob-map compaction test and does not exercise the U↔B band.
Tooling fixes in range:
- #1166 (perf_report.py resolves Ins / Op per harness and arm), #1177 (perf_counters withholds a zero event only when it was co-scheduled), #1217 (lint reads every lane filter);
- #1223: search_boolean drops its materialized results after each timed repetition (benchmark only);
- #1225: bare-metal bench output fails closed on zero-count, empty and stale files;
- #1226: a kernel-released host lock, and a guard that refuses a busy host; #1229: the pinned CPUs run the performance governor for each run; #1230, #1232 and #1234 harden the bench runners (an authorized checkout SHA, a dedicated service account, and a valgrind floor of 3.24.0);
- #1228: discipline pinned by commit.

Performance

Figures are instruction counts, Callgrind or wasmtime fuel, unless marked wall clock. Every figure names its host and commits. The release candidate is f4d1da2e; #1235 lands after it and is covered under Disclosed costs.

Instruction counts

Callgrind, v0.8.2 against the release candidate (measured: dual Xeon E5-2697 v4 x86_64 dev host, iai-callgrind 0.16.1 and valgrind 3.24.0 in rust:1.98, v0.8.2 710f1098 against f4d1da2e, both run unfiltered; a local run, not a CI run; workload: core_instructions).

133 arms exist in both builds: 102 plain arms and 31 sync_* arms. 41 arms exist only at the candidate. 50 of the 133 are exactly equal.
No arm's measured body changed between the two commits. The setup of the six strmap_prefix_scan, strmap_prefix_seek and strmap_cursor_scan arms gained a read-only cursor_prefix check; they are marked "setup changed".

Arms	>0.1% up	>0.1% down	>0.5% up	>0.5% down	>5% up	>5% down
all 133	31	33	28	24	16	7
plain 102	4	30	2	22	0	6
`sync_*` 31	27	3	26	2	16	1

Plain (unshared) containers. 98 of the 102 plain arms are at or below v0.8.2, or within 0.1% of it. The four above 0.1%:

Arm	N	v0.8.2 Ins/op	RC Ins/op	Δ	Moved by
`blobmap32_scan/ipv4_routes`	2k	172.9	174.9	+1.15%	#1203
`strmap_prefix_seek/paths` (setup changed)	64	2,494.4	2,510.4	+0.64%	before `f70af2e2`
`map32_remove/random`	2k	671.5	673.0	+0.22%	before `f70af2e2`; #1203 −0.172%, #1209 +0.067%
`set32_remove/random`	2k	556.2	557.2	+0.17%	before `f70af2e2`; #1203 −0.120%, #1209 +0.031%

The largest plain reductions:

Arm	N	v0.8.2 Ins/op	RC Ins/op	Δ
`strmap_cursor_scan/paths_dense` (setup changed)	50k	311.0	277.0	−10.92%
`strmap_prefix_scan/paths_dense` (setup changed)	12.5k	352.2	318.3	−9.63%
`set_clone/sequential`	50k	56.0	52.0	−7.19%
`strmap_cursor_scan/paths` (setup changed)	50k	204.1	190.0	−6.93%
`map32_insert/sensor_timestamps`	10k	502.8	470.6	−6.39%
`strmap_prefix_scan/paths` (setup changed)	12.5k	244.5	230.8	−5.61%
`map_oscillate/random`	50k	80.1	76.1	−4.99%
`set_insert/sequential`	50k	67.7	64.4	−4.79%
`strmap_insert/routes`	50k	892.2	868.5	−2.66%
`set_clone/random`	50k	310.2	302.5	−2.50%

Twelve more plain arms fell by 0.5% to 2.0%, among them strmap_clear_refill/routes −2.00%, set_insert/clustered −1.83% and strmap_churn/routes −1.73%. set_clone fell with #1199's builder change.

Shared (Sync*) containers. 27 of the 31 sync_* arms are above v0.8.2 by more than 0.1%, and 16 of them by more than 5%; this is the accepted cost of the #1086 fix (see Disclosed costs). The largest are sync_strmap_churn_short/short +12.64% (4,164.9 → 4,691.5 Ins/op), sync_strmap_insert_short/short +11.20% and sync_set_insert/random +8.78%. sync_map_prev_locked/random is −0.01% and three of the four leaf arms are flat or lower (sync_map_get/leaf −10.43%); sync_set_churn/leaf is +0.17%.

What moved after f70af2e2 (same host and image; f70af2e2 against 68d787f8 (#1203), 152b96f9 (#1209), 0a8b924f (#1219, #1220) and f4d1da2e (#1221, #1223)). 37 of the 173 arms common to all five builds moved. Beyond those already listed:

sync_map_drain_floor/top +6.905% and sync_set_drain_floor/top +6.623%, both at #1221. Their bench code did not change; #1221 moved the floor the drain crosses (see Disclosed costs).
sync_map_write_twin/sequential −10.905% and sync_map_count_after_write/sequential −1.787% at #1221.
map32_insert/sensor_timestamps −6.458% (#1203 −5.451%, #1209 −1.065%); set32_insert/sensor_timestamps −0.085% (#1203 +1.080%, #1209 −1.153%).
Every other movement is within ±0.33%. #1219/#1220 changed only test code, and #1223 only the search_boolean bench, which is not in this suite.

Wasm fuel, v0.8.2 against the release candidate (measured: same dev host, scripts/wasm_fuel.py as CI runs it, wasmtime 48.0.0, wasm32 on rustc 1.98.0, wasm64 on nightly-2026-09-03, N = 10,000, 710f1098 against f4d1da2e; workload: wasm_fuel). All 30 arms exist at both commits on each width, and every checksum matches.

wasm64: every arm is within −0.11% to +0.25% of v0.8.2. After f70af2e2 it moved only at #1221: map_remove/random −0.351% and set_remove/random −0.332%.
wasm32: −3.32% to +0.73%. Five arms are above v0.8.2 by more than 0.1%: map_get/sequential +0.73%, map_get/random +0.63%, map_remove/clustered +0.52%, map_get/clustered +0.48% and map_remove/sequential +0.30%. The map_get rise is all #1203. Eight arms fell by more than 0.5%, led by map_insert/random −3.32%, /clustered −2.78% and /sequential −1.97%; the insert reductions are split between #1203 and #1209. The iterate, range and set_contains arms are unchanged.

C ABI against stock libjudy, Callgrind (measured: i9-12900F reference host, v0.8.2 710f1098 against f70af2e2, run 36265221866; workload: capi_vs_stock). None of the 34 Expanse arms regressed. JudyLGet retires 4.3% to 10.8% fewer instructions (judyl_get_expanse −4.32% to −6.92%, judyl_get_expanse_dl −6.72% to −10.77%), because a lookup no longer maintains the insert-path cache (#1159). Every other Expanse arm is unchanged or lower by at most 0.95% (Judy1Set, JudySLIns, JudySLGet and JudyL churn). Expanse executes fewer instructions than stock libjudy on every paired arm.

Wall clock

All wall-clock figures come from the i9-12900F reference host, pinned to 0-15, with BCa 95% intervals (2,000 resamples). A run is admitted only if its artifact records the load inside every timed window; in every admitted run the largest foreign load is at most 0.13 busy core-equivalents. Suites whose runs carry no in-run load record are left out (#1214). Each comparison with v0.8.2 below is one run on each side, so the intervals are within-run and do not bound the spread between runs; a movement is named only when it repeats across runs.

SyncExpanseBytesMap writer scaling (workload: core_concurrency; 50% read / 50% write, 16 threads, total M ops/s, 18 rounds per run):

Build	Run	M ops/s
v0.8.2 `710f1098`	36302483787	33.97 [29.01, 37.44]
after #1204, `5dac3cee`	36307778215	11.14 [11.07, 11.22]
after #1221, `5fdb77f3`	36328184138	40.26 [39.54, 40.89]
release candidate `f4d1da2e`	36333096580	40.39

#1204 made the one-digit BranchU ↔ BranchB band reachable on shared trees. A hash trie's level-7 branches sit near 200 digits, derived as 256 × (1 − e^(−390/256)). With a one-digit band, many of those branches became BranchB, and their removals fell back to the exclusive path.
At 5dac3cee, the occ-stats fallback census recorded 134,513 fallbacks in 4,856,055 writes, against 173 in 14,967,304 at its parent (#1221; dev host, not the reference host).
#1221 widened the band to 32 digits (BRANCHU_TO_B_DOWN = 160). The #1204 loss holds in three consecutive reference runs (5dac3cee, and f70af2e2 runs 36285145713 and 36294918740 at 11.17 [11.09, 11.25] and 11.22 [11.12, 11.31]); the recovery holds in two (5fdb77f3 and f4d1da2e). The ratio to v0.8.2 at 5fdb77f3 is 1.185 [1.071, 1.362].

concurrency suite, selected cells (measured: i9-12900F reference host, 5fdb77f3 run 36328184138 against v0.8.2 710f1098 run 36302483787; workload: core_concurrency; 18 rounds, T threads, total M ops/s; the harness is unchanged between the two commits):

Engine	Workload	T	`5fdb77f3`	v0.8.2	Ratio to v0.8.2
SyncExpanseMap	100% read	16	333.02 [331.36, 334.63]	338.52	0.984 [0.978, 0.990]
SyncExpanseMap	50 / 50	16	88.20 [83.18, 93.84]	85.32	1.034 [0.942, 1.136]
SyncExpanseSet	100% read	16	396.03 [327.79, 448.65]	529.03	0.749 [0.616, 0.852]
SyncExpanseSet	50 / 50	16	216.75 [215.24, 218.65]	209.44	1.035 [0.990, 1.137]
SyncExpanseBlobMap	100% read	16	282.06 [281.23, 282.66]	288.67	0.977 [0.972, 0.981]
SyncExpanseBlobMap	50 / 50	16	6.97 [5.32, 7.98]	7.27	0.959 [0.747, 1.173]
SyncExpanseStrMap	100% read	16	78.74 [78.62, 78.92]	77.72	1.013 [1.011, 1.016]
SyncExpanseStrMap	50 / 50	16	52.79 [52.13, 53.19]	53.32	0.990 [0.978, 0.999]
SyncExpanseBytesMap	100% read	16	115.10 [109.40, 118.08]	125.83	0.915 [0.869, 0.939]
SyncExpanseBytesMap	50 / 50	16	40.26 [39.54, 40.89]	33.97	1.185 [1.071, 1.362]

SyncExpanseMap32 is covered under Disclosed costs.

Movements against v0.8.2 that repeat across runs (the eight post-v0.8.2 concurrency runs on the reference host: the five bisection runs 36303535010 to 36307778215, the two f70af2e2 runs and run 36328184138; workload: core_concurrency):

SyncExpanseBytesMap 100% read, every T: 6% to 9% below v0.8.2 at 5fdb77f3 (0.915 [0.869, 0.939] to 0.938 [0.936, 0.941]), and below in every run from fcebe54b on. The bisection places it on one commit, #1175 (atomic shared accesses, Refs #1086), whose Callgrind cost was accepted when it merged and whose wall clock was unmeasured. This is the first wall-clock figure for it.
SyncExpanseSet 100% read, T = 4 and 16: below in the three latest runs, from 0.749 [0.616, 0.852] to 0.977; the size is unstable and earlier runs flip sign. Unattributed.
SyncExpanseMap 100% read, T = 1 and 4: 0.969 to 0.994 in all eight runs (T = 4 in seven), already at 86adbf15, so before #1175. Unattributed.
Mutex<ExpanseStrMap> 50/50, T = 4: 0.908 to 0.935 in six of eight runs and 0.995 to 1.004 in the other two. Unattributed.
Gains: SyncExpanseSet 50/50 T = 1, +1.6% to +4.1% in all eight runs. The competitor arm RwLock<BTreeMap> 50/50 T = 16 also moved +0.7% to +4.3% in all eight, which sets a floor on the between-run spread of this suite.

The ycsb suite has no v0.8.2 record, so its cells are not compared with v0.8.2 here.

Loss list: cells where Expanse trails a competitor, with the interval excluding 1. Ratios are Expanse / competitor throughput, except patricia_comparison, which is Expanse ns/op over the competitor's (> 1 means Expanse is slower). All are measured on the i9-12900F reference host at f70af2e2, before #1221, except concurrency, which is at 5fdb77f3.

ycsb (runs 36267550245 and 36308858713, both agree; workload E, range scans, vs BTreeMap): ExpanseBlobMap sparse keys 0.389–0.825 in all six size × order cells; ExpanseMap sparse keys 0.487–0.700 at 100k and 10M; ExpanseBlobMap dense keys 0.604–0.781 in four cells.
hashbrown_ycsb (run 36275691729): Expanse vs hashbrown trails on every workload compared (A, B, C, D, F; n = 500k; both orders), 0.373–0.540.
rocksdb (run 36276140654) vs VectorRep: fillrandom 0.023 [0.022, 0.024], prefixscan Batch 0.198 [0.193, 0.200], prefixscan Iterator 0.283 [0.276, 0.287], seekrandom 0.933 [0.927, 0.942]. Expanse leads SkipListRep on all five operations.
patricia_comparison (run 36273455259): 23 scan cells (full_traversal vs qp_trie 1.07–2.77; prefix_scan on prefixed_path vs qp_trie 1.35–4.66, fast_radix_trie 1.18–1.91 and patricia_tree 1.16–1.67), and 16 string-lookup cells with long prefixed_path keys vs fast_radix_trie (1.12–1.75) and qp_trie (1.01–2.36). Tracked in #1096.
ycsb_concurrent (run 36286579298): OLC vs DashMap trails in all 32 cells, 0.15–0.91, lowest at Ac and Fc T = 8 (0.153, 0.151); vs SkipMap at Ac T = 8 (0.455), Fc T = 4 (0.905) and Fc T = 8 (0.447); vs RwLock<BTreeMap> at Fc T = 8, 0.956 [0.882, 0.995]; vs Mutex at T = 1 in Ac (0.832), C (0.900) and Fc (0.682). Pre-registered gate family D G6_peak_8_over_4 is REFUTED: [0.9757, 0.9903].
concurrency (run 36328184138): SyncExpanseStrMap vs DashMap every cell (0.453–0.627) and SyncExpanseBytesMap vs DashMap every cell (0.442–0.888); the BlobMap, StrMap and BytesMap wrappers vs their own Mutex<…> twins at T = 1 (0.446–0.899); SyncExpanseBlobMap vs SkipMap at 50/50 T = 16, 0.402 [0.312, 0.460]. SyncExpanseBlobMap 50/50 scales negatively, C(16) = 0.40 [0.32, 0.45], as it did at v0.8.2.
Memory (deterministic censuses, no interval): art_memory (run 36273216814) at N = 1k, Expanse / ART bytes 1.72× sequential and clustered, 1.93× sparse_stride, 3.39× zipfian; hashbrown_memory_alloc (run 36276027025) random keys, Expanse 58.13 B/key vs BTreeMap 28.90 and hashbrown 34.83 at 1k, down to 30.59 vs 27.24 and 22.28 at 100k.

Disclosed costs and known limitations

Shared-path instructions. Closing #1086 made every word a reader shares an atomic access. The packed-key leaf search on shared trees is scalar, because stable Rust has no 128-bit atomic to feed the SIMD search. Against v0.8.2 at the release candidate (the dev-host Callgrind run above):
- 26 of the 27 tree-size sync_* arms are +2.26% to +12.64%, and sync_map_prev_locked/random is −0.01%.
- The root-leaf arms are −10.43% to +0.17%.
- This cost was accepted when #1175 merged, with an allow-regression: line citing run 36150299210. #1201 recovered part of it (Refs #1191), and the figures include that recovery.
- #1204 added a pre-lock count on BranchU null stores. #1221 narrowed that count to tag words and stops it past the floor. sync_map_write_twin/sequential still retires 2,172,094 instructions against 1,161,694 before #1204 (runs 36256715324 and 36308860629). That arm does not exist at v0.8.2.
sync_map_drain_floor/top and sync_set_drain_floor/top are +6.23% and +6.16% (#1221, run 36308860629, approved by allow-regression:; +6.905% and +6.623% on the dev-host run above). With the floor at 160, 39 of the arm's 200 removals take the optimistic null store instead of the exclusive fallback.
SyncExpanseBytesMap 100% read is 6% to 9% slower than v0.8.2 in wall clock (see Wall clock), attributed to #1175 by bisection. This is the accepted cost of the undefined-behaviour fix.
SyncExpanseMap32 loses throughput to the undefined-behaviour fix. SyncExpanseMap32 is the 32-bit engine's concurrent map; the public Sync* aliases select it only on 32-bit targets. Its fixes (Refs #1187) cost, on the i9-12900F reference host (workload: core_concurrency):
- #1203 (branch nodes through raw pointers and word stores): reads −7% to −10% at every write rate (f70af2e2 run 36294918740 against 68d787f8 run 36334348048).
- #1209 (copy-on-write leaves in the shared writer): the full-duty writer falls from 11.62 to 2.49 M writes/s at one reader (f70af2e2 run 36294918740 against 152b96f9 run 36335596077). Reads in the 1M-writes/s cells fall 47% to 64%, and at 16 readers the writer no longer keeps up with a 1M/s target (0.881 M writes/s at f4d1da2e, run 36333096580).
- #1235 recovers part of it. An overwrite with the value already held opens no bracket, and a bitmap leaf's value overwrite is one atomic word store in place. Linear leaves stay copy-on-write. On the i9-12900F reference host (measured: 1e23a1a1, runs 36355351868 and 36356515520, two runs; against f70af2e2 run 36294918740; workload: core_concurrency, arm sync32), in M ops/s:
  - full-duty writer, one reader: 3.88 and 3.99 M writes/s, against 11.62 before #1209 and 2.54 without #1235 (0.33×–0.34× of f70af2e2);
  - reads with a writer at 1M writes/s: one reader 28.6 in both runs (0.75× of f70af2e2's 37.9; 18.6 without #1235); 16 readers 220.5 and 218.2 (0.69×; 108.8 without #1235); the writer again meets its 1M/s target at 16 readers (0.99, against 0.88 without #1235);
  - lighter write rates: 100k writes/s at 16 readers 400.6 and 404.4 (0.87×); 10k writes/s at 16 readers 431.1 and 426.0 (0.91×, the #1203 per-read cost).
- A stalled reader now makes the writer fail sooner. With one reader parked mid-walk, the writer completed 347,663 mutations before ReclaimBacklog at f70af2e2, 18,951 at f4d1da2e and 36,180 with #1235 (stalled_reader_backlog_census, #1235), because each leaf edit that changes a leaf's key set still allocates a node and retires one. This is a behaviour change for embedded users: size node_cap for the mutations a stalled reader can let through, or keep reader sections short.
- On device (STM32H747I-DISCO, M4 at 200 MHz, DWT cycles, minimum of 5 passes, two code placements, #1209): the saturated writer's mutation rate fell 1.8% and 2.8%; the worst-case interrupt-handler read moved 2,111 → 2,112 and 2,092 → 2,124 cycles; the M4 .text grew by 2,236 bytes. #1198 had raised mean sync32 read cycles by 2.5% to 6.7%. The published sync32 device tables have not been re-measured.
- Tracked for 0.9.x in #1233: word-atomic in-place leaf edits for key-set changes, which would restore both the writer rate and the stalled-reader tolerance.
- The 64-bit Sync* wrappers are unaffected by #1203, #1209 and #1235: every 64-bit cell of the reference-host concurrency suite was 0.95–1.00 of its value before them (measured: f4d1da2e run 36333096580 against f70af2e2 run 36294918740), apart from SyncExpanseBytesMap 50/50, which is the #1221 gain.
The U↔B band is 32 digits. After removals, a branch that holds 161–191 digits keeps its BranchU form (4,160 B), where it used to become a BranchB. At 161 digits, a BranchB takes at least 128 + 161 × 16 = 2,704 B. That puts the extra memory at no more than 1,456 B per such branch, derived from the node sizes in docs/ARCHITECTURE.md §10 with subarray rounding ignored, which can only shrink the gap. No measured density cell reaches that state. scripts/condense_bounds.py still models the old 191 floor for the concluded remove-retention spike (#1221).
The U↔B crossing is expensive. On a shared tree, each crossing of the band falls back to an exclusive section that quiesces the writers. A branch whose digit count oscillates across the band still pays that cost. The wider band makes such oscillation less likely; it does not remove the cost. No wall-clock cell measures it yet (#1208). A header child count that would replace the demotion scans is tracked in #1202.

Deferred to 0.9.x

#1233: word-atomic in-place leaf edits in SyncExpanseMap32, to restore its writer throughput and stalled-reader tolerance.
#1202: a BranchU child count in the node header, to replace the demotion scans (a measured ablation).
#1208: wall-clock cells for a shared BranchU crossing its demotion floor.
#1194: the Sync* operation gaps, including those with_locked_mut's removal left.
#1142: a validated batch cursor, with bounds, on the concurrent map readers.
#1144: concurrent count, rank and select.
#1096: the string-map prefix scan, still slower than the three radix-trie crates in every patricia_comparison scan cell.
#1214: in-run load snapshots for the wall-clock suites that record none; until then those suites are left out of the wall-clock summary.

What's Changed

🚀 Features

feat(32bit,capi,wasm): mem_held and shrink_to_fit on the 32-bit engine (Refs #1135) by @orieg in #1146
feat(sync): mem_held and shrink_to_fit on the concurrent wrappers (Refs #1135) by @orieg in #1148
feat(strmap): cursor_prefix, a cursor bounded by a key prefix (Refs #1096) by @orieg in #1151
feat(sync,capi,bindings): mem_held and shrink_to_fit across the concurrent wrappers by @orieg in #1153
feat(sync): make the map readers' ordered reads public by @orieg in #1172
feat(compact): explicit compact() for the 64-bit ExpanseSet and ExpanseMap by @orieg in #1199

🐛 Fixes

fix(sync): word-atomic root-leaf loads and stores on the shared map and set (Refs #1086) by @orieg in #1133
fix(strmap): atomic sub-map root words on the shared string map (Refs #1086) by @orieg in #1138
fix(strmap): atomic root-leaf shifts in a string node's sub-map (Refs #1086) by @orieg in #1157
fix(capi): resolve UB in lookups, fix inline blob view safety, and add 8 container methods with 100% ABI parity by @orieg in #1159
fix(sync): the ordered walks read bitmaps through shared_bitmap by @orieg in #1163
fix(perf-report): resolve Ins / Op counts per (harness, arm) by @orieg in #1166
fix(strmap): no census re-sync on the deferred twin's insert paths by @orieg in #1167
fix(occ): make Collector::retire an unsafe fn with a safety contract by @orieg in #1173
fix(perf_counters): withhold an event that reads 0 only when co-scheduled (Refs #1096) by @orieg in #1177
fix(slot)!: filter kernels read metadata only from ArenaMeta slots by @orieg in #1179
fix: Judy-fidelity hygiene — derived demotion thresholds, remove SlotTag::Tombstone (breaking), scope §2.2 by @orieg in #1180
fix(map)!: remove ExpanseMap's untagged hot-metadata filters by @orieg in #1181
fix(strmap): prune sub-maps that optimistic removes drain through BranchU by @orieg in #1184
fix(sync): atomic shared accesses and raw-pointer covered writers (Refs #1086) by @orieg in #1175
fix(sync): guarded exclusive handle replaces with_locked_mut; compile-time walk modes; census coverage (Refs #1086) by @orieg in #1196
fix(sync32): readers stop borrowing the engine; published slot table; census workloads (Refs #1187) by @orieg in #1198
fix(sync): optimistic removals keep a BranchU above its demotion floor (Refs #1079) by @orieg in #1204
fix(sync): drop the tree before draining the collector by @orieg in #1206
fix(sync32): branch nodes through raw pointers and word stores; plain walks keep main's code (Refs #1187) by @orieg in #1203
fix(sync32): copy-on-write leaves in the shared writer (Refs #1187) by @orieg in #1209
fix(ci): lint reads every lane filter, and check_ci_filters enforces it by @orieg in #1217
fix(sync): widen the BranchU -> BranchB band; restores SyncExpanseBytesMap writer scaling by @orieg in #1221
fix(bench): drop search_boolean's materialized results after each timed repetition by @orieg in #1223

⚡ Performance

perf(strmap): append a terminal chunk's key bytes in one store (Refs #1096) by @orieg in #1137
perf(strmap): append a suffix entry's key bytes without memcpy (Refs #1096) by @orieg in #1154
bench(instructions): count and ordered-scan arms for the concurrent map by @orieg in #1155
bench(writer_scaling): count_locked cells for concurrent counts under a writer by @orieg in #1160
bench(patricia): prefix scans time cursor_prefix; keep the unbounded walk as an arm (Refs #1096) by @orieg in #1156
eval(patricia): counters for the 1M prefix scan's build-order gap (Refs #1096) by @orieg in #1168
bench(remove_retention): step 0a census, condense bounds and pre-registration by @orieg in #1185
bench(remove_retention): Callgrind arms for the subtree-condense spike by @orieg in #1192
eval(remove_retention): phase 3 is negative, nothing promoted by @orieg in #1195
bench(remove_retention): allocator census and rebuild arm for drained-tree retention by @orieg in #1197
perf(set,map,leaf): cut #1175's plain-path and shared-writer instruction cost by @orieg in #1201
bench(concurrency): AArch64 default vs +rcpc census and dispatch-only A/B by @orieg in #1205
eval(concurrency): AArch64 +rcpc A/B result — no material effect by @orieg in #1207
bench(wasm): re-baseline fuel counts at 152b96f; run lint on the wasm filter by @orieg in #1215

📦 Packaging & Distribution

chore(release): 0.9.0 by @orieg in #1238

🔧 CI & Tooling

ci(nightly): shard the Miri UB-site census and report a timeout (Refs #1086) by @orieg in #1140
config(discipline): recognize _self_test test entry points and Unity TEST_CASE macro by @orieg in #1147
ci(census): record the second innermost frame of bytes_two_writers (Refs #1086) by @orieg in #1149
ci(miri): split the Tier-1 Miri lane into two shards by @orieg in #1152
ci(discipline): bump orieg/discipline action to v0.12.2 by @orieg in #1150
ci(asan): keep the docs-sync test target out of the ASan core lane by @orieg in #1161
ci: gate slow lanes behind a fast lane; drafts and main pushes run it alone; trim version axes; CodeQL/Python daily by @orieg in #1183
ci(workflow): skip a push's slow lanes only when it lands a tree CI already passed by @orieg in #1186

📚 Documentation

docs(benchmarking): re-measure the drain RSS at head (Refs #1135) by @orieg in #1139
docs(sync): state where the concurrent map's pop0 fold runs by @orieg in #1164
docs(man): mem_held and shrink_to_fit are on both widths for map and set by @orieg in #1165
docs: correct README and ALGORITHMS.md against the code and committed artifacts by @orieg in #1170
docs: correct COMPAT, DATABASE and the large-value and 32-bit design docs against the code by @orieg in #1171
docs(architecture): correct technical inaccuracies against the code; gate section 10 citation symbols by @orieg in #1174
docs(visualizer): correct node layouts, thresholds, kernels and read protocol by @orieg in #1176
docs: re-derive the quiet-host libjudy table, correct occ/blobmap comments, pin drifted METHODOLOGY citations by @orieg in #1178
docs: the Sync* undefined-behaviour classes are closed on both widths (Refs #1086) by @orieg in #1218

Other Changes

test(miri): census workloads for the map's ordered reads by @orieg in #1158
test(miri): census workload for the count fold under a reader by @orieg in #1169
test(sync): check that every optimistic-reader answer is validated (Refs #1189) by @orieg in #1219
test(census): fail-then-pass records for the unreached shared stores (Refs #1190) by @orieg in #1220
fix(bench): fail closed on zero-count, empty and stale bare-metal output by @orieg in #1225
fix(bench): a kernel-released host lock, and a guard that refuses a busy host by @orieg in #1226
ci(discipline): pin v0.14.2 by commit; add agent hooks in observe mode by @orieg in #1228
fix(bench): hold the pinned CPUs at the performance governor for each run by @orieg in #1229
fix(test): pace the compactor in stale_locator_window_during_compact_fallback by @orieg in #1224
fix(ci): pin bench checkouts to a SHA the comment authorized by @orieg in #1230
fix(bench): run the self-hosted bench runners under a dedicated service account by @orieg in #1232
ci(bench): refuse a Callgrind suite on valgrind older than 3.24.0 by @orieg in #1234
ci(miri): split the Tier-1 lane into three shards; census the shards by @orieg in #1237
bench(provenance): a load window around every timed case of the single-process suites by @orieg in #1227
ci(callgrind): run the hosted Callgrind jobs under a pinned valgrind 3.27.1 by @orieg in #1236
perf(sync32): recover part of the SyncExpanseMap32 writer cost of copy-on-write leaves (Refs #1187) by @orieg in #1235

Full Changelog: v0.8.2...v0.9.0

Navigation Menu

Repository navigation

v0.9.0

Choose a tag to compare

Sorry, something went wrong.