The list now has an edit buffer

The first test I wanted was simple: save a snapshot, change a number, and read both versions. The saved snapshot should still contain the old number. The current collection should contain the new one. Deleting the entry, adding another, and compacting the storage should not change that answer.

That test now has a Rust implementation and a Haskell implementation. The two APIs look a little different, but they make the same distinction between owning a changing collection and reading one immutable version of it. The code is in the companion example, with executable demos and tests.

In the previous article, I proposed keeping compressed values in immutable chunks and collecting edits separately. That avoids immediately destroying a block's compression when one replacement falls outside its narrow range. Building it forced several less attractive decisions into view: identity has a cost, publishing a lazy value can publish unfinished work, and an append buffer needs a policy for small commits.

This is an experimental bag of unsigned 32-bit numbers. It supports duplicates and does not promise an iteration order. It is not a generic container for arbitrary objects, a durable database, or a replacement for every vector. The useful result is a working contract that we can now test and optimize.

The user gets handles, not chunk coordinates#

I kept physical positions out of the public API. Insert returns an opaque handle. Reading through that handle means looking it up in a particular snapshot. A deleted handle is absent from newer snapshots and may still be present in an older one. Compaction moves storage without changing surviving handles.

That decision avoids pretending that the fifth live entry is necessarily physical slot five. Deletion leaves a hole. Iteration skips the hole, while dense materialization is an explicit operation. A sorted result is another explicit operation; it does not rearrange an existing snapshot.

Rust returns Option<u32> for a snapshot lookup and Result for a fallible edit. Haskell uses Maybe Word32 and Either Error. A missing, deleted, or foreign handle cannot silently turn into access to another entry. Constructors for handles and published state stay private.

A batch in Rust#

The Rust crate has no third-party dependencies. A writer works on private transaction state and publishes only after its closure returns success. The companion demo performs this batch and compares its final counts and sums with an independent calculation in the test script. The article examples are compiled separately as well.

use edit_buffer_bag::{Bag, Error};fn main() -> Result<(), Error> {    let (bag, ids) = Bag::from_values((0..128).map(|i| 1_000_000 + i))?;    let before = bag.snapshot();    let added = bag.edit(|tx| {        tx.set(ids[0], 4_000_000_000)?;        tx.remove(ids[1])?;        tx.insert(42)    })?;    let after = bag.snapshot();    assert_eq!(before.get(ids[0]), Some(1_000_000));    assert_eq!(after.get(added), Some(42));    bag.compact()?;    assert_eq!(bag.snapshot().get(added), Some(42));    Ok(())}

set and remove return the previous value. update takes a function of the transaction's current value, so a counter increment does not have to read a possibly stale snapshot before acquiring writer ownership. Repeated writes to a slot replace its visible edit. Writing its encoded value back removes the edit altogether.

Returning an error discards the private state. An unwinding panic inside the closure does the same. This does not roll back an email, a file write, or another side effect performed by the closure; only the bag is transactional. A process abort, including an aborting panic configuration, is outside that recovery guarantee.

There is a less obvious failure case: the closure can copy a newly issued handle into an external variable and then fail. If the next successful transaction reused that identity, the leaked handle could suddenly become valid. The Rust implementation reserves identities from a process-wide checked counter and never recycles them, including reservations from failed edits. Exhaustion reports an error rather than wrapping.

The same boundary in Haskell#

The Haskell module exposes an Edit monad with a hidden constructor. Its public operations describe changes to one bag; there is no exported liftIO. The owner runs that description, constructs a new root, and publishes it only on success. The implementation uses the base, array, containers, and deepseq libraries shipped with the tested GHC installation.

import qualified EditBufferBag as Bmain :: IO ()main = do  (bag, ids) <- B.fromList [1000000 .. 1000127]  before <- B.snapshot bag  result <- B.edit bag $ do    _ <- B.set (head ids) 4000000000    _ <- B.remove (ids !! 1)    B.insert 42  added <- either (fail . show) pure result  after <- B.snapshot bag  print (B.get before (head ids)) -- Just 1000000  print (B.get after added)      -- Just 42  compacted <- B.edit bag B.compact  either (fail . show) pure compacted

Those list indexes select handles from a known nonempty constructor result. The collection itself is read by handle. For an unknown input, the caller should pattern-match on the returned handle list rather than assume two entries exist.

The stored numeric payload is not a linked Haskell list. Byte differences and exception values live in unboxed arrays. The public list returned by values is an interface for iteration and materialization. The block fold is the alternative for consumers that do not need a collection-sized result.

