ChunkList

ChunkList<T> collects elements when you do not know how many there will be. It stores them in a chain of fixed-size chunks on an arena you supply, then copies them into one contiguous Span<T> once the count is final. No element moves while you build.

You build the list on a scratch arena and flatten it into the caller’s arena — so the chunks are reclaimed and only the flat result survives.

The problem it solves

You often cannot bound a count in advance. The tokens in a source file, the visible objects in a frame, the matches for a search: each depends on data you have not read yet.

The usual answer is to grow: allocate a larger block, copy every element into it, and release the old one. An arena never releases anything.

So on an arena each doubling leaves its predecessor resident, for the arena’s whole lifetime. Grow to 1 M elements one doubling at a time and you abandon roughly 1 M elements’ worth of dead blocks.

A chunk list grows by adding a chunk. Existing chunks stay where they are, and nothing is copied.

The model: build in chunks, finish in one block

A chunk list has two phases, and they use different operations.

Phase	Operation	Shape of the data
Build	ChunkListPush	A chain of chunks. Not contiguous. No indexing.
Finish	ChunkListFlatten	One Span<T>. Contiguous, indexable, final.

ChunkList<Token> tokens = {};

while (Lexer::Next(source, token))
{
    ChunkListPush(arena, tokens, token);   // a new chunk opens only when the last one fills
}

const Span<Token> flat = ChunkListFlatten(arena, tokens);

The list stores no arena. Every operation that allocates takes one, so the allocation stays visible at the call site.

The flatten takes a different arena

The build phase leaves chunk headers and chunk blocks on the arena. An arena cannot free them individually. So a list built and flattened on one arena keeps every chunk resident, next to the result you actually wanted.

Give the flatten its own destination and the cost disappears.

// One arena: the chunks outlive their purpose.
Span<Token> Tokenize(Arena& arena, String8 source)
{
    ChunkList<Token> tokens = {};
    // ... push into `arena` ...

    return ChunkListFlatten(arena, tokens);
}
// `arena` still holds every chunk.

// Two arenas: the chunks are reclaimed.
Span<Token> Tokenize(Arena& arena, String8 source)
{
    const ScratchScope scratch(arena);
    // ... push into scratch.GetArena() ...

    return ChunkListFlatten(arena, tokens);
}
// The scope rewinds the scratch arena here.

The chunks live on the scratch arena. The result lives on the caller’s arena. The scope rewinds the scratch arena on the way out, so the chunking overhead is not amortised or bounded — it is reclaimed.

ScratchScope picks a thread-local arena that is not one of the arenas you pass it. Passing arena is what guarantees the two are different. See Arena for the scratch arenas and the rewind guards.

Addresses stay put

A push never moves an element that is already in the list. So a pointer into a chunk stays valid for as long as that chunk lives, and you may keep pushing.

Header* header = ChunkListPushSlot(arena, records);
// ... thousands of further pushes ...
header->total = records.total_count;      // still the same object

What invalidates pointers is reallocation, not growth. Reallocating allocates a larger block, copies every element into it, and the old addresses die. A chunk list adds a chunk instead, so nothing already stored is touched.

VirtualArray<T> reaches the same guarantee by the other route: it reserves its whole address range up front and commits more of it as it fills, so it grows without ever reallocating. Both keep addresses stable. They differ on contiguity and cost, not on stability.

Flattening copies, so the two then diverge

ChunkListFlatten copies every element into fresh storage. A pointer you kept into a chunk still points at the chunk, not at the flat result. Writing one does not change the other.

Filling large elements in place

ChunkListPushSlot appends one element and returns its address. You fill it through that pointer.

Prefer the slot form for large elements

ChunkListPush(arena, list, value) copies value into the list. For a large struct, build it in the list instead: ChunkListPushSlot hands you the slot, already zeroed, and you write the fields directly. No temporary, no copy.

Chunk size

A chunk’s capacity is chosen when the chunk is allocated, and it is a per-call parameter.

You pass	Capacity used
Nothing, or 0	Derived from sizeof(T) against a 4 KiB target, floored at one element
A count	That count

The default is expressed in bytes, not elements, because the per-chunk overhead is a fixed 32-byte header. A default element count would make a chunk of 4-byte elements 16 KiB and a chunk of 4 KiB elements 16 MiB.

Chunks in one list may have different capacities. Each chunk carries its own, and nothing reads a list-wide capacity, so two call sites passing different values is not an error. A batch push uses this: it sizes one chunk to the whole batch rather than opening a long chain.

Pass your own capacity when you know the shape of the data. A per-slot list in a hash table wants a small chunk; a lexer over a large file wants a large one.

Merging lists from several threads

ChunkListConcat appends one list to another in constant time. It moves no element and allocates nothing — it relinks chunks and empties the source.

