sefer-region

100 % Rust typed handle-addressed store — no C / C++ libraries.

A thin typed membrane over slotmap: values live in slotmap's slot array (resolved by a single indirection), but removed entries leave tombstone holes — iteration skips them, so the backing store is NOT always-compact. Every operation exposes only typed Handle<T> values — raw DefaultKeys never escape as usable values through the API (Debug output renders the underlying key for diagnostics only — it cannot be turned back into a functioning handle through this crate's public surface). The original single-threaded face of sefer-alloc, extracted as a standalone crate.

Runtime relationship to sefer-alloc: This crate exists as a public surface for sefer-alloc (the workspace root crate re-exports Region, Handle, and SyncRegion from this crate), but it is not used by the sefer-alloc allocator runtime itself. Empirically verified by searching the allocator source code (src/) in the main workspace: no direct calls into Region/Handle/SyncRegion on any hot path. Further API evolution is intentionally deferred until a confirmed external consumer requests it — this crate will not be polished in anticipation of needs that have not been demonstrated.

Why?

slotmap's DefaultKey is untyped: a key from one map compiles against another map of a different value type without error. sefer-region wraps it in Handle<T> — a PhantomData<fn() -> T>-branded key plus a region_id — so the compiler rejects cross-type handle confusion at the type level (a Handle<Foo> cannot be used where a Handle<Bar> is expected), and the runtime region_id check rejects cross-instance handle confusion at the value level: a Handle<T> minted by one Region<T> is rejected — treated exactly like a stale handle (None/false, never a panic) — by every other Region<T> of the same type, even when its raw DefaultKey collides with a live key in that other instance (as it commonly does — the first insert into any fresh Region tends to produce the same key). This doubles Handle<T>'s size from 8 to 16 bytes on a 64-bit host (12 bytes on 32-bit) versus the pre-0.2.0 layout.

The differentiator for the pure-Rust audience: zero own unsafe — #![forbid(unsafe_code)] at the top of this crate. The internal unsafe lives upstream, in the mature, widely-used slotmap crate, not in this one. No C / C++ libraries are pulled in. With default-features = false the crate builds under no_std + alloc.

For users who want a typed slotmap-like handle store without pulling a full allocator stack.

Quick start

[dependencies]
sefer-region = "0.1"

use sefer_region::{Region, Handle};

let mut region = Region::new();
let h: Handle<String> = region.insert("hello".to_string());

// I1: fresh handle resolves to the inserted value.
assert_eq!(region.get(h).map(String::as_str), Some("hello"));

let v = region.remove(h).unwrap();
assert_eq!(v, "hello");

// I2 + I3: stale handle resolves to None.
assert!(region.get(h).is_none());

Invariants

• I1 — resolution: a fresh handle resolves via get to the inserted value until it is removed.
• I2 — tombstone: after remove(h), get(h) returns None for roughly 2^31 reuse cycles of that slot (a stale handle that has survived that many insert/remove cycles may wrap and spuriously resolve to a later value). A second remove(h) is a no-op None.
• I3 — no ABA: a stale handle — one whose slot has since been reused for a new value — does not resolve to the new value for roughly 2^31 reuse cycles of that slot. slotmap's DefaultKey carries a generation counter bumped on removal, so the old handle fails the version check and yields None. After ~2^31 cycles the generation wraps and a very old handle may alias a later value. Memory safety is never affected.
• I4 — accounting: len() equals the number of live entries; is_empty() agrees.
• I5 — drop-once: every live value is dropped exactly once. Successful remove transfers ownership to the caller without calling Drop; values still owned when a normally-destroyed Region drops are dropped. The crate never duplicates or internally forgets values.
• I7 — instance isolation: a Handle<T> resolves only through the Region<T> instance that minted it. Every accessor (get, get_mut, remove, contains) stamps its region_id at construction and checks it before touching the backing slotmap; a handle from a different Region<T> is rejected exactly like a stale handle (None/false), even when its raw DefaultKey collides with a live key in this region.

SyncRegion (std feature, default-on)

SyncRegion<T> wraps Region<T> in a std::sync::RwLock for safe concurrent access. It recovers from lock poison rather than propagating it (a panicked op leaves the slotmap structurally intact). Poison recovery guarantees container integrity only — an interrupted operation may have left partial effects visible (e.g., a panicking T::Drop during clear() leaves the region partially cleared, with the exact surviving set an unspecified slotmap-version-dependent detail, not a stable contract).

use sefer_region::SyncRegion;
use std::sync::Arc;

let sr: Arc<SyncRegion<u32>> = Arc::new(SyncRegion::new());
let sr2 = Arc::clone(&sr);

// One-shot convenience: no guard needed for single operations.
let h = sr.insert(42u32);
assert_eq!(sr.get_cloned(h), Some(42u32));
assert_eq!(sr.len(), 1);

