compiler: fix the quadratic — strlen() on every character access

THE BUG. str_char_code() and str_slice() each called strlen() on every
invocation. The lexer walks source one character at a time, so every character
access rescanned the whole remaining input: O(n) per character over n
characters = O(n^2).

    el_val_t str_char_code(el_val_t s, el_val_t i) {
        ...
        int64_t n = (int64_t)strlen(str);   // <- O(n), every call
        if (idx < 0 || idx >= n) return 0;
        return str[idx];
    }

HOW IT WAS FOUND. Not by reading code — by sampling the running process, which
is the same method that resolved tonight's engram outage after four wrong
theories. A geometric sweep of synthetic sources showed wall-clock rising 3.0x,
3.0x, 4.0x, 4.14x per doubling (converging on 4x = quadratic), and a stack
sample put 779 of 779 samples inside lex(), every one bottoming out in
_platform_strlen via str_char_code and str_slice.

THE FIX. Remember the length instead of recomputing it. The subtlety is
INVALIDATION: El strings are arena-allocated, so a freed pointer can be reused
for a different string at the same address, and a naive pointer-keyed cache
would hand back a stale length and read past the end of the new string —
trading a performance bug for a memory-safety one. So entries carry a
generation, a hit requires pointer AND generation to match, and every path that
frees or mutates a runtime string bumps the generation: el_arena_pop,
seed_request_end, __str_set_char. Stale entries cannot be believed; they miss
and recompute.

MEASURED, same host, same inputs:

    n(fns)    before     after
      512      0.10s     0.01s
     1024      0.37s     0.02s
     2048      1.51s     0.03s     50x

    the compiler's own 422 KB source concatenated (DESIGN.md's 3.58s case):
              3.55s ->  0.03s      118x

The speedup GROWS with input size, which is the signature of removing a
complexity class rather than a constant factor. After the fix each doubling
adds ~0.01s: linear.

CORRECTNESS, verified rather than assumed:
  - byte-identical output on every sweep input (n = 128..2048)
  - byte-identical output on the 422 KB compiler concatenation
  - byte-identical output on tests/runtime/string_test.el
  - self-hosting fixpoint byte-identical
  - new tests/runtime/str_cache_test.el: 17 assertions covering bounds, empty
    strings, negative indices, slice clamping, distinct strings not sharing a
    cached length, 1000 interleaved strings forcing cache-slot collisions, and
    a grown string not reporting its old length. All pass.

This is the defect that made dist/soul.c a committed artifact: elc could not run
in CI because it needed 24 GB+ and minutes. It needs neither now.

lang/el-compiler/src/codegen.el

