Choosing a container

Basalt ships no general-purpose containers in the sense the standard library means. There is no vector that quietly doubles, no map that allocates a node per entry from a global heap. Every container here states where its memory comes from, and that single fact decides everything else about it: whether it can grow, whether your pointers survive, whether it can sit inside other data, and what it costs to have ten thousand of them.

Pick the container by asking who owns the storage, not by asking what shape the data is. The shape usually leaves you two candidates; ownership picks between them.

The four answers

Every container on these pages gives one of four answers to that question, and the answer is the first thing its page tells you.

Who owns the storage	Containers	What that means for you
You do	`Array<T>`	You allocate, you decide the lifetime. The container never allocates and never frees.
An arena does	`ChunkList<T>`, `HashTrie<K, V>`	Every operation that allocates takes an arena. The whole container disappears when you rewind it.
The container does	`VirtualArray<T>`, `HashMap<K, V>`, `DenseHashMap<K, V>`	It holds an OS reservation, has a destructor, and gives memory back. It cannot live in arena data.
Nobody	Intrusive lists	Not a container at all. Macros that link structs you already own, through their own pointer fields.

Those rows are not four flavours of the same thing. They are four lifetime models, and mixing them up is the mistake that costs you — a growable collection built on an arena that abandons memory at every doubling, or an owning one pushed into arena data where its destructor will never run.

Why there is no growable, arena-backed array

Start here, because it explains the shape of the whole set.

An arena allocates by bumping a pointer and frees by moving that pointer back. It has no per-object release. That is the property that makes it fast and its pointers stable, and it is also the property that forbids the growth strategy everyone arrives with.

A std::vector grows by allocating a larger block, copying every element into it, and releasing the old one. On an arena the last step does not exist, so every doubling leaves its predecessor resident for the arena’s whole life:

  16 elements  →  32  →  64  →  128  →  256  →  512  →  1024
  ░░ dead         ░░     ░░     ░░      ░░      ░░      ██ live

  Abandoned by the time you reach N: about N elements' worth. One whole array.

So Basalt has no arena-backed growable array. It has three different ways of not needing one, and each is a real container rather than a workaround:

Array<T> refuses to grow at all. You size the storage; an overflowing append is a bug, not an event it handles.
ChunkList<T> grows by adding a chunk rather than replacing a block. Nothing is copied and nothing is abandoned. The price is that it is not contiguous until you flatten it.
VirtualArray<T> reserves its whole address range up front and makes more of it usable as it fills. It never reallocates because it never has to move. The price is that it owns that reservation, so it cannot be arena-resident.

The same fork appears on the associative side: HashTrie<K, V> grows by allocating one node, and HashMap<K, V> grows by rehashing inside a reservation it owns — which lets it hand the old pages back to the operating system instead of abandoning them.

Address stability: the property, not the promise

Half the container choices in Basalt come down to one question: may I keep a pointer into this?

What invalidates a pointer is not growth. It is reallocation — allocating a new block and copying the elements into it. A container that grows some other way keeps every address it has ever handed out.

Container	A pointer into it survives	Because
`Array<T>`	every append	It never grows
`ChunkList<T>`	every push	A push adds a chunk; the existing ones do not move
`VirtualArray<T>`	every append	The addresses past `count` were reserved from the start
`HashTrie<K, V>`	every insert	An insert allocates one node and links it; entries never move
`DenseHashMap<K, V>`	inserts, not erases	Values live in a `VirtualArray<V>`; a rehash moves slots, not values
`HashMap<K, V>`	nothing	Any insert may rehash, and a rehash moves every entry

HashMap<K, V> is the only one whose pointers are strictly borrows, and that is a deliberate trade rather than an oversight — it is what buys the fastest lookup of the three maps. Read that last row as “copy the value out, or use the pointer before you mutate”, not as a defect.

The rule that catches everyone once

A container that owns an OS reservation has a destructor. An arena never runs one.

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

This is not a stylistic preference — the compiler enforces it. And it propagates: any struct with a VirtualArray<T>, HashMap<K, V> or DenseHashMap<K, V> member stops being a POD value, so it too can no longer be pushed onto an arena, copied with a block copy, or nested inside arena-resident data.

When a collection has to live inside arena data — a child list on a tree node, a per-entry table on a symbol — it can only be a ChunkList<T> or a HashTrie<K, V>. Both are plain values, and a zeroed one is a valid empty container:

struct Node
{
    ChunkList<Edge>       edges;         // both are POD values, so Node still is one
    HashTrie<u64, Handle> children;
};

Node* node = arena.Push<Node>().data;    // Arena::Push zeroes → both members are usable

The owning containers pay for their reservation once per instance, which is the other half of the same trade: one large VirtualArray<T> is close to free, and ten thousand small ones cost a reservation each. There is a measured table of exactly that on the VirtualArray page.

