Collection Storage: ArrayList, the Hash Tables and the Tries on Buffer#

Status: designed, not built (2026-10-23) — this record decides how ArrayList, HashMap, HashSet and the three Trie* types are rewritten as ordinary TorbScript on Buffer<Item>, in which order, and what each step may cost. Nothing in std/, runtime/ or compiler/ changed with it; the first slice of section 8 starts the building. It is step 1 of epic #55, "collections: rebuild ArrayList, the hash tables and the tries on Buffer", whose rows are the 52 collection natives of NATIVES.md, and it is the half of COLLECTIONS gap 6 (COLLECTIONS.md) that gap 6 did not do: Buffer is built, the collections still stand on the runtime.

The questions are decided here, with the reason next to each decision. Only a public commitment, a cost, a product direction or the break of a published contract may stay open, and section 9 lists the one that does.

1. Where it stands#

ArrayList, TrieList and Buffer are three names of one runtime object: torb_list, a storage block, an offset and a length (runtime/list.c, RuntimeKind.ListStorage). HashMap and TrieMap are one torb_map, HashSet and TrieSet the same table with a value of size zero (runtime/map.c, RuntimeKind.Map). The three Trie* names are aliases of the flat storage today: TrieList is not a trie, TrieMap and TrieSet are not hash array mapped tries, and the documented cost of a trie (an O(log n) copy that shares its nodes) is not paid or delivered. COLLECTIONS section 3.3 says what the name promises; this record says what it will be (decision 11).

What the compiler knows about them by name, which is the part that makes a rewrite a seed matter:

• ir/instantiate.trb looks ArrayList, TrieList, Buffer, HashMap, TrieMap, HashSet and TrieSet up as primitives of the runtime, and implementationOf(lowering, "ArrayList", ...) (ir/lower/collection.trb) builds every list literal, lowerBuiltList and the spread out of them.
• ir/elements.trb recognizes the one wrapper around torb_list_set (isListSetter) to turn list[i].f = v into an element step instead of a copy of the item.
• witness.trb and instances.trb special-case the name Buffer (the _Buffer witness suffix).
• The VM (interpret.trb, machine.c), the debugger, and crossing.trb / task.c (privatizing a value that crosses a task) know the containers as runtime kinds.
• The slice of a list is O(1) and shared: torb_list_slice makes a second {storage, offset, length} over the same block, and a write to a shared or windowed list copies only the window (torb_list_prepare). A slice of items that may hold a value with a destructor uses torb_list_slice_copied instead, chosen by the program's Closing fact (sliceSymbolOf in backend/c/body.trb, DESTRUCTORS.md 2a).
• Buffer.slice copies, and Buffer writes in place while the storage has one owner and copies once when the value was copied.

The table is runtime/map.c: an insertion-ordered vector of entries plus a bucket array of int32 entry indices. An entry is hash: u64, alive: u32, key, value. The entry capacity starts at 8 and doubles, the buckets are the next power of two at or above twice the entry capacity, and a probe is linear from hash & (buckets - 1). A removal sets alive to 0 and leaves the bucket pointing at the entry (a tombstone: the probe goes on, an insertion may reuse the first one it passed); the key is released at once and the value moved out. The table compacts (drops the tombstones, rebuilds the buckets) when it has more than 16 entries and no more than half of them are alive, and every time it grows. Setting an existing key keeps its position and its stored key. The seed of the hash is fixed, so a run is reproducible, and iteration is insertion order for every map and every set (COLLECTIONS gap 6, decided).

2. The rules every decision answers to#

1. Observable behaviour does not move. Order, Show, equality, Hash, panic texts and sites, the answer of length, the answer of a slice: every conformance program and every doc test runs unchanged.
2. The rewrite is ordinary TorbScript on the kernel. Nothing a slice adds is a new native. The kernel of NATIVES.md is closed; decision 5 is the one place this record asks it to grow, and says why.
3. A decision that costs speed names the benchmark that proves it acceptable (section 6). Where no number exists today, the first slice that needs it records it before it changes anything.
4. The seed refresh stays with the owner (the two-commit rule, section 8): a slice that needs a compiler that reads the new form teaches the compiler both forms first, and moves std/ only after the seed was refreshed.

3. ArrayList#

Decision 1: ArrayList is a TorbScript type that holds a Buffer, not a primitive that gets member bodies. The type is three fields: the Buffer<Item> of storage, the start of its window and the count of the window. The other option, keeping the compiler's list type and writing its members as native fn bodies (BACKEND.md 3.7, issue #53), keeps the name in instantiate.trb forever and has the bodies read a window that only the runtime represents; the rows of NATIVES already say "an ordinary type over Buffer<Item>" for exactly this reason. It also makes #53 no prerequisite: the record needs the K5 operations Buffer already has and no body in IR. #53 helps later, where a Buffer member becomes a body (slice 6).

