Nacre Array Benchmarks: The Numbers

The baseline is Vec<T> from Rust's standard library. This is not a strawman. Vec is one of the most optimized data structures in any language runtime, backed by decades of allocator tuning, LLVM vectorization, and hardware prefetch alignment. Beating it at anything is non-trivial.

Nacre Array uses the current tuned default configuration: 4096-element segments, LZ4 compression, and segment locality cache enabled unless a cache-off variant is shown. For push, we show two Vec baselines: default growth and preallocated capacity. That distinction still matters.

Vec shifts n - k elements on every mid-array insert. Nacre Array shifts within one segment, then updates cumulative suffix metadata across later segments. With the current 4096-element default, Nacre still loses at 1K and 10K, but the structural crossover at scale is decisive. At 100K elements, Nacre is 3.7x faster. Note: elements are 12 bytes with the SlimElementHeader (4-byte header + 8-byte u64), compared to 48 bytes under the previous ElementHeader. Smaller elements also make Vec shifts cheaper, reducing the factor from 8.3x to 3.7x; the structural advantage is unchanged.

This is the clearest structural win on the tuned branch. The old comparison used clone+truncate for Vec; the proper contiguous-array baseline is Vec::split_off. Against that baseline, Nacre now measures 12.1 microseconds (12,105 ns) versus 90.9 microseconds (90,944 ns). That is a real 7.5x win, not a benchmark artifact. The factor decreased from 23.6x because smaller elements (12 bytes vs 48 bytes) also make Vec::split_off cheaper; the memcpy cost that Nacre avoids is proportional to element size.

This is the real metadata win. scan_segments evaluates about 25 segment summaries in 241 ns. A comparable Vec predicate scan over 100K elements takes about 324,578 ns. That is a roughly 1346.5x difference, and it is not a micro-optimization of the same operation. Segment metadata lets you ask which regions are interesting before you touch payloads.

Vec's get is a single pointer offset. Nacre's get resolves the containing segment, then dereferences into that segment. Once the harness stopped timing RNG work, the gap turned out to be much larger than the old draft claimed. For pure random access, disable the cache: it only adds overhead.

Vec wins iteration decisively at every scale. Contiguous memory with sequential hardware prefetch is extremely hard to beat. Per-segment pointer indirection breaks the prefetch stream. This is a fundamental cost of segmentation, not an optimization we missed.

Push needs two baselines. Against default-growth Vec, Nacre briefly wins at 100K because Vec hits a reallocation cliff. Against preallocated Vec, Nacre loses at every tested size. That means push is not a structural reason to choose Nacre Array.

For insert, the crossover is between 10K and 100K elements. At 10K, Vec still wins. By 100K, suffix shifting dominates and Nacre pulls ahead. At 100K, the medians are 19,723 ns for Nacre and 72,047 ns for Vec.

For push, the crossover against default-growth Vec is narrow and unreliable. Against preallocated Vec, there is no crossover. Do not choose Nacre Array for push throughput.

For split, the corrected baseline still shows a clear Nacre win because the operation is fundamentally different: segment-level fracture versus contiguous suffix relocation.

For random access and iteration, there is no crossover in the other direction. Vec wins at every tested size. The question is whether the structural wins elsewhere justify paying that tax.

What still matters from the optimization work:

• The linear segment scan is gone. Lookup uses a cumulative index and binary search.
• The segment cache is real, but it is workload-sensitive. It helps sequential, localized, and the current Zipfian benchmark. It hurts pure random access.
• Insert and remove now update cumulative suffix metadata incrementally. Split now carries only the moved right-half cumulative metadata and renormalizes that side, so the mutation-side upside is more faithful to the segmented design than it was earlier in the branch.

What no longer survives publication:

• The old 15.8x -> 2.55x random-access story. Those ratios were collected under the pre-fix harness and are not the numbers we should publish.

The corrected numbers are the ones above: at 100K, pure random access is 5.96 ns cache-off versus 0.75 ns for Vec. That is the honest current state.

Think of it as a metabolic investment. The per-element header overhead, the segment metadata, the binary search on every get. These are ongoing costs. The returns come when you split a time-series partition without copying, when you scan segment summaries instead of iterating millions of elements, when you insert into a hot region without shifting the entire collection.

The workloads that benefit most: event logs, time-series stores, stream processors, and any system that partitions, scans, or restructures data at runtime. The workloads that should stay with Vec: tight inner loops over contiguous data, random-access-heavy indices, and small collections where the metadata cost never amortizes.

The biology was right about the architecture, but the implementation still matters. Layered structures with differentiated regions do handle certain stresses better than uniform ones. The corrected benchmarks show exactly where that principle pays off today and where the current code still needs work.