The loops that cost more than they read

This is the story of a benchmark that looked impossible, and of what fell out when we refused to accept it. Three ordinary-looking Ring loop patterns turned out to cost far more than they read — one of them is quadratic while looking linear. Every claim below is a measurement you can re-run, every fix is one line, and the Ring++ checker now finds all of them in your code for you.

Where it started: a number that made no sense

While testing Ring on an Android phone, one benchmark — reading a string one character at a time — came out 311 times slower than Lua doing exactly the same work, on the same phone, in the same minute. Interpreters differ, but not by that much. A gap that size is not a slow language; it is a hidden mechanism.

A profiler run on the phone itself settled it: the Ring interpreter was executing for less than half a percent of the time. Something else was eating the machine. Two findings later, that benchmark runs 47× faster — and neither finding changed a single line of Ring itself. The first was about how our Android build was put together, and that story is told elsewhere. The second is about Ring code — your code, possibly — and that is this post.

The first one: the loop header that copies your string

Here is the loop every programmer has written. Read it and estimate its cost:

for i = 1 to len(cText)
    # ... look at cText[i] ...
next

It reads as: measure the string once, then walk it. What Ring actually does is different in one crucial way: the header is re-evaluated on every single pass — and in Ring, a string handed to a function is copied first. So every iteration copies the whole string, just to ask its length again. The loop is O(n²) wearing O(n) clothing.

The measurement — same body, 20,000 passes, only the string size changes:

The string grew 100×; the loop got 350× slower. That is the signature of a hidden full copy per pass. And the fix is one line:

nLen = len(cText)      # measure ONCE
for i = 1 to nLen
    # ... exactly the same body ...
next

Three neighbouring shapes were checked and are fine — we measured them rather than assuming: for c in cText walks without copying, for i = 1 to len(aList) is cheap because lists are passed by reference, and cText[i] itself is constant-time in every context we tried. The trap is strings, in loop headers, and nowhere else.

One confession makes this credible: our own benchmark had the trap. The "byte scan" we had been publishing was silently measuring 6.4 GB of header copies and calling it slow indexing. Hoisting one variable took it from 123 to 13 ms on the desktop and from 518 to 77 ms on the phone — same answer, byte-identical, asserted before any number was printed. If it hid in our benchmark, it is hiding in real code: a sweep of a large Ring codebase found 675 occurrences across 6,020 files.

The second: the binary search that was never O(log n)

Second impossible number, same campaign: binary search over a sorted list, 105× behind Lua. The arithmetic of the loop accounted for a quarter of the measured time. The rest had no explanation — until we tested how Ring reaches a list element.

Ring keeps a cursor at the position you touched last. Reading the same position again is instant, and reading the next one is a single step — which is why ordinary sequential loops are fine. But a read far from the cursor walks the distance. The measurement — 100,000 reads, only the access pattern changes:

A fixed index is flat at any size. Jumping reads scale with the list. Binary search's very first probe jumps half the list — so on a Ring list, the algorithm every textbook calls O(log n) is actually O(n) per lookup.

This is exactly the situation Ring++'s RppIndexed exists for. It asks Ring — using a facility Ring itself provides — to build a direct index over the list, making any jump constant-time. Same searches, same results, asserted equal:

The rule of thumb that survives: loops that walk a list in order are fine. Algorithms whose reads jump around — binary search, heaps, anything probing — want RppIndexed around them, and the list must not change size while it is applied.

The third, and the smallest: for-in

This one had been a suspicion here long before anyone measured it, and the measurement agrees: for x in aList costs about 2× the same loop written with an index — on lists and strings, reading and writing alike. Two times nanoseconds is nothing, so this only matters in genuinely hot loops. But one thing about for-in matters everywhere: its loop variable is live. Write x = 7 inside for x in aL and you have just rewritten the list. Useful when intended; startling when not.

And now the checker finds all of it for you

Every one of these patterns is visible in source code before the program ever runs — which makes them exactly the static analyzer's job. As of today:

On its first run over a large real codebase, the advice pass found 1,009 places where a measured idiom was faster, alongside 675 quadratic headers. None of them is a bug. All of them are minutes to fix, now that something points at them.

What this whole episode teaches

The 311× and 105× numbers were never "Ring is slow". They were three specific mechanisms — a build choice, a loop header, a data-structure access pattern — stacked on top of a perfectly ordinary interpreter. Pulled apart with a profiler and a set of scaling tests, Ring lands within a normal distance of Lua, and every remaining gap has a name, a number, and either a fix or an open question honestly labelled as one.

The measurements, the refuted hypotheses and the raw tables live in FINDINGS.md (F-41 through F-43), and the phone campaign that started it all is reproducible with one command from ANDROID.md.