Counting the coin flips

This site counts three things. Comparisons, because that is what a textbook analysis counts and it is exact. Cache misses, because comparisons are not time and locality decides the constant. Slots, because an in-place sort and an out-of-place one with identical comparison counts are different algorithms and nothing else can say so.

Each of those counters was added because a claim could not otherwise be checked. This essay adds a fourth for the same reason: a randomised algorithm consumes randomness, the amount differs by orders of magnitude between algorithms that produce identical answers, and none of the other three counters can see any of it.

The instrument #

Coins is to randomness what Counted is to comparisons. Nothing in the randomness library can flip a coin without the flip being charged, which turns “how much randomness does this need” from an estimate into an integer.

Three decisions in the cost model are worth stating, because a cost model is a choice and every figure that reports these numbers prints which one was used.

The unit is a bit, not a call. An algorithm that draws one 32-bit uniform and one that draws thirty-two single bits have made a different number of calls and consumed the same randomness. Counting calls would make Algorithm L look thirty-two times better than it is, because its draws are wide. Both counts are kept — draws and bits — and the essays quote bits.

Rejections are charged. Drawing a uniform integer below a $k$ that is not a power of two takes $\lceil\log_2 k\rceil$ bits and starts again if the value is out of range, and the discarded attempts count. Two hundred draws below 3 cost 2.53 bits each, against the 1.58 bits of information such a draw carries. The charged number is what a generator actually delivers; the information-theoretic number is a lower bound on what a cleverer procedure could spend, and the gap between them is where a good deal of derandomisation lives.

The generator is the site’s, seeded. Every bit comes from the same xorshift32 that produces the site’s random inputs, from a stated seed, because a caption may only quote a number the reader can reproduce. What that costs is an essay of its own.

What each algorithm spends #

Five consumers, swept from $n = 256$ to $n = 32{,}768$ and fitted against the site’s candidate classes exactly as a comparison count would be:

The first four are ordinary fits and the fifth is not, and both halves of that are worth going through.

The treap’s spread is 1.000, which is what an exact quantity looks like. Every key draws one 32-bit priority and nothing else draws anything, so the count is $32n$ with no variance whatever. It is the cleanest fit on the site and it is cleanest because there is nothing random about how much randomness it uses.

The skip list’s constant is 2.03 and its expected value is exactly 2. One flip decides whether to promote; on a heads it flips again; the expected number of flips before a tails is two. The 0.03 is the truncation at the maximum level and finite-sample wobble, and the fact that a measured constant lands within 1.5% of a hand-derived one is the sort of agreement that makes the counter trustworthy for the cases where no hand derivation is available.

Algorithm R’s $n\log n$ is a class nobody would expect from the description. “Take a sample of sixteen” sounds like a constant amount of work per item and a constant amount of randomness in total. It is one draw per item, each costing about $\log_2 i$ bits, and the total grows faster than the stream does. The essay on reservoir sampling is about what that costs and what removes it.

The class the site could not grant #

Randomised selection is the interesting row and it is interesting because the answer is no.

Quickselect with a random pivot makes about $2\log_2 n$ pivot draws over its run, each drawn from a range that shrinks geometrically, so each costs about $\log_2$ of the current range. The total is quadratic in the logarithm. Measured over thirty seeds at each of eight sizes, bits divided by $(\log_2 n)^2$ is flat to 1.136, with a constant of 1.131.

The site’s lib/fit.js offers six candidate classes — constant, $\log n$, $n$, $n\log n$, $n^{1.5}$, $n^2$ — and $(\log n)^2$ is not among them. The flattest candidate it does offer is $\log n$ at a spread of 1.98, which is above the 1.6 tolerance and is refused.

So the class is withdrawn, and that is a deliberate choice rather than a gap. Adding $(\log n)^2$ to CLASSES would grant it — and would also change what bestClass returns for every other figure on the site, in order to describe one line on one of them. The blast radius is a poor trade for a naming convenience, so the measurement is reported by its own assertion, assertSelectionRandomnessIsLogSquared, which requires two things at once: that the ratio against $(\log_2 n)^2$ is flat, and that the nearest offered class is refused. Both halves are needed, because a quantity growing slowly enough looks constant over any range short enough.

This is the third claim this site has withdrawn for a reason other than being wrong. Bubble sort on nearly sorted input fits neither $n$ nor $n^2$; the hybrid sort’s fitted class changes when the measurement range is extended. This one is the first withdrawn because the vocabulary is too small rather than because the data is ambiguous, and it is recorded as such.

