A smaller list, one block at a time

One useful result from my list experiment looked almost disappointing. Store a number once, then store the small differences between it and its neighbors. After trying elaborate ways to encode identities, I had arrived at a base and an array of bytes.

In the previous article, I dropped the requirement that a collection preserve its order. Values could stay packed, with the last value filling a hole after removal. The next question was whether the values and their indexes needed so much space. Narrower index fields were a reasonable general improvement. For numeric values that were close together, small blocks offered much more.

Then I tried to align those blocks for the processor. A 132-byte block became 192 bytes. That was an awkward start to a compression experiment, and a useful reminder that the number of bits in an encoding is only part of its cost.

A small rule instead of repeated large numbers#

Take 128 unsigned 32-bit integers whose largest and smallest values differ by at most 255. They would normally occupy 512 bytes. Store their minimum in four bytes and each difference in one byte, and they occupy 132 bytes. Reading an entry needs one base, one byte, and an addition. Positions within the block still come from arithmetic.

This is a restricted frame-of-reference encoding, an established approach rather than a new compression algorithm. Work on integer-key compression and SIMD binary packing has explored this territory in much greater depth. My attraction to the byte-sized version is how little machinery its decoder needs.

The restriction matters. Random full-width integers will not generally fit. Neither will arbitrary objects with pointers and resource ownership. These experiments encode numeric payloads exactly, without a stable-identity table. Handles, generations, or a sorted view would add their own storage. A general collection also needs a wider or uncompressed representation when the byte rule fails.

I chose this variant to develop because it makes the hardware questions concrete: how large should the block be, where should its base live, and how much of it should a worker own? There is no single codec winning on every kind of input.

The cache line is not the block size#

The machine used for this follow-up reported 64-byte cache lines. That is a parameter of this experiment, not a promise about every processor. A cache line is also a unit of coherence: unrelated writers can interfere when their data shares a line. The Linux kernel's false-sharing guide explains why packing the hottest fields together sometimes backfires.

Aligning every 132-byte frame to 64 bytes gives it a 192-byte stride. Those extra 60 bytes do not encode anything. For 128 values per frame, storage rises from about 1.03 to 1.50 bytes per value. Alignment has spent almost half as much space again as the compressed representation needed.

An alternative is to group the bases. Sixteen four-byte bases occupy one cache line; sixteen blocks of byte differences occupy another 2,048 bytes. A 64-byte-aligned group then uses 2,112 bytes, exactly the same as sixteen tightly packed 132-byte frames. Each block's differences start at a line boundary without padding every frame separately.

That does not guarantee faster reads. An isolated lookup now needs a header line and a payload line, and grouping changes which headers compete for cache space. During a scan, many values reuse each base. The access pattern decides whether the arrangement is useful; counting aligned addresses is not a benchmark.

Keep compression small and allocation larger#

I separated three choices that had been bundled into the word block. The compression block decides which values share a base. The allocation chunk decides what can grow or move independently. The ownership unit decides what a worker may change without another worker changing the same storage. There is no requirement that all three have the same size.

One candidate keeps 128-value compression blocks inside independently allocated chunks of 16,384 values. In the all-byte case, a chunk contains 512 bytes of bases and 16,384 bytes of differences: 16,896 bytes in total. That is 16.5 KiB, not a 16 KiB operating-system page. A directory needs one pointer per chunk, rather than one per value.

Fixed logical chunk sizes keep indexing simple even when their physical addresses are unrelated. This formula assumes full chunks except possibly the last, a byte encoding throughout, and an ordinary bounds check. It is not a recipe for indexing arbitrarily half-empty chunks.

// Fixed logical sizes; bounds checked before these operations.chunk_number = index >> 14       // 16,384 values per chunkinside_chunk = index & 16383block_number = inside_chunk >> 7 // 128 values per blockchunk = directory[chunk_number]value = chunk.bases[block_number] + chunk.deltas[inside_chunk]

A new chunk can be allocated without moving existing payloads. Growing the pointer directory can still allocate and copy pointers. A mixed-width chunk also needs tags and offsets, or a uniform wider encoding; it cannot use the all-byte formula unchanged.