Choosing a sequence

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>`
No bound, built once then read	Append without a ceiling	`ChunkList<T>`
No bound, many small collections, or one inside arena data	Append without a ceiling	`ChunkList<T>`
No bound, one large collection, indexed while it grows	Contiguous and pointer-stable	`VirtualArray<T>`
Elements that already exist somewhere else	To thread them onto a list without moving or copying them	Intrusive lists

Span<T> is in that table on purpose. It is the first thing to reach for and the easiest to forget: when the count is known and fixed, an arena push and a span over it is the whole answer, and no container is needed.

Choosing a map

All three maps hash the key and hold key-value entries. They differ on the two axes above — who owns the memory, and whether entries move — and those differences are what you are choosing between.

	`HashMap<K, V>`	`DenseHashMap<K, V>`	`HashTrie<K, V>`
Storage	An OS reservation it owns	An OS reservation it owns	Nodes on an arena you pass
Structure	SwissTable, value in the slot	SwissTable, values in a packed array	32-way hash array mapped trie
A lookup reads	One group of 16 slots, filtered in one instruction	The same, plus one dependent load	One dependent load per five bits of hash
Grows by	Rehashing; the old pages go back to the OS	The same	Allocating one node
Entries move	On every rehash	Slots move, values do not	Never
Lives in arena data	No	No	Yes
Costs to create	One reservation, ~3 µs	One reservation, ~3 µs	Nothing. A zeroed struct is an empty map
Values as a `Span<V>`	No	`GetValues()`	No
Iteration order	Unspecified	Insertion order, until an `EraseSwap`	Unspecified

The decision is usually settled by the bottom half of that table rather than the top.

Reach for HashMap<K, V> by default. It is the fastest of the three at what a map mostly does, and most maps are long-lived, few in number, and read far more than they are written.

Reach for DenseHashMap<K, V> when you want the values contiguous, when iteration order matters, when a V* must survive inserts, or when V is large and you insert more than you look up.

Reach for HashTrie<K, V> when the map must live in arena memory, when there will be many small maps rather than a few large ones, or when a pointer into it has to stay valid across arbitrary later inserts. It is the only one of the three that costs nothing to create and nothing to destroy.

How these compare with what you may be used to

One lookup of a key that is present, nanoseconds per operation. Both std::unordered_map rows are the same container: the first is handed Basalt’s Hash, so that the container is what differs, and the second is what you get out of the box.

	msvc, strings	msvc, `u64`	clang, strings	clang, `u64`
`HashMap`	10.76	4.58	9.51	3.60
`DenseHashMap`	11.08	4.74	10.27	4.23
`HashTrie`	19.10	19.13	20.28	18.71
`std::unordered_map` + `bs::Hash`	26.55	7.14	22.81	6.94
`std::unordered_map`, `std::hash`	41.07	10.24	34.85	10.46
`Sort` + `BinarySearchBy`	130.13	64.77	119.58	60.33
`std::map::find`	155.32	111.88	152.76	68.12

basalt_bench_lookup, fourth workload, release builds on a Zen 3, median of three launches. String keys are 4 000 asset paths sharing long prefixes; u64 keys are 50 000 sparse identifiers. The standard-library rows are built with the same compiler and flags as the Basalt rows, which is what makes them comparable — they say nothing about any other standard library implementation.

Two things there are worth more than the ordering.

HashTrie loses to a flat map on u64 keys and closes most of the gap on strings. The trie pays a dependent load per level and no descent-side trick removes that — it is the structure, not an implementation detail. It comes back on string keys because there a lookup mostly costs the key comparison rather than the descent. You choose the trie for its lifetime contract, and this row is that contract’s price.

Sort + BinarySearchBy is on the list because it is often the right answer anyway. For a table built once and then queried, over a few hundred entries, a sorted Span<T> needs no map, no hashing and no allocation beyond the span itself — and it stays contiguous, which the prefetcher will thank you for. A map earns its overhead when the working set is large or when it keeps changing.

What every container here assumes

These hold across the whole set, so each page states them briefly rather than arguing them again.

Elements must be trivially copyable. Containers relocate with a block copy and run no destructor. Container<const T> never compiles; a read-only view is a Span<const T>, or a const reference to the container.

Nothing is synchronised. No container here takes a lock, and none is safe against a concurrent mutation — including the ones whose own operation only reads, because the concurrent insert may be moving what you are reading. Two containers sharing one arena also race on that arena’s position, even when neither container is itself shared. Each page’s Not synchronised section says what its shape does and does not give you.

Assertions are for bugs, Result is for failure. An out-of-range index or an overflowing Append asserts, because those are contract violations. An operation that can fail for reasons outside your control — a reservation, a commit — returns a Result. Where both readings are legitimate you get both forms: Append asserts, TryAppend returns nullptr.

Absence is not failure. Every lookup returns a nullable pointer rather than a Result, and that pointer is a writable alias into the container, so updating a value needs no second lookup.

The pages

Page	What it is
Array	A fixed-capacity list over storage you already own.
ChunkList	An unbounded sequence built in chunks on one arena, flattened into another.
VirtualArray	A growable, contiguous array that never reallocates.
HashMap	The default map. A SwissTable over a reservation it owns.
DenseHashMap	The same table, with the values in a contiguous array you can take a span over.
HashTrie	The arena-resident map. Entries never move.
Intrusive lists	Macros that link your own structs through their own pointer fields.

Arena is the prerequisite for half of them, and Hash is what the three maps run on.