U Memory System

#Why No GC U has no garbage collector. Ownership is a DAG — strong references point from parent to child, never upward or cyclically. When an owner's refcount hits zero, its entire subtree dies. No tracing, no mark-sweep, no pause. The cost of deallocation is proportional to what was allocated by that owner, not to total heap size. Back-references use +R(parent) annotations. The compiler treats them as weak: they don't contribute to the reference count and resolve to none when the referent dies. The linter enforces the DAG structure using Tarjan's SCC algorithm on the type-reference graph — any cycle must have at least one +R(parent) edge, or the program is rejected. #Slab Chain Allocator Every owner has a slab chain. Allocations bump a pointer within the current slab. When a slab fills, a new slab twice the size is linked in. Owner └─ slab_ptrs: [ptr0, ptr1, ptr2, ...] │ │ │ ▼ ▼ ▼ 4KB 8KB 16KB ... The chain for n total bytes has at most ⌈log₂(n/initial)⌉ slabs. Each slab is a power-of-two allocation, which system allocators can service efficiently through size-class free lists. Allocation is a bump pointer: increment, compare to end. No per-object free-list traversal and no general-purpose allocation metadata is required for individual owner-scoped objects. Deallocation walks the chain and frees each slab. For ordinary request-sized allocations this is only a handful of frees. Cost is O(log n) slab releases for n total bytes and effectively constant for typical scopes. #NaN-Boxed Tagged Values Dynamic values in Lists, Maps, and Trees can use a single 8-byte tagged representation via NaN-boxing. real double → raw IEEE representation, with NaNs canonicalized small integer → tagged integer payload pointer → tagged pointer payload bool true → reserved tagged pattern bool false → reserved tagged pattern none → reserved tagged pattern tombstone → reserved tagged pattern The exact tag layout is an ABI detail. Floating-point NaNs must be canonicalized so tagged payloads cannot be confused with numeric NaNs. A dynamic U value is one machine word whenever its value fits the tagged representation. Leaf values therefore require no separate heap allocation. Tags and payloads are extracted with masks, shifts, and comparisons. #Lists Lists use stable power-of-two slabs. Elements do not move merely because the List grows. slab 0: 4 elements slab 1: 8 elements slab 2: 16 elements slab 3: 32 elements ... Once an element receives a logical index, appending later elements does not change that index or relocate the existing element. O(1) Random Access For index k, the slab can be determined using the highest significant bit, clz, shifts, and arithmetic. slab_index = 31 - clz((k >> 2) + 1) base = (4 << slab_index) - 4 pointer = slab_ptrs[slab_index] address = pointer + (k - base) * element_size The slab-pointer header is small and normally cache-resident. Iteration Iteration holds the current slab pointer, current element pointer, and remaining elements in the slab. It walks contiguous memory until the slab ends, then advances to the next slab. Sequential iteration therefore approaches ordinary contiguous-memory bandwidth and works naturally with hardware prefetching. O(1) Append Appending within the current slab is a bump. When that slab fills, allocate the next power-of-two slab and continue there. Existing elements are never copied merely because capacity grows. Append is therefore worst-case O(1) with respect to existing List length rather than merely amortized O(1). #Maps: Stable Ordered Storage A U Map is fundamentally ordered dense storage, not a hash table. Its authoritative representation is two parallel stable Lists: Map<K,V> index 1 2 3 4 5 │ │ │ │ │ keys [K1] [K2] [K3] [K4] [K5] values [V1] [V2] [V3] [V4] [V5] The defining invariant is insertion index i ↔ keys[i] ↔ values[i]. Indices increase sequentially. Existing live entries never move merely because later entries are inserted. The authoritative direction is index → (key, value). The reverse direction key → index is derived acceleration data. #First Rule of Map Optimization: Avoid Reverse Lookup A conventional hash table assumes key → hash → storage location is fundamental. U does not. Many important PHP, JavaScript, JSON, routing, configuration and application patterns already reveal the relevant stable index through iteration, insertion, compiler-constant keys, shared shapes, previous resolution, or compiler dataflow. Before optimizing key → index, determine whether the operation is necessary at all. The general dynamic resolver handles only the residual case. #Iterator Provenance foreach ($a as $b => $c) { use($a[$b]); } The iterator already knows b, c, and the current stable index bi. Therefore $a[$b] becomes a.values[bi]. There is no reverse lookup. Nested iteration follows the same rule: foreach ($a as $b => $c) { foreach ($c as $d => $e) { use($a[$b][$d]); } } The compiler retains the outer stable index bi and inner stable index di, so $a[$b][$d] can compile approximately as a.values[bi].values[di]. The same principle applies to JavaScript. Iteration-derived keys carry hidden stable-index provenance. If the key is used only to return to its originating Map, the compiler may not need to materialize it at all. #Compiler-Constant Keys and Symbols Literal and compiler-constant keys should not repeatedly execute their key semantics at runtime. $user["id"] $user["name"] $user["email"] "id" → Symbol A "name" → Symbol B "email" → Symbol C A symbol is not a universal Map index. Map A: Symbol("foo") → index 7 Map B: Symbol("foo") → index 19 Map C: Symbol("foo") → absent The pipeline is constant K → canonical Symbol(K) → per-Map/per-shape resolution → stable index i → cache i. Once a Map or shared shape establishes (Map/shape, Symbol("email")) → 2, subsequent accesses can use a guarded cached index. Unrelated appends do not invalidate index 2. #Object Key Semantics Arbitrary objects may be Map keys by defining: __hash__() → deterministic intermediate H __equals__(other) → bool Both are -E-D by default, like ordinary U functions. A key implementation requiring effects or nondeterminism is not eligible for ordinary deterministic Map resolution. K ↓ K.__hash__() ↓ H ↓ resolver generation(s) ↓ candidate stable index i ↓ keys[i].__equals__(K) ↓ match / collision Two unequal objects may legally produce the same H. Resolver algorithms must preserve enough collision information to examine every relevant candidate until __equals__ establishes the result. __hash__ selects candidates; __equals__ establishes key identity. Constant Objects Compiler-constant objects can be canonicalized through the same semantics. Because ordinary U functions are -E-D, these methods may execute during compile/JIT time when their inputs are compiler constants. The resulting symbol still maps independently to a stable index in each Map or shape. Dynamic objects use the same semantics at runtime. #Shared Shapes Maps with the same insertion history can share symbol-to-index metadata. Shape #174 Symbol("id") → 0 Symbol("name") → 1 Symbol("email") → 2 Individual Maps can share the shape rather than maintaining equivalent reverse metadata separately. Shape transitions can themselves be shared. Insertion history is a Map shape. This is especially useful for records, JSON objects, database rows, headers, configuration structures and API payloads. #Tombstones and Reinsertion Deletion does not move later entries. It writes TOMBSTONE into the key position and iteration skips it. before: 0 A | 1 B | 2 C after: 0 A | 1 TOMBSTONE | 2 C Append-on-Reinsert For PHP-compatible semantics, reinserting B appends it, e.g. B → 3. Historical resolver entries remain harmless because the old position is a tombstone. When multiple historical candidates exist, the newest live insertion wins; because insertion indices increase monotonically, this is the greatest live candidate index. Revive-on-Reinsert Other collection semantics may revive the old position. Tombstoning is storage mechanism; reinsertion ordering is language/collection policy. #Stable-Index Invalidation A stable index belongs to a Map storage generation. Append, value update, new storage slabs, tombstones, resolver growth/sealing/replacement/compaction, membership-filter rebuilds, SwissTable resizing inside an unsealed resolver generation, and switching algorithms for later generations do not renumber unaffected entries. Deleting the cached key makes that key's cached position absent/stale, but does not invalidate unrelated indices. Append-on-reinsert gives the reinserted key a new stable index. Storage Compaction Storage compaction that packs away tombstones renumbers entries and therefore creates a new Map storage generation. Caches capable of surviving arbitrary code must be guarded by storage generation or equivalent shape identity. Mutation invalidates a stable index only when it changes the relevant index → entry mapping. #Resolver Compaction Is Not Storage Compaction Map storage compaction renumbers keys[]/values[], changes the storage generation, and invalidates moved stable indices. Resolver compaction reorganizes reverse-index metadata while leaving keys[]/values[] untouched, so stable indices remain valid. #Dynamic Resolution After eliminating iterator provenance, compiler-constant work, shape specialization and cached resolution, the residual problem is dynamic K → stable index i. Maps expose an abstract resolver: Resolver<K>.probe(K) → candidate stable index(es). Exact key equality remains authoritative. The resolver is acceleration metadata, not Map storage. #Two-Stage Dynamic Resolution K ↓ deterministic key function ↓ H ↓ per-Map reverse resolver ↓ stable index i ↓ keys[i] exact validation ↓ values[i]