Give the list an edit buffer

The compact list had acquired an inconvenient habit: removing a value could make it larger. A block of numbers near one million fitted into a four-byte base and an array of byte-sized differences. Then deletion filled a hole with a value from the end of the collection. That value happened to be near four billion. The block no longer fitted.

This was a perfectly valid operation for the unordered bag I started with. It was a bad operation for the assumption its compression relied on. Splitting the payload into separately allocated chunks limited how much had to move, but it did not explain how a compressed chunk should handle changes.

I went looking at integer codecs and analytical databases. Both have encountered versions of this problem. The direction I would try next gives ordinary values a compact home and gives changes somewhere else to wait. The useful question becomes how much waiting we can afford, and what readers are allowed to see in the meantime.

Let one value be awkward#

Our earlier byte-or-raw policy was deliberately blunt. If all 128 values fitted within a range of 255, the block compressed. Otherwise it became raw. One outlier could therefore change a 132-byte payload into a 512-byte payload. That was a property of the policy, rather than an unavoidable consequence of the outlier.

Patched integer encodings keep a narrow representation for ordinary values and record exceptions separately. Lemire and Boytsov's work on SIMD binary packing and FastPFOR explores this tradeoff, including keeping small blocks while grouping exception storage over larger pages. Its results concern those codecs and workloads; they do not establish the speed of our mutable bag.

A simpler variant is enough to see the opportunity. Keep one byte per position. At an exceptional position, put a harmless placeholder in that byte and store the actual 32-bit value elsewhere. The exception also needs a location. Within a 128-value block, a byte-sized position is sufficient, although only seven bits are needed mathematically. A short list of positions costs less than a bitmap when exceptions are rare.

For a concrete storage calculation, give every block an eight-byte header, including its base, codec tag, and exception count. A position-list version needs 136 + 5k bytes for k exceptions. A bitmap version needs 152 + 4k: the same header and byte payload, a 16-byte bitmap, and the exceptional values. A raw block with the same header needs 520 bytes.

At one exception, 141 bytes is a more reasonable outcome than 520. At sixteen exceptions, the two location representations tie. At ninety-two, even the bitmap form has caught up with raw storage. Real selection should also compare wider differences and decoding cost; the smallest byte count need not produce the fastest block.

The base needs care too. If a single low outlier becomes the new minimum, nearly every formerly ordinary value may become an exception. During editing I would keep the old base. During rebuilding I would consider a base covering the dominant cluster, along with wider and raw alternatives. An exceptional value can be below the base because its full value is stored separately. No unsigned subtraction should silently wrap into a valid delta.

An encoding exception is not an edit#

A four-billion-valued entry might have been present since construction. That makes it an encoding exception. An entry changing from 1,000,010 to 1,000,011 is an edit, even though both values fit the byte encoding. These cases can share machinery eventually, but they answer different questions: how is a value represented, and which value belongs to this reader's view?

DuckDB's 2024 description of analytics-oriented concurrency makes the difficulty concrete. Because its stored data is compressed, it keeps changes separately, with version information grouped by column and batches of 2,048 rows, and incorporates changes during checkpointing. That is a database design with transaction machinery we do not need to reproduce. The relevant precedent is that efficient reads need not require editing compressed bytes in place.

For the numeric bag, I would keep immutable encoded chunks, a bounded overlay of replacements, and deletion information. New values enter an ordinary mutable append buffer. A writer can coalesce repeated replacements of the same slot before publication. Ten writes to one entry then need one visible replacement, unless the API explicitly promises access to the intermediate versions.

The reader checks visibility, then replacements, then the base. A slot here is a location in one snapshot, not a permanent identity. A real handle resolves through the map owned by that same snapshot. After compaction, the next snapshot may map the handle elsewhere.

// Resolve the handle using this snapshot's identity map first.read(snapshot, slot):    if snapshot.deleted(slot):        return missing    if snapshot.edits.contains(slot):        return snapshot.edits[slot]    return decode(snapshot.base, slot)

I would not turn this into an unbounded linked list of little edit buffers. A point lookup should not grow another search step after every publication. Merge visible replacements into a bounded structure per chunk, or rebuild that chunk. Cheap writes are useful only while the deferred work remains under control.

