append's growth path is the entire sieve benchmark gap (not slice indexing) — and the obvious realloc fix is unsound

[javimosch]

bench/native-speed has always shown machin trailing Rust and Zig on the sieve
kernel by ~1.4x, and the benchmark README explained it as:

On the array-heavy sieve machin trails by ~1.4× — its slice indexing/layout
is less optimal than a Rust Vec or a Zig slice.

That diagnosis is wrong. Phase-timing the kernel shows slice indexing is not
the problem at all — the sieve loop ties Rust exactly:

phase	machin	Rust
build the 10M array by append	70–83 ms	27–29 ms
the sieve loop itself	110 ms	111 ms
the count loop	5–7 ms	3 ms

The generated C for the hot loop is already what you would write by hand — direct
pointer indexing, no bounds check, no indirection:

while ((v_m <= v_n)) { ((int64_t*)(v_sieve).data)[v_m] = 0LL; v_m = (v_m + v_p); }

The entire gap is append's growth path.

Mechanism

mfl_append doubles capacity through mfl_realloc, and mfl_realloc can only
ever copy:

static void* mfl_realloc(void* old, size_t sz) {
    void* p = mfl_alloc(sz);                 /* a brand-new malloc'd arena block */
    if (old) { size_t o = ((mfl_blk*)old - 1)->size; memcpy(p, old, o < sz ? o : sz); }
    return p; /* old reclaimed with its arena — never freed individually */
}

So growing to 10M elements walks ~21 doublings, each one allocating a fresh block
and memcpy'ing, and never releasing the previous buffer (an arena frees nothing
mid-life). The process therefore touches roughly 2x the final array in freshly
faulted pages. Vec::push hands the block to realloc, and glibc extends a large
block in place via mremap — no copy, no new pages.

The obvious fix is unsound — do not just do it

When the block being grown is the arena's most recent allocation, nothing is
layered on top of it in the block list, so it looks safe to hand it straight to
realloc() and let glibc mremap it. I implemented and then rejected this,
because MFL slices share backing storage:

func mutate(s) { s[0] = 77 }

a := []int{1,2,3}
b := a            // b.data == a.data  (verified: mutating a changes b)
mutate(c)         // params share too  (verified)

Today, a = append(a, x) allocating a fresh block leaves every existing alias
pointing at the old block, which is still live because the arena frees nothing.
That is Go-like "append may stop sharing" — surprising, but memory-safe:

a := []int{1,2,3}
b := a
i := 0
while i < 1000 { a = append(a, i)  i = i+1 }   // ~8 reallocations
println(b[0])                                   // prints 1 — still valid today

With an in-place realloc, that b[0] becomes a use-after-free whenever the
block moves. Trading a 45 ms benchmark win for a silent dangling read is exactly
the bug class machin exists to eliminate, so the naive version must not ship.

Directions that could be sound

1. Escape/alias analysis on the slice. machin already computes provenance
   interprocedurally for ARENA001. If we can prove a slice has no live alias at
   the append site, in-place growth on the arena-head block is safe. This reuses
   machinery that exists rather than adding a new concept.
2. Free the abandoned block when provably unaliased, keeping the copy but
   letting the pages be reused — cheaper than in-place growth but far simpler to
   justify.
3. A capacity hint (make([]int, 0, n) or similar) so the common
   "I know the final size" case does one allocation. Sidesteps the analysis
   entirely for the case the benchmark actually hits, though it does not help
   code that genuinely grows unboundedly.

(1) is the one that matches machin's existing direction — inferred, no
annotations.

Why this is worth fixing beyond the benchmark

append in a loop is the single most common way to build a collection in MFL, so
this is not a synthetic-benchmark artifact — it is on the hot path of ordinary
code. grange's index builds and any parser accumulating tokens pay it.

Reproduce: bench/native-speed/./run.sh, then the phase breakdown in
bench/native-speed/README.md.

[javimosch]

Measured the ceiling first: this closes the gap entirely, not partially