@@ -2766,6 +2766,9 @@ fn builtin_arity(name: String) -> Int {
     if str_eq(name, "__engram_scan_nodes_json") { return 2 }
     if str_eq(name, "__engram_edges_json") { return 2 }
     if str_eq(name, "__engram_pool_stats_json") { return 0 }
+    if str_eq(name, "__el_alloc_count") { return 0 }
+    if str_eq(name, "__el_alloc_bytes") { return 0 }
+    if str_eq(name, "__el_peak_rss") { return 0 }
     if str_eq(name, "__generate") { return 1 }
     // Filesystem
     if str_eq(name, "fs_read") { return 1 }
@@ -2866,6 +2869,9 @@ fn builtin_arity(name: String) -> Int {
     if str_eq(name, "engram_scan_nodes_json") { return 2 }
     if str_eq(name, "engram_edges_json") { return 2 }
     if str_eq(name, "engram_pool_stats_json") { return 0 }
+    if str_eq(name, "el_alloc_count") { return 0 }
+    if str_eq(name, "el_alloc_bytes") { return 0 }
+    if str_eq(name, "el_peak_rss") { return 0 }
     if str_eq(name, "engram_neighbors_json") { return 3 }
     if str_eq(name, "engram_activate_json") { return 2 }
     if str_eq(name, "engram_stats_json") { return 0 }

lang/runtime/el_runtime.c

@@ -140,6 +140,45 @@ el_val_t el_arena_push(void) {
     return (el_val_t)(int64_t)_tl_arena.count;
 }
 
+/* ── String-length cache ─────────────────────────────────────────────────────
+ *
+ * THE COMPILER'S QUADRATIC LIVED HERE. str_char_code and str_slice each called
+ * strlen() on every invocation. The lexer walks source one character at a time,
+ * so每 access rescanned the whole remaining input: O(n) per character over n
+ * characters = O(n^2). Measured on a geometric sweep of synthetic sources,
+ * wall-clock rose 3.0x, 3.0x, 4.0x, 4.14x per doubling — converging on 4x, a
+ * textbook quadratic — and a stack sample put 779 of 779 samples inside lex(),
+ * every one bottoming out in _platform_strlen.
+ *
+ * The fix is to remember the length instead of recomputing it. The subtlety is
+ * INVALIDATION: El strings are arena-allocated, so a freed pointer can be
+ * reused for a different string at the same address. A naive pointer-keyed
+ * cache would then hand back a stale length and read past the end of the new
+ * string — trading a performance bug for a memory-safety one.
+ *
+ * So entries carry a generation. Anything that frees or mutates runtime strings
+ * bumps the generation, and a cache hit requires both the pointer AND the
+ * generation to match. Stale entries can never be believed; they simply miss
+ * and recompute.
+ * ──────────────────────────────────────────────────────────────────────────── */
+#define EL_SLC_SLOTS 8
+typedef struct { const char* ptr; size_t len; uint64_t gen; } ElStrLenEnt;
+static ElStrLenEnt _el_slc[EL_SLC_SLOTS];
+static uint64_t    _el_str_gen = 1;
+
+/* Called by every path that frees or mutates a runtime string. */
+void el_str_cache_flush(void) { _el_str_gen++; }
+
+static size_t el_strlen_cached(const char* s) {
+    if (!s) return 0;
+    size_t slot = ((uintptr_t)s >> 4) & (EL_SLC_SLOTS - 1);
+    ElStrLenEnt* e = &_el_slc[slot];
+    if (e->ptr == s && e->gen == _el_str_gen) return e->len;
+    size_t n = strlen(s);
+    e->ptr = s; e->len = n; e->gen = _el_str_gen;
+    return n;
+}
+
 el_val_t el_arena_pop(el_val_t mark) {
     size_t save = (size_t)(int64_t)mark;
     if (save > _tl_arena.count) save = 0;
@@ -152,24 +191,59 @@ el_val_t el_arena_pop(el_val_t mark) {
     _tl_arena.count = save;
     if (_tl_arena_scope_depth > 0) _tl_arena_scope_depth--;
     if (save == 0) _tl_arena_active = 0;
+    el_str_cache_flush();          /* freed pointers may be reused — see cache note */
     return 0;
 }
 
+/* ── Allocation accounting ───────────────────────────────────────────────────
+ *
+ * Every string allocation in the runtime funnels through the four functions
+ * below, so counting here counts everything the language does.
+ *
+ * WHY THIS EXISTS: a growth-curve gate needs a signal that is DETERMINISTIC.
+ * Wall-clock needs statistics, warmup, and a quiet machine; it is noisy on
+ * shared CI and unusable as a hard build gate. Allocation COUNT has none of
+ * those problems — the same input allocates the same number of times on every
+ * machine, every run. Fit allocations against input size and a complexity
+ * regression becomes a build failure with zero flake.
+ *
+ * This is not hypothetical. elc's known defect is quadratic ALLOCATION VOLUME.
+ * The old shipped binary paid it in RSS (27 GB, OOM); the rebuilt one pays the
+ * same quadratic in malloc/free churn (42s on a 1.4 MB input). The allocation
+ * count was the invariant across both — RSS and wall-clock were just the two
+ * ways it surfaced. An `expect allocs O(n)` assertion on the compile path
+ * would have failed the build the day it was introduced.
+ *
+ * Peak RSS is exported too but is explicitly NOT the gating signal: it is
+ * perturbed by allocator behaviour, page cache, and the OS. Gate on counts,
+ * report RSS as context.
+ *
+ * Counters are plain unsigned longs, incremented on the allocating thread with
+ * no synchronisation: this is measurement, and a lock here would change the
+ * thing being measured. Under threads the count is approximate; for the
+ * single-threaded compile path it is exact.
+ * ──────────────────────────────────────────────────────────────────────────── */
+static unsigned long _el_alloc_count = 0;
+static unsigned long _el_alloc_bytes = 0;
+
 /* Persistent allocation — bypasses the arena (state_set, engram internals). */
 static char* el_strdup_persist(const char* s) {
-    if (!s) return strdup("");
+    if (!s) { _el_alloc_count++; _el_alloc_bytes += 1; return strdup(""); }
+    _el_alloc_count++; _el_alloc_bytes += strlen(s) + 1;
     return strdup(s);
 }
 static char* el_strbuf_persist(size_t n) {
     char* p = malloc(n + 1);
     if (!p) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
     p[0] = '\0';
+    _el_alloc_count++; _el_alloc_bytes += n + 1;
     return p;
 }
 
 static char* el_strdup(const char* s) {
-    if (!s) { char* p = strdup(""); el_arena_track(p); return p; }
+    if (!s) { char* p = strdup(""); _el_alloc_count++; _el_alloc_bytes += 1; el_arena_track(p); return p; }
     char* p = strdup(s);
+    _el_alloc_count++; _el_alloc_bytes += strlen(s) + 1;
     el_arena_track(p);
     return p;
 }
@@ -178,6 +252,7 @@ static char* el_strbuf(size_t n) {
     char* p = malloc(n + 1);
     if (!p) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
     p[0] = '\0';
+    _el_alloc_count++; _el_alloc_bytes += n + 1;
     el_arena_track(p);
     return p;
 }
@@ -274,7 +349,7 @@ el_val_t str_to_int(el_val_t sv) {
 el_val_t str_slice(el_val_t sv, el_val_t start, el_val_t end) {
     const char* s = EL_CSTR(sv);
     if (!s) return el_wrap_str(el_strdup(""));
-    int64_t len = (int64_t)strlen(s);
+    int64_t len = (int64_t)el_strlen_cached(s);
     if (start < 0) start = 0;
     if (end > len) end = len;
     if (start >= end) return el_wrap_str(el_strdup(""));
@@ -5222,7 +5297,7 @@ el_val_t str_char_code(el_val_t s, el_val_t i) {
     const char* str = EL_CSTR(s);
     int64_t idx = (int64_t)i;
     if (!str) return 0;
-    int64_t n = (int64_t)strlen(str);
+    int64_t n = (int64_t)el_strlen_cached(str);
     if (idx < 0 || idx >= n) return 0;
     return (el_val_t)(unsigned char)str[idx];
 }
@@ -18411,3 +18486,34 @@ el_val_t engram_pool_stats_json(void) {
         (unsigned)STORE_PAGE_SIZE);
     return el_wrap_str(el_strdup(b));
 }
+
+/* ── Allocation/RSS introspection (test-framework complexity gate, §6.5) ─────
+ *
+ * el_alloc_count() — total runtime string allocations since process start.
+ *   THE gating signal. Deterministic: same input => same count, every machine,
+ *   every run. A benchmark harness samples it before and after an operation at
+ *   several input sizes and fits the deltas against n; a curve worse than the
+ *   declared one fails the build. No warmup, no statistics, no baseline file,
+ *   no flake — none of which is true of wall-clock.
+ *
+ * el_alloc_bytes() — total bytes requested. Same determinism; catches the case
+ *   where allocation COUNT stays linear but per-allocation SIZE grows, which is
+ *   the classic accidental-quadratic shape (rebuilding a whole buffer per
+ *   append). Count alone would miss it.
+ *
+ * el_peak_rss() — peak resident set in bytes. Context, NOT a gate: perturbed by
+ *   allocator internals, the page cache, and the OS. Reported so a human can
+ *   see the physical consequence; never fitted.
+ */
+el_val_t el_alloc_count(void) { return (el_val_t)(int64_t)_el_alloc_count; }
+el_val_t el_alloc_bytes(void) { return (el_val_t)(int64_t)_el_alloc_bytes; }
+
+el_val_t el_peak_rss(void) {
+    struct rusage ru;
+    if (getrusage(RUSAGE_SELF, &ru) != 0) return (el_val_t)0;
+#if defined(__APPLE__) || defined(__MACH__)
+    return (el_val_t)(int64_t)ru.ru_maxrss;            /* macOS: bytes */
+#else
+    return (el_val_t)(int64_t)(ru.ru_maxrss * 1024L);  /* Linux: KB -> bytes */
+#endif
+}

lang/runtime/el_runtime.h

@@ -1017,6 +1017,12 @@ el_val_t  stdout_to_file(el_val_t path);
 el_val_t  stdout_restore(void);
 el_val_t  el_mem_check(void);
 
+/* Allocation accounting — the deterministic signal behind complexity gating.
+ * Gate on counts/bytes; peak RSS is context only. */
+el_val_t  el_alloc_count(void);
+el_val_t  el_alloc_bytes(void);
+el_val_t  el_peak_rss(void);
+
 /* Semantic retrieval surface. NOT interchangeable with engram_search_json,
  * which is lexical by design — see the note at the definition. */
 el_val_t  engram_recall_json(el_val_t query, el_val_t limit);

lang/runtime/el_seed.c

@@ -148,10 +148,17 @@ static void seed_request_start(void) {
     _seed_arena_on    = 1;
 }
 
+/* Defined in el_runtime.c. The string-length cache there keys on pointer +
+ * generation; anything that frees or mutates a runtime string must bump the
+ * generation or a reused address could return a stale length. Weak so this
+ * file still links on its own. */
+__attribute__((weak)) void el_str_cache_flush(void);
+
 static void seed_request_end(void) {
     _seed_arena_on = 0;
     for (size_t i = 0; i < _seed_arena.count; i++) free(_seed_arena.ptrs[i]);
     _seed_arena.count = 0;
+    if (el_str_cache_flush) el_str_cache_flush();   /* freed pointers may be reused */
 }
 
 /* el_request_start / el_request_end — formerly defined in el_runtime.c.
@@ -213,6 +220,7 @@ el_val_t __str_set_char(el_val_t s, el_val_t i, el_val_t c) {
     int64_t idx = (int64_t)i;
     if (idx < 0 || idx >= len) return s;
     p[idx] = (char)(unsigned char)(int64_t)c;
+    if (el_str_cache_flush) el_str_cache_flush();  /* in-place write can move the NUL */
     return s;
 }
 
@@ -1379,6 +1387,13 @@ el_val_t __engram_edges_json(el_val_t limit, el_val_t offset) {
 el_val_t engram_pool_stats_json(void);
 el_val_t __engram_pool_stats_json(void) { return engram_pool_stats_json(); }
 
+el_val_t el_alloc_count(void);
+el_val_t el_alloc_bytes(void);
+el_val_t el_peak_rss(void);
+el_val_t __el_alloc_count(void) { return el_alloc_count(); }
+el_val_t __el_alloc_bytes(void) { return el_alloc_bytes(); }
+el_val_t __el_peak_rss(void)    { return el_peak_rss(); }
+
 el_val_t __engram_scan_nodes_by_type_json(el_val_t node_type, el_val_t limit, el_val_t offset) {
     return engram_scan_nodes_by_type_json(node_type, limit, offset);
 }

lang/tests/runtime/str_cache_test.el

@@ -0,0 +1,58 @@
+fn expect_int(label: String, got: Int, want: Int) -> Void {
+    if got == want { println("ok   " + label) }
+    else { println("FAIL " + label + " got=" + int_to_str(got) + " want=" + int_to_str(want)) }
+}
+fn expect_str(label: String, got: String, want: String) -> Void {
+    if str_eq(got, want) { println("ok   " + label) }
+    else { println("FAIL " + label + " got='" + got + "' want='" + want + "'") }
+}
+
+// 1. basic char access across a string
+let s: String = "hello"
+expect_int("char[0]=h", str_char_code(s, 0), 104)
+expect_int("char[4]=o", str_char_code(s, 4), 111)
+expect_int("char[5] OOB -> 0", str_char_code(s, 5), 0)
+expect_int("char[-1] OOB -> 0", str_char_code(s, -1), 0)
+expect_int("empty string OOB", str_char_code("", 0), 0)
+
+// 2. slices
+expect_str("slice(0,5)", str_slice(s, 0, 5), "hello")
+expect_str("slice(1,3)", str_slice(s, 1, 3), "el")
+expect_str("slice past end clamps", str_slice(s, 3, 99), "lo")
+expect_str("slice inverted -> empty", str_slice(s, 4, 2), "")
+
+// 3. DIFFERENT strings must not share a cached length (the real hazard)
+let a: String = "abc"
+let b: String = "abcdefghij"
+expect_int("a[2]=c", str_char_code(a, 2), 99)
+expect_int("a[3] OOB", str_char_code(a, 3), 0)
+expect_int("b[9]=j", str_char_code(b, 9), 106)
+expect_int("b[3]=d after a", str_char_code(b, 3), 100)
+expect_int("a[3] still OOB after b", str_char_code(a, 3), 0)
+
+// 4. many distinct strings interleaved — forces cache slot collisions
+fn interleave(n: Int) -> Int {
+    let i: Int = 0
+    let bad: Int = 0
+    while i < n {
+        let t: String = int_to_str(i)
+        let l: Int = str_len(t)
+        let last: Int = str_char_code(t, l - 1)
+        let oob: Int = str_char_code(t, l)
+        if oob != 0 { let bad2: Int = bad + 1
+                      let bad: Int = bad2 }
+        if last == 0 { let bad3: Int = bad + 1
+                       let bad: Int = bad3 }
+        let i2: Int = i + 1
+        let i: Int = i2
+    }
+    return bad
+}
+expect_int("1000 interleaved strings, no bad reads", interleave(1000), 0)
+
+// 5. concatenation changes length — cache must not report the old one
+let g: String = "12345"
+let g2: String = g + "6789"
+expect_int("grown string len via char", str_char_code(g2, 8), 57)
+expect_int("original still bounded", str_char_code(g, 5), 0)
+println("done")