A 50,000-row page and two quadratic surprises

Deep technical August 2026 · from the RingScript project

We had benchmarks. We had a soak suite running forty thousand evaluations, a fuzzer with thousands of hostile inputs, and ~850 programs verified byte-for-byte against native Ring. Then we drove a real application the way a user drives it — and found two O(n²) behaviours in the VM's list machinery within minutes. This is the story of both, with the diagnosis, the fixes, and why they were invisible until then.

The setup

The application is the savings-circle register: records live inside the resident Ring VM, and each user interaction — filter, sort, total, page — is one Ring call. Every call is timed against human budgets (16 ms for instant, 100 ms for responsive), and every answer is verified against an independent computation. At 20,000 rows the first numbers came back… mixed. Sorting a column: 217 ms. And after sorting, recomputing the totals — a plain linear pass — took 377 ms, and the leaderboard over a second. At 50,000 rows the leaderboard took 19.8 s.

A linear pass that gets four times slower when the data doubles is not linear. Something underneath was quadratic.

Surprise one: sort(list, nColumn)

Isolating the sort was easy — sort the same 20,000 values twice, once as a flat list, once as [key, index] pairs:

The ratio doubles when the data doubles — the signature of O(n²) hiding inside an O(n log n) operation. The algorithm itself was fine: Ring extracts the keys, quicksorts an index array, then rebuilds the list by reading it at idx[i] — in sorted order. Which is to say: in random order. And random access is where surprise two was waiting.

Surprise two: the cursor that walks

Ring's lists are linked lists with a clever optimisation: a cursor that remembers the last position. Ask for item k and then k+1, and the second access is O(1) — which makes ordinary sequential loops fast, and is why none of our benchmarks had ever noticed anything. But ask for items in random order and the cursor cannot help; the access falls through to a linear walk from whichever end is closer, and nothing remembers the work.

Now consider what every data page on earth does: sort the table, then total the visible rows. The sorted view is a permuted index into the data. Every read walks. One aggregate pass over 50,000 rows became 50,000 walks — 19.8 seconds for work that should take milliseconds. And no benchmark had ever caught it, because benchmarks iterate forward.

The fixes

Ring already has the right tool: an items array — pItemsArray — a flat array of item pointers that makes any access O(1). It just was not being built on these paths. Two small, surgical patches:

In the sort (ring_list_sortnum_gc / sortstr_gc in rlist.c): generate the items array before the rebuild, so reading the list in sorted order stops walking. Column sort at 20,000 rows: 257 ms → 16 ms.

In the accessor itself (ring_list_getitem_gc): when a random access falls past the cursor into the walk — and the list is big enough for it to matter — build the items array once and answer from it.

We proposed both to Ring. The first was merged. The second was rejected, and the rejection was right.

Being wrong in public, and measuring it

Mahmoud Fayed's objection was that building the array inside the accessor is not free: a program that mixes adding and reading would create and destroy it over and over, and you cannot measure one access pattern and generalise from it.

So we measured it, with two runtimes identical but for that one change. He was right:

A large win on read-heavy work, and 1.7–2.3× slower when adds and reads interleave — because any structural change frees the array and the next random read rebuilds it whole. The patch turned an occasional O(n) rebuild into a per-iteration one.

And the answer was already in the language. Ring ships ringvm_genarray(aList): the same items array, built when you say so. The register app now calls it after loading and after adding, and never inside a read:

func LedgerIndex
	if nRows > 64 and lIndexed = 0
		ringvm_genarray(aRowAmount)
		# ...one call per column
	ok
	lIndexed = 1

Marked stale on a write, rebuilt at most once before the next read that needs it. Rebuilding on every add instead costs 824 µs a row on a 20,000-row ledger — worse than the problem it solves. That is the whole of Mahmoud's objection, reproduced in our own application.

RingScript now carries no accessor patch at all, and the numbers below are unchanged: measured against a build that still had it, the two agree to within noise at 20,000 and 50,000 rows. One fewer patch to carry across a Ring upgrade, and the language author's own mechanism instead of a private one.

Why it was safe to touch

ring_list_getitem is the most-used accessor in the entire VM — everything reads lists. The safety net this project maintains for exactly that reason is Ring's own sample corpus plus every runnable example in its documentation — about 850 programs — run through the modified VM and compared byte-for-byte against native ring.exe, alongside the soak, the fuzzer, and the permanent gates. All of it green.

And it told us nothing about the regression. Not one of those 850 programs interleaves adds and reads on a list large enough to matter, so the corpus was as green with the bad patch as without it. It proved the VM still computed the right answers; it could not prove the VM was still fast, because that was never what it measured.

That is the correction worth carrying away. A differential oracle is a correctness instrument. Against a performance change it is silent, and silence reads like approval. What catches a regression is an A/B on two builds differing in exactly one thing — including the access pattern the change would hurt, not only the one it helps.

The lesson we keep relearning

Both behaviours were invisible to every benchmark we had, because benchmarks iterate forward and real pages read sideways. The application found in minutes what the suites had missed for weeks — which is why the register app is now part of how this project tests itself, and why the next performance question will start the same way: build the real thing, drive it like a user, and believe what it shows you.

The full trail, for the source-inclined: VENDOR_PATCHES.md (patch 7, and 8 for why it was withdrawn), the app write-up, and the oracle that guards it all.