The breakthrough was deleting the map

The previous implementation could compress 128 nearby integers into a base and a small array of differences. Then, to change one integer, it copied a location map containing every live identity. I had made the values small and left an expensive directory beside them.

That was the next useful thing to remove. The map existed because an entry could move almost anywhere during compaction. A handle remembered its identity, and the map remembered where that identity had gone. What would happen if compaction had less freedom?

The resulting Rust prototype kept the snapshot and edit-batch API while removing both the per-entry location map and the reverse array of identities. On the dense test input, container-owned heap fell from 61.5 MB to 2.66 MB. There is a small proof behind the change, and a sparse test where it loses. Both are more informative than the favorable number alone.

Remember where an entry was born#

I give each new entry a coordinate consisting of a birth-block number and a lane from zero through 127. Those coordinates are consumed once. Deleting an entry does not make its coordinate available for a replacement. A handle packs the block and lane into one 64-bit integer, with the lane occupying the bottom seven bits.

A directory finds the leaf belonging to a birth block. Inside that leaf, a bitmap records which lanes are represented in the compressed base. Values are stored densely in increasing lane order. The original lane can therefore find its current packed position by counting the represented lanes before it. That count is called rank.

The handle never promises a byte address. It names a coordinate whose current meaning comes from the selected snapshot. Local compaction can remove dead values and change the packed positions while leaving those coordinates alone.

Birth lanes:       0    1    2    3Base values:      [A,   B,   C,   D]Base mask:         1    1    1    1Live after delete: 1    0    1    1Before compaction, C is base[rank(base_mask, 2)] = base[2].After compaction: [A, C, D], with base_mask = live_mask.Now C is base[rank(base_mask, 2)] = base[1].Its handle still says birth lane 2.

This works because values stay inside their birth block and retain lane order there. Moving C into another block would require information this representation does not store. I am deliberately giving up arbitrary cross-block packing. The collection is still a bag with stable handles, but it no longer promises that compaction will pack all survivors into the fewest possible blocks.

Three masks replace the moving parts#

The edit-buffer design needs slightly more than a live bitmap. It needs to distinguish the lanes in the old compressed base from the lanes visible in the current version. A deletion changes visibility immediately; the old base need not move until a later fold.

Each leaf keeps a base mask, a live mask, and a dirty mask. Base values follow the set-bit order of the base mask. Replacement values follow the set-bit order of the dirty mask. A replacement takes precedence; a cleared live bit makes the entry absent regardless of anything left in either payload.

get(handle):    leaf = directory.find(handle.birth_block)    if leaf is absent or not live[handle.lane]:        return missing    if dirty[handle.lane]:        return edits[rank(dirty, handle.lane)]    return decode(base, rank(base_mask, handle.lane))rank(mask, lane):    return popcount(mask & ((1 << lane) - 1))

The separate base mask is easy to miss. In the example above, counting live lanes before C would return one immediately after the deletion, while C is still at base position two. Only after rebuilding does the live mask become the new base mask. Using the wrong rank would quietly return a different entry.

Three 128-bit masks occupy 48 bytes per leaf before object headers, encoding metadata, and edit values. That is not zero overhead. On a full leaf it replaces much more than 48 bytes of identity bookkeeping. On an almost empty leaf it can be wasteful.

The base still uses the previous byte-delta codec, including full-width exceptions and a raw fallback. This change does not depend on inventing another integer encoding. Repeated writes to the same lane replace one edit entry. A leaf can publish up to 32 outstanding replacements; adding a thirty-third folds the leaf into a new base.

The part that can be proved#

Call the sets represented by the three masks B, L, and E: base, live, and edited lanes. The invariant is that E is a subset of L, and every lane in L belongs to B or E. The base and edit arrays contain exactly one value per set bit, in increasing lane order.

Take any live lane i. If it is edited, its value is at the number of edit bits preceding it. Otherwise the invariant says it must be represented by the base, and its value is at the number of base bits preceding it. Both positions are in bounds because rank is exactly the position of a member in an ordered enumeration of its set.

Now collect the current live values in increasing lane order and encode that sequence. Replace B with L and clear E. For any surviving lane i, its new rank in L selects the same value we just collected for i. Dead lanes remain dead. That proves local compaction preserves every handle's observation, assuming an exact codec.