Before designing anything, I built a throwaway unsound prototype (in-place
realloc on the arena's head block) purely to find out what the win is worth.
It does not narrow the sieve gap — it erases it:

	build phase (10M appends)	whole sieve kernel
current	79 / 71 / 69 ms	0.18–0.20 s
prototype	24 / 28 / 25 ms	0.14 s
Rust	26 / 26 / 29 ms	0.14–0.15 s

So the last remaining loss in bench/native-speed becomes a tie. That is the
justification for the complexity below; without this measurement the work would
have been speculative. The prototype has been deleted — it is unsound for the
reason in the issue body.

The design: a FAIL-CLOSED whitelist, not a shared-bit

The question the optimization needs answered is "does any other live reference
observe this slice's backing array?" Two ways to answer it, and the difference
matters more than the implementation:

Rejected — a dynamic shared bit on the slice header. Set it wherever
codegen copies a header (assignment, argument pass, struct store, closure
capture, return), then append grows in place when it is clear. Tempting, and
much less code. But it fails open: a header-copy site nobody thought of stays
unmarked, and an unmarked alias is a use-after-free. The failure mode of a missed
case is silent memory corruption.

Proposed — a static, intraprocedural whitelist. For a local variable v of
slice type, v is unaliased if every operation on it in the whole function is
one of:

• initialization from a slice literal,
• v = append(v, …),
• v[i] read, v[i] = e, v[i].f = e,
• len(v),
• for … range v.

Anything else — assignment to another variable, passing as an argument, storing
into a struct/slice/map, capturing in a closure, returning, sending on a channel,
slice-ranging — disqualifies v. An unrecognised construct also disqualifies
it. This fails closed: the cost of a case nobody thought of is a missed
optimization, not corruption.

arena_prov.go is worth correcting on: it answers "was this freshly
allocated?", which is a different question from aliasing. Its AST walkers
(provWalkAssignments, provWalkReturns), its per-function fixpoint shape and
its call-graph scaffolding are reusable; the analysis itself is new. I previously
described it as "most of the machinery", which overstated it.

Runtime gate

Static proof is necessary but not sufficient — the block also has to be safely
realloc-able. A second, dynamic condition: the block must be the arena's
head. The arena is a singly-linked list, so growing a mid-list block would need
its predecessor. Head-only needs no list surgery, and it is the common case
precisely because a tight append loop allocates nothing else in between (which is
why the prototype hit Rust parity while only handling head).

Also required, and easy to forget: mfl_realloc growing in place hands an address
back to the allocator, which breaks the substr strlen cache's invariant that a
live pointer's length never changes identity. The cache must be invalidated on
that path. (This bit me building the prototype — the cache variable is declared
after mfl_realloc in the emitted C, so it needs moving.)

Scope, honestly

Covers: the local-slice-built-in-a-loop shape, which is the sieve, grange's index
builds, and any parser accumulating tokens.

Does not cover: a slice passed to a helper that appends to it, a slice living
in a struct field, or a slice built across functions. Those keep today's
copy-and-abandon behaviour, which stays correct.

Verification plan — the part that decides whether this ships

1. ASan gate, already proven to work. machin builds through cc, so
   CC=<gcc -fsanitize=address> works today with no new machinery, and it catches
   this exact bug. Run against the unsound prototype on an aliasing program:

   ==921117==ERROR: AddressSanitizer: heap-use-after-free on address 0x504000000020
   READ of size 8 at 0x504000000020 thread T0
       #0 in mfl_main
   

   So the safety net exists and is demonstrated to detect the precise failure
   mode. The whole example corpus should run under ASan with the optimization on.

2. Differential output check: every example and test program, built with and
   without the optimization, must produce byte-identical output.

3. An adversarial alias suite: one program per disqualifying construct
   (b := a, pass-to-function, struct field, closure capture, return, channel
   send, slice-range), each asserting the alias still reads correct data. These
   fail loudly under ASan if the whitelist ever gains a hole.

4. A negative test on the analysis itself: assert that each disqualifying
   construct actually disqualifies, so a refactor cannot silently widen the
   whitelist.

Suggested sequencing

1. the analysis + a --json way to see which slices qualify (reviewable on its
   own, ships nothing);
2. the ASan CI job and the adversarial suite (the net, before the thing it
   catches);
3. the codegen change behind the analysis;
4. re-run bench/native-speed and update the published numbers — including
   docs/BENCHMARKS.md, the README and the blog post, which all currently say
   machin loses the sieve by 1.46x.