A structure made of coin flips

Every structure on this site so far has had a shape that is a function of its contents. The same keys into a binary search tree in the same order give the same tree; a different order gives a different one, which is the whole trouble with binary search trees. The data decides the shape, the shape decides the cost, and an unlucky arrival order is an unlucky structure.

A skip list breaks that link, and it breaks it completely rather than partially. Its shape is decided by a sequence of coin flips made before any key is looked at. Two builds from identical keys are two different objects. One build from sorted keys and one from shuffled keys, under the same seed, are the same object.

What the coins decide #

A skip list is a sorted linked list with express lanes over it. Level 1 is an ordinary linked list holding every key in order. Level 2 holds a subset of those keys; level 3 a subset of those; and so on. A search starts on the top lane, runs forward until the next key would overshoot, drops a level, and repeats. The express lanes let it skip over long runs of the bottom list, which is the only reason it is faster than a linked list.

The question is which keys get express lanes, and the answer is the one that makes the structure interesting: whichever ones the coins say. When a key is inserted, a coin is flipped. Heads, it is promoted to level 2 and the coin is flipped again. Heads again, level 3. The first tails stops it. A key’s height is therefore a draw from a geometric distribution and has nothing whatever to do with the key, its neighbours, or how many keys came before it.

Compare that with what a balancing scheme does. An AVL tree or a red-black tree looks at the structure — measures a height difference, detects a violated invariant, and performs work to correct it. The correction is a response to the data. A skip list has no invariant about balance, detects nothing, and corrects nothing. It flips a coin.

That sounds like it should be worse and it is not, and the reason is worth stating precisely before any measurement: balancing schemes are defending against a bad arrival order, and a skip list has removed the arrival order’s ability to matter. There is nothing left to defend against.

The shape is the coins, and it is checkable #

The claim above is easy to make rhetorically. It is also a claim about two objects being identical, which is the strongest kind of claim a measurement can settle.

Take the integers 0 to 511. Build a skip list from them in sorted order under seed 777. Shuffle them and build a second skip list from the shuffled order under the same seed 777. Then compare the two structures key by key.

They are the same. Both are eleven levels tall. Every one of the 512 keys has the identical height in both. The sequence of heights, read off in insertion order, is byte-identical, because the kth key to arrive gets the kth draw from the coin stream whatever key it happens to be. This is not an approximation or a statistical similarity; it is an equality, and assertTheShapeIsTheCoinsNotTheData in the site’s gate fails the build if it ever stops holding.

What the data does decide #

It would be wrong to conclude that the input has become irrelevant, and the measurement says exactly where it still reaches.

Building the sorted list cost 4,099 comparisons. Building the shuffled list cost 7,433 — 81% more, on the same keys, producing the same structure. The data does not decide the shape, but it decides the route taken through the shape while the shape is being assembled.

The mechanism is visible in the second counter. Building from sorted keys took 4,099 forward hops; building from shuffled keys took 3,096. Sorted insertion always walks to the far end of every lane, so every comparison it makes succeeds and becomes a hop, and the comparison count and the hop count come out exactly equal. Shuffled insertion stops in the middle more often, so it makes more comparisons that fail — a failed comparison costs a comparison and buys no progress.

This is a distinction the site has not needed before and will need repeatedly from here. There are two different things a randomised structure can be asked about:

• What does it look like? For a skip list, entirely the coins.
• What did it cost to get there? The coins and the data together.

Confusing the two is how “a skip list is not affected by insertion order” gets said, which is true of the first and false of the second by a factor of nearly two.

The eighty-one per cent is partly a convention #

The two build costs decompose exactly, and the decomposition is worth doing because it turns the gap into something a reader can decide whether to believe.

Sorted: 4,099 comparisons, 4,099 hops. Shuffled: 7,433 comparisons, 3,096 hops. Subtract, and the shuffled build makes 4,337 comparisons that bought no progress — one per level the walk dropped through after a key overshot — while the sorted build makes none at all.

That zero is the whole story. A sorted insertion’s key is always the largest so far, so no node on any lane can overshoot it; the walk descends because it has run off the end of a lane, not because it compared against something and lost. Dropping at the end of a lane costs a null check, and a null check is not a comparison.

So the 81% is not the shuffled build doing more work. It is doing fewer useful hops — 3,096 against 4,099, a quarter fewer — and paying 4,337 charges the sorted build gets for free. At 8.5 drops an insertion over a list eleven levels tall, that is very nearly one charged drop per level, which is what the mechanism predicts.

