[ailang-parse] String primitives: charAt is O(i), find has no offset — per-character scanners are quadratic or 5x too slow

[sunholo-voight-kampff]

Writing a markdown inline-formatting scanner in AILANG took three attempts to
get to acceptable speed, and the two failures were both caused by string
primitives whose cost is not what their shape suggests. Numbers below are from
two minimal repros you can run directly.

1. charAt(s, i) is O(i), so any index-based scan is quadratic

This is the big one. charAt(s, i) reads like array indexing and costs a walk
from the start of the string.

module bench/charperf

import std/string (length, charAt, charCode, repeat, foldChars)
import std/clock (now)
import std/io (println)

pure func byIndex(s: string, i: int, acc: int) -> int =
  if i >= length(s) then acc else byIndex(s, i + 1, acc + charCode(charAt(s, i)))

pure func byFold(s: string) -> int =
  foldChars(\acc c. acc + charCode(c), 0, s)

export func main() -> () ! {IO, Clock} {
  let sizes = [2000, 4000, 8000, 16000];
  runAll(sizes)
}

func runAll(sizes: [int]) -> () ! {IO, Clock} =
  match sizes {
    [] => (),
    n :: rest => {
      let s = repeat("abcdefghij", n / 10);
      let t0 = now();
      let a = byIndex(s, 0, 0);
      let t1 = now();
      let b = byFold(s);
      let t2 = now();
      println("n=${show(n)} index=${show(t1 - t0)}ms fold=${show(t2 - t1)}ms (${show(a)}/${show(b)})");
      runAll(rest)
    }
  }

n=2000 index=32ms fold=6ms
n=4000 index=70ms fold=12ms
n=8000 index=192ms fold=21ms
n=16000 index=593ms fold=48ms

Doubling the length costs 2.2x, then 2.7x, then 3.1x — and per-access cost
itself climbs from 16us to 37us. foldChars over the same data is flat at ~3us
per character, so the fold is linear and the indexing is not.

Ask: O(1) character access. Either a rune-indexed string representation, or an
explicit conversion to an array of characters that indexes in constant time. If
neither is cheap, the docs for charAt should say O(n) in bold — it currently
reads like the obvious way to write a scanner, and it is a trap.

2. find() has no offset, which forces an O(n) copy per search

find(string, string) -> int searches from 0 only. "Find the next X after
position i" therefore has to be written

find(substring(s, i, length(s)), needle) + i

and that substring copies the tail on every single search. This is what made
the first version of my scanner quadratic even where I avoided charAt.

Ask: find(s, needle, from), plus lastIndexOf(s, needle) and
indexOfAny(s, [needles]). std/string already has splitAny, so indexOfAny is
the natural companion.

3. foldChars is linear, but consing into the accumulator dominates

Record WIDTH turns out to be cheap, which was the opposite of what I assumed.
Building a list one element per character is what costs.

module bench/recperf

import std/string (charCode, repeat, foldChars)
import std/clock (now)
import std/io (println)

type S1 = { a: int }
type S9 = { a: int, b: int, c: string, d: bool, e: [string],
            f: string, g: int, h: bool, i: [string] }

pure func foldInt(s: string) -> int =
  foldChars(\acc c. acc + charCode(c), 0, s)

pure func foldRec1(s: string) -> S1 =
  foldChars(\acc c. { acc | a: acc.a + charCode(c) }, { a: 0 }, s)

pure func foldRec9(s: string) -> S9 =
  foldChars(\acc c. { acc | a: acc.a + charCode(c) },
            { a: 0, b: 0, c: "", d: false, e: [], f: "", g: 0, h: false, i: [] }, s)

pure func foldRec9Cons(s: string) -> S9 =
  foldChars(\acc c. { acc | a: acc.a + charCode(c), e: c :: acc.e },
            { a: 0, b: 0, c: "", d: false, e: [], f: "", g: 0, h: false, i: [] }, s)

export func main() -> () ! {IO, Clock} {
  let s = repeat("abcdefghij", 2000);
  let t0 = now(); let r0 = foldInt(s);
  let t1 = now(); let r1 = foldRec1(s);
  let t2 = now(); let r2 = foldRec9(s);
  let t3 = now(); let r3 = foldRec9Cons(s);
  let t4 = now();
  println("20k chars: int=${show(t1 - t0)}ms rec1=${show(t2 - t1)}ms rec9=${show(t3 - t2)}ms rec9+cons=${show(t4 - t3)}ms");
  println("(${show(r0)}/${show(r1.a)}/${show(r2.a)}/${show(r3.a)})")
}

20k chars: int=56ms rec1=65ms rec9=80ms rec9+cons=332ms

A 9-field record accumulator costs 43% more than a bare int — fine. Adding one
cons per character costs 4x — 17us per character. A character-level tokenizer
in interpreted AILANG is therefore ~5x the cost of the fold that drives it,
almost entirely in list allocation.

4. What this cost in practice

Same feature, same 41KB input document, three implementations:

no inline parsing at all (before) 2.0s
index-based scanner (charAt/substring) 16.9s
per-character foldChars state machine 15.0s
token-peeling with split (shipped) 4.2s

The shipped version splits on one marker token at a time so allocation scales
with the number of segments rather than the number of characters, and the hot
loop stays inside native Go. That is a 4x win purely from moving work out of
interpreted per-character code — which suggests the general guidance for AILANG
today is "never touch a string one character at a time", and that is a sharp
edge worth blunting.

Asks, in the order that would help most

1. O(1) character access (rune-indexed strings, or a char-array conversion).
2. find(s, needle, from), lastIndexOf, indexOfAny.
3. A native scanning primitive — spanWhile(s, pred) -> (prefix, rest), or a
   tokenize/splitMany — so hand-written lexers can stay in native code.
4. Cheaper list cons in hot folds (or a builder/accumulator type).
5. A lint: flag charAt(s, i) inside a function that recurses on i. That single
   diagnostic would have saved me an hour today, and it is a purely syntactic
   pattern.

Related and already known on our side: accumulating strings with
"${acc}${x}" in a fold is quadratic, and so is concat(xs, [x]). A rope or
builder representation would remove the first; we work around both by hand.

Context: docparse/services/markdown_parser.ail in sunholo/ailang-parse, shipped
in v0.33.0. Happy to run any diagnostic build against these repros.

Environment: AILANG v0.33.0-41-g65f287107-dirty, macOS arm64 (Darwin 23.2.0).

---

Reported by: ailang-parse via ailang messages