intrusive

A Large Array Of Things (LAOT), as described by Anton Mikhailov.

A forest of uniformly shaped nodes in one flat array, linked by integer indices instead of pointers. Children of a node form a circular doubly linked ring.

go get github.com/soypat/intrusive@latest

Design goals

Indices, not pointers. A node is four uint32 links plus a generation and a kind. No pointer chasing, no per-node allocation, and the whole structure is one contiguous slice.

Handles go stale, detectably. Every slot carries a generation, bumped on free and on reset. A handle to a recycled slot resolves to null instead of silently naming whatever thing landed there.

No panics, no error returns. Index 0 is the null sink: a real, never-owned thing. Allocation failure, a stale handle, a handle from another LAOT, and a refused operation all resolve to it. Reading and writing it is legal and harmless — garbage there is only reachable by starting from a null ref, so no live tree can be corrupted by it.

The contract: check the ref you were handed. Operating on a null one is a no-op or yields another null ref. That is what makes fluent wrappers over this package safe to chain.

Invalid states are unrepresentable, and Check() proves it. Sibling links only ever connect things that share a parent. A node in no ring is a ring of one. Check() walks the arena and asserts every invariant; the tests call it after every mutation, and the fuzzer drives millions of random operation sequences through it.

Compact, and invisible to the GC. The arena is one allocation. If T holds no pointers, the whole thing holds no pointers, and Go's collector never scans it — no matter how many things are in it. Measured on a 200k-node tree against the equivalent *Node tree:

	pointer tree	LAOT
GC mark pause	10.0 ms	86 µs
heap objects	199,993	2
bytes/node	79	64

An empty heap marks in 79 µs, so the LAOT costs the collector essentially nothing. Put one string in your T and this evaporates — the collector goes back to scanning every entry.

Non-goal: Traversal slower than pointer chasing: A tree walk over a LAOT costs 2–4× the same walk over a pointer tree due to validation of indices. What you buy is safety, compactness and a quiet GC — not pointer-chasing speed. Also although memory is contigous it does not guarantee cache locality. Locality depends on order which you added entities to LAOT.

Times below are ns per node, same 200k-node tree:

	pointer tree	LAOT
All — linear sweep	n/a	3.6
tree walk, built in tree order	4.5	12.9
tree walk, built scattered	18.7	40.7
tree walk, after delete/reuse churn	—	50.6

inventory-ecs example

In this example the LAOT is used to contain the following data structure:

type Entity struct {
	Name     [16]byte
	Position ms2.Vec
	Health   uint8
	Rarity   Rarity
	Quantity uint8 // 255 max item quantity.
}

The size for Entity is 32 bytes. When stored in a LAOT each entry occupies an additional 6*4=24 bytes. So sizes per LAOT entry is 56 bytes regardless of system architecture.

So a Raspberry Pi Pico (RP2040) could handle 2500 simultaneous entities at 140kB, occupying less than half of available RAM. This is regadless of the complexity of the entity interrelationships (child/sibling/parenthoods).

Notably on larger 64-bit systems it's interesting to note 20 million of above Entities uses up 1.1GB of RAM- regardless of complexity of entity relationships.

Example

package main

import (
	"fmt"

	"github.com/soypat/intrusive"
)

type Kind uint8

const (
	_ Kind = iota // The zero kind marks a free slot. It can never name a live thing.
	KindDir
	KindFile
)

func main() {
	var laot intrusive.LAOT[string, Kind]
	laot.Reset(64) // Must be Reset before use.

	root := laot.New(KindDir).Set("/")
	if root.IsNull() {
		return // Out of capacity. This is the only check you owe.
	}
	src := root.NewChild(KindDir).Set("src")
	src.NewChild(KindFile).Set("laot.go")
	src.NewChild(KindFile).Set("check.go")

	doc := root.NewChild(KindDir).Set("doc")
	readme := doc.NewChild(KindFile).Set("README.md")

	// Moving one child moves exactly that one; its siblings stay put.
	src.AdoptChild(readme)

	for c := range root.AllChildren { // iter.Seq. The body may Delete what it is handed.
		fmt.Println(*c.Value(), c.NumChildren())
	}
	// src 3
	// doc 0

	doc.Delete() // Frees doc and everything under it, in one pass.

	// A stale handle sinks into slot 0 rather than aliasing a recycled thing.
	fmt.Println(doc.IsNull(), *doc.Value() == "") // true true

	laot.Clear() // Reuse the arena. No allocation, and every handle above goes stale.
}

See _examples/inventory-ecs for a fluent domain layer built on top: a game inventory where containment is the tree.