Array loops repeatedly rescan unconsumed elements

perfloop/grol · Inefficient Algorithm

https://perfloop.ai/t/oss/case_7rrzcj3ap0

Verdict

VERIFIED · settled 2026-11-03 · pull request opened as grol-io/grol#556

What happened: The paired measurements met the required improvement.

Hypothesis

Array iteration rebuilds the unconsumed suffix before each loop body. On a longer array this scans elements the loop has already prepared for later visits. A profile of the checked-in help script shows a small attributable CPU share; a net saving has not been measured.

At revision b9b1d44, `examples/functions_list.gr` iterates `info.gofuncs` with `for name := info.gofuncs`. `Environment.BaseInfo` builds that array from registered extension names. `go run . -no-auto -quiet -c 'len(info.gofuncs)'` returned 77 with the CLI's extensions. `repl.EvalString` reaches `evalForSpecialForms`' ARRAY case, then `evalForList`. That loop calls `Rest` before each body. For arrays, `Rest` passes each remaining suffix to `NewArray`, whose `Value` loop visits every element. A complete 77-element iteration makes 76 such `NewArray` calls and 2,926 suffix-element visits; an error, break, or return can stop it earlier. Continue still advances the list.

A CPU profile of repeated successful `repl.EvalString` evaluations of the unmodified script with CLI-equivalent extensions sampled 5.86 CPU-seconds. The BigArray branch of `object.Rest` accumulated 50 ms, about 0.85% of total samples and about 1.5% of the 3.25 CPU-seconds on the `repl.EvalString` stack. These are samples across benchmark repetitions, not per-call latency or production frequency. Even removing that entire branch gives only an optimistic roughly 1.5% sampled evaluator-CPU ceiling for this script; cursor overhead could offset it. `NewArray` intentionally dereferences references. A mutation check through `go run . -no-auto -quiet -c` returned the next value as 1 with nine elements and 42 with ten, showing the snapshot-to-alias boundary a cursor must preserve.

The required Case proof is an end-to-end before/after benchmark of the unmodified `examples/functions_list.gr` through `repl.EvalString`, with the same extension setup and fresh state per evaluation. Verify its full output, CPU time, wall time, and allocations. Optional length samples of 8, 9, and 256 and in-body mutation controls can check the crossover and aliasing rules. No end-to-end resource saving, or different values or control-flow behavior, would reject the change.

Change to test: Use an array-specific cursor in list iteration so already-materialized arrays advance without rebuilding and dereferencing every suffix. Preserve reference snapshots, in-body mutation and aliasing across the BigArray-to-SmallArray transition, and break/continue/return behavior; retain the existing path when cursor equivalence cannot be established.

Where it lives

perfloop/grol · repl/repl.go

Evidence

Help script via EvalString · 15 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2866469 2818219 −41103 −104927 to +23051 loss ≤ 0.05 × |baseline median| PASSED
B/op 1573735 1571743 −0.1% (−1735) −3627 to −628 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 21809 21742 −0.3% (−67) −68 to −66 loss ≤ 0.05 × |baseline median| PASSED

EvalString array loop (1k elements) · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2044313 414640 −79.2% (−1620046) −1708770 to −1582255 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
cpu-ns/op 2085029 454069 −78.5% (−1637196) −2399842 to −1509995 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 99560 75677 −24% (−23884) −23897 to −23881 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
allocs/op 5062 4072 −19.6% (−990) −990 to −990 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

EvalString array loop (10k elements) · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 157990555 3672893 −97.7% (−154309299) −161132869 to −150016786 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
cpu-ns/op 152857143 4239994 −97.2% (−148540041) −210463084 to −142219310 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 895229 655295 −26.8% (−239937) −240029 to −239916 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
allocs/op 50063 40073 −20% (−9991) −9992 to −9990 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

EvalString array loop (40k elements) · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2454773379 14861390 −99.4% (−2440046450) −2520757577 to −2405566604 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
cpu-ns/op 2375000000 15877481 −99.3% (−2359122520) −3183846154 to −2305595238 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 3539120 2579190 −27.1% (−959919) −965463 to −959679 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
allocs/op 200067 160075 −20% (−39992) −39997 to −39989 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

CLI array loop (10000 elements) · 16 sample pairs

metric baseline candidate paired median change confidence range required result
wall-ns 157712199 8470668 −94.6% (−149166208) −163628886 to −146296826 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

CLI array loop (40000 elements) · 16 sample pairs

metric baseline candidate paired median change confidence range required result
wall-ns 2457948066 19897790 −99.2% (−2437450164) −2546022965 to −2383275457 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

Parsed array loop (0 elements) · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 68.21 66.21 −0.9 −6.83 to +2.68 loss ≤ 0.05 × |baseline median| PASSED
B/op 0 0 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 0 0 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

Parsed array loop (1 elements) · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 254.4 177 −30.6% (−77.8) −98.5 to −64 loss ≤ 0.05 × |baseline median| PASSED
B/op 160 16 −90% (−144) −144 to −144 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 2 1 −50% (−1) −1 to −1 loss ≤ 0.05 × |baseline median| PASSED

Parsed array loop (8 elements) · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2268 2225 −31 −248 to +56 loss ≤ 0.05 × |baseline median| PASSED
B/op 2288 2144 −6.3% (−144) −144 to −144 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 23 22 −4.3% (−1) −1 to −1 loss ≤ 0.05 × |baseline median| PASSED

Checks: 4 of 4 passed. Verification: no defect found.

Timeline