Which makes the ranking a property of the counter rather than of the structure. Charge the end-of-lane check as a comparison and the ordering reverses. A sorted insertion descends roughly ten levels, so 512 keys would add about five thousand charges, taking the sorted build past nine thousand against the shuffled build’s seven and a half. Same two objects, same coins, same 512 keys, opposite conclusion — decided by whether comparing a key against nothing counts as a comparison.

Neither convention is wrong, and this collection’s is the ordinary one: cmp is charged when two elements are compared, and a null pointer is not an element. What the decomposition shows is that the sentence building from shuffled keys costs 81% more rests on that choice, and the sentence building from sorted keys walks further — 4,099 hops against 3,096 — does not. The hop count is convention-free, and it says the sorted build is the one doing more traversal.

That is one run, two counts arriving inside a single essay’s headline number rather than between two algorithms, and it sharpens the distinction this page draws two sections up. What does the structure look like is the coins. What did it cost to get there is the coins, the data, and the accounting — three inputs where the essay names two, and the third is the one that can be changed without touching either of the others.

The practical reading survives all of it. A skip list built from ordered keys does more pointer-following than one built from shuffled keys, by a third, and that is what a machine pays — which is the opposite direction from the tree that is a list’s failure, where sorted arrival is the catastrophe rather than a mild extra cost.

The height distribution, which is a closed form #

Because the heights are coin flips and nothing else, their distribution is not something to be measured and puzzled over. It is a formula. A key reaches exactly level $\ell$ when the first $\ell - 1$ flips came up heads and the $\ell$-th came up tails, so the share of keys at level $\ell$ is

$$P(\ell) = p^{\ell-1}(1-p)$$

with $p = \tfrac12$ for a fair coin. There is no algorithm in that expression and no data. It is a prediction the structure has to meet.

At twenty thousand keys, 49.68% of them stayed on the bottom lane against a predicted 50%; 25.29% reached level 2 against 25%; 12.52% reached level 3 against 12.5%. The agreement continues down to level 8, where 0.34% is measured against a predicted 0.39%.

That the measurement matches is unsurprising. What the figure is for is the other thing it shows: the total height of the list — 20 in this build — is nowhere in that table. It is the maximum of twenty thousand geometric draws, and a maximum has no closed form and no bound. It is a random variable in its own right, and the essay after this one is about what that means for a structure people describe as $O(\log n)$.

What it costs, over many builds #

Here is where the discipline this site applies everywhere else has to be applied harder. A skip list’s cost is not a number. It is a distribution over builds, and quoting one build’s number is quoting an anecdote.

At $n = 2{,}048$, averaged over every key in the list, a lookup costs 21.67 comparisons — but that is itself an average over 200 independent builds. The individual builds range from 19.35 to 26.71, with a relative standard deviation of 5.86%. The worst of the two hundred cost 1.23 times the average.

Two things follow, and they pull in opposite directions.

The unhappy one: there is no guarantee here. A skip list can come out badly, and unlike a balanced tree it has no mechanism that would notice. Nothing in the algorithm prevents every one of 2,048 keys from landing at height 1, producing a linked list. The probability is $2^{-2048}$, which is not a number anyone needs to plan around, but it is not zero and the distinction matters for how the claim should be phrased.

The happy one, and the one that makes the structure usable: the distribution is narrow. 5.86% is tight enough that the expected cost is a real prediction about the build that was actually produced, rather than a mean over a population containing wild outliers. This is the same property that makes randomised quicksort trustworthy and the same property that averaging without a distribution throws away.

The height across those same two hundred builds ranged from 9 to 19, against $\log_2 2048 = 11$. That is a much wider spread than the search cost’s, and it is not a contradiction: the height is a maximum over 2,048 draws and the search cost is an average over 2,048 lookups, and maxima are volatile where averages are not.

What a search costs, and against what #

The standard statement is that a skip list search costs $O(\log n)$ expected, with the usual constant of about $2\log_2 n$ for a fair coin. The derivation is short and worth having, because it explains where the two comes from and the two is the part that gets dropped.

Walk the search backwards, from the key found up to the head. At each step the walk is either at a node that continues upward — probability $p$, and the walk goes up a level — or at one that does not, in which case it goes left along the current lane. Going up happens with probability $\tfrac12$, so the expected number of steps to climb one level is two, and there are $\log_2 n$ levels to climb. Hence $2\log_2 n$, and hence the fact that the constant is $1/p$ and the number of levels is $\log_{1/p} n$, which is the pair of quantities the next essay trades against each other.

