A cryptography library had a bottleneck no test could see: encrypting half a
megabyte took fifty seconds. Every test passed. They had been passing for months.
The cause is a trap that keeps recurring: a correct, well-documented
optimisation that fixes the constant and not the order — and whose comment,
precisely because it is well written, convinces the reader the problem is already
solved.
What the code did
Quipu renders encrypted data as a sequence of symbols. To do
that it converts the whole message into a single huge integer and repeatedly
divides it to extract digits, the same way you would convert a base-10 number to
base 2 by hand.
The code did not divide one digit at a time. It carried a sensible optimisation:
divide by the largest power of the base that fits in a machine word, extracting
nine digits per pass instead of one. The comment explaining it opened by saying
that doing it one at a time would be quadratic, and then described the
improvement.
All true. And the result was still quadratic: extracting nine digits per pass
divides the work by nine; it does not change how the work grows.
That sentence — "doing it this way would be quadratic" — reads in the past tense,
as if it described the previous state. It described the current one.
The measurement, which is the only thing that says so
| Size | Time | Factor per doubling |
|---|---|---|
| 64 KiB | 0.79 s | — |
| 128 KiB | 3.16 s | ×4.0 |
| 256 KiB | 12.6 s | ×4.0 |
| 512 KiB | 50.7 s | ×4.0 |
Exactly four, three times running. That is textbook quadratic: every time the
input doubles, the time quadruples. Extrapolating, ten megabytes would have cost
about five and a half hours.
And here is the point: a correctness test sees none of this. A slow algorithm
produces exactly the same bytes as a fast one. The suite stayed green, and would
have stayed green forever.
The fix is two hundred years old
Nothing had to be invented. Divide-and-conquer radix conversion is a classical
algorithm: instead of peeling digits off one end, you split the number in half —
dividing by a power with half as many digits — and repeat on each half. The tree
has as many levels as the size has doublings, and each level costs one big
multiplication instead of thousands of divisions.
| Size | Before | After | |
|---|---|---|---|
| 512 KiB | 50,698 ms | 457 ms | 111× |
| 10 MiB | ~5.6 h | 41.4 s | ~490× |
The factor per doubling dropped from 4.00 to 2.82, which is not an arbitrary
number either: it is what you get from combining the tree with fast big-integer
multiplication.
What to check BEFORE writing it
And this is what separates an improvement from one that makes things worse:
divide-and-conquer only pays off if your big-integer library's division is
sub-quadratic.
If division is schoolbook, splitting in half and recursing is still quadratic —
and with a worse constant than the loop you set out to replace. You would have
written an algorithm that is more elegant, harder to read, and slower.
The library in use turned out to ship Burnikel-Ziegler recursive division, so it
pays off. That gets checked before the first line is written, not after measuring
a disappointing result.
How to avoid this in the next repository
The question that saves the five and a half hours is not "is this optimised?" but
"did the ORDER change, or only the constant?" — and it is answered with two
sizes and one division, not by reading the code:
- if doubling the input doubles the time, it is linear;
- if it quadruples, it is quadratic;
- if it goes up by ~2.8, there is a tree and a fast multiplication behind it.
It costs a minute. And that measurement deserves to become a test that fails if
someone reintroduces a loop: a cost regression is invisible to a correctness
suite, because the code still gives the right answer — it just takes five hours.
Top comments (0)