Builtin call with a single list argument is O(len(list)) — the direct-borrow heuristic scans the user's list, making `len of xs` loops quadratic

[InauguralPhysicist]

Summary

Calling any builtin with a single list argument costs O(len(list)) per call, even for O(1) builtins like len. The cost is not in the builtin — it's the post-call direct-borrow heuristic, which scans the argument list's top-level items comparing pointers against the result. For multi-arg calls the scanned list is the freshly packed [a, b] (tiny); for argc==1 the user's own list is the arg, so the scan walks all of it.

Net effect: the idiomatic loop

loop while i < (len of xs):    # len re-evaluated per iteration
    xs[i] *= g
    i += 1

is quadratic in len(xs) — ~520x slower than the same loop with the length hoisted, at 88k elements. Verified at v0.29.0, HEAD 82ab2ae, release build.

Reproduction

define scale_a(xs, g) as:          # len in condition
    unobserved:
        i is 0
        loop while i < (len of xs):
            xs[i] *= g
            i += 1

define scale_c(xs, g) as:          # len hoisted
    n is len of xs
    unobserved:
        i is 0
        loop while i < n:
            xs[i] *= g
            i += 1

88,200-element list: scale_a 5,033 ms, scale_c 9.7 ms.

Scaling (scale_a): N=11025 → 81 ms, N=22050 → 320 ms, N=44100 → 1,261 ms — clean 4x per doubling, i.e. O(N²).

Discriminating cases (44,100 calls each, in a loop body):

call	time	note
len of a (list arg)	1,270 ms	O(len) per call
abs of i (number arg)	6 ms	fine
first of a (USER fn, list arg)	6 ms	fine — user-fn param binding is by reference

Unaffected by unobserved:, JIT thresholds (reproduces with EIGS_JIT_*_THRESHOLD=999999999), and reads-vs-writes in the body — it is purely the builtin call path.

Root cause

src/vm.c CASE(CALL), VAL_BUILTIN branch (and its two mirrors): after the builtin returns, the direct-borrow heuristic runs

if (arg && arg->type == VAL_LIST) {
    int n = arg->data.list.count;
    Value **items = arg->data.list.items;
    for (int i = 0; i < n; i++) {
        if (items[i] == result) { val_incref(result); break; }
    }
}

For argc > 1, arg is the VM-packed argument list (2–3 items) and the scan is what the comment intends — catching append/dict_set/coalesce returning items[0]. For argc == 1 the raw value is passed through (arg = STK_AS_VAL(...)), so when that value is a list, the scan walks the entire user list on every call. All three sites share the pattern: src/vm.c:1868 (jit_helper_call), src/vm.c:3173 (CASE(CALL)), src/vm.c:5041.

Suggested fix

Track whether arg is the VM-packed temp (a packed flag set in the argc > 1 branch) and run the borrow scan only when packed. In the argc==1 path the argument is a live user value with its own refcount; a builtin returning a direct child of a bare list argument would be a borrow from a value that outlives the call anyway — and if any such builtin exists, capping the scan or increfing unconditionally-and-correctly for that builtin is still cheaper than O(n) on every len.

Consumer impact (InauguralSystems/DeslanStudios)

Audio code hits this constantly: every loop while i < (len of chan) over a 44.1 kHz sample buffer is quadratic. Profile before/after hoisting lengths in the DAW port's buffer helpers: ab_scale on 1 s of stereo audio 2,511 ms → ~10 ms; a full 1-second mixer render 9.2 s → (mostly this). The workaround is mechanical (hoist len out of loop conditions), but the failure mode is silent and the idiom is what SYNTAX.md examples teach.

Environment

• EigenScript 0.29.0, HEAD 82ab2ae, x86-64 Linux, release build (make).