Measured across two hundred builds at $n = 2{,}048$, a lookup costs 21.67 comparisons against a predicted $2\log_2 2048 = 22$. That is agreement to one and a half per cent on a constant that a bound written $O(\log n)$ discards entirely, and it is agreement of the kind this site treats as the point rather than as a footnote: the formula is not being quoted, it is being held against a count.

One caveat belongs with that number and is easy to miss. The comparison count is not the cost. A skip list search follows pointers between nodes that were allocated at different times and sit wherever the allocator put them, so it is a pointer chase in the sense the cache essays mean — every hop is a potential miss. A balanced tree of the same size makes fewer comparisons and touches fewer cache lines, and the gap between the two counts is wider here than the comparison count alone suggests. That is a reason to prefer a B-tree in a database and it is not a reason the analysis above is wrong; the two counts measure different things and disagree, as they always do.

The silhouette is the coins and nothing else, and the cheapest way to say so is to change the coins and change nothing else.

The seed is one dial and the coin’s bias is the other, and only the second one is a design decision anybody makes.

The third dial is the one the analysis is written in, and it is the one that moves the structure least over the range a picture can hold.

The third resource #

Every algorithm on this site is measured in comparisons and, since the space phase, in slots. A skip list needs a third counter, because it consumes something the other two cannot see.

Building a skip list of $n$ keys with a fair coin consumes 2.03 random bits per key, measured, fitted against $n$ across three orders of magnitude with a spread of 1.03. The expected value is exactly 2 — one flip to decide whether to promote, and on average one more, because the expected number of flips before a tails is two.

Two bits per key sounds negligible and is worth having the number for anyway, because it is the quantity that separates a skip list from the structure in the next essay but one. A treap makes the same kind of bargain and pays 32 bits per key for it — a full random priority per node rather than a level. Both are $\Theta(n)$; the constant is sixteenfold, and the constant is the content, as usual.

What the trade actually buys #

The comparison that matters is against the structure a skip list replaces, on the input that separates them.

Insert the integers 0 to 2,047 in order. An ordinary binary search tree reaches height 2,047 — it is a linked list with extra pointers, and every lookup is a linear scan. A skip list over the same keys is eleven levels tall and costs about 22 comparisons per lookup. The plain tree is not slightly worse; it is worse by a factor of the input size, and it is worse on the most ordinary input there is.

There is a deterministic answer to this, of course: use a balanced tree. The comparison to draw is therefore not “randomised beats naive” — that is easy and uninteresting — but what randomisation costs relative to the deterministic repair. Three things, all measurable:

1. It costs randomness. Two bits per key that a red-black tree does not need. This matters when the randomness is expensive or when there is none.
2. It costs reproducibility. Two runs of the same program build different structures, so a performance bug may not repeat and a test may not be deterministic. Every figure on this site names its seed for exactly this reason.
3. It costs the guarantee. A red-black tree’s height is $\le 2\log_2(n+1)$, always, proved. A skip list’s height is a random variable with no bound at all.

And what it buys, also measurable, is that the code has no rebalancing in it. A skip list insertion is a search, a coin loop, and a handful of pointer writes; there are no rotations, no colour bits, no case analysis over four rebalancing configurations. That is not a complexity-class argument and it is not nothing — the cost that shows up in practice is often the cost of getting the case analysis right.

The honest limit, which is specific here #

This site’s standing limit is that a finite measurement cannot establish an asymptotic claim. Randomised structures add a second limit on top of it, and it is sharper.

Every number in this essay came from a seeded generator. The heights at seed 777 are the heights at seed 777 on every machine that renders this page, which is what makes them safe to print. But a seeded generator is a deterministic function, and a skip list built from a published seed is a deterministic structure whose shape is published. Everything this essay says about the input not mattering is true of the input; none of it is true of an adversary who has read the seed.

That is not a caveat about the figures. It is the subject of an essay later in this phase, because the same gap sits underneath every randomised structure that gets deployed with a fixed seed for reproducibility — and underneath the sentence in what randomising the pivot buys that says randomisation is worthless as a defence when the seed is known.

What can be said, and is the whole content of this essay, is narrower and still surprising: for a skip list, the structure is not a function of the data. Two builds from the same keys are different objects; two builds from different orders of the same keys under one seed are the same object. Everything else about the structure follows from that one fact, and it is the fact that every other data structure on this site does not have.