Haskell also adds a publication question that the Rust version does not have in this form: has the next value actually been evaluated? The MVar documentation warns that putting a thunk in an MVar can move its evaluation onto the reader. Here that could mean moving encoding work, or an exception, past the apparent commit point.

The initial implementation takes a conservative approach. It forces the next root and the action's result before publishing, and edit requires NFData for that result. A test deliberately returns a deferred error after changing a value and verifies that the old root remains current. There is a cost: forcing the root traverses metadata, even for a small batch. That is explicit technical debt rather than a claim that immutable updates are free.

Handles use the actual opaque Unique value, not its hash. They are process-local identities, not a portable serialization format. Neither implementation promises that a handle can be written to disk and recovered in another process.

What goes into a chunk#

Both implementations use 128-value compression blocks, logical chunks of up to 1,024 positions, and at most 32 visible replacement entries per chunk. These are deliberately modest prototype settings, not a new benchmark showing that 1,024 beats the 16,384-value allocation chunks from the earlier experiment.

A block chooses a base covering the largest cluster within a range of 255. Ordinary values become byte differences. An outlier gets a byte-sized position and its complete 32-bit value in separate packed streams. If those numeric buffers would occupy at least as much space as the raw values, the block stays raw.

For a full 128-value block, the encoded numeric contents occupy 132 + 5k bytes for k exceptions. With one exception that is 137 bytes; raw values occupy 512 bytes. These figures exclude the codec enum or constructor, allocation headers, buffer descriptors, identities, and deletion information. They also use a different accounting boundary from the proposed eight-byte serialized header in the previous article. The prototype has no wire format.

Choosing the dominant cluster matters. If 127 values are near one million and one value is zero, using the global minimum would make the ordinary values awkward. The encoder can keep a base near one million and store zero as an exception. Rust uses widened arithmetic and checked subtraction; Haskell uses widened arithmetic for range decisions. Values near the largest 32-bit number are tested too.

Patched integer representations have a substantial history, including Lemire and Boytsov's SIMD compression work. This codec is intentionally much simpler than FastPFOR. The experiment combines a small codec with an ownership and publication API; it does not introduce a new integer-compression algorithm.

Folding edits is different from closing holes#

Replacing one entry records a logical edit without modifying the encoded base. On the thirty-third distinct outstanding replacement in a chunk, the implementation folds replacements into a new encoding and clears that overlay. It retains the existing slot identities and deletion bits. A lookup never has to search an ever-growing chain of published edit buffers.

Deletion clears the entry from the new root's identity map and sets a bit in the chunk's deletion mask. It does not import a distant tail value into the block. Every prototype chunk has a fixed 128-byte deletion bitmap, even when untouched. Making the all-live case implicit would save that storage; the implementation has not yet done so.

Explicit compaction gathers the live entries, rebuilds their chunks, and reconstructs the handle map. The prototype does not globally re-sort those entries to manufacture better compression. Old snapshots retain the old structure. The new snapshot has no physical holes and no pending replacement overlay. The rebuilding work is real: repeated tree-map insertion adds logarithmic work per entry, and compaction uses a live-entry workspace.

Appending needs its own compromise. New values first enter the transaction's pending map. At commit, a partial final chunk is rebuilt together with those new entries, then full chunks are appended. Without that rule, a sequence of one-value commits could leave one allocation group per value. With it, small commits can repeatedly rebuild the tail. Batching is consequently part of using the API well, not just a convenient spelling.

One root, two synchronization jobs#

The Rust owner has a writer mutex and a separate RwLock<Arc<Root>> for publication. Writer admission covers the whole read-modify-publish operation. The publication lock is held only while obtaining or replacing the current root. The Haskell owner uses a writer-admission MVar and another MVar containing the current snapshot.

This lets a reader acquire the previous committed root while a writer is preparing private changes. Once acquired, a snapshot needs no collection lock for lookup or scanning. Rust's Arc retains shared allocations, and Arc::make_mut copies a touched chunk descriptor when necessary. Haskell relies on immutable values and garbage collection. Neither lifetime scheme means old data disappears as soon as the new root is installed.

The writer publishes a compatible set of chunks, edits, deletion bits, and identity locations together. Two writers cannot both start from the same root and silently replace each other's results, because the second waits before reading its starting version. Compaction follows the same writer path.

This is intentionally serialized writing. It provides neither lock-free progress nor independent concurrent mutation of different chunks. A long callback delays other writers. Recursively calling edit on the same Rust bag from inside its edit closure can deadlock and is forbidden by the API documentation; taking a snapshot inside that closure is allowed and observes the previously published version.