That makes the multi-threaded shape straightforward: give each producer its own arena and its own list, then splice the results on one thread.

// On each worker thread, with its own arena:
ChunkList<Result> local = {};
ChunkListPush(worker_arena, local, result);

// On the joining thread, once the workers are done:
ChunkListConcat(all_results, local);

Two lists on one arena still race

A chunk list is not synchronised, and every push allocates. So two threads pushing to two different lists that share one arena race on that arena’s position. One arena per producer is what removes the race, not one list per producer.

The trap: a copy shares the chunks

ChunkList<T> is a plain value, so copying it compiles. The copy points at the same chunks.

Never grow two copies of one list

ChunkList<T> other = list; gives you a second handle onto the same chain. Push to both and their total_count fields drift over one set of elements. Concatenate them and a chunk is linked ahead of itself, which turns any later iteration into an infinite loop.

Copy a list to read it. Never to grow it.

Clearing does not reclaim

ChunkListClear empties the list. The chunks stay on the arena, now unreachable, because an arena has no per-object release.

Clearing a list every frame on a long-lived arena therefore grows that arena forever. Rewind the arena instead: wrap the work in an ArenaScope, or build on a scratch arena.

ChunkList or VirtualArray

Both grow without a ceiling and both keep addresses stable, so the choice turns on two other things: how many collections you have, and where they live. Choosing a container sets out why those two questions decide the whole set.

	ChunkList<T>	VirtualArray<T>
Storage	Chunks on an arena you pass	Its own OS reservation
Cost	Per push, a pointer bump	Per instance: one reserve, one release
Lives inside arena data	Yes — it is a POD value	No — will not compile
Contiguous while building	No. Flatten first	Yes, always
Finishing	Copies every element	Nothing to do

The structural row is the one that decides most cases. VirtualArray<T> owns a reservation, so its destructor must run, and an arena never runs one. Arena::Push<VirtualArray<T>> does not compile, and any struct with a VirtualArray<T> member stops being a POD value. A collection that has to sit inside arena-resident data — a child list on a tree node, a bucket in a hash map — can only be a chunk list.

The cost row decides the rest. A VirtualArray<T> pays its reservation once per instance, not per element, so one large collection is close to free. Ten thousand small ones are not.

10 000 collections, 4 elements each	Windows	Linux
ChunkList<i32> on one arena	41 ns/instance — 0.4 ms	40 ns/instance — 0.4 ms
VirtualArray<i32>, 64 KB reserve each	2 894 ns/instance — 28.9 ms	10 317 ns/instance — 103 ms

Release builds; the Linux figures are under WSL2. Reserve, fill and teardown together. Tearing down every chunk list is one arena->Clear(), measured at 0 µs.

Two things push you the other way, towards VirtualArray<T>.

Indexing or sorting the elements while you are still appending needs contiguous storage, and a chunk list has none until you flatten it.

Flattening costs a copy and a transient 2× peak

ChunkListFlatten reads every element and writes it into a fresh block, so for a moment the chunks and the flat result both exist. Flattening 4 GB of elements needs 8 GB at that instant, and pays the bandwidth of a full copy. A VirtualArray<T> is already contiguous and copies nothing.

No removal

A chunk list streams elements in and hands them over. Nothing takes one back out — no Pop, no RemoveSwap. Removing an element from the middle of a chunk would break the address stability the shape exists to provide.

Element requirements

ChunkList<T> accepts trivially-copyable element types only, and requires them to be trivially constructible as well, because it allocates its chunks through the arena. ChunkList<const T> does not compile: flatten into a Span<T> and take a Span<const T> view of it.

API summary

Parameters, assertions and invariants are documented in basalt/core/ChunkList.h.

Building

Signature	Purpose
ChunkListPushSlot(arena, list, capacity)	Appends one element and returns its slot, zeroed.
ChunkListPush(arena, list, value, capacity)	Appends a copy of one element.
ChunkListPushSpan(arena, list, values, capacity)	Appends a block of elements. Returns how many were appended.
ChunkListGetDefaultChunkCapacity<T>()	The capacity a push uses when given none.

Finishing

Signature	Purpose
ChunkListFlatten(arena, list)	Copies every element into one contiguous span in arena.

Merging and emptying

Signature	Purpose
ChunkListConcat(list, to_append)	Relinks one list onto another in constant time. Empties the source.
ChunkListClear(list)	Empties the list. Does not reclaim the chunks.

Iterating

Signature	Purpose
begin() / end()	Range-for support over every element, chunk by chunk.

Fields

Field	Purpose
first / last	Ends of the chunk chain. Both null when the list is empty.
chunk_count	Chunks in the chain.
total_count	Elements across all chunks. What a flatten allocates.