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

2026-08-16T02:28:39Z

will.anderson commented

2026-08-16 02:28:39 +00:00

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²).

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. By sampling the running process, not reading code — the same method that resolved tonight's engram outage after four wrong theories. A geometric sweep showed wall-clock rising 3.0×, 3.0×, 4.0×, 4.14× per doubling (converging on 4× = quadratic), and a stack sample put 779 of 779 samples inside lex(), every one bottoming out in _platform_strlen.

The fix, and its subtlety. Cache the length — but 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 return 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; every path that frees or mutates a runtime string bumps it (el_arena_pop, seed_request_end, __str_set_char).

Measured:

n (fns)	before	after
512	0.10s	0.01s
1024	0.37s	0.02s
2048	1.51s	0.03s (50×)
compiler's own 422 KB source (DESIGN.md's 3.58s case)	3.55s	0.03s (118×)

The speedup grows with input size — the signature of removing a complexity class, not a constant factor. After the fix each doubling adds ~0.01s: linear.

Correctness, verified not assumed: byte-identical output on every sweep input, on the 422 KB concatenation, on string_test.el, and the self-hosting fixpoint holds byte-identical. Plus a new tests/runtime/str_cache_test.el — 17 assertions covering bounds, empty strings, negative indices, slice clamping, distinct strings not sharing a cached length, 1,000 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 couldn't run in CI because it needed 24 GB+ and minutes. It needs neither now.

**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²)**. ```c 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.** By sampling the running process, not reading code — the same method that resolved tonight's engram outage after four wrong theories. A geometric sweep showed wall-clock rising 3.0×, 3.0×, 4.0×, 4.14× per doubling (converging on 4× = quadratic), and a stack sample put **779 of 779 samples inside `lex()`, every one bottoming out in `_platform_strlen`**. **The fix, and its subtlety.** Cache the length — but 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 return 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; every path that frees or mutates a runtime string bumps it (`el_arena_pop`, `seed_request_end`, `__str_set_char`). **Measured:** | n (fns) | before | after | |---|---|---| | 512 | 0.10s | 0.01s | | 1024 | 0.37s | 0.02s | | 2048 | 1.51s | **0.03s (50×)** | | compiler's own 422 KB source (DESIGN.md's 3.58s case) | 3.55s | **0.03s (118×)** | The speedup **grows** with input size — the signature of removing a complexity class, not a constant factor. After the fix each doubling adds ~0.01s: linear. **Correctness, verified not assumed:** byte-identical output on every sweep input, on the 422 KB concatenation, on `string_test.el`, and the self-hosting fixpoint holds byte-identical. Plus a new `tests/runtime/str_cache_test.el` — 17 assertions covering bounds, empty strings, negative indices, slice clamping, distinct strings not sharing a cached length, 1,000 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 couldn't run in CI because it needed 24 GB+ and minutes. It needs neither now.

will.anderson added 1 commit 2026-08-16 02:28:41 +00:00

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

El SDK CI - dev / build-and-test (pull_request) Failing after 10m21s

Details

d231b7e5e7

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.

will.anderson merged commit 0288024396 into dev

2026-08-16 02:29:05 +00:00

will.anderson referenced this issue from a commit

2026-08-16 02:34:46 +00:00

design: gate on THREE signals -- the alloc gate would have missed el #132

will.anderson referenced this issue from a commit

2026-08-16 02:45:22 +00:00

bench: real black_box barrier + three-signal growth-curve gate

will.anderson referenced this issue from a commit

2026-08-16 02:58:55 +00:00

bench: arm the Phase 4 gate -- proven to pass clean AND fire on a quadratic

will.anderson referenced this pull request