Rust mutex poisoning also needs an explanation rather than an automatic unwrap. A panic can poison the writer-admission mutex, but published state was never edited through that guard. The implementation can recover admission because the incomplete work was private. That reasoning depends on this exact ownership design; it is not general permission to ignore poisoned mutexes.

The design borrows the separation of compressed data and changes from systems such as DuckDB, but not its transaction engine. There is no persistence, recovery log, conflict detection between independent writers, or database-level durability here.

A scan gets a block, not an index lookup per value#

The Rust entry iterator owns a reusable 128-value scratch array. It decodes a block, applies codec exceptions and visible replacements, and skips deleted lanes. It does not resolve a handle through the global map for every entry in the scan. A lower-level for_each_block callback receives the decoded values and a live-lane mask.

On x86-64 with AVX2 available, the optional Rust decoder loads eight difference bytes, widens them to eight 32-bit lanes, adds the base, and writes into that scratch array. Runtime detection guards the specialized function. Incomplete batches take the scalar path, so no load requires bytes beyond the allocated slice. Disabling the default SIMD feature exercises the portable implementation.

The Haskell block fold uses a bounded unboxed array per decoded block. Its implementation is scalar and currently performs bounded edit-map lookups while constructing those values. It has the same visible-value semantics, but it is not an instruction-for-instruction port of the Rust kernel. No performance comparison between the languages is claimed.

This is also less aggressive than the earlier fused decode-and-consume benchmark: Rust writes to a small scratch buffer before the consumer runs. It avoids a full-collection decoded allocation, but register-only fusion remains an optimization to investigate. A live mask does not authorize evaluating partial operations or side effects on deleted lanes.

The uncomfortable part of the memory bill#

The numeric buffers can be small while the whole container remains large. Rust retains a 64-bit identity for every physical slot and a B-tree mapping live identities to chunk and slot coordinates. Haskell retains handle references and tree maps with their own nodes. Both have chunk descriptors, overlays, deletion masks, and runtime allocation overhead.

The logical chunk is a rebuild and ownership boundary. It is not yet one coallocated slab: encoded blocks have separate primitive buffers. That matters given the earlier measurements of tiny allocations. A grouped buffer arena could improve locality, but it would be a subsequent representation change, not something this code already demonstrates.

There are straightforward costs in the publication path too. Rust clones the live identity map and chunk directory when beginning a transaction, while sharing unchanged payloads. Haskell can share tree structure but currently traverses the root to force it before publication. A one-entry edit therefore does not have constant cost in the collection size in either implementation.

The exposed statistics deliberately separate encoded numeric bytes from replacement counts, physical slots, live entries, and bitmap bytes. They do not present a fake total-heap estimate. A raw vector may be smaller and faster for many workloads, especially when stable identities and retained snapshots were never required.

What the tests establish#

Each language has a seeded 5,000-step model test. It mixes inserts, replacements, removals, snapshots, failed batches, and compaction, comparing visible entries against a plain map. It also keeps earlier snapshots and checks that later work has not changed them.

The focused tests cover empty collections, block and chunk boundaries, low and high outliers, every block length through 128, deletion masks, raw fallback, repeated replacements, foreign handles, and compaction preserving identity. The Rust suite also compares scalar and selected SIMD decoding and checks that a leaked handle from an aborted batch never aliases a later insertion.

Both implementations run four writer threads incrementing a pair of values in batches. Readers acquire one root and require the two values to agree. The final count checks for lost updates. Haskell additionally tests an asynchronous cancellation during private editing; Rust tests an unwinding callback panic and subsequent successful use of the owner. Cancellation after publication is different: the new state may already be visible even if the caller does not receive a success result.

The test script builds optimized and unoptimized Rust configurations, a scalar-only Rust configuration, and the Haskell tests with warnings treated as errors. Haskell runs with one and two runtime capabilities. Both demos must match values calculated independently in Python. These checks exercise particular schedules and inputs; they are not a proof of every concurrent execution, and they provide no throughput benchmark.

The part worth keeping#

The implementation gives the earlier proposal a usable boundary: collect edits in one place, publish one version, and make readers choose a snapshot. A caller does not need to decide when a numeric block becomes raw or how its exceptions are stored. It does need to decide how long to retain a snapshot and when a batch is complete.

The next optimization should earn its place against this implementation: a cheaper identity map, coallocated chunk buffers, a stricter bound on retained versions, or a better block consumer. There is now code to compare against, and tests that say what those optimizations are not allowed to change.