// Multi-op transaction: hold the write guard for interleaving isolation
// (serializes the critical section). Panics mid-transaction do NOT roll
// back already-applied changes — all-or-nothing rollback is not provided.
{
    let mut w = sr.write();
    let _ = w.insert(1u32);
    let _ = w.insert(2u32);
} // guard dropped, lock released

assert_eq!(sr.len(), 3);

Note: SyncRegion uses blocking std::sync::RwLock, which is not async-aware. For async runtimes (e.g. tokio), see the "Async runtimes" section in the SyncRegion type documentation (docs.rs) for concrete hazards and recommendations.

Feature flags

Disable default features for no_std + alloc (Region<T> + Handle<T> only):

sefer-region = { version = "0.1", default-features = false }

Performance

Measured with bench-scale-tool (a fixed-iteration harness — the iteration count is calibrated once and pinned, so run time is a direct speed signal, not a statistical estimate). Single noisy Windows dev host, 3 runs each; the table below shows the median, with the observed min–max range in parentheses so the numbers aren't read as more precise than they are. Measured on commit 0c83f14 (after F1's region_id widening to usize and F2's domain-aware Handle<T> identity redesign — every accessor now checks region_id before touching the slotmap; this is NOT the final pre-publish SHA, F8-F10/ F12-F19 have not landed yet, but it is the first re-measurement since F2):

Note: The insert and remove rows above are measured with bench_batched, which means the fixture (a fresh Region/SyncRegion) is dropped inside the timed window — these numbers include allocation, teardown, and cold-path overhead, not just the steady-state operation cost. See the steady-state churn rows for the warm-path performance.

