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
2026-09-26· Case opened2026-11-03· PR opened