Where the four counters agree and where they do not #

The site now measures four quantities, and the useful thing about having four is the disagreements. Set the randomised structures side by side at $n = 4{,}096$:

No column ranks them the same way. The quarter-coin skip list beats the half-coin one on space, ties it on comparisons and loses on randomness. The treap beats both on comparisons per lookup — a mean depth of 13 against about 23 comparisons — and loses on randomness by a factor of sixteen.

That is the two-counts theme with a fourth column added, and each addition has done the same thing: taken a set of algorithms that a single number ranked cleanly and revealed that the ranking was an artefact of only counting one thing. Comparisons ranked the sorts; cache misses reordered them; slots reordered them again; and randomness reorders the structures in this phase. There is no total order over algorithms, and each counter added is another demonstration of it.

One run is an anecdote, here more than anywhere #

Randomised selection’s row also produced the phase’s clearest lesson about how to measure this quantity, and it is the opposite of the intuition.

A skip list’s bit count at $n = 4{,}096$ is smooth in $n$, because it is a sum of 4,096 independent draws and sums concentrate. Randomised selection’s is a sum of about twenty-four draws, and twenty-four is not many: a single run’s total wanders by tens of per cent from seed to seed. Fitted from one seed per size, the counts refuse every candidate class including $(\log n)^2$. Fitted from thirty seeds per size, they are flat to 1.14.

So the number of trials needed to measure a randomness consumption is set by how many draws the algorithm makes, not by how large its input is. That is a slightly surprising rule and it is a useful one: the algorithms that need the most careful measurement here are the ones that use the least randomness.

The instrument checks itself #

A counter nobody has verified is a counter that reports whatever it reports, and this one is checked in two directions before any figure uses it.

Against a case counted by hand. One bit(), one seven-bit draw, one 32-bit uniform and one draw below 4 is 1 + 7 + 32 + 2 = 42 bits, and the counter must say 42. It must also say two 32-bit words were pulled, because 42 bits needs two, and two draws requested. That is the same check assertCountsAreExact makes on the comparison counters, for the same reason: a counter off by a constant leaves every curve the right shape with the wrong constant, and the constant is what this site reports.

Against the property the draws are supposed to have. Sixty thousand draws below 3 must land within 3% of a third each, and they measure 0.82% off. Without that check a drift towards the cheap word() % k shortcut would go unnoticed — it is faster, it is not uniform, and every reservoir figure would keep drawing while the sampler quietly stopped being correct.

Both checks are in the site’s gate, and both would fail the build rather than the figure. That matters because a broken bit counter is invisible in the output: the lines still rise, the fits still fit, and the constants are simply wrong.

Three more readings, because a fitted class is a claim about a range and the range is a choice.

Shortening the sweep is the sharper test of a fitted class, because a shorter range gives the fit less to work with and a class that only appears over four doublings is not a class.

And dropping the skip list rescales the plate, which matters here because the refusal below is about a curve that is nearly flat beside one that is not.

What the fourth counter is for #

Having a number is not self-justifying, and it is worth being specific about what having this one has changed.

It makes two identical algorithms distinguishable. Algorithm R and Algorithm L return samples from the same distribution, hold the same $k$ slots, make the same single pass, and spend 1,356,399 and 9,380 bits respectively at $n = 65{,}536$. Without a randomness counter the second algorithm has no reason to exist. This is the direct parallel of the two merge sorts in the space phase — identical in every counter the site had, different by a factor of $\log n$ in the one it added.

It makes derandomisation a measurable trade. Median-of-medians selection spends zero bits, which is the point of it, and pays 2.54 times the comparisons of the randomised version. “Zero” is a measurement here rather than an observation about the source code, and it is what makes the exchange rate — comparisons per bit saved — a number.

It gives derandomisation results a scale to be read against. There is a whole body of theory about removing randomness from algorithms — pseudorandom generators that stretch a short seed, the method of conditional expectations, $k$-wise independent families that need only $k\log n$ bits instead of $n$. Every one of those results is a statement about a bit count, and without a bit count they are statements about a quantity the reader has no feel for. Knowing that a treap spends 32 bits per key and a skip list spends 2 makes “this construction uses $O(\log n)$ random bits” a claim with a comparison behind it.

And it puts a price on the parameter choices. A skip list at $p = \tfrac14$ is cheaper to search and holds a third fewer pointers than one at $p = \tfrac12$, and it costs 2.67 bits per key against 2.00. Without the counter that setting is simply better; with it, the improvement has a price and the price is on an axis the other counters do not have.

