VirtualArray

VirtualArray<T> grows without ever moving an element. It asks the operating system to set aside a large range of addresses up front, then makes that range usable a step at a time as you fill it. It owns that range and releases it when it is destroyed.

Reserving address space is not using memory: a 64 GB reservation costs no physical pages until you fill it, and it is the reservation that makes every pointer into the array permanent.

Address space and memory are two resources

A 64-bit process has 128 TB of addresses it may name, and far less memory it may actually use. The two are handed out by separate operations.

Operation	Costs	Gives you
Reserve	A range of addresses. No physical memory.	The promise that nothing else will be placed there
Commit	Physical pages, on first touch	The right to read and write that range

VirtualArray<T> reserves once, at a size you will not reach, and commits as the fill advances. Reserve() defaults to 64 GB. That number is a ceiling, not a cost.

VirtualArray<Vertex> vertices;
if (!vertices.Reserve().ok)                  // 64 GB of addresses, ~0 bytes of memory
{
    return;
}

vertices.Append(vertex);                     // commits 256 KB the first time it needs to

It grows without reallocating

An append never moves an element that is already stored. The array does not allocate a larger block and copy into it, because it does not need to: the addresses beyond the live elements were already reserved when the array was created.

So a pointer into a VirtualArray<T> stays valid for the array’s whole life, however much you append afterwards.

Vertex* first = &vertices[0];
// ... a million further appends ...
first->position = origin;                    // still the same object

This is the same guarantee Array<T> gives by never growing, and ChunkList<T> gives by adding a chunk instead of replacing one. What breaks the guarantee elsewhere is reallocation, not growth.

The cost is per instance, not per element

One VirtualArray<T> costs one reservation when you call Reserve(), and one release when it is destroyed. An append costs nothing beyond the write, except when the fill crosses a commit step.

Measured, filling a single VirtualArray<i32> with one million elements:


Reserve	1 system call
Each `Append`	0 system calls
Crossing a 256 KB commit step	1 system call
Destructor	1 system call
Total for 1 000 000 elements	18 system calls — one per ~55 000 elements
Fill time	2.01 ns per element

MSVC release build, x86_64. 1 reserve + 16 commits + 1 release.

Two elements each cost the same as the millionth. Reaching for a VirtualArray<T> when you have one large collection is close to free.

The bill arrives when you have many collections instead of one large one. Every instance pays its own reserve and its own release, whatever it holds.

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

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

It cannot live in arena memory

VirtualArray<T> owns a reservation, so its destructor has to run. An arena never runs a destructor: it frees by rewinding a pointer.

The type is therefore not trivially constructible, and the compiler stops you:

// Does not compile: Arena::Push<T> requires a trivially-constructible T.
Span<VirtualArray<i32>> arrays = arena.Push<VirtualArray<i32>>(8);

The same applies to any struct with a VirtualArray<T> member. It stops being a POD value, so it can no longer be pushed onto an arena, copied with a block copy, or nested inside arena-resident data.

Hold a VirtualArray<T> where destructors run: a local, a member of a class you construct yourself, or a static. When the collection has to live inside arena data, use ChunkList<T>.

Construction happens in two steps

The default constructor cannot fail and touches nothing. Reserve() performs the one operation that can fail, and reports it as a Result.

VirtualArray<Entity> entities;               // valid, empty, holds no reservation
const auto reserved = entities.Reserve();    // the fallible step, checked here

The type is movable and not copyable. A move transfers the reservation and leaves the source empty, so pointers into the buffer stay valid across it. Two copies of one reservation would release it twice.

The reservation is a ceiling

The capacity is fixed by Reserve() at the reserved bytes divided by sizeof(T). Filling past it is a contract violation, not a trigger to grow — there is no second reservation and no relocation.

This is why the default is generous. A ceiling you cannot reach behaves like no ceiling; a small one is a trap. Pass your own size when you know the collection’s real bound; the number costs address space rather than memory.

When this is the wrong tool

You have	You want	Use
A known count, filled once	A range to read or write	`Span<T>`
A known bound, filled incrementally	Append, then read	`Array<T>`
Many collections, or one inside arena data	Append without a ceiling	`ChunkList<T>`
One large collection, indexed as it grows	Contiguous, pointer-stable, unbounded	`VirtualArray<T>`

Two cases send you elsewhere. Many small collections pay the per-instance cost measured above, and a collection that must live inside arena-resident data cannot be a VirtualArray<T> at all. Choosing a container covers that second rule once, for every container it applies to.

Element requirements

VirtualArray<T> accepts trivially-copyable element types only, and requires alignof(T) to be no greater than 4096 — the alignment a fresh reservation guarantees. VirtualArray<const T> does not compile: a read-only view is Span<const T>, from ToSpan().

API summary

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

Lifecycle

Signature	Purpose
`VirtualArray<T>()`	An empty array holding no reservation. Cannot fail.
`Reserve(bytes, commit_step)`	Acquires the reservation. Both arguments default. Returns a `Result`.
`TryCommitFor(count)`	Commits enough for `count` elements. Returns whether it succeeded.

Adding

Signature	Purpose
`Append(value)`	Adds one element. Asserts when full or when a commit fails.
`TryAppend(value)`	Adds one element. Returns the slot, or `nullptr`.
`AppendSpan(values)`	Adds a block of elements. Asserts when they do not fit.
`TryAppendSpan(values)`	Adds a block of elements, or nothing. Returns whether it fit.
`AppendUninitialized(count)`	Reserves `count` slots and returns them, for filling in place.
`TryAppendUninitialized(count)`	The same, returning an empty span on failure.

Reading

Signature	Purpose
`operator[](index)`	Element access. Asserts on an out-of-range index.
`ToSpan()`	A span over the live elements only.
`size()`	The live element count.
`IsEmpty()` / `IsFull()`	Occupancy tests.
`GetRemainingCapacity()`	Free slots left below the ceiling.
`begin()` / `end()`	Range-`for` support over the live elements.

Removing

Signature	Purpose
`Pop()`	Removes and returns the last element. Asserts when empty.
`RemoveSwap(index)`	Removes an element in constant time. Does not preserve order.
`Clear()`	Sets the live count to zero. Keeps the reservation and the commits.

Bookkeeping

The array gives its reservation back to the operating system when it is destroyed, and it does that on the strength of these numbers. You can read them; you cannot write them.

Signature	Purpose
`GetCount()`	Live elements. Always `<= GetCapacity()`.
`GetCapacity()`	Elements the reservation holds. Fixed by `Reserve`.
`GetCommittedBytes()`	Bytes made usable so far.
`GetReservedBytes()`	Bytes of address space held. Zero when no reservation is held.
`GetCommitSize()`	The commit step, fixed by `Reserve`.