collections: design record for `ArrayList`, the hash tables and the tries on `Buffer` (step 1 of #55)

orion commented

2026-10-23 04:17:49 +00:00

Collaborator

Context

Step 1 of #55 (collections: rebuild ArrayList, the hash tables and the tries on Buffer; ROADMAP "The kernel of natives", COLLECTIONS gap 6). Buffer<Item> is built (#54, #299, #300), but #55 is not one PR: the compiler names ArrayList in about 200 places (list literals, the element access and write lowering, the ArrayList.* rows of compiler/src/backend/c/natives.trb, RuntimeKind.ListStorage), HashMap and HashSet stand on runtime/map.c (open addressing, tombstones, insertion order) which #56 is changing right now (torb_map_slot), and TrieList, TrieMap and TrieSet are today documented aliases of the flat storage, not tries. What the rebuilt types look like, in which order, and what each step must not cost is not written down. That has to be decided in writing before any native is removed. This step is documentation only.

Goal

A design record docs/design/COLLECTION-STORAGE.md that specifies how ArrayList, the hash tables and the tries are written in TorbScript over Buffer, and cuts the work into slices, each one PR.

Acceptance criteria

docs/design/COLLECTION-STORAGE.md exists with pdisc frontmatter, a status line ("designed, not built") and an entry in docs/design/index.md; COLLECTIONS gap 6 and ROADMAP "The kernel of natives" link it; docs/ regenerates skills/ (torb docs skill docs skills, a tier A gate).
ArrayList: the record decides the representation (a TorbScript type holding a Buffer, or the compiler's list type staying a primitive whose members are bodies per #53) and says what happens to the three things the rewrite touches: the O(1) shared slice against Buffer.slice copying, withCapacity as the one native the lowering answers itself, and list literals and for over a concrete ArrayList (COLLECTIONS gap 9). Each is a numbered decision with its reason; a decision that costs speed names the benchmark that proves it acceptable.
Hash tables: the layout of HashMap and HashSet as TorbScript over Buffer (entry vector, bucket array, tombstones, compaction, insertion-order iteration, entryAfter and itemAfter as the iteration contract), checked against what runtime/map.c does today; how it meets #56 (the slot access of map[key] = value) and in which order the two land.
Tries: states plainly that TrieList, TrieMap and TrieSet are aliases of the flat storage today and decides whether the rewrite builds real persistent tries (COLLECTIONS 3.10 "copy on write, per structure") or keeps the aliases on the rewritten types. Either way the observable behaviour (order, Show, equality) is unchanged.
Cost: a table of the benchmarks that bound each slice, with today's number as the baseline: benchmarks/list-index, list-iterate, array-write, buffer-write, map-count, bytes-pass, plus any new one the record names. The bound is "no slower than before" read as a ratio on the same forge CI runner (the pattern of tools/buffer-cost.sh: fastest of nine runs, measurement and not a gate). A slice whose measured ratio is worse is not landed until the record's decision for it is revisited with the numbers.
Natives: the ArrayList.*, HashMap.*, HashSet.*, Trie*.* rows that each slice removes from the manifest are named, with the migration order owed to the audit table of #52 (docs/design/NATIVES.md, #407, if landed; otherwise the manifest itself) and to #53 where a kernel native becomes a body.
Slices: the record lists them in order, each fitting one PR of one or two Conventional Commits, with its seed impact under the two-commit rule (teach both forms, refresh the seed, then migrate); the seed refresh itself stays with the owner. A slice is filed as its own issue only when it starts.
Open design questions are decided by the record (technical choices); one is left open only if it is a public commitment, a cost, a product direction or a breaking change of a published contract.
Gates green in both tiers.

Design record point

COLLECTIONS gap 6 and 3.7 / 3.10; ROADMAP "The kernel of natives"; BACKEND 3.5 (the container natives) and 3.7 (the manifest); PERFORMANCE round P9 (#56) for the map.

Seed impact

None for this step (documentation only). The later slices add or remove natives the compiler looks up, so they fall under the two-commit rule.

Size

One PR, one Conventional Commit (docs(collections): design record for ArrayList, the hash tables and the tries on Buffer).

Out of scope

Any change to std/, runtime/ or compiler/; running the benchmarks (the record names them and takes today's numbers from the published performance tables or states that the first implementing slice records them); the seed; Bytes and Window (done, #300 and #4).

Dependencies

None hard. Read docs/design/NATIVES.md (#407) and the record of #410 if they have landed. Part of #55; #56 changes runtime/map.c concurrently, so the hash table section must be written against its landed shape.

## Context Step 1 of #55 (collections: rebuild `ArrayList`, the hash tables and the tries on `Buffer`; ROADMAP "The kernel of natives", COLLECTIONS gap 6). `Buffer<Item>` is built (#54, #299, #300), but #55 is not one PR: the compiler names `ArrayList` in about 200 places (list literals, the element access and write lowering, the `ArrayList.*` rows of `compiler/src/backend/c/natives.trb`, `RuntimeKind.ListStorage`), `HashMap` and `HashSet` stand on `runtime/map.c` (open addressing, tombstones, insertion order) which #56 is changing right now (`torb_map_slot`), and `TrieList`, `TrieMap` and `TrieSet` are today documented aliases of the flat storage, not tries. What the rebuilt types look like, in which order, and what each step must not cost is not written down. That has to be decided in writing before any native is removed. This step is documentation only. ## Goal A design record `docs/design/COLLECTION-STORAGE.md` that specifies how `ArrayList`, the hash tables and the tries are written in TorbScript over `Buffer`, and cuts the work into slices, each one PR. ## Acceptance criteria - [ ] `docs/design/COLLECTION-STORAGE.md` exists with pdisc frontmatter, a status line ("designed, not built") and an entry in `docs/design/index.md`; COLLECTIONS gap 6 and ROADMAP "The kernel of natives" link it; `docs/` regenerates `skills/` (`torb docs skill docs skills`, a tier A gate). - [ ] **`ArrayList`:** the record decides the representation (a TorbScript type holding a `Buffer`, or the compiler's list type staying a primitive whose members are bodies per #53) and says what happens to the three things the rewrite touches: the O(1) shared `slice` against `Buffer.slice` copying, `withCapacity` as the one native the lowering answers itself, and list literals and `for` over a concrete `ArrayList` (COLLECTIONS gap 9). Each is a numbered decision with its reason; a decision that costs speed names the benchmark that proves it acceptable. - [ ] **Hash tables:** the layout of `HashMap` and `HashSet` as TorbScript over `Buffer` (entry vector, bucket array, tombstones, compaction, insertion-order iteration, `entryAfter` and `itemAfter` as the iteration contract), checked against what `runtime/map.c` does today; how it meets #56 (the slot access of `map[key] = value`) and in which order the two land. - [ ] **Tries:** states plainly that `TrieList`, `TrieMap` and `TrieSet` are aliases of the flat storage today and decides whether the rewrite builds real persistent tries (COLLECTIONS 3.10 "copy on write, per structure") or keeps the aliases on the rewritten types. Either way the observable behaviour (order, `Show`, equality) is unchanged. - [ ] **Cost:** a table of the benchmarks that bound each slice, with today's number as the baseline: `benchmarks/list-index`, `list-iterate`, `array-write`, `buffer-write`, `map-count`, `bytes-pass`, plus any new one the record names. The bound is "no slower than before" read as a ratio on the same forge CI runner (the pattern of `tools/buffer-cost.sh`: fastest of nine runs, measurement and not a gate). A slice whose measured ratio is worse is not landed until the record's decision for it is revisited with the numbers. - [ ] **Natives:** the `ArrayList.*`, `HashMap.*`, `HashSet.*`, `Trie*.*` rows that each slice removes from the manifest are named, with the migration order owed to the audit table of #52 (`docs/design/NATIVES.md`, #407, if landed; otherwise the manifest itself) and to #53 where a kernel native becomes a body. - [ ] **Slices:** the record lists them in order, each fitting one PR of one or two Conventional Commits, with its seed impact under the two-commit rule (teach both forms, refresh the seed, then migrate); the seed refresh itself stays with the owner. A slice is filed as its own issue only when it starts. - [ ] Open design questions are decided by the record (technical choices); one is left open only if it is a public commitment, a cost, a product direction or a breaking change of a published contract. - [ ] Gates green in both tiers. ## Design record point COLLECTIONS gap 6 and 3.7 / 3.10; ROADMAP "The kernel of natives"; BACKEND 3.5 (the container natives) and 3.7 (the manifest); PERFORMANCE round P9 (#56) for the map. ## Seed impact None for this step (documentation only). The later slices add or remove natives the compiler looks up, so they fall under the two-commit rule. ## Size One PR, one Conventional Commit (`docs(collections): design record for ArrayList, the hash tables and the tries on Buffer`). ## Out of scope Any change to `std/`, `runtime/` or `compiler/`; running the benchmarks (the record names them and takes today's numbers from the published performance tables or states that the first implementing slice records them); the seed; `Bytes` and `Window` (done, #300 and #4). ## Dependencies None hard. Read `docs/design/NATIVES.md` (#407) and the record of #410 if they have landed. Part of #55; #56 changes `runtime/map.c` concurrently, so the hash table section must be written against its landed shape.

orion added the

loop

ready

labels

2026-10-23 04:17:49 +00:00

orion referenced this issue

2026-10-23 04:17:56 +00:00

collections: rebuild ArrayList, the hash tables and the tries on Buffer #55