Leave holes until moving them is worthwhile#

A deletion mask avoids importing a distant value into a tightly clustered block. The deleted slot remains physically present until compaction, but scans exclude it. If every position in a 16,384-value chunk has a bit, that mask takes 2,048 bytes. Compared with the all-byte chunk's 16,896 bytes of bases and differences, it adds about twelve percent. Even a one-bit flag is worth counting once the values themselves are this small.

Untouched blocks can mean all-live without a bitmap; affected blocks can allocate a bitmap or short deletion list. The descriptors that distinguish those cases still cost space. A deletion bitmap is also different from a null bitmap: a null entry remains an entry, while a deleted one must disappear from the bag's visible contents.

This choice changes indexing. A handle can still resolve to a slot, but the fifth live element is no longer necessarily slot five. Dense positional indexing needs counts and rank/select machinery, or a materialized view. I would offer handle lookup and a live iterator during editing, and make a dense positional view an explicit operation. Otherwise the interface hides the exact cost the representation introduced.

During compaction, an unordered bag can regroup nearby numeric values before encoding new blocks. That may improve their ranges, at the cost of grouping work and a new identity-to-location map. It is legal only when physical iteration order is genuinely unspecified. Stable output needs a separate ordering key or view, and callbacks with visible ordering effects cannot be shuffled without permission.

Make the scan understand the representation#

The per-entry reader is useful for explaining semantics, but I would not implement a large scan by calling it repeatedly. The earlier SIMD experiment worked because a whole group of byte differences fed directly into its consumer. Searching an edit hash table for every lane would add work to the part we had just simplified.

Group visible edits by block and position before publishing a scan-friendly snapshot. An untouched block uses the ordinary decoder. A patched block applies its encoding exceptions, then its visible replacements, then its deletion mask. That can happen in registers or a small reusable scratch buffer. Neither requires expanding the entire bag into another full-sized array.

snapshot = acquire_one_snapshot()for block in snapshot.blocks:    lanes = decode_base_and_codec_exceptions(block)    lanes = apply_visible_replacements(lanes, block.edits)    live = block.live_mask    matches = predicate_on_live_lanes(lanes, live)    consume(lanes, live & matches)

The order is important. A predicate on the old value can reject an entry whose replacement should pass. Stale min/max metadata can similarly skip a block containing a new matching value. Either evaluate the edited lanes separately or update conservative summaries in the published snapshot. Treating deleted lanes as masked does not permit unsafe loads, traps, or side effects from evaluating them anyway.

DuckDB's execution format provides a useful interface example: operators accept logical vectors with flat, constant, or dictionary-backed representations. A dictionary vector carries a child vector and selection indexes. Our compiler could similarly pass a block and its active positions between operators instead of requiring a freshly packed output at every step.

Selection is another representation choice. Within 128 positions, a byte-index list takes one byte per selected lane, while a bitmap takes sixteen bytes. Below sixteen selected lanes the list is smaller; above sixteen the bitmap is smaller. That arithmetic says nothing by itself about the fastest downstream kernel. Sparse gathers and dense masked scans should be measured separately.

Publish one version, not several pointers#

Separately allocating the base, edits, and masks does not mean they can be replaced independently. Suppose compaction moves slot 17 while another thread reads the old identity map and a new payload pointer. Each pointer might be perfectly valid. Together they describe an entry that never existed.

I would publish one immutable root containing the compatible chunk directory, overlays, live counts, and identity mapping. A scan acquires that root once and keeps it. Rust's ArcSwap snapshot guidance stresses the same point: repeated loads can observe different objects, whereas retaining one loaded object preserves a consistent view across the operation.

A conservative implementation can use a lock to clone an owned reference to the current root, then release the lock before scanning. A read-mostly atomic ownership container is a later option to measure. Neither resolves write conflicts automatically. Two writers starting from the same root can otherwise publish replacements that discard each other's changes. Serialize the entire read-modify-publish operation initially; an optimistic version must detect a changed root and retry or merge against it. A flat directory clone also costs time proportional to its chunk count; sharing payloads does not make that bookkeeping disappear.