Insertion, replacement, and deletion preserve the invariant by updating their masks and packed edit arrays together. The full argument also covers empty-leaf pruning, never-reused identities, snapshot publication, and the update bound. It is a mathematical representation proof, not machine-checked verification of every instruction in the Rust implementation.

I backed that argument with a finite model. There are five legal combinations of base, live, and edited membership for each lane. On eight lanes that gives 390,625 mask states. The model checks 3,125,000 before-and-after lane observations using distinct tokens for values. It exhausts that small model; it does not exhaust the 128-lane program or every possible thread schedule.

Copy the path instead of every identity#

Removing the location map would achieve little if the directory itself were copied in full. The directory is a persistent radix tree over birth-block numbers. A branch has up to sixteen children, with another bitmap describing a packed child-pointer array. Updating a leaf copies the branches on its path and shares the rest.

That technique is established. HAMT implementations already use bitmap rank and structural sharing. Here the directory indexes blocks rather than individual entries, and the same rank idea is used again inside the numeric leaf. There is still a directory; what disappeared is the record saying where every individual entry moved.

A transaction starts by sharing the root and creating an empty map of touched leaves. The first change to a leaf copies its small mutable description. Further changes in the batch reuse that private copy. On commit, only touched leaves are installed through new directory paths.

For one replacement in an existing leaf, the implementation touches one leaf, can re-encode at most 128 values, and creates no more branches than the directory height. Each branch has at most sixteen child references. With 57-bit block numbers the height is at most fifteen; it follows the key space, not just the current live count. This is a structural work bound, not a guarantee about allocator latency or scheduling.

Identity allocation stays outside the rolled-back root. Writers reserve globally distinct birth-block tickets within the library instance and consume their lanes even if an edit aborts. A handle leaked from a failed callback cannot later identify a new entry. Exhaustion returns an error rather than wrapping. These are process-local names, not persistent identifiers to save in a file and reuse after restarting.

Measure the container this time#

The comparison uses the earlier Rust implementation and the new one on the same repeating, locally clustered integer input. Both expose stable handles, snapshots, and atomic publication of edit batches. They use the same base codec. Their compaction contracts differ, which becomes important in the next test.

A counting allocator records requested live heap bytes, including directories, node allocations, masks stored in heap objects, retained capacities, and codec buffers. It excludes allocator bookkeeping, stack objects, and resident-page effects. The caller's returned handle vector is reported separately. Construction is outside the timings. The run used Rust 1.90.0 on a shared Linux runner reporting an AMD EPYC 7763.

Keeping every returned handle adds 8,388,608 bytes to either million-entry result. Including that vector, the totals are 69,859,720 and 11,050,056 bytes. A plain vector of these integers would be smaller than either total, but would not provide the same identity and snapshot interface. Arbitrary full-width data would also change the payload contribution; this is not a universal compression ratio.

The update measurement holds an old snapshot, replaces one existing value, and checks that the old snapshot remains unchanged. Each row below is the median of seven successive updates to the same handle. The allocator instrumentation adds work to allocation-heavy paths, so the elapsed times are measurements of these instrumented builds, not a clean estimate of production speed.

At the largest size, the median elapsed update was 8.186 milliseconds for the earlier container and 0.521 microseconds for the ranked one. The earlier design was doing an avoidable full-map clone; these numbers expose that defect rather than show that a new collection outruns all existing persistent structures. A persistent location map is an obvious alternative baseline, and I have not measured that control.

Scattered handle lookups also improved in this run, from about 390 to 89 nanoseconds per query at the largest size. Those are batched throughput figures using the same deterministic probe sequence, with snapshot acquisition outside the timer. The raw samples and reproduction source accompany the article. Seven samples on one shared runner do not establish a general hardware ranking.

The test that makes it lose#

Then I removed 127 entries from every original group of 128 and compacted. There were 8,192 survivors, spread across 8,192 birth blocks. The previous container could collect those survivors into a small number of dense chunks. The ranked version had to keep a leaf for each original block.

