The list syntax can stay

The last version of the collection had a satisfying trick and an awkward leftover. Birth coordinates let a handle find its value without a location map. But keeping one survivor in every old block left a lot of small, mostly empty blocks behind. Stable identity had become a restriction on where the values could go.

That restriction made sense for an entity store. It was a strange requirement for the default list in a small functional language. When I write filter, I usually want a new sequence of values. I do not need every surviving integer to remember which allocation first contained it.

So this experiment takes a different path from the birth-ranked bag. That bag is still useful for stable handles and remains unchanged. The new type is a sequence value: ordered, immutable, and free to repack its output. I put it behind a little compiler called Reel to see how much familiar list code could remain familiar.

Start with the code I wanted to write#

Reel accepts list literals, cons, and an empty-or-head-and-tail pattern. It also has map, filter, and a strict left fold. This is actual input to the compiler in the repository:

let xs = [1000, 1001, 1002];let before = xs;let changed = 9 :: tail(xs);print(before);print(changed);print(match changed { [] => 0, x :: rest => x + sum(rest) });

The two lists print as [1000,1001,1002] and [9,1001,1002]. The match produces 2012. Nothing in that program names a chunk, reserves a buffer, or invalidates an earlier value. The compiler gives the same answers using either packed chunks or ordinary one-value cons cells.

The source language is deliberately small. It has finite lists of unsigned 32-bit integers, Boolean expressions, immutable bindings, and printing. It does not implement user-defined recursive functions, polymorphism, floating point, or lazy and infinite lists. Those are substantial omissions. Haskell's non-strict evaluation is part of its meaning, not something an array backend can quietly discard.

The useful target here is strict, finite numeric sequence code. Its notation can resemble an ordinary functional list without choosing an object-per-element representation. OCaml's list documentation is a good account of the familiar syntax and sharing model; this experiment changes the storage behind a similarly small interface.

A list of arrays, with fewer moving parts#

The runtime stores up to 256 values in each chunk. A chunk points to the next chunk. A sequence value stores a head pointer, its first visible offset, and its length. There are no per-element handles, masks, edit overlays, or location maps in this version.

This is an unrolled linked list, not a new data-structure family. It is also intentionally uncompressed: values occupy four bytes each. The earlier byte-difference format still has a use for suitable cold data, but putting its exceptional-value logic on every ordinary sequence read was not necessary for this experiment.

For a million values, the representation has a few thousand chunk boundaries instead of a million pointer-following steps. Inside a chunk the consumer sees an ordinary contiguous span. The chunks themselves can be allocated in different places; no single large contiguous reservation is required.

The chunks do not have to be cache-line sized. On the tested machine, a 256-value payload contains 1,024 bytes, the capacity of sixteen 64-byte cache lines. An unaligned buffer can touch seventeen lines; this runtime does not pad every allocation to a line boundary. That gives a useful run for a scan while keeping the amount of copying at the head bounded. It is a starting size, not a proved optimum. The benchmark records one size rather than claiming a completed chunk-size search.

Fix the edges that reach the caller#

Taking a tail advances the first-visible offset. At a chunk boundary it follows the next pointer. There is no array-wide shift. When the final value disappears, the result is the canonical empty descriptor and retains no buffer.

That is different from putting a start offset into one enormous shared array. A tail holding one final value should not accidentally retain a million-element prefix. Here it can retain at most the unused part of its current 256-value chunk. A separate old alias can of course still keep the old sequence alive.

A prefix has the opposite retention problem: its root points onward to a suffix the caller does not need. For take, I chose to copy the requested values into a fresh packed result. This makes taking a prefix linear in the prefix length, but stops a tiny prefix from owning the entire old chain. Both choices are covered by tests at empty, full, and partial chunk boundaries.

Cons has a bounded copying rule. If the visible first chunk has room, create a new chunk containing the new value followed by that visible head. If it is full, put a one-value chunk in front. The remainder is shared in either case. Old values never mutate. At most 255 existing integers are copied by one prepend.

