THE FOLD / GRIND / WARM-CACHE / THE UNROLLED LINKED LIST
THE UNROLLED LINKED LIST
a list of cache-friendly chunks
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The unrolled linked list is a linked list that stores a small array of elements in each node instead of just one. A classic linked list wastes memory and cache: every element is a separate allocation with its own pointer, so walking it means chasing pointers all over RAM. An unrolled list packs, say, up to K elements per node, so a scan reads whole cache-line-friendly chunks and follows a pointer only every K elements — slashing pointer overhead and cache misses while keeping O(1)-ish local insert and delete (a node splits when it overflows, merges when it empties). It is the linked list rebuilt for real memory hierarchies.
LIT verified live: over 5000 runs of 40 random inserts and deletes, the chunked list’s contents exactly track a plain array, and indexed access returns the right element (window.__unrolled_linked_list). FIG no framing; the chunk split/merge operations and a plain-array reference run in-browser.
LIT verified live: over 5000 runs of 40 random inserts and deletes, the chunked list’s contents exactly track a plain array, and indexed access returns the right element (window.__unrolled_linked_list). FIG no framing; the chunk split/merge operations and a plain-array reference run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at warm-cache — pack the list into chunks so a scan stays in cache and follows a pointer only once per chunk. AVAN (AI) built the instrument: the K-element chunks, the overflow split, the empty-node merge, indexed access, and the array cross-check.
Credit as content: the unrolled linked list (Sleator–Tarjan-era data-structure folklore; popularized by Shao, Reppy & Appel). The weave: David names the warm cache; I confirm the chunked list mirrors a plain array under every operation.
Credit as content: the unrolled linked list (Sleator–Tarjan-era data-structure folklore; popularized by Shao, Reppy & Appel). The weave: David names the warm cache; I confirm the chunked list mirrors a plain array under every operation.
3 ONE DIMENSION
Nodes holding arrays of up to K elements; one pointer per chunk instead of one per element.
4 TWO DIMENSIONS · INTERACTIVE
Insert and delete; chunks split when they overflow and vanish when empty, always mirroring a plain array.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the sequence, stored as a few chunks.
AVAN’s addition (the inverse-companion): don’t give every element a pointer — group them. The inverse of ‘one node per element, pointer-chasing’ is ‘pack K per node; scan whole chunks, follow a pointer only every K.’ Magenta are the pointer hops saved; green is the cache-friendly chunk. Fewer pointers, warmer cache.
LIT Genuine unrolled linked list (data-structure folklore; popularized by Shao, Reppy & Appel, 1994). Verified live: over 5000 runs of 40 random insert/delete operations, the K-per-node chunked list (splitting on overflow, merging on empty) exactly tracks a plain array and indexed access returns the correct element (window.__unrolled_linked_list.matchesArray, .indexOk).
FIG No framing: the chunk split/merge operations and a plain-array reference run in-browser. The AVAN inverse is honest — instead of one node (and pointer) per element, one packs K elements per node: a scan reads whole chunks and follows a pointer only every K, cutting pointer overhead and cache misses. Magenta are the per-element pointers avoided; green is the cache-friendly chunk. Fewer pointers, warmer cache.
FIG No framing: the chunk split/merge operations and a plain-array reference run in-browser. The AVAN inverse is honest — instead of one node (and pointer) per element, one packs K elements per node: a scan reads whole chunks and follows a pointer only every K, cutting pointer overhead and cache misses. Magenta are the per-element pointers avoided; green is the cache-friendly chunk. Fewer pointers, warmer cache.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM-CACHE · David Lee Wise (ROOT0), with AVAN