What the new runs actually measured#

I built a C++20 harness with GCC 14.2, optimization enabled, and explicit AVX2 kernels. It ran on a shared, virtualized AMD EPYC 9V74 host. The larger dataset had 16,777,216 values: 64 MiB as ordinary 32-bit integers. Every group of 1,024 values fit the byte-delta rule, so all tested block sizes could represent exactly the same data.

Random queries were batched throughput tests. Scans decoded every value, performed the same wrapping integer multiply, and counted high bits, without writing an intermediate uncompressed array. Construction was outside the timings. The table gives the range between two runs' medians, each from seven trials; those ranges are not confidence intervals.

The separately allocated chunks were assigned to logical positions in shuffled allocation order. This interrupts the regular address progression, without pretending to control physical pages or NUMA placement. Allocating every tiny group separately was especially costly for scans. Larger chunks paid much less for indirection, although the tightly packed contiguous frames remained faster to scan in these runs.

Grouping headers also failed to produce a universal lookup improvement. Its random-read timings were noisy and sometimes poor. At the smaller, roughly million-value size, the raw array read faster than several compressed layouts. The smaller footprint is a plausible explanation for some large-dataset improvements, but I did not collect hardware counters that would establish the cause.

The source, raw samples, and reproduction notes accompany the article. Every decoded value and timed checksum was checked against the raw array. A smaller run passed AddressSanitizer and UndefinedBehaviorSanitizer. These are storage kernels, not a tested concurrent container, and these timings are native rather than Wasm.

SIMD needs a consumer, not just a decoder#

The first implementation read compressed values one at a time. For the larger dataset, its deliberately non-vectorized scan took about 0.61-0.63 nanoseconds per value. The explicit AVX2 version of the same packed representation took about 0.056. That comparison tests scalar versus vector code; it does not mean compression made a well-vectorized raw array eleven times faster.

The decoder loads eight byte differences, widens them into eight 32-bit lanes, and adds a broadcast base. The consumer immediately multiplies and tests those lanes. This is why 128 values is a convenient starting point: sixteen batches fit without a tail inside a full block. A final partial block still needs a safe tail path; the timed harness deliberately uses complete blocks.

Expanding the entire collection into another array before processing it would introduce output writes, another allocation, and another memory pass. The interesting interface is a block iterator that lets decoding feed the next operation directly. Some operations can avoid expansion altogether: a sum can use the base times the count plus the sum of the differences. That would be a different benchmark from the per-value consumer used here.

SIMD also belongs at the backend. Wasm uses 128-bit vectors, and its widening operations allow the same general decoder strategy with different lane groupings. The AVX2 timings do not predict its speed. Separately allocated chunks can already be represented by offsets inside one Wasm linear memory; a memory per chunk is unnecessary.

A bigger compression block can lose its advantage#

Larger blocks amortize the base over more values. They also force more values to share its range. I repeated the space calculation after replacing roughly one value in a thousand with an unrelated full-width integer. A byte-or-raw policy then expanded the affected block. The table counts encoded payload only; a usable mixed-width format would additionally need its tags and location metadata.

There is an even simpler failure case. With a fresh unrelated base every 128 values, all 128-value blocks compressed in the test, while all the 256-value blocks fell back to raw storage. The compression boundary needs to respect the data's locality. Making the allocation chunk larger does not require making the compression block larger with it.

I would start with 128-value blocks and test 64 and 256 on the actual workload. Rare exceptions, 16-bit differences, and narrower bitpacked widths are further options. Each adds metadata and another kernel. A raw fallback is more important than collecting codecs before measuring whether their dispatch and rebuild costs are justified.

The old removal trick can break the new encoding#

This is the catch I would want to see before adopting the design. A block near one million can store its values as byte differences. Remove an entry and move the collection's last value into the hole: that value might be near four billion. The byte representation is now invalid, even though the unordered-bag operation itself is perfectly valid.

Preserving a globally dense logical array means allowing that destination block to rebase, widen, or become raw. A single edit can therefore rebuild a block. Repeated random edits can progressively destroy the compression advantage. Batch edits and retaining a wider representation for a while avoid repeatedly shrinking and expanding the same block.