The other edge was destruction. Releasing a long unique chain through recursive destructors can use one stack frame per node. The runtime instead follows and releases unique suffix edges in a loop, stopping when it reaches a shared node. The cons-cell control uses iterative cleanup too, so it is not being penalized with a broken destructor.

The sparse case gets a different answer#

Filtering keeps the survivors in order and writes them into a private builder. That builder fills a chunk before starting the next one. It does not preserve empty coordinates from the input.

In the million-entry test, retaining one value out of every 256 produces 4,096 values. They occupy sixteen chunks and 17,152 bytes of node-plus-payload storage in this build. They do not require 4,096 mostly empty birth blocks.

This fixes sparse output for the sequence API. It does not solve the stable-handle bag's relocation problem. A caller that needs persistent entity identity must still use that type or pay for an identity layer. A caller retaining both xs and filter(xs) also retains both representations; the small output figure is not a measurement of their combined process memory.

Keep pipelines out of the heap#

Packing alone is useful, but it still leaves a program that creates and destroys a list after every transformation. I wanted this expression to describe a calculation rather than a series of intermediate allocations:

let xs = range(0, n);print(sum(xs  |> map(x => x * 1664525 + 1013904223)  |> filter(x => (x & 7) == 0)  |> map(x => x ^ (x >> 11))));

The compiler parses and type-checks the program, then emits C++20. When a pipeline feeds directly into sum or fold, its stages become one loop over borrowed chunk spans. A map changes the current scalar, a filter decides whether it continues, and the final value feeds the accumulator. No output list is needed for that reduction.

When the pipeline itself must become a value, the same traversal feeds one output builder instead. A named let is a materialization boundary in this implementation. I have not added liveness analysis that fuses through bindings or quietly removes a shared result. The original input sequence is also still constructed.

This is a small form of fusion, with recognizable predecessors in functional compilers. What makes the transformation straightforward here is the restricted callback language. Map, filter, and fold bodies contain only total scalar expressions. The type checker rejects list traversals and arbitrary calls inside them. There are no callback effects or user exceptions to reorder.

Unsigned arithmetic wraps modulo 2^32, and an arbitrary left fold retains its order. The language's full scalar rules are documented with the source and semantics argument. Resource exhaustion is outside that equivalence argument: removing allocations can change whether a run exhausts memory. The restrictions are explicit rather than inferred from the appearance of a lambda.

Give the native compiler a loop it recognizes#

The compiler does not emit SIMD intrinsics. It hands the native backend contiguous reads and scalar arithmetic with no reference-count operation inside the numeric loop. In the recorded build, GCC turned that loop into AVX2 multiply, add, compare, shift, and reduction instructions. The generated source, vectorization diagnostics, and an assembly excerpt are included with the results.

This is a concrete instance of the loop transformations described in GCC's vectorization work. It is not a guarantee that every fold vectorizes. A reducer whose next accumulator depends on the previous one in a nonassociative way still has that dependency. The unsigned sum in the benchmark gives the backend more freedom than an arbitrary user reducer would.

Borrowing matters too. The owner stays alive while a whole span is consumed. Constructing a fresh owning tail value for every integer would add reference-count work at every step and obscure the straightforward scan. The runtime supports both interfaces; the compiler uses the span interface for its collection operations.

Separate the two improvements#

I compiled the same pipeline five ways: cons cells with and without fusion, chunks with and without fusion, and a fused flat-vector control. The cons control really has one allocation per value, with the same immutable-value contract and atomic ownership discipline. It is not an emulation of an optimized Haskell or OCaml runtime.

Each configuration processed 1,048,576 runtime-sized input values. Input construction, input teardown, printing, and storage accounting were outside the timed operation. Intermediate construction and destruction remained inside the unfused pipeline timing. There were no allocator probes in the timed builds.

These ranges span two runs' medians, each from seven samples. The machine was a shared Intel Xeon Platinum 8573C host, with GCC 14.2, -O3, and AVX2 enabled. All benchmark processes were pinned to the same allowed CPU. The programs' outputs were checked against independently calculated answers. The ranges are not confidence intervals.