Decision 2: the slice stays O(1) and shared, and Buffer.slice keeps copying. list.slice(from, to) is a new ArrayList with the same Buffer value (a copy of the value shares the storage, which is what makes the next write a copy) and a different start and count. Reason: a slice in a loop (first/rest recursion, a parser that advances a window, split) is O(n) per step if it copies, and list-iterate-shaped programs go quadratic; the sharing is the published contract of List (std/core Buffer documents "a slice of an ArrayList shares its storage"). Buffer copies because it is the type for code that cannot afford the second owner. The cost is the hidden one the Buffer docs already name: a write to a list that has a live slice copies. The record moves where it copies: a write to a windowed list first rebases (a new Buffer of exactly the window, start 0), then writes in place, so a write after a slice copies the window and not the storage behind it, as torb_list_prepare does today. The check on every write is start == 0 and count == items.length(), which is two comparisons. Benchmark: list-slice and list-write-shared (section 6), both new.

Decision 3: ArrayList.withCapacity is the one row of the family answered by lowering, and it is Buffer.withCapacity. The manifest row ArrayList.withCapacity (target Container) is answered by lowering because it needs the element descriptor of Item, which only the lowering of the instantiated type knows. After the rewrite ArrayList.withCapacity is the body ArrayList(items: Buffer.withCapacity capacity, start: 0, count: 0), and the row that stays lowering-answered is the K5 member Buffer.withCapacity. The hash tables use it for their two vectors (decision 7). No other row of the family is answered by lowering: length, get, set, append, insert, removeAt, replaceBetween, reverse, clear, compact and sliceBetween are bodies. In slice 1 the bodies that move many items (insert, removeAt, replaceBetween, reverse, clear) call the Buffer members that exist today (they are natives now: bulk moves, a memmove where the runtime has one) after the rebase. They become element loops or native { } blocks only when NATIVES rewrites the five Buffer rows, which is slice 6 and a measurement of its own (M5). Reason: a loop of get and set where a bulk move is, is a regression the slice would have to explain.

Decision 4: list literals and for over a concrete ArrayList keep their lowering and change what they call. (COLLECTIONS gap 9, PERFORMANCE.md findings 2 and 5.)

• A literal is built exactly as today: empty with capacity, then append per item or per ...spread in written order (filledList). implementationOf keeps the name "ArrayList"; what changes is that it resolves a declared generic type instead of a runtime primitive. The capacity is the number of items, so a literal still allocates once.
• for item in list over a concrete ArrayList keeps the inline iterator record of section 3.6 of COLLECTIONS: a cursor of the Buffer value, the index and the end of the window. next is a Buffer.get that needs no window check, because start and count were checked when the iterator was made and the loop holds the list, so no write can happen in it (exclusivity). Reason: this is the loop list-iterate measures, 39.09x slower than C today, so it is the one place a rewrite is most likely to lose speed to a bounds check or a retain it should not pay, and the record says what it must not do instead of leaving it to the slice.
• A TrieList literal and loop are the same code over the other type (decision 10).

Decision 5: the sharing of a slice is made safe by one lowering-answered constant, Buffer.holdsClose, which grows K5 by one member. Today a slice of items that may hold an object with a destructor copies the window, because two lists sharing a Close value would release it twice (DESTRUCTORS 2a), and the compiler decides it per item type (Closing.holds). A TorbScript body cannot ask that. The record makes it a constant of the instantiated type that lowering answers, true for a type that may hold a Close value and false otherwise; the slice body is if Item holdsClose then copied window else shared window, and for every type that does not hold one the branch folds away and the emitted code is today's. The alternatives are always copying the slice (decision 2 gives the reason against) and the record keeping a flag of its own that a program would set (the compiler already computes the fact exactly, per layout, to a fixpoint). The cost is one name the compiler answers; it enters the closed list as a sixth member of K5 in slice 1, with its row, and it is a seed matter (section 8). Benchmark: list-slice for a type without a destructor must equal the shared form; a conformance program with a Close item pins the copying form.

4. HashMap and HashSet#

Decision 6: the table is runtime/map.c written over three Buffers' worth of state: an entry vector, a bucket array and a count. It keeps the exact observable algorithm of section 1, so the iteration order, the position of a re-set key and the moment a removed key is released do not move:

• Tombstones. A removal writes Gone over the entry with Buffer.set. The bucket keeps pointing at it, so the probe goes on past it; an insertion may take the first tombstone's bucket. Reason for the enum over C's alive flag: a Buffer entry has to hold a valid Key and Value, and a generic body has no placeholder for either; writing Gone releases the old key and value at the same moment map.c does, which a Close key can observe.
• Compaction. When there are more than 16 entries and the live ones are at most half, and on every growth, the table builds a new entry vector of only the live entries in their order and rebuilds the buckets by probing each one. The thresholds are map.c's, copied, because they decide when a program pays and a different number is a measurable change of behaviour in map-count.
• Growth. The entry vector grows by Buffer.append, whose growth is the runtime's amortized doubling and moves the items with no retain and no release. Only the bucket array is rebuilt when the capacity doubles (integers, no reference counts). The entries are copied one by one (get, append: a retain and a release for a counted key or value) only in a compaction. Benchmark: map-remove (section 6) is the one that would show it.
• Insertion-order iteration and the contract. HashMap.entryAfter(cursor) and HashSet.itemAfter(cursor) stay the iteration contract the iterators of std/collections are written against: the cursor is an entry index, the answer is the next Live entry at or after it and the cursor behind it, and a Gone entry is skipped. A write to the table cannot happen during a for over it (exclusivity), so a compaction can never move an entry under a cursor.
• Sharing. A copy of a table is a copy of two Buffer values, and each one copies on its own first write, as torb_map_prepare does for the one block today.
• Hashing. Hash.hash(): Int is the contract; the table keeps the 64-bit hash in the entry, masks it with the K2 operations, and does the key comparison with == (K4) after comparing the stored hash first, as map.c does.

Decision 7: HashSet has its own entry, not a map with a value of size zero. The C table gets a set for free from a descriptor of size zero. A generic TorbScript HashMap<Item, Unit> depends on a field of type Unit costing nothing in every layout of both back ends, which no document promises. The set's Slot carries the hash and the item. The probing code (hash to bucket, linear walk, the tombstone rule, the rebuild of the buckets) is a private helper over the bucket Buffer and a comparison, written once and used by both types, so the two are the same algorithm and the duplicated part is the entry type. Benchmark: set-count (new).

Decision 8: the order with #56. #56 (P9) is open and in review: torb_map_slot, Instruction.TakeOut with a MapMiss, and ir/maps.trb, so that map[key].f = v probes once instead of twice (baseline map-count 5.78x C, 50 048 allocations; it records map-write). #56 lands first and the hash-table slice (section 8, slice 3) comes after it. The slice is written against the shape #56 lands, and it makes #56's runtime half redundant on purpose: with the entries in a Buffer, HashMap.slot(key) returns the entry index (or a miss), and the write is the element step the pass of ir/elements.trb already does for a list, entries[slot].value.f = v. That is one probe, with no void *, no TakeOut and no MapMiss, and torb_map_slot, ir/maps.trb, the map.slot VM operation and RuntimeKind.Map are deleted in the same slice. Reason for the order: #56 is in review and measured, it needs nothing from this record, and it hands the slice a baseline (map-write) and a test that pins the panic of a missing key. Reason for not waiting for the slice: #56 is the answer for every program in the period before the slice, and the slice would otherwise carry its design and its measurement. The slice must keep map-write and map-count no slower than the numbers #56 records.

5. The tries#

Decision 9: the three Trie* types are said plainly to be aliases of the flat storage, in std/ and in the docs, until decision 11 builds them. The doc comment of each and COLLECTIONS section 3.3 say "today the same storage as ArrayList", with the cost that follows: a copy followed by a write is O(n), not O(log n).

Decision 10: the aliases are kept, on the rewritten types, as their own types. Observable behaviour is unchanged either way (order, Show, equality, Hash). TrieList<Item> becomes a type with one field, an ArrayList<Item>, that passes every member on; TrieMap and TrieSet hold a HashMap and a HashSet the same way. They stay distinct types because the programs and the prelude name them (List, Map and Set default literals choose the flat types, a TrieList is written on purpose) and because decision 11 replaces them one by one without touching a call site. A type alias (type TrieList<Item> = ArrayList<Item>) would make them the same type, which is a change in overload resolution and in the Show of a type name. Benchmark: trie-alias (new) must be equal to the flat loops, which also proves a one-field type is free in the emitted code; if it is not, the slice reports it before it lands.

Decision 11: real persistent tries are built, later, and each only when a benchmark shows the win. A real trie is a product direction already taken (the name promises it, COLLECTIONS 3.3 and gap 6 say TrieList becomes a real trie or loses the name) and not a speed-up of anything measured today: it makes var b = a; b.append x cost O(log n) where it costs O(n) now, and every access a few more steps. So:

• TrieList is a 32-way persistent vector of Buffer nodes with a tail, the shape the NATIVES row names; append, set and removeAt at the end path-copy in O(log n), insert and replaceBetween in the middle are O(n) and say so in the docs.
• TrieMap and TrieSet are a hash array mapped trie over Buffer nodes plus the insertion-ordered entry vector of decision 6: iteration order is a language contract for every map and set, and a trie alone does not have it. The trie maps a hash to an entry index; the vector keeps the order and the tombstones.
• Each is a slice of section 8 and lands only if two numbers hold, both on the same forge runner: trie-fork (new: build a list of a million items and make a copy with one write each, in a loop, keeping all copies) is at least 10x faster than the flat alias, and list-index, list-iterate and map-count with the trie type are within the ratio of section 6 of the alias they replace, or within a stated bound that the decision is revisited with. If the trie fails the second, the alias stays and the doc says why.

6. Cost#

The bound for every row is no slower than before: the ratio torb of the slice / torb of the merge base of the fastest of nine runs, on the same forge runner, at most 1.00 plus the noise that the same script measures between two runs of the same binary. The pattern is tools/buffer-cost.sh: a built --release program, nine runs, the std/ of the merge base against the std/ of the branch, a measurement and not a gate (it exits 0 whatever it finds and says where it could not measure). A slice with a worse ratio is not landed until the decision it implements is revisited with the numbers; Argus reads the table in the PR. The first slice adds tools/collection-cost.sh in that pattern and runs it at the end of tier B, as buffer-cost.sh is.

Two cost risks are named here so that a slice checks them first. A native wrapper is a call to a runtime function that the C compiler sees whole (torb_list_get and torb_list_length are static inline in the header), and a body is a function the program's own C holds: gcc inlines a direct call on a concrete type and gets -flto across units; clang inlines inside a unit and has no LTO across units, so the bodies must be emitted static in the unit that calls them, and the slice measures with both compilers where the runner has both. The second is the allocation count: a HashMap of two Buffers allocates two blocks plus the bucket fill where the C table allocates one storage and two raw blocks; the budget of every conformance program (.allocations) must not rise.

7. The natives each slice removes#

NATIVES lists the 52 rows, all verdict rewrite; this record gives the order and what they become. A row is deleted from nativeEntries() in compiler/src/backend/c/natives.trb by the slice that rewrites it, and the drift check of NATIVES fails until it is.

The order owed to NATIVES (#407, landed) is the one above: the lists first because Buffer already has everything they need, the tables after #56, the tries last because they are the one case where the rewrite is not a copy of what exists. The order owed to #53 is that it does not block these slices (decision 1); the five Buffer rows (insert, removeAt, replaceBetween, reverse, clear) are rewritten in a slice of NATIVES of their own once #53 allows a native { } block, and until then the ArrayList bodies call them.

8. The slices#

Each slice is one PR of one or two Conventional Commits and is filed as its own issue only when it starts (the loop files it; this record does not). The two-commit rule (CLAUDE.md, and the recipe of COLLECTIONS section 5, C2c): when a slice changes what the seed compiler has to read, the first commit teaches the compiler both forms and is reached by nothing, the owner refreshes the seed, and the second commit moves std/. The seed refresh is the owner's and is never part of a slice.

Every slice leaves both tiers of the gates green: the docs gates (torb docs check docs, torb docs index --check docs, torb docs skill docs skills --check), torb check ., torb canon --check, the bootstrap fixpoint of tier B, and the allocation budget of every conformance program. A slice that touches a published doc comment regenerates skills/.

9. What stays open#

One question is not decided here, because it is a public commitment: the guarantee Buffer and ArrayList make to a program about when a write copies. Decision 2 changes it in one place (a write to a list with a live slice copies the window, as it does today, and a write to a Buffer with a live copy copies the storage, as it does today), and a real trie (decision 11) would make a copy-then-write cheap for the Trie* types only. Whether the docs state the guarantee as a promise of List ("a write is O(1) amortized unless a copy is alive") or leave it as an observation of the implementation is the owner's to say, because it fixes what the persistent types are for. Until then the docs say what they say today. It blocks none of the slices.

Everything else is decided above: the representation (1), the slice (2), withCapacity (3), literals and for (4), the Close hazard (5), the table (6, 7), the order with #56 and #53 (8), the trie question (9 to 11), and the bound and its numbers (section 6).

Related#

• NATIVES.md — the 52 rows, the closed kernel K1 to K8, the measurements M1 to M6.
• COLLECTIONS.md — gap 6 (Buffer), gap 9 (for over a concrete collection), section 3.3 (the tries), section 3.6 (the iterator as an inline record).
• BACKEND.md — 3.5 (the heap containers), 3.7 (the manifest and native fn bodies).
• PERFORMANCE.md — P7 (the baselines), finding 10 and round P9 (#56).
• DESTRUCTORS.md — 2a, why a slice of a Close item copies.