Compiler Changelog
A record of the compiler's internal quality-of-implementation work — LLVM passes, the memory-model chronology, in-place reuse, structured parallelism, resource safety, and codegen. None of it changes the language specification; it is the "what was done and why" history behind the behavior described in Compiler Architecture and the IR Reference. A short list of deliberately-deferred capabilities is kept at the end so the design analysis is not lost.
Entries below describe the implementation at the time each item landed. In particular, the early arena-only, erased-drop, old closure-layout, and "no runtime RC" entries are historical and are superseded by RC Perceus migration below. Use the architecture and IR references for the current contract.
Completed Work
All original audit findings have been addressed:
| Area | What was done |
|---|---|
| RC Perceus migration | Escaping ordinary graphs now use compiler-inferred ownership and runtime RC: per-function borrowed/consumed summaries, last-use/branch-entry RcDrop, late RcDup, layout-aware recursive drops, uniqueness specialization, and DropReuse/AllocReusing with a fresh-allocation null fallback. Complete-graph normalization prevents mixed-lifetime parents and children. Small cells use dense per-thread RC chunks plus constant-time exact-size free-list bins; large cells return directly to the OS. Compiler-proven scratch, task/capability state, mmap-backed views, parallel publication copies, and the persistent Map/HashMap to-space retain explicitly classified regions with multi-scale RSS gates. See RC Perceus migration chronology and verification. |
| LLVM passes | Targeted pipeline (mem2reg, instcombine, early-cse, reassociate, gvn, dce, inline, licm, dse) at O1–O3. PLT32 + PE relocation support. Freestanding builtins (memcpy, memset, strlen, memcmp, bcmp) emitted per module. |
| Memory allocator | OS-backed mmap/VirtualAlloc chunks (4 MB each, on demand; a single allocation larger than one chunk grows a chunk to fit — see CO-31). Bounds checking with clean error. |
| Arena deallocation | Phase 1: scope watermarks for copy-type results. Phase 2a: TCO per-iteration reset for copy-type args. Phase 2b: copy-out (CopyOutArena IR instruction) for TStr scope results. Phase 2c: TCO copy-out for TStr and TList(copy-type) args. Phase 2d: abandoned OS chunk reclamation via ReclaimArenaChunks (split from RestoreArenaState to prevent use-after-free — restore resets pointers, reclaim frees chunks after copy-out completes). Phase 3: per-function-call watermarks. Phase 4: extended copy-out — CopyOutList (deep cons-chain copy for TList with copy-type element), CopyOutClosure (closure struct + env copy; 24-byte closure layout {code, env, env_size}), ADT with copy-type fields. Phase 5: extended TCO copy-out — CopyOutTcoListCell for TList(TStr) and TList(TList(copy-type)) args (single-cell + head copy), closure and ADT args via CopyOutClosure/CopyOutArena. |
| Extended TCO copy-out | Replaced CanCopyOutTcoArg with GetTcoCopyOutKind in Lowering.cs. Added CopyOutTcoListCell IR instruction for single-cell + head copy-out, and ListHeadCopyKind enum (Inline, String, InnerList). TList(TStr) via CopyOutTcoListCell(String), TList(TList(copy-type)) via CopyOutTcoListCell(InnerList), closures via CopyOutClosure, ADTs via CopyOutArena(staticSizeBytes). |
| Linkage-aware Byte.indexOf | Ashes.Byte.indexOf no longer unconditionally imports libc memchr on Linux (which made every scan-using image dynamically linked). Images that already carry the glibc-linked TLS runtime keep glibc's SIMD memchr (marker global __ashes_glibc_runtime); all other images use a freestanding per-module SWAR word scan (__ashes_memchr_swar, Hacker's-Delight zero-byte mask, absolute-address alignment so unaligned Byte views are safe) and stay fully static. |
| String operations | EmitCopyBytes → LLVMBuildMemCpy. Comparison → memcmp/bcmp. Literals → .rodata global constants (no heap alloc). |
| Pattern matching | Tag/zero/non-zero checks → single CmpIntEq/CmpIntNe + one conditional jump. |
| Function attributes | nounwind on all functions. willreturn, noalias, nonnull, readonly, memory(read) on builtins. |
| CPU targeting | --target-cpu CLI flag; native auto-detects via LLVMGetHostCPUName/LLVMGetHostCPUFeatures. |
| IR optimizer | Constant folding (with cross-label propagation), identity/strength reduction, unreachable code elimination, dead code elimination. |
| Compile-time evaluation | IrCompileTimeEval runs first in IrOptimizer.Optimize — best-effort partial evaluation that removes work LLVM cannot (it never folds a recursive function to a constant, and simplifycfg is deliberately excluded from the pass pipeline). A straight-line caller scan finds a CallClosure/CallKnown whose closure and argument are compile-time constants and whose callee is pure-and-modeled, runs a small concrete IR interpreter, and replaces the call with a LoadConst*; the existing DCE + arena-bracket passes then delete the now-dead closure/argument construction. Evaluability is a whole-program least fixpoint (ComputeEvaluableFunctions, same shape as ComputeNonAllocatingFunctions): a function is evaluable iff every reachable instruction is modeled and side-effect-free (no IO / FFI / capability-handler / async / resource / transcendental / big-int / bytes / raw-memory op) and every function it references by label is evaluable; CallClosure targets are checked dynamically at eval time. Because the interpreter executes the real modeled instruction semantics, a completed evaluation yields exactly the runtime value; any unmodeled/impure instruction, budget overrun, or non-scalar result bails and keeps the original runtime code — best-effort, never an error, no new syntax, no spec change. Memoization on (label, env, arg) makes pure recursion cheap (fib(40) is ~41 evaluations, not 331M). Step (50M) and depth (20k) budgets bound compiler work; the interpreter runs on a 512 MB-stack thread so the depth cap turns runaway recursion into a clean bail rather than an uncatchable StackOverflowException that would abort the compiler (found via a 2M-deep linear recursion core-dumping the compiler). Scope: scalar results (Int/Bool/Float) and closures without a captured environment; string/aggregate result embedding is deferred (see Deferred). Toggles: ASHES_NO_COMPILE_TIME_EVAL disables the pass, ASHES_EXPLAIN_COMPILE_TIME traces each decision. Measured: fib(40) ~268 ms of runtime work → a printed constant (~60 µs, and constant regardless of N); fib(35) 24.3 ms → 56 µs; typical intrinsic/IO-bound programs unchanged (identical output and binary); compile time unchanged within noise. Gotcha: the e2e TestRunner compiles at -O0, so it does not exercise this pass — the IrOptimizerTests Compile_time_eval_* cases (which call IrOptimizer.Optimize directly) are what verify folding fires; correctness across real programs is verified by a -O2-vs--O0 differential and on linux-x64, linux-arm64 (qemu), win-x64 (Wine). Regressions: tests/compile_time_eval_recursive.ash, tests/compile_time_eval_factorial.ash. |
| Borrow elision | ElideBorrowsForConstants in IrOptimizer.cs. Temp aliasing infrastructure: use-def chain tracking per temp (copy-type producers via LoadConst* scan, per-temp use count via CollectUsedTemps). Copy-type elision: Borrow instructions whose source is produced by LoadConstInt/LoadConstFloat/LoadConstBool are removed; all uses of the borrow target remapped to the original source temp. Single-use elision: non-copy Borrow instructions whose target is used exactly once are also elided. Transitive chain resolution via ResolveTemp. RemapSourceTemps helper rewrites all source-temp references in any IrInst variant using with record syntax. |
| Drop elision | ElideRedundantDrops in IrOptimizer.cs (Pass 4). Removes non-resource-type Drop instructions (String, List, Tuple, Function, non-resource ADTs) — these are no-ops in codegen since arena deallocation handles bulk memory reclamation. Resource-type drops (Socket) are always preserved for platform-specific cleanup. Also removes the associated LoadLocal when its target temp is only used by the elided Drop, and StoreLocal instructions to slots with no remaining LoadLocal references — cascading dead code cleanup in a single pass. Uses BuiltinRegistry.IsResourceTypeName to distinguish resource types. |
| TCO | IR-level tail recursion → loop. LLVMSetTailCall on tail-position calls. |
| Escape analysis | Conservative stack allocation for proven non-escaping values. Added AllocStack, AllocAdtStack, and MakeClosureStack IR instructions plus LLVM alloca codegen. Closures are stack-allocated when used only as direct callees within scope (including captured-env closures), and ADTs are stack-allocated for immediate single-arm constructor destructuring (`match Box(42) with |
| Debug info | DW_TAG_auto_variable for locals, DW_TAG_formal_parameter for lambda args. Custom DWARF language code 0x8001. isOptimized wired to -O level. |
| Decision-tree matching | Matches over >4 single-ADT constructor arms (distinct tags, trivial sub-patterns, no guards) lower to one SwitchTag IR instruction → LLVM switch. O(n) tag-comparison chain → O(log n) (or O(1) where LLVM picks a jump table). |
| Jump-table linking | The image linkers apply switch jump-table relocations (R_X86_64_64 in .rela.rodata, IMAGE_REL_AMD64_ADDR64 in .rdata, defensive R_AARCH64_ABS64), so LLVM's O(1) table dispatch links and runs correctly; the no-jump-tables attribute was removed. |
| String-literal interning | Identical string-literal .rodata globals are content-addressed and emitted once per module (LlvmTargetContext.GetOrAddStringLiteralGlobal), shared across all functions and internal call sites. Compile-time, bounded, leak-free. |
| Mutual-recursion TCO | Eligible let recursive … and … groups (same arity, identical parameter types, a cross-member tail call) are merged into one self-recursive dispatch function with thin per-member wrappers, so the existing single-function TCO turns mutual recursion into a loop. Ineligible groups keep the closure path. Design constraint: members can legally have different parameter types (ping: Int → Str tail-calls pong: Str → Str), which a single shared typed parameter list cannot merge without unifying incompatible types; hence the same-arity + identical-parameter-types gate (verified against each member's inferred type). Heterogeneous-parameter generalization would need distinct per-member slots (an IR-level slot-union loop) or opaque-coercion dispatch. |
| In-place reuse (Perceus-style) | Immutable recursive-ADT accumulators are rebuilt in place instead of reallocated: a one-time defensive deep copy at loop entry makes the accumulator uniquely owned, then matched-and-rebuilt-with-the-same-constructor cells are overwritten (AllocReusing). Covers direct accumulators, helper-rebuild inlining, recursive-function specialization, the full Ashes.Map.set shape (multi-param / nested-recursive-returning / helper-rebuilding / intermediate-value linearity), recursive scalar-list rewriters (untagged cons-cell reuse), and an immediate rewriter over a fresh call-produced list of single-constructor records. The latter overwrites the fresh spine and record heads inside their shared arena call window. At a TCO RC boundary, a same-length fresh list of copy-only records may also reuse the preceding runtime-owned graph: the compiler first checks the complete old spine and every record head for uniqueness, then overwrites fields while preserving RC headers; a mismatch, shared node, or pointer field keeps the normalize-and-drop fallback. Fresh heap leaf fields (Str/Bytes/tuple keys & values) are materialized into a persistent to-space/blob on insert and overwritten in place on update; a genuinely-new insert node also lands in to-space. Pure readers (result type ≠ the accumulator, e.g. Map.get : … → Maybe) are kept off the reuse path so their result cell isn't stranded in the never-reset to-space. A conservative IsFullyReusing gate + AccumulatorIsFullyPersistent guard the per-iteration arena reset (extended to admit reset-safe accumulators + scalar resource-handle args). Result: string/int/tuple-valued Map.set folds and scalar-list rewrite loops are constant-memory. The nested-re-entry leak is addressed by the CO-2 elision below. |
| Move/linearity reuse-copy elision (CO-2) | The reuse entry deep-copy (the specialization f$reuse path and the direct-reuse prologue) is elided when a whole-program move analysis (Lowering.MoveAnalysis.cs) proves the accumulator is uniquely owned at every external call site; the copy stays on any uncertainty, so it can only leak, never corrupt. An accumulator argument is a move when it is a sole-nullary seed, a fully-fresh construction, a move-linear reference to a move-safe accumulator parameter, a let-bound fresh value proven dead-after-use, or a registered-function call admitted by the result-reachability (may-alias) summary. That summary (ComputeResultReach, a monotone least fixpoint) records, per function, which of its own parameters the result may alias (per-parameter multiplicity capped at 2 — internal sharing poisons via hierarchical path tokens + per-binding identity tokens) plus a poison flag; f(args) is a move iff not poisoned and every reached parameter's argument is itself a move (IsResultAliasMove). Covers result-fresh builders (reach {}, incl. recursive let recursive build), wrap-style result-alias builders (reach {x}), higher-order / closure-produced seeds (capture-aware over-application reach), and Ashes.Map.set-shape reuse-rewriting results (nested-recursive-return registration; reach {map,key,value}). Remaining conservative (the correct boundary short of full ownership): a result the summary poisons — reaches a global or an unmodeled shape. Measured: nested Map.set re-entry O(batches×size)→constant; a recursive-builder-seeded fold 504 MB→4.7 MB; a Map.set-result-seeded fold ≈2× (200k-key). |
| Deterministic resource safety | File/socket/process handles are closed deterministically without GC/RC (Ground Rule 6), via an affine ownership model: recursive Drop for resource-bearing aggregates (Result(_,FileHandle), Some(Socket), tuple/list of resources), move-on-destructure and move-on-construction (no double-close), resource drops at the TCO back-edge (fixes the loop-over-files fd leak), Process reaping on drop, and deterministic close of resources captured by an escaping closure (a dropper at closure+24 invoked when the closure is dropped). All runtime gaps closed & verified (fd-bounded under ulimit -n 64). |
| Use-after-close for match-arm-bound resources (CO-4) | The static use-after-close check (ASH006) already tracks resources whether bound by let or by a match arm, but the FileHandle read intrinsics (Ashes.File.readChunk, Ashes.File.readLine) never consulted it, so a handle destructured from Ok(fh) and read after an explicit Ashes.File.close compiled silently (it stayed runtime-safe — the read after close returns an Error). Wired CheckUseAfterDrop into both file-read intrinsics, so a read after close on a match-arm-bound (or let-bound) FileHandle is now flagged at compile time, matching the existing socket/process behaviour. |
| Parallel tunables (CO-5) | The two hard-coded parallelism knobs are now configurable, defaults unchanged. Per-worker stack size: the --parallel-stack-size <size> CLI flag (byte count or K/M/G suffix), threaded BackendCompileOptions.ParallelWorkerStackBytes → LlvmTargetContext → codegen; unset = 1 MiB on linux (mmap) and the OS default on win-x64 (CreateThread). Grain size for map/reduce: exposed as an explicit library parameter — Ashes.Parallel.mapGrained(grain) / reduceGrained(grain), with map/reduce = grain 1 (the original split-to-singleton behavior). |
Structured parallelism (Ashes.Parallel.both) | Genuinely parallel fork/join of two pure thunks on all three targets, deterministic (result identical to sequential) and memory-bounded, via per-thread bump arenas + worker threads + deep-copy-on-join. Per-thread arena mechanism: linux-x64 a GS-segment TCB (arch_prctl); win-x64 the TEB ArbitraryUserPointer (gs:0x28); linux-arm64 real ELF TLS (thread_local arena cursors, TPIDR_EL0, PT_TLS + R_AARCH64_TLSLE relocs resolved in the in-house linker; the entry prologue sets TPIDR_EL0 only when a loader has not — see CO-3). Threads: clone/futex (linux) / CreateThread/WaitForSingleObject (win); a lock xadd/ldxr-stxr worker counter caps concurrency and over-budget forks run inline. both forks only at a concrete result type (deep-copy-on-join needs it); abstract results run sequential. Worker-stack lifetime on linux is tied to true thread exit via CLONE_CHILD_CLEARTID: the kernel zeroes a ctid word and futex-wakes it only after the worker has fully left its stack, and the parent waits on that (non-private FUTEX_WAIT) before reclaiming the stack/TCB/arena — distinct from the result-ready word, so the join still consumes the result immediately. (win-x64 already gates reclamation on WaitForSingleObject, which waits for full exit.) |
| arm64 networking + parallelism coexistence (CO-3) | The arm64 per-thread arena is real ELF TLS (PT_TLS + local-exec cursors) and is now enabled for every arm64 image, including dynamically linked (networking / external) ones — so both can hand a worker its own arena even in a program that also dlopens rustls. The apparent conflict was never in the TLS layout: a dynamically linked image's local-exec PT_TLS is reserved by the loader in the static-TLS block (at the same TPREL the in-house linker bakes in), independently of the DTV that backs the dlopen'd module's dynamic TLS. The only real hazard was the old entry prologue unconditionally msr-ing TPIDR_EL0 to a private BSS block, which on a dynamic image clobbered the loader's thread pointer (breaking rustls/libc TLS). Fix: the prologue now reads TPIDR_EL0 and self-initialises it only when zero (an unloaded static image); a dynamic image keeps the loader's pointer and resolves its arena cursors through the loader-reserved local-exec slot. Verified under qemu-aarch64-static -L <sysroot>: networking-only (HTTPS loopback, external) still runs; a program linking rustls and using both runs correctly and memory-bounded (PT_TLS + dlopen'd rustls both present); parallelism forks genuinely (clone/futex observed via qemu -strace) in dynamically linked images. Caveat (separate, pre-existing, target-independent): a both does not temporally overlap an in-flight async I/O — the async runtime is synchronous/blocking, so a fork runs before or after a live TLS session, never concurrently with one. (The earlier wording here — that both "runs inline" in an async program — was a misdiagnosis: a concrete-result both forks normally regardless of async usage; see CO-7 and its detailed analysis.) That temporal coupling is orthogonal to the arm64 TLS/arena coexistence solved here (tracked as CO-7). |
| win-x64 parallelism + networking coexistence (CO-6) | The win-x64 per-thread arena is the TEB ArbitraryUserPointer scratch slot (gs:0x28), not PE thread-local storage, so — unlike arm64's real-ELF-PT_TLS arena (CO-3) — it does not collide with rustls's Windows TLS: Rust's std TLS goes through the standard PE .tls / TlsAlloc path (the TEB ThreadLocalStoragePointer), which never touches ArbitraryUserPointer. Consequently win-x64 keeps both genuinely forking in networking programs (the fork runtime is emitted unconditionally, with no networking gate). Empirically verified under Wine: a program that runs heavy both fork/join both before and after a full rustls loopback TLS handshake produces correct results on both sides with no crash/corruption (tests/parallel_tls_coexist.ash); the fork is genuine (~2.4× wall-clock speedup, two independent CPU-bound thunks: sequential ≈ 860 ms vs parallel ≈ 355 ms) and memory-bounded (peak RSS flat at ~27 MB across 300 → 30 000 outer iterations — ~2 M forks — on par with the linux-x64 baseline). No CO-3-style conflict exists on win-x64. |
Data-parallel map/reduce (CO-1) | Ashes.Parallel.map/reduce (and the grain-parameterized mapGrained/reduceGrained) are now genuinely data-parallel via call-site monomorphization: above the grain threshold their bodies split the list in half and evaluate the two halves through both, and a saturated call at a concrete element type generates a monomorphic self-recursive specialization whose both splits see a concrete result and fork (at or below grain they run the sequential plSeqMap/plSeqReduce). Used polymorphically or partially applied they degrade to a correct sequential evaluation (the polymorphic copy, whose both sees an abstract result). The specialization references the module's top-level list helpers by-label (static code, empty env) so nothing arena-allocated crosses a fork. Verified deterministic (result identical to sequential, incl. heap-Str deep-copy on join) and memory-bounded on all three targets (linux-x64 native, linux-arm64 qemu, win-x64 wine). |
| TCO back-edge reset of a relocated reuse accumulator (CO-8) | The Ashes.Map "sorted-key SIGSEGV" was misdiagnosed as an AVL/balance bug and a stack overflow — both disproven: balancing is O(log n) (height 18 at 200k sorted keys) and direct sorted inserts of 200k keys run clean; the gdb backtrace showed 2–3 frames faulting on a garbage child pointer (corruption, not exhaustion). The real defect was a use-after-free at the TCO back-edge plain arena reset. An accumulator marked reset-safe (its in-place reuse specialization rewrites it below the loop watermark) was assumed address-stable from its param name alone, but the reset never checked that the back-edge argument expression actually preserved that address. When the value threaded back went through a nested reuse fold whose entry deep-copy was not elided (a retained/declined seed — CO-2's conservative case), the accumulator was a copy relocated above the watermark each iteration; the plain reset then freed the live tree, and the next round's deep-copy read the dangling source while bump-allocating over it → SIGSEGV (growing key sets shift the layout and expose it; a fixed key set survives by accident). Fix (Lowering.cs): the plain reset now additionally requires the back-edge argument to be provably address-stable — a bare accumulator Var (live-scope slot check), an in-place reuse call whose last arg is stable, or a call to a fold proven to thread its accumulator through at a stable address (elided entry copy + every tail leaf stable, recorded by definition span). When stability can't be proven, control falls through to the existing sound fallback (no reset; the arena grows for the loop's duration). Fully-elided nested reuse folds keep the fast reset (verified RSS-flat at 200k rounds). Regression: tests/reuse_map_tco_reset_declined_seed.ash (growing keys, retained seed — crashed pre-fix, prints 7 post-fix). |
| TCO back-edge argument slot mis-mapping (CO-9) | The reported "recursive ADT accumulator in a non-last curried position → SIGSEGV" was misdiagnosed on the trigger (a lone recursive/copy-field ADT in a non-last position is fine, at 1 iteration and at scale) but pointed at a real, position-keyed TCO miscompile. A recursive function's per-iteration parameter slots (tco.ParamSlots) were built in capture-discovery order (the order free variables first appear in the body), but the back-edge stored argument i into ParamSlots[i] assuming parameter-declaration order (as do the copy-out and CO-8's reset-stability check). When the two orders differ — e.g. loop s xs n whose body mentions s before xs while a string and a list are both threaded — the string and list pointers were written into each other's slots (a swap); the next iteration then read a list through the string slot and vice versa, corrupting both accumulators and crashing after a single back-edge. It only surfaced with two heap accumulators of different kinds in the "wrong" order (same-kind pairs and copy-type args happened to stay consistent), which is why it looked ADT/position-specific. Fix (Lowering.cs): build ParamSlots in parameter order by resolving each tco.ParamNames[i] through the loop-entry scope (the innermost param resolves to its arg slot, captured params to their freshly-bound locals), so ParamSlots[i] is always the i-th parameter's (and i-th back-edge argument's) slot. Proven with gdb: pre-fix the list slot held the string's address; the swap is eliminated. Regression: tests/tco_multi_heap_accumulator_arg_order.ash (string+list and string+reuse-ADT in reversed capture order — both SIGSEGV'd pre-fix, print 11 15 post-fix). |
Cooperative async runtime — both overlaps in-flight I/O (CO-7) | The original "both lowers inline inside an async state machine" framing was a misdiagnosis (a concrete-result both always forks); the real gap was temporal — the async runtime was eager/synchronous (await/run = a blocking RunTask, and the suspending-coroutine path was dead code), so a both fork could only run before or after an I/O, never during one. Closed by building a real cooperative runtime in slices: (a-1) async(E) with an await now lowers through StateMachineTransform into a suspending coroutine (captures free vars; await → AwaitTask; emits CreateTask), driven by RunTask — behavior-preserving. (a-2) cooperative sleep — a sleeping leaf yields (WaitKind = WaitTimer, remaining ms in SleepDurationMs); the list scheduler waits only to the earliest deadline then decrements, so tasks interleave across sleeps; also fixed the list driver to resolve a coroutine's awaited sub-task before resuming (it read a stale result otherwise). (b-1/2/3) networking overlap: the leaf tasks were already non-blocking (epoll/IOCP/WSAPoll), so with the a-2 driver fix a loopback HTTP/HTTPS request in Ashes.Async.all overlaps a sibling task — verified on linux-x64, win-x64 (Wine), linux-arm64 (qemu). (c) a genuinely-parallel both fork inside an async segment runs concurrently with another task's live I/O, all results correct and memory-bounded on all three targets. Regressions: tests/async_sleep_interleave.ash, async_http_overlap.ash, async_https_overlap.ash, parallel_async_overlap.ash, and AsyncCoroutinePathTests. |
u8 → Int widening (CO-11) | Ashes.Bytes.get returns u8 and there was no way to convert it to Int for arithmetic (b - 48 failed ASH002 … got u8 and Int), so byte-level integer parsing was impossible — code had to slice each field into a Str and parseInt, allocating per row. Added Ashes.UInt.toInt(value) : Int (a new Ashes.UInt builtin module): every uN is a width-masked i64, so the widening is value-preserving for u8/u16/u32 (a bit-reinterpret for u64) and lowers to a retype with no runtime instruction — the saturated call accepts any unsigned width (checked in LowerUIntToInt, not via the reference scheme, which is u8 → Int). A byte from Bytes.get can now feed Int arithmetic directly, enabling the branchless byte parse the 1BRC temperature field wants. Regressions: tests/uint_to_int.ash (u8 get, byte-sum fold, scaled-int parse, getU16Le) and tests/uint_to_int_type_error.ash (a non-unsigned argument is rejected with a clear diagnostic). |
SIMD byte scan — Bytes.indexOf via libc memchr (CO-13) | The stdlib byte-scan loops were scalar and the LLVM loop-vectorizer is deliberately disabled in the pass pipeline (it/lib-call-recognition miscompile the freestanding parallelism inline-asm → SIGSEGV), so auto-vectorization was not an option. Instead Ashes.Bytes.indexOf now delegates to glibc memchr on Linux (SSE2/AVX2), keeping the freestanding scalar loop on Windows (no libc memchr wired there; selected by TargetTriple). memchr added to the shared linux dynamic-import dict (covers linux-x64 and linux-arm64); from is clamped into [0, len] so the size_t length can't underflow, and a NULL result maps to -1. Measured 50× faster on a long scan (4 KB line, ';' near the end, 2M iterations) — but only ~3% on 1BRC brc, whose per-line scans are ~15 bytes (too short for SIMD to beat the call overhead; output byte-identical). Correct on linux-x64, linux-arm64 (qemu), win-x64 (Wine). String.compare / Bytes.hash were assessed and deferred: 1BRC keys/hashes are also short, so memcmp/hashing SIMD would be marginal there, and FNV is inherently sequential. Regression: tests/co13_indexof_memchr.ash. |
Zero-copy mmap file input — Ashes.File.mmap (CO-12, mmap half) | Added Ashes.File.mmap(path) : Result(Str, Bytes) — memory-map a file read-only and return a zero-copy Bytes view over the mapping, reusing the existing string/bytes view representation ({len|VIEWFLAG, backingPtr}, built for the uncons zero-copy work) via EmitStringView. No read()/copy: the mapping's pages fault in on access, so a data-parallel fold touching different chunks faults them in parallel, and the single mapping is shared read-only across worker threads (verified: the deep-copy-on-fork does not materialize the whole-file view — 8-worker RSS is unchanged, not +8×file). Program-lifetime mapping, so slices into it stay valid. Linux (x64 + arm64) maps the file; Windows falls back to the capped readAllBytes read. challenges/1brc/brc_parallel.ash now uses it: byte-identical output and ~2% faster than the readAllBytes copy (2.68 s → 2.61 s at 10M). The 1BRC win is small because the fold reads every byte (so all pages are resident and the read was already ~1% of the time), but it is a general zero-copy capability (sparse/large-file access, parallel-fault I/O) and the direct answer to "parallelize the read". Regression: tests/file_mmap.ash (linux-x64, linux-arm64 qemu, win-x64 Wine). |
| Loop-invariant heap arg reset-safety — parallel fold made constant-memory (CO-10) | The data-parallel brc was not constant-memory (13.4 GB @ 10M, OOM @ 100M), while the sequential brc is 50 MB flat — with the same Ashes.Map.set. Root cause (distinct from the HashMap.set reuse-eligibility gap — CO-15 in Roadmap below): the per-worker fold foldLines(bytes)(pos)(hi)(map) threads the Bytes view unchanged, and the TCO back-edge arena reset requires all args reset-safe. bytes (a heap type) was not recognized as reset-safe, and the accumulator Map is not copy-out-able, so neither the plain-reset nor the copy-out path fired → the loop's arena never reset → every iteration's Map.set scratch leaked. But bytes is loop-invariant — passed as its own unchanged Var at every tail self-call — so it only ever holds the value passed into the loop (below the watermark) and survives a plain reset. Fix (Lowering.cs): compute the set of params passed unchanged at every tail self-call (CollectLoopInvariantParams, with shadow tracking) and treat such a back-edge arg as reset-safe in ArgResetSafe. Result: parallel brc is now near-constant-memory — 10M: 13.4 GB → 1.6 GB; 100M: OOM → 16.9 s / 2.9 GB, byte-identical to sequential (and 7.5× faster than the 127 s sequential run). Verified: full C#/e2e suites, a growing-key UAF stress test (tests/tco_loop_invariant_heap_arg.ash, 400k distinct keys with the invariant Bytes read every iteration), all three targets. (Note: foldLines puts the recursive call directly in each match arm; a let m2 = match … in loop(m2) accumulator is still not recognized — a separate, smaller follow-up.) |
| Data-parallel chunked fold — the full 1BRC (CO-14) | A streaming fold is single-threaded; the data-parallel chunked fold splits a large input into per-core chunks, folds each on a worker, and merges — and it works via the existing Ashes.Parallel.reduce with no new combinator: represent the input as a list of (bytes, lo, hi) chunk tuples split at newline boundaries and call reduce(merge)(emptyAcc)(foldChunk)(chunks). The monomorphized reduce forks each chunk's fold via both at the concrete Map result type, workers read the shared read-only Bytes, and the partial Maps are deep-copied across the fork and merged — byte-identical to the sequential fold (purity makes it order-independent). Sharp edges: foldChunk must be a top-level, non-capturing function (thread bytes through the chunk tuple, not a closure crossing the fork); a worker that reads out of bounds deadlocks the join. Enabled by Ashes.File.readAllBytes (uncapped whole-file Bytes; a standalone mmap on Linux, since a single arena allocation can't exceed one chunk) and preferably Ashes.File.mmap (CO-12, zero-copy); made constant-memory per worker by the loop-invariant reset-safety fix (CO-10). Result: challenges/1brc/brc_parallel.ash runs the 1BRC ultimate goal — 1,000,000,000 rows in 2 m 36 s at 15.9 GB, correct (41,343 stations), ≈8× parallelism (the 8-worker cap) (100M: 16.9 s / 2.9 GB; 10M: 2.6 s / 1.6 GB, 4.9× the sequential brc). Before this arc the parallel path OOM'd past ~15M rows and 1e9 was impossible. Regressions: tests/parallel_chunked_fold.ash, tests/file_read_all_bytes.ash. |
Three-way byte compare intrinsic (Ashes.Bytes.compare) | String.compare was a byte-at-a-time TCO loop (Bytes.get per byte) executed ~2×tree-depth times per keyed-map operation. Added the BytesCompare IR instruction + emitter (one memcmp over min(len), length tie-break, normalized -1/0/1, view-aware) and rewired Ashes.String.compare to delegate through Bytes.fromText. Sequential 1BRC 13.6 s → 12.1 s @10M. Regression: tests/bytes_compare.ash. |
Known-closure devirtualization (IrInst.CallKnown) | Every helper call was MakeClosure (a 32-byte arena alloc) + an indirect call *(reg) through the closure's code pointer — opaque to LLVM's inliner. New IR pass (IrOptimizer.DevirtualizeKnownClosureCalls): a CallClosure whose closure temp is a single-definition MakeClosure/MakeClosureStack (and whose env temp is single-definition) becomes CallKnown(label, env, arg) → a direct LLVM call that inlines; stranded MakeClosures are removed by dead-code elimination. Debug builds give locationless CallKnowns an artificial line-0 !dbg (LLVM requires locations on inlinable calls). |
| Redundant arena-bracket elision | Lowering brackets function bodies and copy-type-returning helper calls in SaveArenaState/RestoreArenaState/ReclaimArenaChunks; for tiny accessors (Map.height) the reclaim's munmap loop + dynamic stack slot made them ~78 instructions and ineligible for LLVM inlining. New interprocedural pass: a whole-program non-allocation fixpoint (explicit whitelist; CallKnown via callee summary), then (a) every bracket in a provably non-allocating function is removed, and (b) straight-line Save…Restore(+Reclaim) triples guarding only non-allocating instructions are removed. With devirtualization: sequential 1BRC 12.1 s → 6.5 s @10M (helpers now inline into the reuse spec). |
Runtime worker-cap detection + --parallel-workers (CO-5 completion) | The fork gate compared against a hard-coded cap of 8. The cap is now the machine's core count, detected once at first fork and cached in a global (__ashes_parallel_cap_get: linux x64/arm64 sched_getaffinity + SWAR popcount of the 128-byte mask — respects taskset/cgroup masks; win-x64 GetSystemInfo.dwNumberOfProcessors, new PE import; fallback 8 when detection reports nothing). --parallel-workers <n> pins a fixed cap at compile time (threaded BackendCompileOptions.ParallelWorkerCap → fork-gate constant). On a 32-core box the parallel 1BRC went 8-way → ~29-way. |
Zero-copy byte slices — Ashes.Bytes.subView (CO-17, explicit half) | subText copies its result; per-record name slices in scan loops paid an alloc + memcpy per row. subView returns the existing zero-copy view representation ({len|VIEW, ptr}) over the same clamped range — O(1), no byte copy. Lifetime is explicit (backing must outlive the view; mmap backings are program-lifetime, and values stored into structures are materialized by the copy-out/blob paths), so the automatic escape-analysis half of CO-17 remains open. Regression: tests/bytes_subview.ash. |
Str-specialized map operations (Ashes.Map.getStr/setStr/upsertStr) | get/set take a comparator closure — two indirect calls per node visit that no analysis could devirtualize (the closure is a parameter). The Str-keyed variants compare with the Bytes.compare intrinsic inline (UTF-8 byte order, same total order as String.compare); upsertStr(key)(missValue)(onHit) folds the lookup and the update into one traversal. All three are reuse-specializable like set (the upsertStr spec fires fullyReusing). Regression: tests/map_upsertstr.ash. |
| User-file functions join the reuse machinery | Only stitched module (Ashes_*) functions were ever registered for reuse specialization — the stitcher renders the user program as a nested let-pyramid in the entry body, which RegisterInlinableFunctions never saw, so a user-defined Map.set-shaped fold silently missed in-place reuse (9 KB/row leak). RegisterEntryBodyFunctions now walks the entry body's leading let-chain and registers specializable shapes, gated on (a) no shadowing anywhere in the body (binder-count walk) and (b) the lambda's free variables all resolving to stitched top-level bindings (a spec lowers in an isolated scope where only by-label/inline resolution works). The inline path also accepts qualified stdlib callees (Ashes.Map.makeNode inside a user spec). Two supporting soundness/precision fixes: (1) a constructor field that is any non-variable expression in a spec arm (e.g. an upsert's onHit(value) result) is now materialized into the persistent blob — previously only fresh-input variables were, so an in-arm computed value dangled past the reset (caught as scale-dependent corruption); (2) IsFullyReusing accepts a fresh in-arm Alloc that is only written into, field-read, borrowed, moved through single-store locals, and finally materialized (CopyFixedInto/CopyOutArenaToSpace). Regression: tests/reuse_user_fold_specialization.ash. |
| 1BRC result after this arc | challenges/1brc/brc_parallel.ash (subView slices + user upsertMeasurement + auto worker cap, 32 chunks): 1e9 rows in 24.7 s (was 2 m 36 s — 6.3×), byte-identical output, 41,343 stations, ~29× parallelism on a 32-thread box. Sequential brc.ash (getStr/setStr): 10M in 6.5 s (was 12.8–13.6 s), still ~50 MB flat. |
16-ary hash trie (Ashes.HashTrie) — the CO-19 endpoint, without the compiler generalization | The sub-10-s blocker was framed as "a trie descent must thread the shifted hash, so the reuse spec needs a multi-parameter inner go". The shipped design sidesteps it: each TrieNode16 carries its own nibble shift (HAMT-style path compression, splits at the first differing nibble of the two hashes; equal-hash collisions chain through the leaf's next), so the descent is a single-parameter go and the existing specialization machinery applies unchanged. Enabler in the compiler: AccumulatorIsFullyPersistent generalized from its MapTree special-case to a structural check (every constructor field is the accumulator ADT itself or a reuse-materializable leaf type), which admits Trie (and any similar user ADT) to the per-iteration arena reset. Found + fixed en route: a reuse-token/blob-aliasing hazard (roadmap CO-23) — the trie's split arm builds two same-arity TrieLeafs, and the fresh-value leaf stole the matched cell's reuse token, so its in-place value materialization clobbered the old leaf's blob cell while the sibling rebuild still referenced it (silent cross-key stat corruption at scale); Ashes.HashTrie avoids it by binding the rebuild first (it takes the token and writes its own value pointer back), and the general compiler-side gate is CO-23. Result: 1BRC 1e9 rows 24.7 s → 12.2 s (challenges/1brc/brc_trie.ash; sequential fold 3.9 s → 1.6 s @10M), byte-identical output, constant memory per worker. Regression: tests/stdlib_hashtrie.ash. |
| Reuse-token liveness gate (CO-23) | The in-place value materialization (CopyFixedInto over the matched cell's blob) assumed the token-consuming constructor supersedes the old value — false when the arm also rebuilds the matched cell as a sibling (the hash-trie leaf split), where the fresh-value constructor stole the token and clobbered a blob the sibling still referenced (silent cross-key corruption). Gate: at token issuance each variable-bound field records (local slot, total references in the arm body); LowerVar counts references as they lower (lowering order = evaluation order within a path); the in-place path is taken only when every reference to the superseded binding has been accounted for, else the update materializes a fresh blob cell (bounded — one extra cell per such arm, e.g. per trie split). Branch handling: while lowering one arm of an if/match, sibling-branch references are pre-credited as seen (mutually exclusive at runtime), and on branch exit the seen-map is restored to its entry snapshot — rolling back both the credits and the branch's own increments, so a sibling (or the join) never observes path-local references; totals are shadow-unaware over-counts and seen is slot-keyed, so every imprecision forces the safe fallback. Debugged via a 200-key repro: two prior unsound iterations (stale counters across re-lowerings of the same function — reset at issuance; then-branch increments leaking into the else — snapshot restore) each manifested as wrong gate verdicts in the compile-time [co23] trace. Ashes.HashTrie's split now uses the natural construction order (the fresh leaf first), exercising the gate in production; 1e9-row 1BRC unchanged (12.2 s / same RSS — the hot hit-arm update keeps the in-place path). Regression: tests/reuse_split_sibling_value.ash. |
| 1BRC parallel-efficiency investigation + worker-slot release at completion (CO-24) | The measurement plan ran in full on the 32-thread reference box (Ryzen 9 9950X3D — 16 cores / 32 HT in two asymmetric CCDs: CCD0 has 96 MB V-cache L3, CCD1 32 MB). (1) Per-worker tail (100 ms /proc/<pid>/task/*/stat sampling): all 32 HT saturate to ~8.7 s, then a ~4 s decay tail — and the finish order partitions almost perfectly by CCD: V-cache workers need 8.4–9.1 s CPU per equal chunk, CCD1 workers 10.5–11.9 s (~1.4×). Cause is L3 fit: 16 workers × ~5 MB trie working set sits inside CCD0's 96 MB but thrashes CCD1's 32 MB; the workload is latency- not bandwidth-bound (~5–10 GB/s of ~80). (2) Isolation runs (taskset, whole file): CCD0-16HT 21.1 s / 229 s CPU, CCD1-16HT 29.1 s / 340 s, CCD0-8-solo 22.0 s / 164 s, CCD1-8-solo 35.9 s / 229 s → SMT is worth ~1.4× throughput per CCD; an optimal static CCD-proportional split computes to ≈ the observed baseline, i.e. OS placement already achieves it — placement/affinity is a wash, the loss is fork-join packing. (3) Root cause of the chunk-count dead end: the worker-slot counter was released in the parent's join cleanup, so the cap counted un-joined descriptors, not running workers — an exited worker freed no capacity until the static join tree happened to reach its join, so finer chunking could never rebalance. Fix: release __ashes_parallel_active in the worker trampoline right after the result is published (all three flavors); cleanup now only reclaims OS resources. At the default 32-chunk config this is behavior-neutral by construction (31 forks never exceed the cap, so every fork spawned before and after — interleaved A/B confirms parity within noise at ~12.2–12.9 s), but it makes the cap honest and is a prerequisite for any queued scheduler. Chunk counts above the cap were remeasured with the new semantics (48/64/96/128/256): slot turnover now genuinely works (129 threads spawned over a 256-chunk run; 256 chunks improved ~13.1 → ~12.5 s) but every such config still loses to 32 chunks — a fork-join tree without work stealing blocks parents at joins, so freed slots idle whenever no thread has a pending fork to shed. Ceiling analysis: saturated-phase throughput is 3.26 chunks/s → ~9.8 s fold floor + 0.4–0.7 s serial merge/sort/format tail ≈ 10.2–10.5 s is this fork-join runtime's ceiling on this box; sub-10 s needs a work-conserving scheduler (CO-25) and likely per-worker working-set reduction below CCD1's per-worker L3 share on top. Also fixed en route: win-x64 parallel compilation had been broken since the auto-cap commit — EmitParallelWorkerCapFn named the void GetSystemInfo call, failing LLVM module verification on every program that forks; unnoticed because wine-target tests are not in the default suite. All 8 parallel e2e tests now pass under wine, and the arm64 both coverage passes under qemu. |
Work-conserving queued Parallel.reduce (CO-25) | A saturated 4-arg Parallel.reduce at a concrete, worker-liftable result type now lowers to a runtime chunk queue instead of the grained fork-join tree (reduceGrained keeps the tree — an explicit grain requests the divide-and-conquer shape; abstract result types still fall back to the sequential combinator). New IR ParallelQueueStart/Await/Cleanup: __ashes_parallel_queue_start snapshots the list into one zeroed OS region (header, elements, per-index results, per-index publish flags, 64-byte worker records) and spawns min(cap, n) workers under the same active-slot counter as both — when not a single slot is claimable the caller drains the whole queue inline, so nested queued reduces cannot deadlock. Workers pull element indexes from a shared atomic counter (lock xadd on x64, ldaxr/stlxr on arm64), evaluate f(elem) in their own per-thread arena, and publish each result under its flag word (atomic-increment release + futex wake; win-x64 awaits by Sleep(1) poll — results arrive at chunk granularity, so the poll is cold). The caller awaits indexes in ascending order and left-folds combine as results arrive — the merge overlaps the remaining fold — deep-copying each raw result before cleanup frees the worker stacks, arena chains, TCBs, and the region. Determinism: fixed list-order merge under the same associative-combine contract the tree already assumed; empty list yields the identity, a singleton yields f(x) alone, exactly like plSeqReduce. The both clone/trampoline machinery is reused (worker records mirror the fork-descriptor offsets 32–56, so the hardcoded ctid asm serves both layouts). Measured at 1e9 rows (interleaved A/B, chunk sweep 32/48/64/96/128/192/256): the per-thread timeline is now the flat 32-active band the CO-24 endpoint asked for (~0.2 s head, ~10.5 s fully-packed fold, then a decay tail of last-chunk stragglers plus the parent's serial merges), 128 chunks is the sweet spot, and the wall is ~11.9–12.5 s vs ~12.5–14.8 s for the fork-join baseline in the same interleaved session with byte-identical output (256 chunks regresses to ~13.8 s — the serial in-order merge becomes the bottleneck; CPU% drops as workers finish while the parent still merges). Sub-10 s was not reached, and the CO-24 endpoint estimate is falsified by measurement: the ~9.8 s fold-floor arithmetic assumed total fold CPU stays ~285–300 s, but at a full 32-wide pack the same fold costs ~335–345 s CPU — per-row cost inflates under sustained full LLC/bandwidth pressure, i.e. the idle that the queue eliminated had been partly hiding contention (at 32 chunks queue-vs-tree total CPU is identical, ~320 s; the growth appears exactly when packing tightens). Wall floor is therefore ~10.7 s + merge tail even with perfect scheduling. Remaining levers, per this measurement: per-worker working-set reduction below CCD1's per-worker L3 share (attacks the contention itself; CO-24 estimated it insufficient alone), and a deterministic pairwise parallel merge (removes the serial tail that dominates ≥192 chunks); likely both are needed together for sub-10 on this box. Tests: tests/parallel_reduce_queue.ash (empty/singleton/order-sensitive-combine/n-above-cap; passes on linux-x64 and under wine), arm64 qemu coverage test for list-order merging, plus the existing parallel suite on all three flavors. challenges/1brc/brc_trie.ash raised from 32 to 128 chunks. |
Deterministic pairwise parallel merge for the queued reduce (CO-26) | CO-25's queue ran all n−1 combine merges serially on the awaiting caller, the measured bottleneck above ~192 chunks (256 chunks: ~13.8 s while workers idled and CPU% sagged) and the cap on chunk granularity — which matters because finer chunks are the queue's straggler defense. Now the workers merge: the queue region carries an item slot and a publish flag for every node of the merge tree (S = n + ceil(n/2) + … + 1 slots, arrays laid round-major), and the drain loop gains a second phase — once the element counter is exhausted, workers claim merge tasks from a second atomic counter in round-major order, wait on the task's two operand flags (futex; Sleep(1) poll on win-x64; at most one waiter per flag since every item has exactly one consumer), and publish combine(left)(right) — or promote an odd round's trailing item — under the output's flag. Round-major claim order is topological, which makes the scheme deadlock-free by construction: the claimed prefix is contiguous (fetch-add), so the earliest incomplete task is always claimed and its operands (all in earlier rounds) are already published. The tree pairs adjacent indexes per round, so its shape depends only on n and respects list order — deterministic under the same associative-combine contract, byte-identical 1BRC output (md5-verified at 100M and 1e9). The caller now awaits only the root and deep-copies once (was: n per-result copies + n−1 serial combines) and no longer competes as a 33rd runnable thread; intermediate merge results live in the arenas of whichever workers computed them (mixed-arena trees are fine — every worker arena stays live until cleanup, which runs after the root copy). Measured at 1e9 rows (interleaved, 3 rounds, vs the CO-25 compiler): 128 chunks 11.83–11.87 s vs 11.78–12.03 s (parity with a tighter spread — at 128 the overlapped serial merge had not yet been the bottleneck), and the ≥192-chunk regression is gone: 256 chunks 12.19–12.35 s (was ~13.8 s), 384 chunks 12.6–12.7 s, with CPU% flat at ~2900% for every chunk count (the workers-idle-while-parent-merges dip no longer exists) and the post-fold decay tail down from ~1.7 s to ~0.6 s (what remains is last-chunk straggler spread plus the constant ~0.4 s sequential sort/format epilogue). The 128-chunk wall is unchanged, as CO-25's analysis predicted: the binding constraint is fold CPU under full LLC/bandwidth pressure, and finer chunks still cost more total CPU (~345 s at 128, ~355 s at 256, ~368 s at 384) — per-worker working-set reduction is now the single remaining sub-10 lever. Tests: order-sensitive odd-count merges (promotion rounds) added to tests/parallel_reduce_queue.ash (n = 13) and the arm64 qemu coverage (n = 7); full suites green on all three flavors. |
| Per-worker working-set reduction investigated and falsified (CO-27) — the 1BRC sub-10 s question is closed on this box | Measurement first: the per-worker hot set was computed exactly by replaying the trie build offline (station set parsed from the reference output; FNV-1a 64 replicated; HashTrie's split/chain algorithm simulated) — 41,343 stations make 13.2k TrieNode16 internals (1.90 MB at 144 B each, average occupancy 4.1 of 16 slots, 56% of nodes hold exactly 2 children), 41.3k leaves (1.65 MB), 41.3k boxed stats tuples (1.32 MB), key view headers (0.66 MB) = 5.5 MB structural (confirming CO-24's ~5 MB estimate), plus ~2.6 MB of scattered file-map cache lines touched by the per-row leaf memcmp against stored zero-copy subView keys. Two reduction experiments were then built and A/B-measured at 1e9 rows, both byte-identical to the reference output: (1) packed stats + dense keys — min/max/count bit-packed into one word (value cells 32 → 16 B) and inserted keys copied via subText so stored keys live densely in the blob instead of 41k scattered file positions (~3.3 MB effective reduction): parity on the full box (12.19–12.47 s vs 12.30–13.20 s interleaved) and — decisively — 3% slower when pinned to the small-L3 CCD alone (27.1 vs 26.3 s on CCD1's 16 HT, where footprint pressure is maximal); (2) inline-value leaves — a TrieLeafP(hash, key, w1, w2, next) packed-leaf constructor storing both stat words inline, eliminating the per-row boxed-value dependent load and its cell: ~5% slower (12.86–13.38 s vs 12.20–12.36 s) — the extra scalar-closure call and wider leaf cost more than the removed cache line saved. Conclusion: the fold is bound by the length and latency of the serialized dependent-load chain per row (~4–6 loads through node hops, leaf, and key bytes), not by the working set's byte count — shrinking footprint by ~40% changed nothing even under maximal L3 pressure, and shortening the chain by one link cost more in call overhead than it saved. With scheduling fully solved (CO-25/26) and footprint falsified, sub-10 s at 1e9 rows is closed as not reachable on this box with the current per-row upsert architecture; the wall stands at ~11.9 s. Any future attempt needs a different shape entirely (e.g. row batching that overlaps multiple independent descents to hide latency — nontrivial in a pure per-row fold). Experiment code was reverted (repo unchanged except this analysis); kept: a debug print in IsFullyReusing's instruction-kind reject path. Reuse-machinery landmines hit en route, recorded for CO-15/22 work: a copy-type-returning closure parameter called inside a specialized go gets an arena-bracket CopyOutArena that disqualifies IsFullyReusing (silent 55 GB leak); an accumulator ADT whose type still carries an unresolved type variable (a phantom V never constrained by the packed operations) fails AccumulatorIsFullyPersistent and silently disables the per-iteration reset — pin such parameters to a concrete type; a pair-returning update closure destructured in a spec arm leaks its 16 B tuple per row into to-space. |
| In-place-reuse eligibility generalized to the eta-applied shape (CO-15) | The constant-memory reuse specialization fired only for the Map.set structural shape (outer params, then let rec go = … in go returned bare). Ashes.HashMap.set writes the equivalent worker differently — given k -> given v -> given map -> (let target = hashKey(k) in let rec go tree = … in go(map)) — so a HashMap-keyed fold was not specialized and leaked 9.6 GB at 1M inserts (vs Map's constant ~9 MB). Two independent gaps, both fixed in Lowering.cs: (1) detection — TryGetNestedRecursiveReturn now peels a leading chain of non-recursive lets before the let rec and accepts the eta return … in go(lastOuterParam) (the accumulator arrives as the last outer argument and is forwarded verbatim into the worker, whose own parameter stays the linear reuse root; argCount = outerParams for the eta form vs outerParams + 1 for the bare form). (2) IsFullyReusing — HashMap's per-node composite-key descent inlines strCompare's own let rec go i = … in go(0) helper, whose closure is MakeClosure → StoreLocal → LoadLocal → CallClosure (a stored-then-called recursive helper under an arena bracket that yields a scalar and never escapes into the rebuilt tree). The old check rejected any MakeClosure whose reader was not a direct CallClosure callee; it now accepts a closure that is consumed as a call target through a single-store local slot or Borrow (mirroring the existing SafelyConsumed walk), while still rejecting a closure passed as a call argument (which could be captured or returned). With both fixes the Ashes_HashMap_set__reuse spec is fullyReusing and the fold is constant memory: 9.3 MB at 1M and 9.1 MB at 4M inserts into a bounded keyspace, output identical to Map. Verified for correctness (not just footprint) by a growing-key insert+update+readback checksum against an independently computed value. The change is general — any user function with the eta shape and a stored-then-called helper is now specializable (confirmed on a synthetic user tree). Regression: tests/reuse_hashmap_set_bounded.ash (200k growing string keys, every 7th updated, spread-readback checksum). |
Let-bound match/if accumulator recognized for the loop arena reset (CO-16) | The per-iteration arena reset requires the loop's back-edge accumulator to be provably address-stable (IsStableAccumulatorExpr), which only held when the recursive call sat directly in each match/if arm (` |
| Entry-body helper inlining via a transitive free-variable closure (CO-22) | Entry-file functions (user declarations, which the import stitcher renders as the program body's nested let-chain rather than top-level items) were registered for reuse only as specializations, and only when self-contained — every free variable had to be a stitched module binding. So a user fold that called its own local makeNode-style rebuild helper was rejected outright (the helper is a user sibling, not a stitched name) and leaked (1.48 GB at 1M inserts vs constant when the helper was Ashes.Map.makeNode); user-local helpers were never registered as inlinable at all. Fix (Lowering.cs RegisterEntryBodyFunctions): collect the entry let-chain's single-binder lambda candidates, then compute the maximal registerable set by fixpoint — a candidate is registerable iff every free variable of its body is globally resolvable at an inline/spec site (a stitched module binding, a constructor, or an already-registered function) or is itself another registerable candidate. Each registerable function is then registered exactly like a flat top-level item: the nested-recursive-return / single-param-recursive shapes become reuse specializations, and any other non-recursive helper with an allocating body becomes an inlinable rebuild helper (into _inlinableFunctions / _inlinableDefiningValues). Soundness: the fixpoint's key property is that a registerable function captures nothing that isn't globally resolvable, so it lowers as an empty-env by-label callee (reaching _topLevelFunctionRefs) and its body resolves when inlined inside another function's specialization — which is exactly the scope hazard the old all-stitched gate existed to avoid (registering helpers naively had produced ASH001). Verified in both directions: a three-deep chain upd → mkNode → hgt (each helper referencing the next, bottoming out at constructors) specializes to fullyReusing constant memory (1.4 MB at 500k inserts), while a helper that captures a plain value binding is correctly left unregistered and still compiles and runs correctly. Correctness checked (not just footprint) by a growing-key insert+update+full-readback checksum whose totalSum = n(n-1)/2 and totalCt = n are shape-independent. Regression: tests/reuse_user_local_helper_specialization.ash. |
| Debug info combines with any optimization level (CO-21) | --debug capped optimization at -O1, and the -O1 pipeline runs no inliner, so a sampled profile of a debug build systematically exaggerated call overhead vs the real -O2 binary (1BRC helpers showed ~30% self at O1-debug but inline at O2). Fix: the CLI cap is removed — --debug still defaults to -O0, but an explicit -O1/-O2/-O3 is now honored (both the compile and run arg parsers). Two backend pieces keep the optimized debug output valid: (1) the artificial line-0 fallback that previously covered only a devirtualized CallKnown now applies to every unlocated instruction in a scope — the -O2/-O3 inliner stitches each inlined instruction's !dbg into an inlined-at chain rooted at the call site, so any call left without a location produces invalid debug info; line 0 is the DWARF convention for compiler-generated code. (2) When debug info is emitted the backend re-verifies the module after the passes (the existing verify runs only on the unoptimized module), so an inliner-mangled location fails the build instead of shipping as broken DWARF. Verified: compile --debug -O2 is llvm-dwarfdump --verify-clean, gdb sets file:line breakpoints and shows correct backtraces identically to --debug -O0 (both map lines 2/3/6/7/9/11 and break at _start_main), the optimized debug binary is far smaller than the O0 debug binary (109 KB vs 178 KB — the inliner ran) and its wall time equals plain -O2 (0.49 s vs 0.49 s on a 2e8-iteration loop), and O1/O2/O3 debug builds all run correctly. Docs: DEBUGGING.md and COMPILER_CLI_SPEC.md updated. Regression: OptimizationLevelTests.Debug_info_combines_with_every_optimization_level (O0–O3, helper/recursive calls driving the inliner; the post-pass verify throws on bad debug IR). |
Ashes.Parallel.splitChunks record-boundary chunker (CO-18) | The data-parallel byte-scan (1BRC) hand-rolled a buildChunks helper to split the mmap'd buffer into (bytes, lo, hi) sub-ranges at newline boundaries before Parallel.reduce. The roadmap framed CO-18 as a reduceChunks(bytes)(sep)(n)(identity)(foldChunk)(merge) combinator; the prerequisite it named — a stdlib module importing another Ashes.* module — is now already supported (post the inline-modules work: import Ashes.Bytes inside lib/Ashes/Parallel.ash compiles and runs). But a measurement falsified the wrapping combinator: Parallel.reduce gets its parallelism by monomorphizing the user's call at a concrete result type, so wrapping it in a polymorphic stdlib reduceChunks degrades the inner reduce to the sequential fallback — measured 99% CPU / 0.54 s vs a direct call's 2342% CPU / 0.04 s (same result, 13x slower). The fix ships the splitting as a pure helper and leaves reduce at the caller: Ashes.Parallel.splitChunks(bytes)(sep)(n) : List((Bytes, Int, Int)) (importing Ashes.Bytes for indexOf/length), used as reduce(merge)(identity)(foldChunk)(splitChunks(bytes)(sep)(n)). This keeps the ergonomic win (the buildChunks boilerplate is gone) with no parallelism footgun — measured 1864% CPU / 0.05 s on the same scan, and challenges/1brc/brc_parallel.ash now calls splitChunks(bytes)(10)(32) in place of its buildChunks, byte-identical output (md5-verified at 10M) and still parallel. Regression: tests/parallel_split_chunks.ash (chunk count, per-chunk fold sum, and exact buffer tiling via a spans-sum). Docs: STANDARD_LIBRARY.md. |
Ashes.Regex backed by PCRE2 | The self-hosted combinator regex engine is replaced by PCRE2. The 8-bit library (Unicode on, JIT off) is compiled from source to per-target LLVM bitcode (scripts/download-pcre2.sh → runtimes/<rid>/libpcre2.bc), stripped to the exposed API with internalize+globaldce, and linked into a program only when it uses Ashes.Regex, after the program's own optimization passes — mirroring the openlibm model. PCRE2's malloc/free route to an emitted bump allocator over a lazily-mmap'd 64 MiB region; a compiled pattern (pcre2_code*) persists there (stable handle — the arena never relocates it) and per-match scratch is reclaimed by a region cursor save/restore. Five backend intrinsics (RegexCompile/RegexCompileError/RegexFind/RegexCaptures/RegexSubstitute) back the pattern-string API (compile/isMatch/find/findAll/captures/replace). The Windows payload uses the windows-gnu triple (MS x64 ABI, >4-arg calls) with vendored declaration-only stub headers + a memchr/strchr/ctype shim, so no MinGW sysroot is needed. Byte-identical on linux-x64/arm64/win-x64. Pinned via <Pcre2Version>; payloads git-tracked like libopenlibm.bc. |
Overload-generic == / != / + helpers | A non-recursive function that applies ==, !=, or + directly to two of its own parameters is now usable at Int/Float/Str/Bool across one program: each concrete call site inlines a type-resolved copy of the body (reusing the capability-generic inline path), so the operator resolves at that call's type. Generalization is unchanged, so first-class/unsaturated uses keep the prior monomorphic behavior. Also adds the missing Bool case to ==/!= (booleans are i64, compared via CmpIntEq). This is what lets Ashes.Test.assertEqual assert several basic types in one test. |
String/Json/Rpc on Bytes primitives | The stdlib string hot paths scanned char-by-char via Text.uncons (a string-view allocation per character), and String.split was O(n²) (its substring re-walks per field). Rewritten on the Bytes layer (memchr-backed Ashes.Bytes.indexOf, byte slicing): String.startsWith/indexOf/contains/split/trim*, a no-escape string fast path in Json.parseQuotedStr, and Rpc.parseContentLength. Measured ~1000× (String.split) and ~900× (Json.parse of a string-heavy payload) faster at the same or smaller binary size, with no PCRE2 dependency. A benchmark confirmed a regex-backed stdlib would instead be slower and +300 KB on every consumer (PCRE2 links whenever any lowered function uses a regex intrinsic, even uncalled). indexOf still returns a code-point index; public API and Unicode behavior unchanged. |
Local type declarations coexist with stitched imports (CO-20) | A user file that both imports a stitched module (import Ashes.String, ...) and declares its own ADT (type Shape = ...) failed with ASH003 Expected expression but found EOF, forcing user programs to piggyback on stdlib ADTs. The type declarations were in fact already hoisted to the very top of the combined source; the failure was in the entry-body placement: BuildCompilationLayoutCore only parenthesized the entry body when the entry had no type declarations, so a type-declaring entry was appended bare after the stitched module bindings — where a flat declaration block cannot parse (the paren wrap is exactly what routes the entry through the parser's parenthesized flat-entry-block path, and after a legacy binding chain's trailing in a bare flat block never parses). Fix: parenthesize the entry body whenever any module binding precedes it, independent of hoisted type declarations; the paren branch now carries the entry's type-declaration length as the layout's BodyStart so diagnostic span mapping keeps working, and the entry-only-type-declarations case (no stitched bindings) still appends bare — an ordinary flat program with exact original offsets for the type region. Verified: flat entries (types + lets + trailing expression, including a type declared between lets with constructors used across declarations) and legacy pyramid entries both compile and run with stitched imports; stitched-module calls resolve in both flat let values and the trailing expression. Regressions: tests/type_decl_with_stitched_import.ash, tests/type_decl_with_stitched_import_pyramid.ash. Noted en route (pre-existing, unchanged): referencing a nonexistent member of an imported stitched module reports a misleading Unknown module 'Ashes.String' instead of an unknown-export error. |
Growing whole-value accumulator reclamation — fixed loop-entry watermark + BigInt copy-out (CO-28) | A TCO loop re-saves its arena watermark at the loop-body label, so the mark advances past the threaded accumulator each iteration. For a cons-list that is correct and O(N) (only the fresh top cell is copied; the shared tail stays below the mark), but for a growing whole-value accumulator (String, BigInt) the whole value is copied to the new mark each iteration and the previous copy is stranded below it forever → O(N²) resident memory (pidigits N=1000 = 168 MB; a growing-String fold = 195 MB @ 20k iters). Two changes: (a) a BigInt is a self-contained {header, limbs} buffer with no internal pointers, so it is copied out across the reset like a String — a BigIntSize sentinel on CopyOutArena reads the byte size from the header limb count — reclaiming the loop's intermediate BigInt garbage; (b) a loop threading only non-sharing whole-value accumulators (copy type, resource handle, String, BigInt — never a TList, whose shared tail needs the advancing mark) saves a second fixed loop-entry watermark and resets to it, so each grown accumulator overwrites the previous one in place. Result: pidigits 168 MB → constant 0.25 MB at every N (only the O(N³) long-division time remains); a growing-String accumulator loop 195 MB → 0.25 MB; output unchanged. Fixed en route (correctness, challenges/fannkuch): the shallow single-cell TCO list copy-out preserved only a list's top cons cell, so a rebuilt/multi-cell list left interior cells dangling (dropped early ADT return, then segfault at N≥3) — the reset is now disqualified for any list accumulator that is not a single fresh cons. Regressions: tests/bigint_tco_accumulator.ash, tco_fixed_watermark_whole_value_accumulators.ash, tco_multi_fresh_list_accumulator.ash. |
| Fixed-shape pointer-bearing accumulator reclamation — deep-copy-out for ADTs and tuples (CO-29) | A pointer-bearing accumulator that is a fixed-shape (non-recursive) ADT (fannkuch's State(perm, count)) or a tuple (fasta's (seed, output)) returned CopyOutKind.None, so any loop threading one disqualified the arena reset entirely and every per-iteration transient leaked (fannkuch N=10 = 4.6 GB; a (seed, String) fold O(N²)). Such a value is carried across the reset by a recursive deep copy (the existing synthesized ADT copier / EmitDeepCopy tuple rebuild) — a self-contained clone whose list/string fields are fully copied, which breaks any tail-sharing with the previous accumulator and so is fixed-watermark safe (CO-28). Added CopyOutKind.DeepAdt + a CanDeepCopyOutAdt predicate in GetTcoCopyOutKind; self-recursive ADTs (trees like MapTree) are excluded — an unbounded per-iteration deep copy would be O(size)/iter and those shapes are owned by the in-place reuse specialization (deep-copying one out from under it corrupts it, caught by the reuse_* suite — hence a path-based cycle check that declines any self-recursive ADT). Result: fannkuch 4.6 GB (N=10) → constant 0.25 MB, N≥11 now reachable (time-bound only); a (Int, String) tuple accumulator bounded (fasta's natural form). Regressions: tests/tco_deep_adt_accumulator.ash, tco_tuple_accumulator.ash. |
Ashes.String.substring from O(start + count²) to O(start + count) (CO-30) | substring was take(drop(text)(start))(count): drop walks start codepoints via Text.uncons, and take rebuilds count codepoints with per-character string concatenation (each an O(count) copy), so a sliding k-mer window (k-nucleotide) was catastrophic — ~63 s at 8000 characters. Rewrote it as a single codepoint→byte-offset walk (reusing the UTF-8 start-byte rule: a byte is a codepoint start iff < 128 or >= 192) plus one Ashes.Bytes.subText, so it is O(start + count) with no concatenation and stays codepoint-correct (verified on multibyte UTF-8). The same 8000-character window now runs in 0.03 s (~2000×). It is still O(position) per call because strings are not byte-indexable; the standard-library reference now steers repeated indexed slicing to the byte-indexed Ashes.Bytes.subText (O(count) per slice). Regression: tests/stdlib_substring.ash. |
| Variable-sized heap chunks — a single allocation larger than one chunk no longer OOMs (CO-31) | The arena grows in fixed 4 MiB OS chunks, and EmitHeapEnsureSpace loops grow→recheck until a request fits — but EmitHeapGrow always allocated exactly one 4 MiB chunk, so any single allocation larger than 4 MiB never fit and grew one chunk per iteration forever, exhausting memory (surfaced by regex-redux: chaining Ashes.Regex.replace on a >1.5 MB subject allocated the 2*subject + 256 substitute buffer, which exceeds a chunk, and blew up to a constant ~28 GB before the OS refused — even with a non-matching pattern, since the fault is in accepting the large subject; the same trap applied to any large String/Bytes allocation). Chunks are now variable-sized: EmitHeapGrow sizes an oversized chunk to max(4 MiB, request + overhead). Because the abandoned-chunk reclaim walk reconstructed a chunk's base as end − 4 MiB (a fixed size), each chunk now carries an 8-byte header (the previous chunk's end, for the backward link) and an 8-byte footer at its usable end (its own base), so the walk recovers a chunk's base from its end pointer with no size assumption. All chunk sites share one format via a new EmitHeapChunkSetup: the main arena init/grow/reclaim, the per-thread to-space, and the parallel worker arena setup + parent-side worker-chunk free walk (LlvmCodegenParallel). Result: the ~5 MiB regex chain completes in bounded memory, and 1000 iterations of a reclaimed >4 MiB temporary stay flat under a 2 GB cap (no leak, no corruption) on all three targets. Regression: tests/regex_large_subject_chain.ash. |
List(ADT) accumulator reclamation + the DeepAdt two-pass overlap fix (CO-32) | Completes CO-29: a TCO loop threading a List(fixed-shape-ADT) accumulator (n-body's List(Body)) previously disqualified the arena reset entirely (CopyOutKind.None), so every per-iteration transient leaked — O(N) growth for a constant-state loop. A synthesized recursive list deep-copier (SynthesizeListDeepCopier, cached per element type; nil passes through, each head deep-copies via EmitDeepCopy — e.g. through the element ADT's synthesized copier — and the tail recurses via the self-closure at env[0]) clones the list whole, so GetTcoCopyOutKind classifies List(deep-copyable-element) as DeepAdt and the loop takes the fixed loop-entry watermark. Measured: a 5-record List(Body) advanced 3,000,000 steps runs at 0.25 MB max RSS (was 4.27 GB at 1e6). Root-caused en route (a first attempt had been reverted on a wrong "async interaction" diagnosis): the two-pass back-edge copy-out's disjointness argument has a hole for DeepAdt — Phase B writes its down-copy at [W, W+S) while reading the Phase-A up-copy at [W+B, W+B+S) (B = the loop body's allocations that iteration), overlapping whenever B < S. Shallow kinds are safe because the fresh accumulator itself was just body-allocated (B >= S); a deep clone's size adds copier env/closure overhead beyond the raw value, and a list-tail argument may not be body-allocated at all (B ~ 0). At B = 0 the copy self-overwrites at zero skew — each write lands on its own source byte with an identical value, accidentally benign, which is why optimized builds masked it; the test runner compiles unoptimized IR, where one dead 24-byte MakeClosure in the loop body skewed the overlap and corrupted the clone (readme_showcase priced 41.00 instead of 12.50). Fix: DeepAdt Phase A clones twice (a clone of the clone — the second starts at least one full clone-size above W), making Phase B's destination end W+S provably below its source start W+B+S for any B >= 0 and any number of DeepAdt args; this also closes the same latent hazard for the already-shipped ADT/tuple DeepAdt copy-outs. Verified on all three targets and on both the optimized and unoptimized pipelines. Regression: tests/tco_list_of_adt_accumulator.ash; tests/readme_showcase.ash guards the capability+async shape. Amended (same branch): the whole-list clone is licensed per ARGUMENT, not per type. Cloning a list at every back-edge costs O(length) per iteration, affordable only when the body already paid O(length) REBUILDING the list that iteration (n-body's advance(dt)(bodies) call result — a callee's list result is copied out of its arena scope on return, so it is self-contained; likewise list literals and cons spines ending in one of those, per IsFreshListRebuildExpr). A threaded/consumed shape — a bare var, a pattern-derived tail, a cons onto the accumulator — can share unbounded structure with the previous iteration, and the per-back-edge clone multiplies the loop's cost by the list length: 1brc's merge phase (a List(tuple) walked by pattern tails) regressed ~400x in time and ~27x in memory (0.25 s / 2.1 GB -> 85 s / 54 GB on a 12 MB input, OOM-killed on the real file) before the gate. Non-fresh list args now downgrade to CopyOutKind.None at the back-edge (the pre-CO-32 no-reset behavior). |
| BigInt division: Knuth Algorithm D in base 2^32 (CO-33) | bignum_divmod was bit-by-bit binary long division — one full compare/subtract pass over the divisor per dividend bit — making pidigits O(N^3) time (its memory was already constant via CO-28). Rewritten as Algorithm D in base 2^32, the Hacker's Delight divmnu64 formulation: one quotient digit per outer iteration (normalize so the top divisor digit has its high bit set; estimate qhat from the top two dividend digits with a native 64/32 divide; correct it at most twice with the short-circuited overshoot check; multiply-subtract with a signed borrow; rare add-back when qhat was still one too large). Digits are the 32-bit halves of the 64-bit limbs, so every intermediate fits native i64 arithmetic — deliberately NOT base 2^64, whose qhat estimation needs 128/64 division and LLVM lowers udiv i128 to a __udivti3 libcall that a freestanding zero-runtime binary does not have. Single-digit divisors take a short-division path (one 64/32 divide per digit). The helper gains a caller-allocated scratch buffer (normalized divisor + working dividend, la+lb+4 words). Measured: pidigits N=1000 3.46 s -> 0.027 s (~128x), N=500 0.41 s -> 0.007 s, N=2000 0.11 s — output byte-identical. Edge coverage in tests/bigint_divmod_algorithm_d.ash: the canonical Hacker's Delight add-back trigger, the qhat correction loop, odd digit counts (top limb < 2^32 on either side), exact division, equal magnitudes, the short path, and truncated-toward-zero signs — expected values computed independently, remainder recovered as a - a/b*b so the mul/sub round-trip is checked too; verified on all three targets. Schoolbook mul is now the next asymptotic ceiling (Karatsuba deferred — no benchmark currently hits it). |
| Loop-invariant pass-through args + deferred TCO reset decisions (CO-34) | Two independent holes let growing-accumulator loops leak quadratically despite the CO-28 fixed watermark. (a) A loop-invariant heap argument disqualified the fixed mark: fasta's randomFasta threads its table CLOSURE unchanged through the loop; TFun was not in the fixed-watermark whitelist, so the loop fell back to the ADVANCING mark and stranded every iteration's copy of the growing output string — 6.8 GB at N=20000, 27 GB at N=40000. A pass-through arg (the param's own unchanged Var at every tail self-call, per the existing LoopInvariantParams analysis, which the plain-reset path already honored but the copy-out path ignored) holds the pre-loop value — below even the fixed loop-entry watermark — so it needs no copy-out and is now exempt from both the copyability scan and the fixed-mark qualification. Also unlocks loops threading an invariant LIST (previously allCopyable=false, no reset at all). fasta: constant 3.8 MB at every N (output identical). (b) A late-typed accumulator silently lost its reset entirely: the back-edge copy-out decision dispatches on argument types, but an accumulator constrained only by a deferred + (or by the caller) is still an unresolved inference variable when the back-edge lowers — e.g. whenever the stable [] -> acc match leaf lowers before the cons arm — and GetTcoCopyOutKind(TVar) = None declined the whole block: 1.76 GB for a 60k-iteration string fold, silently. The back-edge now emits an IrInst.TcoResetPending placeholder (no temps; never reaches the backend) with the AST/scope-dependent facts captured eagerly (pass-through, single-fresh-cons, stable-accumulator — the scope is gone by resolution time) and live TypeRefs; ResolveDeferredTcoResets, running after the deferred-operator resolutions at the end of lowering, re-runs the decision on the pruned types and splices the real block in place (swapping _inst and the temp/local counters per target function, the established synthesis pattern). The block emission itself was refactored into EmitTcoBackEdgeArenaBlock, shared by the inline (types-known) and deferred paths. 0.25 MB constant. Also re-measured the historical "growing cons-list O(N^2)" shapes: single- and multi-cons string builders and reverse-complement are all LINEAR today (~23–96 B/elem); what remains is the fat list-of-small-Str constant (in-place-reuse milestone) and copy-per-iteration O(N^2) TIME. Regressions: tests/tco_loop_invariant_args.ash, tests/tco_late_typed_accumulator.ash (the test runner's unoptimized pipeline is exactly where a wrong splice would miscompile). |
| Amortized fixed-watermark compaction (CO-35) | The fixed-watermark path copied the WHOLE accumulator at every back-edge — O(live) copy work per iteration, so a growing accumulator costs O(N^2) time in copies alone, and the CO-32 List(ADT) loop paid three deep clones per iteration for a constant-size value. The back-edge now skips the entire copy-out + reset while the arena has grown less than 2x the live size recorded at the last compaction (+4 KB slack): skipped iterations just keep allocating above W (exactly the no-reset behavior every non-qualifying loop already has — trivially sound), and each compaction reclaims at least as much garbage as it copies, so total copy work is linear in bytes allocated (the doubling amortization) while resident memory stays bounded by ~3x live. The live size is measured exactly and for free at the only moment that is possible: right after a compaction, [W, cursor) holds precisely the down-copies, so M = cursor - W — computing it per-iteration would require walking deep structures, which is the very O(N^2) being eliminated. The slack is a thrash guard, not a correctness knob: with M ~ 0 (empty/tiny accumulators) a bare 2M threshold would compact every iteration; 4 KB lets tiny-live loops batch hundreds of iterations of garbage per compaction. The trigger is a handful of i64 instructions (cursor read via SaveArenaState, subtract, shift, compare, branch) emitted only on the fixed-watermark two-pass path — the advancing-mark path is NOT amortized (its single-cell list copies must track the moving mark every iteration), and the all-copy-type plain reset needs no amortization (it copies nothing). Measured: the List(Body) 3M-iteration loop 0.289 s -> 0.054 s (5.4x) at an unchanged 0.25 MB; fasta ~1.5x faster at 1 MB constant (its remaining O(N^2) time is the immutable out + ch concat itself — each concat copies the whole string; that needs in-place unique-string growth, i.e. the ownership milestone). Verified on all three targets; full suites green. |
| Affine in-place string growth (CO-36) | The first concrete affine-ownership analysis beyond ADT reuse: immutable acc + x copies the whole accumulator per iteration by definition, so every growing string fold was O(N^2) TIME no matter what the arena did. Uniqueness is proven by two facts composed: (a) the affine analysis (CollectAffineAccumulators) — along every loop-continuing path the accumulator param is consumed at most once, and only as the leftmost leaf of the + chain producing its own tail-call argument (exit-path uses are unrestricted: nothing extends after the loop ends); (b) the watermark boundary — a value at/above the fixed loop-entry watermark W is loop-created, so the caller cannot alias it (this replaces the hard global half of the uniqueness proof; the caller-passed seed simply sits below W and falls back). Growth is reservation-based: each affine param gets a reservation slot pair (start/end locals, zeroed at loop entry). An armed append lowers to ConcatStrTip, whose emitter extends in place iff the left operand IS the reservation start and the appended bytes fit within the reserved end — memcpy onto the accumulator's end, grow the length header, cursor untouched — so the fast path is immune to interleaved per-iteration allocations (uncons views, scratch values) that land between the accumulator and the arena tip. When the check fails, the fallback allocates the concatenation with 2x headroom, copies once, and records the new reservation bounds — classic doubling, amortized O(1) per appended byte. Three interplay rules with the amortized compaction (CO-35) keep it sound and linear: (1) reservation spans are netted out of the growth measurement in the back-edge trigger — else every capacity doubling reads as arena growth and re-triggers a compaction that reclaims the fresh reservation (threshold resonance: compact, zero, re-reserve, compact); (2) the compaction zeroes the reservation slots it reclaims; (3) the compaction's Phase-B down-copy of an affine accumulator is itself a reserving ConcatStrTip (empty right operand against the just-zeroed slots) — without this, an accumulator larger than the watermark chunk's remainder re-reserves in ANOTHER chunk on the first post-compaction append, and the cross-chunk guard then forces a full copy EVERY back-edge (a measured cliff: fasta N=320000 took 34 s). Chunk mechanics: oversized chunks get 2x headroom (virtual-only cost — pages fault lazily), and on a chunk crossing the compaction rebases W via the chunk footer (usable end -> own base) to the new chunk's allocation start, preserving the B >= S two-pass disjointness. Also fixed en route: CO-35's cursor - W arithmetic was garbage across chunks (distinct mmaps) — the trigger now forces a compaction on chunk crossing and the live-size recording is chunk-guarded. The deferred-+ path participates via AddInt.AffineResvStartSlot/AffineResvEndSlot (a late-typed accumulator's armed adds patch to ConcatStrTip in ResolveDeferredAdds). Measured: a 3M-iteration acc + "xy" fold (6 MB result, crossing chunks): >120 s/OOM -> 0.003 s; a 960k-iteration closure-call append fold: >120 s -> 0.002 s; fasta N=80000: 67 s -> 0.013 s, N=320000 0.050 s, N=1280000 0.53 s at 41 MB RSS — all LINEAR, both program halves on the fast path. Regression: tests/tco_affine_string_append.ash (in-place growth, closure-call operands, chains, chunk crossing, on the unoptimized pipeline). |
| Large-list copy-out stack overflow fixed (CO-37) | The scope-exit list copier (CopyOutList / inner-list copy-out) cached every head value in a dynamic stack alloca of 8 bytes per cell — a list past ~1M cells burned 8 MB+ of stack in one shot, and entry-frame allocas are never popped, so consecutive top-level list bindings compounded: two 1M-list lets (e.g. let xs = build(...) then let ys = reverse(xs)) overflowed the default 8 MB stack and segfaulted. Surfaced by re-running the mandelbrot benchmark (the packed-bitmap list is N^2/8 cells: N=2500 crashed; N=2000 survived at 8.0 MB by luck). Head caches larger than 32 KB now spill to a dedicated OS allocation (mmap/VirtualAlloc) released as soon as the destination list is built; small lists keep the stack path. mandelbrot N=16000 (32M-cell list) and multi-million-element List.reverse at top level now run on all three targets. Regression: tests/list_copyout_large.ash (1.5M-element build + reverse, two copies in one frame). |
| Diagnostic source mapping — combined-source spans render at the user's coordinates | Compilation runs on the stitched combined source (imported source modules + reshaped entry), so diagnostic spans are offsets into it — but the CLI rendered them against the original file text, producing positions past EOF (line 71 in a 66-line file, columns in the thousands pointing into the stitched single-line prefix) whenever the entry sat behind a stitched module, and off-by-the-import-header positions even for simple files. ProjectSupport.MapDiagnosticsToOriginal now maps spans back before rendering, using the property that makes this a contained fix rather than full source-map infrastructure: the entry region of the combined source is line/column-preserving with respect to the user's file (imports blanked keeping newlines, hoisted declarations blanked via BlankSpans, alias preludes overwriting blank import lines) — entry spans map by line/column arithmetic. Hoisted entry type/capability/provide declarations map exactly via a fragment table recorded as TryShapeFlatModule extracts them (CombinedCompilationLayout.EntryTypeDeclFragments); spans inside a stitched (reconstructed) non-entry module region render header-only, attributed to the owning file via ModuleOffsets. Measured: x + "oops" behind an Ashes.List import went from 9:2568 (blank caret past EOF) to the exact 6:9 with the right line text and underline; multi-error files locate every error. Unit tests cover the three mapping paths (ProjectSupportTests.MapDiagnosticsToOriginal_*). |
| Formatter fidelity — standalone comments preserved, trailing whitespace eliminated | The canonical formatter is AST-based and the AST carries no trivia, so CLI fmt -w silently deleted every // comment outside the leading header block; it also left trailing whitespace after =/->/in/else wherever the tree writers appended structural padding before breaking the line. Comments: the anchor-based reinsertion the LSP's format-document path already had was formatter-domain logic living in a consumer — moved to Ashes.Formatter.CommentReinserter and wired into CLI fmt, so both paths behave identically (each standalone comment line is re-anchored to the surrounding significant lines by a whitespace-insensitive token signature; a comment whose anchor disappears falls back to the previous anchor, then the top of the file — never dropped; idempotent). Whitespace: Formatter.FinishOutput trims every line (safe — string literals are emitted single-line with escaped \n), landed with the coordinated ~400-file repo-wide reformat it was deferred for (verified whitespace-only via git diff --ignore-space-at-eol and idempotent). Gotcha recorded: fmt -w itself does not honor // fmt-skip: (only scripts/verify.sh's check loop does) — bulk fmt -w runs must exclude those fixtures. |
RC Perceus migration chronology and verification
The migration completed on 2026-07-23. It replaced the arena/copy-out model as the general lifetime mechanism for escaping ordinary values while retaining regions only where their owner and reclamation boundary are explicit. The current contract lives in Compiler Architecture and IR Reference; this section preserves why the implementation took its present shape.
The work was grounded in the PLDI 2021 paper and extended report, Perceus: Garbage Free Reference Counting with Reuse. Ashes adopted precise owned/borrowed environments, late dup, early drop, recursive drop specialization, uniqueness, and reuse tokens without exposing ownership syntax in the language.
| Phase | Lasting result |
|---|---|
| 0 — decision and inventory | Classified language heap values, runtime buffers, layouts, allocation sites, ABI constraints, and the intended RC header. |
| 1 — ownership summaries | Replaced fragile call-site reasoning with FunctionOwnershipSummary: consumed/borrowed parameters, result reach, captures, and uniqueness. |
| 2 — explicit lifetime IR | Separated ordinary RcDup/RcDrop from deterministic resource cleanup and introduced control-flow-precise PerceusLifetimePlacement. |
| 3 — first runtime family | Added the 16-byte RC header, runtime counts, and type-directed recursive drops for ADTs and lists while preserving payload offsets. |
| 4 — specialization and fusion | Added constructor/deep-unique drop paths, branch sinking, safe dup/drop fusion, and the per-thread exact-size free list after native profiling exposed per-cell OS map/unmap as untenable. |
| 5 — reuse tokens | Made DropReuse return a compatible unique cell or null after decrementing a shared cell; AllocReusing consumes the token or allocates fresh, including field-transfer rules. |
| 6 — broader heap coverage | Added runtime ownership for Strings, Bytes, BigInts, result containers, tuples, records, user ADTs, lists, and supported closure environments. |
| 7 — arena retirement | Propagated ownership through scopes, calls, higher-order results, matches, closures, and TCO; normalized complete graphs so an RC parent never owns an arena child; confined to-space operations to persistent Map/HashMap. |
| 8 — conformance and documentation | Classified every remaining copy by CopyOutPurpose, compared the implementation with the paper, resolved ordinary-value blockers, and audited permanent documentation. |
The migration tests found correctness problems that output-only tests did not: branch-local releases suppressed by other arms, mixed RC/arena graphs, premature parent drops during payload transfer, unreturned TCO owners, and linear growth in String, closure, async HTTP, and persistent-collection workloads. Each fix gained focused IR/native coverage. Memory tests use 2K/10K/50K workloads to bound total and late ru_maxrss growth while checking output at every scale; the 1BRC gate additionally uses 75K/150K/300K-row inputs. The permanent method and matrix are documented under Compiler Memory Regressions.
The final exit gates were:
dotnet build Ashes.slnx --no-restore: zero warnings and errors;dotnet format Ashes.slnx --verify-no-changes --no-restore: clean;- compiler suite: 1,641 passed, zero failed, including native RSS/CPU gates;
- linux-x64 native execution, linux-arm64/qemu coverage, win-x64/Wine coverage, and a win-arm64 PE machine-field smoke test;
- README showcase and the VitePress production documentation build.
Post-migration challenge status: the exit gates above did not initially run the opt-in
challenges/suite. A fresh pre/post A/B then surfaced P1 ownership failures plus severe scaling and peak-RSS regressions across it. All of them have since been resolved — each fix is narrated in the chronology below and locked by a regression test undertests/, and the two remaining forward-looking perf gaps (the list-of-small-Strconstant and the output buffering question) are tracked under Deferred. Challenge conformance now holds against the pre-migration control at every scale run.
The first post-migration scaling correction removed repeated RC graph normalization across ordinary closure calls. A second ownership bit in the closure's packed metadata now advertises that the direct parameter entry can adopt an RC-owned argument. The caller transfers a fresh result directly or conditionally retains a non-fresh root, then passes the ownership bit through the closure ABI; the callee adopts that reference or keeps the defensive arena-to-RC copy for unknown inputs. Only the direct lifted-function parameter advertises adoption; earlier curried parameters have already been captured in closure environments. Late-inferred TCO parameter eligibility resolves pending call flags before code generation. This restored reverse-complement from quadratic time (4.80 seconds at fasta N=30,000) to linear scaling (0.01 seconds at N=30,000; 0.06 seconds at N=100,000), with byte-identical output.
The next scaling correction replaced the RC allocator's single unsorted exact-size free list with per-size bins for cached blocks up to 4 KiB. The old allocator linearly searched every differently sized released block, so workloads such as Ashes.Text.join became quadratic despite correct ownership and stable RSS. Direct bin lookup restored 1BRC to 0.01/0.03 seconds at 10,000/30,000 rows, matching the pre-migration timings with byte-identical output. A variable-size recycling CPU gate covers the allocator shape.
Scalar folds received a separate borrowed-cursor correction. A tail-recursive walk over List(Float) had been normalized to RC and then duplicated/dropped one cons cell per iteration, even though inline list heads have no child ownership to transfer. Such cursors now borrow the caller-owned graph, and scalar-only frames omit the otherwise-redundant arena reset at the back edge. Spectral norm N=5,500 returned from 10.95 seconds to a 4.639-second median, matching the pre-migration 4.683-second control with byte-identical output. Pointer-bearing consumed lists remain runtime-managed unless the traversal is proven inspect-only (see the n-body borrow below). The same rule removed Mandelbrot's duplicate packed-bitmap representation: N=16,000 peak RSS returned from 2,756,764 KB to 1,757,596 KB, within 0.23% of the 1,753,536 KB pre-migration control.
Task-private arenas received a lazy-footer correction after their chunk-reclamation fix. Spawned handlers map a 4 MiB initial chunk; eagerly writing its footer touched the far page even when the handler used only its frame page, adding one recurring minor fault per connection. Reapers now derive the fixed first chunk from the task address, while genuinely grown chunks retain the common footer/previous-end chain. Minor faults for the 1,000-request diagnostic returned from 2,416 to the 1,215 pre-migration level, and three interleaved 50,000-request TCP runs matched the pre-migration throughput at concurrency 1, 8, and 64. A native minor-fault gate and an 8 MiB receive stress cover the short-task and grown-chunk paths.
The final standard-workload sweep found a scale-dependent TCO string-exit defect that small pidigits probes missed. Unreachable dummy stores after tail jumps obscured a returned-accumulator join, and its sibling exit concat retained stale arena provenance after late RC parameter promotion. Control-flow reachability now excludes those stores, derived exit concatenations adopt the managed regime, and runtime-managed ConcatStrTip consumes its predecessor uniformly across in-place and fallback paths. Standard N=10,000 is byte-identical and completes in 3.26 seconds.
Fresh-result helpers used directly as TCO successor arguments are now inlined into the back edge. This retains their aggregate inside the loop arena until the existing copy/reset boundary instead of normalizing it to RC at an intermediate helper return. Ownership-summary freshness is the gate, and capture expansion supplies any functions referenced by the inlined helper. Combined with local list-and-record reuse, n-body's N=5,000,000 diagnostic improved from 4.05–4.11 seconds to 3.62–3.72 seconds with byte-identical output and flat 8.2 MB peak RSS.
The remaining gap closed by borrowing the inspected acceleration graph. Profiling the saturated accel call located a defensive whole-graph deep copy at every entry: accel's others argument is allBodies, and because its Body element is a heap record the consumed-tail rule normalized the list — one 64-byte copy and one runtime-managed cons cell per element — even though accel only reads inline Float fields and returns a Float tuple. The borrowed-cursor rule now extends to pointer-bearing elements: a consumed-tail List(record) parameter whose recursive body only inspects the list (every bound head and tail is a match scrutinee or the same-position tail self-call argument, never returned, consed, stored, or passed in an owning position — proven by a structural escape analysis) and whose element is an all-inline-copy-field record is borrowed from the caller instead of normalized. This is the ordinary Perceus borrowed-vs-owned parameter distinction for a read-only traversal; owning traversals (updateVel/updatePos rebuild the list; energy hands its tail to potential) are excluded automatically, and the aliased allBodies read is preserved because a borrowed graph is never overwritten. n-body's N=5,000,000 diagnostic improved from 3.37 seconds to a 1.56-second median — below the roughly 2.00-second pre-migration control — with byte-identical output through the standard N=50,000,000 workload and a flat RSS slope. Regressions: ReuseTokenTests.Inspect_only_record_list_traversal_borrows_instead_of_normalizing and its escaping counterpart.
Arena in-place reuse of a TCO accumulator's ADT cell is now declined when the ADT carries runtime-managed (pointer-bearing) children. Such an accumulator's cell is arena-managed while its children are RC, so the back-edge deferred drop releases the previous value by re-reading THIS cell's fields — but an arena AllocReusing had already overwritten them with the new children, freeing the live new children (a child rebuilt from a shared tail, value :: rest, lost cells across iterations). Keeping the old cell intact by rebuilding fresh lets the deferred drop release the real old value; the runtime-managed reuse path, which manages its children explicitly, is unaffected. The extra per-iteration cell is bounded (the deferred drop reclaims it). Regression: EndToEndNativeBackendTests.Tco_adt_with_shared_tail_list_children_survives_across_iterations and the native tests/runtime_rc_tco_positional_adt_children.ash.
The lifetime placement now follows an owner's borrow through a local slot. The conditional runtime-argument retain (EmitConditionallyRetainedRuntimeArgument, used when a non-fresh runtime-managed value is passed to a closure that may adopt it) stores the borrowed owner into a fresh slot and reloads it for the call, so the drop-placement alias walk — which followed Borrow but not StoreLocal/LoadLocal — lost the borrow and placed the owner's drop before the call: a use-after-free that segfaulted or corrupted every JSON keyword/literal parse (Ashes.Text.Json.parse and hand-written string parsers). CollectOwnerAliases now also follows an alias through any slot it is stored into and reloaded from, to a fixpoint. This only lengthens liveness (the drop lands after the last real use, never earlier), so it cannot introduce a premature free. Regression: EndToEndNativeBackendTests.Runtime_managed_string_passed_through_identity_then_consuming_call_is_not_freed plus the recovered tests/stdlib_json.ash and tests/namespace_nested_modules.ash.
The same alias walk now also follows an owner captured into a closure. A runtime-managed value borrowed into a transient closure's arena/stack environment (StoreMemOffset of a borrow into an env pointer, then MakeClosure/MakeClosureStack), or into a curried partial application (CallClosure(f, x) whose result is itself applied again), must stay live until that closure is APPLIED — the borrow lives in the env until then. Previously the drop landed right after the capture, before the application read the value back: benign for a string recycled on the free list but a use-after-free (segfault) for one larger than the 4 KiB RC cache, whose independent mmap the drop munmaps. CollectOwnerAliases now follows an alias through a closure env and through a partial-application result, so the owner's drop lands after the closure's application. Recovers tests/regex_large_subject_chain.ash (chained Ashes.Text.Regex.replace over a >4 KiB subject — the subject was freed before the substitute read it). Regression: EndToEndNativeBackendTests.Large_runtime_managed_string_captured_into_closure_survives_until_applied.
A TCO loop's string accumulator returned inside a tuple is now copied out of the reused arena. A tail-recursive parser step such as readWord acc text = ... | Some((h, t)) -> if h == " " then (acc, t) else readWord(acc + h)(t) returns its String accumulator (and the match-bound suffix tail) in a tuple. Both live in the callee's arena, which the loop resets in place on every back-edge; a directly-returned String is copied out at the return boundary, but a String nested in a tuple field was not, so a second call reusing the same arena overwrote the first call's word (value=value instead of name=value). MaterializeEscapingStringTupleElement now copies such a field out to an independent RC string — but only inside a TCO loop (_tcoCtx set), only for a bare variable with no RC ownership of its own (an already-owned value like let text = fromInt(42) in (text, 2) stays arena-managed, preserving the borrowed-pointer-tuple contract), and skipping any element the ownership system already keeps alive. Because inference is interleaved with lowering the accumulator's element type is often an unresolved type variable at this point (indistinguishable from a scalar accumulator's), so the copy-out is emitted provisionally with a DeferredElementType and a post-inference pass (ResolveDeferredTupleMaterializations) keeps it when the type resolved to Str or rewrites it to a plain Borrow alias when it resolved to a scalar — a scalar field is never byte-copied as a length-prefixed string. The same hazard when the tuple is wrapped in an ADT constructor (Ok((acc, tail)), which every hand-written parser's parseStringBody returns) is handled by recursing ProducesFreshTuple into constructor arguments so the tuple flag is set through the wrapper. Recovers tests/text_json_parser_smoke.ash (a hand-written JSON parser whose object keys and member suffixes were both corrupted). Regressions: EndToEndNativeBackendTests.Tco_loop_string_accumulator_returned_in_tuple_survives_next_call, its _adt_wrapped_tuple_ counterpart, and Tco_loop_int_accumulator_returned_in_tuple_is_not_corrupted_as_string.
Arena in-place reuse of a TCO-parameter ADT cell is now declined for any ADT with a heap child. A tail-recursive loop that destructures and rebuilds a single-constructor product around its back edge (fannkuch-redux's nextPerm rebuilding S(perm, count)) had its product shell rebuilt with an arena AllocReusing reusing the destructured cell; the back-edge RestoreArenaState then freed that shell before it became the next iteration's parameter — a use-after-free (segfault, or a corrupt count read returning a premature result). The reuse-decline gate now fires whenever a matched constructor has a field that is not an inline copy scalar (List/String/Bytes/BigInt/Tuple/nested ADT): such a child is RC-normalized at runtime even when the ADT is flat-copy-out-able (S(List(Int))'s Int-element list still becomes an RC list), so the arena shell cannot survive the reset. This supersedes the earlier narrower !CanCopyOutAdt gate, which missed the copy-out-able-but-heap-bearing case. The constructor is read from the match pattern, since the scrutinee's inferred type is often still an unresolved type variable at the reuse decision. Recovers challenges/fannkuch-redux (hung at N=3, segfaulted at N≥4 at every optimization level). Regression: EndToEndNativeBackendTests.Tco_positional_product_with_list_child_survives_back_edge_reset.
The paper comparison found no unresolved blocker inside the declared Ashes memory model. The scope is intentionally hybrid:
- ordinary escaping acyclic graphs use RC Perceus ownership;
- proven non-escaping scratch may use scoped arenas;
- task/capability state remains scheduler-region-owned because suspension is non-linear;
- RC counts are thread-local, so worker publication uses independent copies until
tsharemarking or an atomic transition exists; - borrowed mmap-backed
Bytesviews remain tied to their mapping/resource; - persistent
Map/HashMapreuse retains a measured specialized region; - language resources keep affine
CleanupResource, separate from ordinary RC; - cyclic graphs require future cycle handling and are not admitted to RC.
These are named IR boundaries with bounded-memory regressions, not implicit fallbacks. Consequently Ashes claims the Perceus ownership invariant for admitted RC graphs, not that every byte of mixed runtime state is governed by the paper's formal calculus.
Scope decision — runtime string interning remains rejected. The original arena-only design could neither retain dynamic entries safely nor reclaim a permanent intern table. RC Perceus removes the first obstacle, but a strong table reference would still keep every distinct dynamic string alive. A bounded implementation now requires weak table entries or eviction, removal synchronization, and a workload demonstrating that the lookup cost wins back enough allocation. Ashes therefore still interns only the finite, compile-time-known literal set. This is a performance decision, not a claim that reference counting is unavailable.
Roadmap
The full 1e9-row 1BRC runs in ~11.8–11.9 s (work-conserving queued reduce with worker-side pairwise merging, CO-25 + CO-26 — see Completed Work). The sub-10 s milestone is closed as not reachable on the reference box with the current per-row upsert architecture: scheduling losses were eliminated (flat 32-active timeline, parallel merge, sub-second tails), and working-set reduction was investigated and falsified (CO-27 — the fold is bound by the per-row dependent-load chain's latency, not by footprint).
No active roadmap items remain — every task with a demonstrated payoff has shipped (the in-place-reuse cluster CO-15/16/22, the 1BRC scheduling arc CO-24/25/26/27, the debug tooling CO-20/21, and the parallel-chunking ergonomics CO-18). The two items below are deferred: each is a genuine capability gap, but neither has a workload that exercises it and both sit on the highest-risk code in the compiler (the reuse / lifetime analyses, where the CO-8/CO-9 use-after-frees lived). Implement either one only when a concrete program demands it — that program then serves as the required UAF/allocation regression test. They are kept here (not deleted) so the design analysis is not lost.
Deferred
| ID | Task | Notes |
|---|---|---|
| Compile-time eval — aggregate/string result embedding (deferred) | Embed evaluated list / ADT / record / Str results as static data | Compile-time evaluation (see Completed Work) folds only scalar results today; a call that evaluates to a list, ADT, record, or string keeps its runtime construction (e.g. a list-of-fib(k) folds each element but still builds the cons chain at startup). Embedding these needs a value-graph serializer that writes the evaluated heap graph into .rodata with internal relocations (the string-literal and jump-table relocation machinery shows the linkers can), plus marking those constants immortal and excluding them from Perceus in-place reuse — an AllocReusing write into a .rodata constant would segfault, so the move/uniqueness analysis (Lowering.MoveAnalysis) must never treat an embedded constant as uniquely owned. This is where the ASCII-classification-table / parser-table startup-elimination win lands. Also out of scope until then: captured-environment closures (needs an env-memory model / LoadEnv), raw-memory tuples/records (Alloc/StoreMemOffset), and tail-call / loop folding (the interpreter recurses in C#, so loops beyond the depth budget bail). Intrinsic-backed results stay runtime-only regardless — regex pcre2_code* is a native pointer and openlibm transcendentals raise cross-host float-determinism concerns. Risk: MEDIUM — the serializer itself is mechanical; the reuse-exclusion interaction is the schedule risk. |
| Per-fd wakeup targeting (deferred) | Wake only ready leaves in the run-queue scheduler's aggregate wait | The aggregate wait re-queues every parked leaf per wakeup (O(parked)); re-queuing only the leaves whose fd is ready would cut re-step work under very high connection counts. A first attempt served the happy path but was reverted as too delicate — three hazards to respect next time: (a) struct epoll_event is __attribute__((packed)) on x86-64 (12-byte stride, data at offset 4) but unpacked on arm64 (16-byte stride, data at offset 8), so registering the fd in data and reading it back from epoll_wait must be arch-correct — the existing registration writes data at offset 8, harmless only because the current requeue-all never reads it back; (b) the batched event buffer must be a module-global, not a stack alloca, since EmitSchedulerAggregateWait runs inside the scheduler loop and a per-wakeup 1 KB alloca overflows the stack; (c) the requeue pass must partition the parked list (re-queue only ready sockets and elapsed timers, rebuild the rest) without breaking the drain-timer / graceful-shutdown path, which the first attempt got wrong. Guard with the full server suite plus the concurrent-HTTP test. Risk: HIGH — the scheduler hot path that all serving depends on. |
| CO-17 (deferred) | Zero-copy borrowed slices from Bytes.subText / String.substring | Deferred — poor value/risk, and the explicit escape hatch already covers it. The manual half shipped as Ashes.Bytes.subView (a caller-lifetime zero-copy view), and every performance-oriented path already uses it (the fast 1BRC variants brc_trie/brc_parallel take a subView of the station name; only the naive reference brc.ash and String.split still call subText/substring). So the automatic half would help only transient slices in code that (a) is allocation-bound on subText and (b) didn't reach for subView — a narrow, currently-unmeasured slice — while costing HIGH-risk escape/lifetime analysis that interacts with the reuse materialization. Revisit only if a measured subText-allocation-bound workload appears that can't simply use subView. Original analysis: this item covers the automatic, escape-analysis-driven half. These copy their result today. The string/bytes view representation already exists (EmitStringView; the mmap-input half landed as Ashes.File.mmap). Making subText return a view is not an unconditional win — a slice stored in a structure (a 1BRC station name inserted into the Map) is materialized (copied) on insert anyway, so a view would be created then copied, strictly more work; only transient slices (parsed/compared then discarded) benefit. Approach: a context-sensitive lowering — return a view when the slice provably does not escape, copy when it is stored — which needs an escape/lifetime check at the subText site (or a materialize-on-store follow-on). Endpoint: a field-slicing fold that keeps only transient slices shows an allocation/time drop with no correctness regression. Risk: HIGH — escape/lifetime analysis; interacts with the reuse materialization. |
| CO-19 (deferred) | Multi-parameter inner go in the reuse specialization | Deferred — the motivation is obsolete and the performance premise was falsified. The wide-trie endpoint that drove this shipped WITHOUT it (Ashes.HashTrie node-carried shifts keep the rebuild worker go single-parameter), and CO-27 then showed the ~11.9 s 1BRC wall is contention-bound (per-row dependent-load latency), not structure-bound — so the "beats AVL ≥2×, 1e9 < 10 s" endpoint below is moot regardless of go's arity. Nothing shipped needs it: every multi-parameter inner go in the stdlib/challenges is a reader (foldLeft's go acc t) or a driver (fromList's go entries map, whose reuse fires at the inner set call) — the only rebuild workers (Map.set, HashTrie) are single-parameter. The genuine remaining gap — a fold whose rebuild worker threads extra per-recursion state alongside the accumulator (go extra… acc) can't be reuse-specialized and would leak — has no known workload; most such state is better expressed node-carried, captured as an outer loop-invariant param, or recomputed. Revisit only when a real multi-param-rebuild fold shows up and leaks (that program is then the UAF regression test). Original analysis: |
List-of-small-Str representation constant (deferred) | Shrink the ~96 B/element cost of a list of single-character strings | Surfaced by the challenge sweep (reverse-complement). Growing accumulators already scale linearly in time and memory (CO-34/CO-35/CO-36); this is the remaining constant: a list of single-character Str values costs about 96 bytes per element — each element is a separate length-prefixed heap string plus a cons cell — producing about 1 GB peak resident set for a 10 MB input. Reducing it needs in-place cons-cell reuse, an ownership/linearity feature rather than a point fix (same machinery as the affine string growth, CO-36). It also gates the standard 25M-base reverse-complement workload, which extrapolates to ~24 GB. Risk: MEDIUM — the reuse/uniqueness analysis, but a narrower case than the general escape analysis. |
| Line-oriented output buffering (deferred) | Confirm, and if needed buffer, Ashes.IO.write | It is not yet confirmed whether Ashes.IO.write buffers output or issues one write syscall per call. Fasta and reverse-complement emit one write per 60-character line — over two million syscalls at benchmark scale. If the path is unbuffered, the throughput cost should be measured and, if material, addressed with a line/block buffer (flushed on close and on explicit flush). Risk: LOW — an isolated IO-path change with a clear before/after benchmark; the only subtlety is preserving flush ordering with process exit and interleaved stderr. |