Comparing the two extremes gives roughly 313–317 times the throughput. That large figure includes eliminating intermediate allocation as well as changing representation. Holding fusion constant is the better packing comparison: chunks were about 11–12 times faster than cons cells in these runs. Holding chunk storage constant, fusion improved the pipeline by about thirteen times.

The flat-vector control is the more interesting endpoint. The chunk version was within about eight percent of it in both runs, with no consistent winner. A plain sum over the input took 0.138–0.140 milliseconds for chunks and 0.130–0.149 for the vector. On these scan workloads, array-like performance is an observed result rather than a name given to the structure.

The source list occupied 4,390,912 bytes of node-plus-payload storage in this build, compared with 4,194,304 for the vector and 25,165,824 for cons cells. The chunk representation added about 4.7 percent to the raw array's capacity. These figures count node sizes and retained value buffers, excluding allocator bookkeeping, stack descriptors, and peak construction scratch; they are not resident-memory measurements.

The raw observations and reproduction instructions also include smaller inputs. Nothing here measures GHC, Scala, Rust iterators, Wasm, or all functional programs. A good existing functional compiler can already fuse some list code; it would be misleading to give every such compiler the unfused-control number.

The ordinary list still wins some operations#

Prepending one value at a time exposes the partial-head copies. At 131,072 values, cons cells took 2.406–2.472 milliseconds and chunks took 6.114–6.821. I also walked those lists explicitly through owning head/tail views: 1.623–1.626 milliseconds for cells, versus 2.107–2.511 for chunks.

So the speedup depends on the compiler using bulk operations, not simply substituting a container underneath an arbitrary recursive walk. Reel currently has built-in sequence operations and patterns, but no general recursive-function optimizer. Keeping every intermediate prepend version also keeps the copied prefixes alive; cons cells are particularly good at that sharing pattern.

A uniqueness-aware implementation could reuse a privately owned prefix instead of copying it. Perceus explores that kind of functional in-place reuse much more thoroughly. This prototype does not implement that analysis. It would also need a different structure for consistently fast indexed updates or concatenation; existing persistent vectors are an obvious comparison, not something to rediscover without checking.

What happens when another thread reads it?#

The published value buffers and suffix edges never change. A thread can retain its own descriptor and scan while another thread constructs a different value sharing the suffix. The four-reader tests exercise that case. Concurrent assignment to the same C++ descriptor is not supported, and Reel has no parallel scheduler yet.

The reference counts are still shared writable state. False-sharing guidance is relevant even for an otherwise immutable structure. Scanning a borrowed span avoids a count update per element, but this experiment does not establish multicore scaling, cache-line isolation, or NUMA placement. I would measure those before making another padding or allocation policy part of the default.

Small enough to inspect, large enough to test#

The frontend includes a Python list interpreter independent of the C++ layout. I compared 180 generated pipelines and explicit pattern, fold, alias, overflow, and boundary cases across the storage and fusion configurations. Type errors and parser limits are checked too. The runtime passed two seeded 10,000-step reference-vector tests, retained-version checks, sparse repacking, suffix retention, concurrent readers, and long-chain cleanup. AddressSanitizer and UndefinedBehaviorSanitizer, with leak checking, passed the runtime suite.

The source is small enough that the important rules fit beside the code. The two literal Reel snippets in this article are compiled and run by CI. Timing figures are verified against the stored observations, but speed is never a test threshold. Different hardware is allowed to give a different answer.

The result is a narrower default than the earlier bag, and a more useful one for this little language. A sequence has values and order. An entity store has identity. A lazy stream has a demand-driven computation. Giving all three the same list-shaped implementation had been making each carry the other's requirements.

For this finite numeric subset, I could keep the literals, patterns, immutable bindings, and transformation pipelines. The large gains came from choosing packed storage where a value had to exist, and avoiding intermediate values where it did not.