get (wrong-region handle) is the rejecting path F2 added: since the domain-aware Handle<T> identity redesign (task #802), every Region::get/get_mut/remove first compares the handle's region_id against the region's own before touching the slotmap at all. The wrong-region row above (st/get_wrong_region in benches/region_bench.rs) times a handle minted by a second, distinct Region passed to .get() on the first — it is cheaper than both the hit and same-region-stale rows here (the region_id mismatch short- circuits before any slotmap generation check), so the new safety check adds no cost on the rejecting path and is within noise on the accepting path (compare this table's get_hit/ get_stale numbers to their pre-F2 counterparts three revisions back in this file's git history — same ~5 ns/op order of magnitude).

Region::new() under thread contention

Region::new() mints its region_id from one process-wide AtomicUsize counter (NEXT_REGION_ID, fetch_update — a CAS retry loop since task #813's exhaustion fix) — the only state the F2 redesign added that is shared across threads. Measured with a barrier-aligned fixed-work harness (5 samples, 200k iterations/thread):

• 8 threads: 6.68M Region::new() calls/sec (median), ~85% throughput penalty vs. a no-contention baseline (see docs/perf/R827_REGION_NEW_CONTENTION_GATE.md for full methodology and all thread counts). The baseline arm (which isolates the SlotMap allocation and handle-minting work from the shared atomic) scales near-linearly to 43.4M ops/sec at 8 threads, while the real Region::new() arm stays flat (6.6M-7.0M ops/sec) regardless of thread count — the NEXT_REGION_ID contention bottleneck saturates almost immediately.
• The historical pre-#813 harness (measuring the old fetch_add mechanism) reported ~13.9M ops/sec at 8 threads, but that measurement had fidelity gaps (no barrier-aligned start, no baseline, Instant::elapsed() inside the hot loop — see docs/reviews/2026-08-11-sefer-region-static-release-audit.md §P-perf-3). Reproduce: cargo bench -p sefer-region --bench region_new_contention_gate

Contended reads

Under multi-threaded read contention, SyncRegion's one-shot convenience methods (get_cloned, contains, len, is_empty) anti-scale: each call pays a shared-cache-line lock acquisition that dominates the nanosecond-scale lookup. Batching reads under one read() guard restores flat scaling. Single noisy Windows dev host, 3 runs each (median reported):

Provenance: Measured by examples/contended_reads.rs (one-shot vs. batched reads at 8 readers). A later gate (docs/perf/R828_STRUCTURAL_LEVERS_GATE.md §2) measured the same question with r828_batch_guard_probe.rs and found 9.15× — explicitly recorded as an open discrepancy, not silently reconciled. Do not treat the 31.6× ratio derived from the table above as a stable measurement without consulting the R828 gate's analysis.

Reproduce: cargo run --release --example contended_reads -p sefer-region.

Note on SyncRegion steady-state churn's range: the landing commit's own message cites a wider spread (~69.6-84.2 ns/op) than the table's published 3-run median-of-3 (72.1-84.2) for the same workload — a broader across-multiple-runs sample was taken while iterating on the fix, of which the table publishes only the specific 3 runs the median is drawn from. Re-measured independently while auditing this note: three fresh runs came back 83.60-86.17 ns/op, a third distinct range again — this workload's absolute number visibly drifts on this single noisy dev host from one measurement session to the next, more than most other rows in this table. Treat the published range as an order-of-magnitude anchor for this specific workload, not a tight bound.

Iteration cost scales with high-water mark, not live count: the three Region::iter rows measure the same 1,000 live values, but with different hole percentages (0%, 50%, 90%). Since the underlying slotmap provides no shrink operation, iteration cost is proportional to the slot-array length, which stays at the historical high-water mark of live entries. The 50%-holes case (2,000 high-water mark) is ~1.9× the zero-holes baseline; the 90%-holes case (10,000 high-water mark) is ~8.7×. The only way to reclaim that cost is to build a fresh Region and re-insert (which invalidates every outstanding handle from the old one).

get's single-indirection lookup is roughly 30–60x cheaper than insert, consistent with slotmap::SlotMap's own documented lookup/churn tradeoff (see docs/BENCHMARKS.md in the parent workspace for the container-choice comparison this crate's backing store was picked from). Reproduce: cargo bench -p sefer-region --bench region_bench (add -- --calibrate <secs> to recalibrate the pinned iteration counts in bench-iters.txt first, or -- <substring> to run/time one workload — e.g. -- st/insert runs only Region::insert, never SyncRegion::insert, since the two prefixes are chosen to never be substrings of one another).

Wrapper overhead: measured, not assumed

Region<T> is documented as "a thin typed membrane" that "delegates every operation to slotmap" — but that was a design claim, never actually measured against the type it wraps. benches/region_bench.rs also runs raw/insert/raw/get_hit/raw/remove directly against a bare slotmap::SlotMap<DefaultKey, u64> (Region's own backing type, no Handle<T> involved) as an A/B baseline. Re-measured on commit 0c83f14 (same session as the table above, F2's region_id check now included on every st/* accessor — raw/* has no such check, so this comparison now also isolates F2's cost, not just the Handle<T> membrane). Median-of-3: st/insert 306 ns/op vs raw/insert 356 ns/op; st/get_hit 5.41 vs raw/get_hit 5.78; st/remove 115.03 vs raw/remove 118.61 — the wrapped numbers are consistently at or below the raw numbers across all three pairs in this run, still fully inside the ~15–25% run-to-run noise this dev host already shows elsewhere in this table: across the same three runs st/insert ranged 299–311 ns/op and raw/insert ranged 287–359 ns/op, i.e. the two distributions overlap. No measurable wrapper overhead — including F2's added region_id check — was found. None of Region's methods carry an explicit #[inline] hint; since every method is generic over T (so its MIR is available for cross-crate monomorphization regardless) and each is a short, straight-line delegation (now including the region_id comparison), LLVM's own size-based inlining heuristic already inlines them at the release optimization level this bench (and any real consumer's release build) uses. Investigated so this stays a checked fact rather than an assumption — no code change was made, because none was supported by the measurement.

Capacity growth (verified, not assumed)

Measured with captrack (tests/captrack_probe.rs, run manually — slotmap::SlotMap isn't one of captrack's natively-wrapped collection types, so this drives its public registry API directly rather than the usual macros):

• Organic growth (Region::new(), 1,000 sequential inserts): capacity grows geometrically — 3 → 127 → 255 → 511 → 1023 — landing at 1,023 for 1,000 live values (~2.3% overhead), not the tight-fit guess a caller might otherwise assume.
• Churn is genuinely free-list-bounded, not just documented as such: inserting 1,000, removing every other one, then inserting 500 more measured capacity staying flat at 1,023 through the whole cycle — the refill reuses freed slots rather than growing past the prior high-water mark. (Region::reserve's own doc comment already claimed this; this is the first time it was actually measured rather than trusted.)
• Region::with_capacity(n) reserves exactly n up front for realistic n — no intermediate reallocation for a workload that stays within it. If you know your workload's peak live count ahead of time, pre-sizing avoids the ~2.3% organic-growth overhead entirely. (Fallible alternatives: Region::try_new, Region::try_with_capacity, and Region::try_reserve are available for recovery from capacity-limit and region-id exhaustion.)

Reproduce: cargo test -p sefer-region --test captrack_probe -- --ignored --nocapture.

Safety

#![forbid(unsafe_code)] at the top of this crate. The internal unsafe lives upstream, in the slotmap dependency, not in this crate -- this crate contributes zero unsafe blocks and pulls in no C / C++ libraries. No version-scoped audit record for slotmap is tracked by this project; slotmap is a mature, widely-used dependency, and this crate's own cargo-deny CI check covers advisories/licenses/sources of the current lockfile (not a substitute for a code audit).

License

Licensed under either of:

• MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)
• Apache License, Version 2.0 (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)

at your option.