The floor under a bit count #

The other three counters on this site each have a floor beneath them — comparisons have $\log_2 n!$, and the space and miss counts have their own bounds — and it turns out this one does too, computable from the same kind of counting argument and available for three of the five consumers above.

The question is: how much randomness does the algorithm’s output distribution actually require? An algorithm that produces one of $N$ equally likely structures must consume at least $\log_2 N$ bits on average, because a procedure spending fewer bits has fewer than $N$ distinguishable executions and cannot reach every structure. That is the same pigeonhole the memory-state floors use, applied to executions rather than to states.

The skip list. Its randomness is one geometric draw per key: the level, promoted with probability a half. The entropy of a geometric distribution at $p = \tfrac12$ is exactly 2 bits, so a skip list cannot be built with less than 2 bits per key, and it measures 2.03. The structure is at its floor, to within the truncation at the top level, and the two-flips-per-key implementation is not merely convenient — it is optimal, because the flips are exactly the information the structure needs and none of them is discarded.

The treap. Its priorities are used for one thing: the relative order of the keys, which is what decides the shape. There are $n!$ orders, so the floor is $\log_2 n!$ bits in total, or about $\log_2 n - 1.44$ per key — 13.6 bits per key at $n = 32{,}768$ against the measured 32.00. The treap spends 2.35 times what its own output distribution requires, and the excess is the difference between drawing a number wide enough that ties are unlikely and drawing a permutation.

That reframes the skip-list-against-treap comparison in the table above. The factor of sixteen between 2.03 and 32.00 is not a fact about which structure is more random; it is two facts. The treap genuinely needs more randomness than the skip list — 13.6 bits per key against 2 — because it is choosing among $n!$ shapes where the skip list is choosing $n$ independent small levels. And on top of that it is wasting a further factor of 2.35 by drawing a fixed-width priority.

The waste is removable in principle and awkward in practice, which is worth stating because it is the usual shape of such things. Drawing priorities as a random permutation would hit the floor and would require knowing $n$ in advance, which a structure built by insertion does not. Drawing them lazily, refining a priority only when a comparison needs more bits, would also hit it and would make every comparison a variable-length operation. The 32-bit draw is the price of not having to do either, and having the floor is what turns that from a design detail into a measured overhead.

And the reservoir samplers are the case where the floor is most damning. A sample of $k$ items from a stream of $n$ is one of $\binom{n}{k}$ subsets, so the floor is $\log_2\binom{n}{k}$ bits — at $n = 65{,}536$ and $k = 16$ that is about 220 bits. Algorithm R spends 1,356,399 and Algorithm L spends 9,380. The better algorithm is a factor of 145 over the floor and the worse one a factor of six thousand, which says that the gap between them is real and that neither is anywhere near what the problem requires.

None of the three floors is achieved by anything anybody would deploy, and that is the ordinary situation for a floor. What having them changes is the reading of the table: a bit count is now a distance from a bound rather than a bare number, and 2.03 against a floor of 2 is a different kind of fact from 32.00 against a floor of 13.6.

What the counter does not measure #

Three limits, all of which are the same limit seen from different angles: a bit count is not a cost.

It is not time. Pulling thirty-two bits from a xorshift generator costs a handful of cycles; pulling them from a cryptographic generator costs considerably more; pulling them from /dev/random may block. The bit count is machine-independent in exactly the way the comparison count is, and it is not a duration for exactly the same reason.

It is not entropy. The site’s generator is a 32-bit xorshift with a 32-bit state, so the total entropy available from one seed is 32 bits regardless of how many bits are drawn from it. A count of 1.36 million bits is a count of generator output, not of unpredictability, and conflating the two is the error the whole of the seeding essay is about.

And it is not a lower bound. The charged count is what the procedure spent, including rejections. A cleverer implementation of the same algorithm — buffering leftover bits across draws, or using an arithmetic-coding style extractor — spends less for the same distribution. So a comparison between two algorithms by bit count is only fair when both are implemented against the same drawing primitives, which they are here, and it is stated because it would not be true of numbers taken from two different libraries.

That last limit is the one worth carrying, because it is the honest version of what the counter is: a count of what this implementation asked the generator for, under a stated cost model, comparable across the algorithms in this library and nowhere else. Which is exactly what a comparison count is, and exactly what a slot count is, and is why all four sit on the same axes.