Alternatively, an owner can fill holes from its own chunk and leave other chunks alone. That improves locality and reduces cross-worker coordination, but chunks can now be partially occupied. Translating a global rank such as list[5000] needs occupancy metadata and a rank search, unless the API uses chunk-local handles instead. I would not claim arbitrary local deletion, globally packed ranks, and the simple shift-and-mask indexing formula at the same time.

This pushes my first implementation toward a clear boundary: mutable, ordinary chunks while edits are frequent; compact chunks for a read-heavy snapshot. A mixed mutable codec is a later experiment. Stable identity remains another contract, including mapping repair whenever values move.

Give writers space, even when readers like density#

Four workers incrementing four distinct atomic counters provide a small illustration. In two runs, keeping the counters next to one another took about 8.8-11.7 nanoseconds per increment in aggregate. Putting each on its own 64-byte line took about 0.54-0.72. The corresponding single-worker controls were roughly 1.8 nanoseconds either way.

That is a false-sharing microbenchmark, not a parallel-list speedup. It demonstrates why I would isolate frequently modified owner counters, locks, or publication fields while keeping read-mostly payload dense. Padding every value would solve the wrong problem. Grouped base headers are another trap if different writers update bases on the same line.

Bitpacking introduces a separate correctness issue. Two different logical fields can share the machine word that an encoder reads, modifies, and writes. Unsynchronized edits may conflict even when their indexes differ. A wide SIMD read can likewise overlap a concurrent write. Rust's atomic memory model treats conflicting unsynchronized non-atomic accesses as a data race; alignment alone does not make them legal.

I would begin with one writer per ownership chunk, or an ordinary lock around changes to a chunk and its metadata. A global tail-fill involving two chunks needs a consistent locking order and coordinated identity updates. A length counter becoming atomic does not make the whole operation atomic.

For read-heavy snapshots, build a replacement chunk privately and publish a new immutable directory. A conservative Rust starting point is an RwLock protecting an Arc to that directory: readers retain one snapshot, then scan without touching a reference count per value. Unchanged chunks can be shared. Writers still need serialization or conflict detection, and a simple directory clone costs time proportional to the chunk count.

Publishing a pointer with release/acquire ordering would only address visibility. It would not keep the old allocation alive for readers, reclaim abandoned snapshots, or make a separate identity table match the same version. Slow readers also retain old chunks, increasing peak memory. Those lifetime and consistency costs belong in the design before anyone calls it lock-free.

Separate allocations are not separate memory nodes#

Letting chunks live at different addresses gives the allocator flexibility and lets a chunk be replaced independently. It also introduces directory loads, more allocations, and less regular access between chunks. The measurements are a reason to make those jumps relatively infrequent, not a reason to scatter every tiny frame.

On a NUMA machine, allocation policy and the thread that faults in pages also matter. Linux's memory-policy documentation describes local and interleaved allocation. Having an eventual owner initialize its chunks under an appropriate policy is worth testing; calling malloc from one thread for everybody does not establish locality near the later readers.

This host exposed only one NUMA node, so there is no NUMA result here. Nor did I measure translation-cache misses, page migration, a concurrent compressed container, or the cost of snapshots under slow readers. Those are the next measurements, rather than benefits to quietly add to the compression numbers.

The version I would keep building#

For one writer and long scans, the tightly packed frames remain a useful baseline. For independent growth and read-heavy concurrent access, I would try small compression blocks inside larger, separately allocated chunks, with dense read-only headers and isolated mutable control fields. The two layouts can share a block-processing interface without promising one permanent pointer to a conventional array of values.

The language would expose indexed reads, block iteration, and explicit snapshots. An operation that needs an ordinary contiguous array would request materialization and pay for it. The runtime would reserve the right to keep unhelpful data raw, and the type would say whether positions or persistent identities survive edits.

There is room for indirection here. In the 16,384-value variant, the directory and retained ownership bookkeeping added only 32 KiB across more than sixteen million values. The useful place to spend that space was between substantial chunks, where it bought an independently replaceable allocation. Inside each chunk, I would keep the arithmetic simple.