Its requested owned heap was now 1,588,296 bytes, versus 488,357 bytes for the earlier container: roughly 3.25 times as much. Dead payload had been released, but leaf headers and directory structure remained. After removing every remaining entry, the ranked root pruned all leaves and retained only 72 heap bytes in this build.

This is the price of the rule that made the proof short. Birth-local storage works best when related entries survive together or an application releases whole groups. Heavy churn leaving isolated survivors is an adverse workload. A more general design could add relocation metadata for sparse groups, but that would be another representation with another proof and benchmark, not a capability this prototype already has.

The caller still sees an edit batch#

The physical coordinates remain private. The caller receives handles, captures a snapshot, and performs edits in a closure. In the small example below, the outlier can change the leaf's encoding during compaction without changing the surviving handle.

use birth_ranked_bag::{Bag, Error};fn main() -> Result<(), Error> {    let (bag, ids) = Bag::from_values([1000, 1001, 1002])?;    let before = bag.snapshot();    bag.edit(|tx| {        tx.remove(ids[0])?;        tx.set(ids[2], 4_000_000_000)?;        Ok(())    })?;    bag.compact()?;    assert_eq!(before.get(ids[0]), Some(1000));    assert_eq!(bag.snapshot().get(ids[0]), None);    assert_eq!(bag.snapshot().get(ids[2]), Some(4_000_000_000));    assert_eq!(bag.snapshot().sorted(), vec![1001, 4_000_000_000]);    Ok(())}

The exact snippet is compiled and executed by the example's CI. The implementation also passes a 20,000-step reference-map trace with retained snapshots, tests at lane boundaries, callback-panic rollback, aborted and foreign handles, and four concurrent writers. The scalar-only build runs the same behavior checks. This follow-up implements the new representation in Rust; it does not claim a corresponding new Haskell benchmark or port.

Sorting materializes an ordered vector without changing the internal birth coordinates. There is no promise of a single contiguous slice for the whole bag, nor constant-time access to the nth live entry after arbitrary deletions. Those were different promises from looking up a stable handle, and the API does not disguise the distinction.

What happens to SIMD and concurrent readers?#

The block consumer decodes a base once, combines replacements and live lanes into bounded scratch storage, and passes a compact slice to its callback. It reuses the previous optional AVX2 decoder and scalar fallback. That keeps vector decoding possible, but this experiment did not establish a new SIMD throughput result. Merging sparse lanes remains work, and this version allocates individual leaves rather than a large coallocated slab.

The masks are ordinary immutable fields once published. Two writers do not concurrently flip different bits in the same shared mask. A writer mutex protects the whole private edit and commit; the publication lock protects replacement of one root. A reader retains that root through an Arc and then walks an internally consistent version. Writer throughput is still serialized, and old snapshots can keep old nodes and payloads alive.

A short update path does not eliminate eventual reclamation. Dropping an old snapshot after many changes can release substantial storage. Whole-bag compaction also visits every retained leaf. Those costs belong in a workload-level benchmark before adopting the structure for latency-sensitive code.

A breakthrough in this project, with recognizable ancestors#

I looked for prior work before describing the result as a new data-structure family. Bitmap-ranked arrays and path copying are familiar in HAMTs. The 2015 CHAMP work by Steindorfer and Vinju explores compact immutable trie representations. Slotmap already makes stable-key and dense-storage tradeoffs explicit.

Lance's row-ID specification is especially close conceptually: it describes stable IDs, ranges with holes, and range bitmaps. It also describes translating IDs to current physical addresses as data moves across fragments. The local no-relocation contract here is a meaningful implementation distinction, but it does not establish historical priority.

Separating compressed data from updates likewise has established precedents, including DuckDB's compressed-data concurrency design. The prior-art audit records these overlaps and the unmeasured alternatives. I have not proved that the complete combination is historically novel, and the article does not claim that it is.

What I can establish is narrower and useful: under the birth-local contract, handles survive compaction without a per-entry relocation table, updates copy one leaf and a directory path, and the working implementation removes a measured cost from the earlier prototype. The sparse counterexample tells us when that bargain becomes expensive.

I had spent several experiments trying to store the same relocation information more cheaply. The useful turn was to stop allowing some of the relocations. Once the layout had a rule, a few masks could remember what a large map had been recording entry by entry.