Compaction is a writer too. It may build new blocks while edits continue, but it cannot install a cleaned-up old view over newer changes. Keep a generation on its input and validate it at publication, or arrange an explicit handoff that preserves intervening edits. An atomic store is only the final step of that protocol.

Old readers also keep old allocations alive. The Linux RCU documentation separates removal from reclamation for exactly this reason: making an object unreachable to new readers does not establish that existing readers have finished using it. A raw acquire/release pointer exchange alone is not a lifetime scheme.

The memory budget must therefore include retained old chunks, new chunks being built, overlays, and temporary workspace. One reader holding an old root retains that view; many staggered readers can retain several generations. Structural sharing helps with unchanged chunks, but it does not release a changed chunk that someone still needs. Memory-pressure backoff and snapshot-lifetime metrics belong in the implementation.

The writer should have its own cache lines#

Compression gets more appealing when most of its bytes are immutable. Multiple readers can share them while a writer changes private storage elsewhere. The frequently modified append cursor, lock, and publication bookkeeping deserve a different placement from those densely packed values. The kernel's false-sharing guide shows how writes to one field can disturb readers of an unrelated field on the same cache line.

I would separate worker-owned hot fields and align the larger allocations, rather than pad every tiny compressed frame. A bitmap word also makes a poor independent mutation unit for several writers: two distinct logical bits still share an update location. Private edit buffers followed by coordinated publication avoid putting atomics into the tightest part of the representation.

SIMD loads still need explicit bounds. A mapped page beyond a buffer is not permission to read beyond the allocation. Provide accessible padding or use a safe tail path. The Arrow format's alignment and padding recommendations are useful precedent for making that promise part of a buffer contract. They do not require every small compression block to occupy a padded allocation of its own.

The three sizes from the chunking experiment remain separate: a small compression block, a larger independently allocated chunk, and a worker's ownership unit. For a coherent whole-collection scan, the snapshot root sits above them. Giving each chunk an independent publisher would require an additional protocol to obtain one collection-wide version.

Rebuild when the work pays back#

Counting exceptions gives a space threshold, but rebuild policy also depends on reads. As a simple decision model, compare the cost of rebuilding with the expected extra cost of carrying the edits through future scans. Costs here are measured time for the same workload, not byte counts mixed with nanoseconds.

expected_remaining_scans * (patched_scan_cost - clean_scan_cost)    > rebuild_cost

That estimate assumes the edit set stays roughly stable long enough to benefit. A chunk that will be rewritten again immediately may belong in raw mutable form. A chunk about to be scanned repeatedly has a stronger case for rebuilding. A hard memory limit is a separate reason to compact, although retained snapshots can prevent immediate reclamation.

I would budget compaction work per batch and use different thresholds for expanding and shrinking a representation. Otherwise a value near the byte-range boundary can repeatedly compress and decompress its block. Append buffers, overlays, codec exceptions, and old snapshots each need limits; moving costs off the foreground operation does not erase them.

There are no new throughput results for this combined design yet. The byte table is an explicit format calculation. The next comparison should include plain raw chunks, copy-on-write compressed chunks, and compressed chunks with bounded edits, varying edit concentration, scan frequency, outliers, and reader lifetime. Besides throughput, I would record bytes rewritten per edit, peak retained memory, and the slowest publication times.

What the language would promise#

I would expose a mutable owner for batching edits and an immutable snapshot for scanning. Handles name entries; positions belong to a particular view. Sorting and dense materialization are explicit consumers. A numeric codec may change between snapshots without changing the values, provided every visible edit and identity mapping changes with it.

This remains a numeric storage experiment. For arbitrary resource-owning values, retaining an old snapshot can also retain the resource. The language must say whether deletion releases it immediately or merely removes it from the new view. Byte compression and deferred destruction cannot silently rewrite ownership semantics.

The ordinary mutable array still looks right for small collections or values that change constantly. For a larger bag that is scanned often and edited in batches, a compressed base with somewhere for edits to wait looks worth building. Most values can stay where they are until there is enough work to justify arranging them again.