The count somebody chose

An earlier essay took one run of each sorting algorithm and reported four counts from it — comparisons, swaps, reads and writes — and showed that they rank the algorithms differently. The site has since acquired two more countable quantities: modelled cache misses, and peak auxiliary space.

Six quantities, one run, ten algorithms. Ranking the algorithms by each quantity gives six orderings, and the question this essay is about is how far apart they are.

Far enough that “which sorting algorithm is best” is not a question with a hidden answer. It is a question with six answers, and the disagreement between two of them is close to total.

The rankings #

Every sort at $n = 4{,}096$ on random input, ranked 1 to 10 by each quantity, with 1 the cheapest. Traffic is reads plus writes; misses are modelled with 64 lines of 8 elements; peak is the largest number of scratch slots and stack frames held at once.

Two rows are worth stopping on before any statistics.

Selection sort is first by writes and last by comparisons. It writes 8,158 times to sort 4,096 elements — two writes per element, because it finds the minimum by looking and then puts it in place — and it compares 8,386,560 times. By one measure it is the best algorithm on the page and by another it is the worst, and both measures are exact counts of the same run.

Insertion sort is first by swaps and eighth by comparisons. It records zero swaps, not because it moves nothing but because it moves data by shifting with get and set rather than by exchanging pairs. The swap counter measures a particular way of moving data and an algorithm that avoids the primitive shows up as free.

How far apart the rankings are #

A rank order can be compared with another by counting the pairs of algorithms they put in different relative orders. Zero percent means identical rankings; fifty percent means no relationship at all; a hundred percent would be exact reversal.

The two extremes are the useful part.

Comparisons and peak space disagree about 91% of pairs. That is very nearly a reversal, and it has a cause: the algorithms that compare least are the ones that buy their efficiency with a buffer, and the ones that hold nothing are the quadratic sorts. The two quantities are close to being negatives of one another over this set of algorithms, which is exactly why the frontier between them has five points on it rather than one.

Memory traffic and modelled misses disagree about 7%. One pair out of forty-five. These two are nearly the same measurement, which is worth knowing because they are usually presented as different levels of the story — the operation count and the machine behind it. On this set, at this size, the cache model adds almost nothing to what reads-plus-writes already said.

That second result is uncomfortable for a site that carries the cache model as its second independent quantity, and it deserves the two qualifications that make it survivable rather than a quiet embarrassment. The model’s parameters are fixed here at 64 lines of 8, so the working set at $n = 4{,}096$ is eight times capacity for every algorithm; at other sizes and other capacities the two separate, which is what the cliff figure is about. And the pairs the two do order differently are the interesting ones — the ones where locality rather than volume decides — which is a small number of important cases rather than a large number of unimportant ones.

Both of those are true and neither makes 7% into a large number. The honest statement is that on this workload the second count earns much less than the fourth column of the ranking table suggests, and the case for carrying it rests on the sizes and parameters where it does not.

The same two counters, four more ways #

Choosing a counter is choosing a ranking, and the demonstration is only as good as the settings it was taken at.

The other axis is the input, and it moves both counters — not by the same amount and not for the same algorithms.

The disagreements move with n #

A table of disagreements at one size invites the question of whether they hold at others, and for one pair they emphatically do not.

Restricting to the seven linearithmic sorts — the quadratic three cannot be traced at large $n$, because bubble sort at 32,768 elements generates over a hundred million accesses — and sweeping the size:

The right-hand column explains the left ones. The modelled cache holds 512 elements, so at $n = 512$ everything fits: every algorithm’s miss rate is between 0.2% and 0.4%, the differences between them are compulsory misses and rounding, and the ranking they produce is noise. That is why traffic and misses disagree about 71% of pairs at that size — the second column is not measuring anything, so it disagrees with everything at about the rate two random orderings would.

Above the cliff the miss rates separate — heapsort at 7.6% against merge sort’s 2.8% at $n = 32{,}768$ — and the ranking becomes stable and close to the traffic ranking.

Two lessons, and the first repairs a claim made three sections above.

The 7% agreement between traffic and misses is a fact about one size. It runs 71%, 19%, 0%, 10% across the sweep, and the low numbers all come from sizes above the cache’s capacity. The honest version of the earlier claim is that above the cliff the two counts agree closely, and below it the second count has nothing to say.

A count can be uninformative rather than wrong. At $n = 512$ the miss counts are exact, reproducible and correct, and they carry no information about which algorithm is better because the answer is “none of them, at this size”. A measurement that is precise and empty looks exactly like a measurement that is precise and useful, and the only way to tell is to know what the model’s parameters are — which is why the site prints them on every figure.

The comparisons-against-space column comes with its own qualification. It runs 95%, 100%, 95%, 81% over these seven algorithms, against 91% for all ten at $n = 4{,}096$ — a different population, so the numbers are not directly comparable, and the conclusion is the same either way. That disagreement is near-total at every size measured and is not a single number.

What a cost model is #

The six columns are not six opinions. They are six cost models, and a cost model is a weighting over operations: how much a comparison costs relative to a write relative to a cache miss.

Written that way, the published complexity of a sorting algorithm is a cost model in which the weight on comparisons is one and every other weight is zero. That is a defensible choice — comparisons are the operation the lower bound is about, they are machine-independent, and for sorting integers they are a reasonable proxy for everything else — and it is a choice, and it is almost never stated as one.

Choosing a different weighting is not a refinement, it is a different question, and the answer changes:

Sorting 32-bit integers. A comparison and a move cost about the same, so the traffic column is the right one, and quicksort with median-of-three wins it.

Sorting 200-byte records by value. A move is fifty times a comparison. The write column dominates, and selection sort — last by comparisons — is doing 8,158 writes where merge sort does 49,152 and bubble sort does 8,384,368. It is still the wrong algorithm, because 8.4 million comparisons is 8.4 million, but the reason it is wrong has changed and the margin has narrowed by a factor of fifty.

Sorting pointers to objects. Every comparison chases a pointer to somewhere unrelated, so a comparison is itself a probable cache miss and the comparison count becomes a miss count. The misses column and the comparisons column merge.

Sorting something that barely fits in memory. The peak-space column is not a cost at all, it is a feasibility constraint, and every algorithm in the bottom rows of it is simply unavailable.

Four workloads, four different columns, one set of measurements. The columns are properties of the algorithms; which column matters is a property of the data, and no amount of measuring algorithms determines it.

What the site does about it #

Three procedural things, and they are the whole of the method.

Report the vector rather than a number. Every figure names the quantity it plots in its caption strip. A bar chart of “cost” would be a bar chart of whichever column the author preferred, and there is no such column.

Draw the frontier where two quantities matter together. Comparisons against peak space has five algorithms on the frontier and five dominated, and being dominated — beaten on both counts at once — is the one statement that survives not knowing the weighting.

Never sum the columns. They are in different units and no addition of them means anything. The one place this site does sum operations is the graph field’s work, which adds four graph primitives into one number, and every figure that uses it says so explicitly because it is exactly the sin this essay is about. It is done there because the four primitives are all “one step of the traversal” in a way that a comparison and a cache miss are not, and it is still a choice.

A weighted sum is not the answer either #

The obvious way out of six rankings is to combine them: choose weights, sum, rank once. It is what a benchmark does implicitly and it is worth saying why this site does not do it explicitly.

The weights are the answer, not an input to it. Choosing a weight for a cache miss relative to a comparison is choosing a machine and a data type — which is the question the ranking was supposed to help with. A weighted sum does not eliminate the workload dependence; it hides it inside a number somebody picked.

One of the columns is not a cost. Peak auxiliary space is a constraint: below the limit it costs nothing and above it the program does not run. Adding it to a sum with a weight treats a cliff as a slope. The frontier handles it correctly because dominance does not require the axes to be commensurable, which is exactly why a frontier is the right structure here and a weighted sum is not.

The sum destroys the information that survives not knowing the weights. Dominance is weight-independent: if one algorithm beats another on every axis, it beats it under every weighting, and that conclusion is available before any weight is chosen. Summing first and ranking second throws that away and replaces it with an answer that is only as good as the weights.

So the procedure this site uses — report the vector, draw the frontier, discard the dominated — is not an evasion of the choice. It is everything that can be said before the choice, and the choice belongs to whoever knows the data.

With six columns, almost nothing is dominated #

The section above says that several algorithms are dominated on every axis at once and can be discarded outright. That is worth actually computing from the table rather than asserting, and the answer is smaller than the sentence suggests.

An algorithm is dominated when some other algorithm ranks at least as well on all six columns and better on one. Working through the ten rows:

Bubble sort is dominated by insertion sort — 8, 1, 9, 8, 8, 1 against 9, 10, 10, 10, 10, 3, better or equal in every column and better in five.

Quicksort with a first-element pivot is dominated by quicksort with median-of-three — 4, 6, 2, 1, 1, 6 against 5, 7, 5, 2, 5, 8, better in all six.

And that is the whole list. Eight of the ten algorithms sit on the six-dimensional frontier, including selection sort, bubble sort’s near-twin by comparison count, which survives because nothing beats its write count; including heapsort, which is beaten on five columns by several algorithms and holds its place on peak space; including Shellsort, which is nobody’s first choice on any column and nobody’s worst on any either.

That is a genuinely deflating result and it is the right one. Adding columns destroys dominance, necessarily and monotonically: every new axis is a new way for an algorithm to be the best at something, so the frontier can only grow as the vocabulary does. With one column there is a total order and a winner. With six there is a frontier of eight, and the discarding step that looked like the useful half of the method removes two rows.

Which sharpens what the method is actually for. It is not a filter that narrows ten to two; it is a filter that removes the two algorithms nobody had to be told about — a quadratic sort beaten by a better quadratic sort, and a pivot rule beaten by a better pivot rule. Everything interesting survives, and it survives because the six quantities genuinely conflict rather than because the measurement is too coarse to separate them.

The consolation is that dominance, where it does hold, is the strongest statement available. Nothing about weights, machines or data types can rescue bubble sort here: it is beaten by insertion sort under every weighting of these six columns simultaneously, which is a conclusion no benchmark on one workload could reach.

And there is a seventh column #

Six is not the vocabulary either, and the missing one is worth naming because it would reorder the table again in a direction none of the six anticipate.

A processor guesses which way a branch will go and pays a penalty when it guesses wrong. That penalty is not a function of how many comparisons an algorithm performs; it is a function of how predictable their outcomes are. Two algorithms with identical comparison counts can differ enormously in it — and this collection has measured exactly that, in the essay on the branch the machine guesses.

Quicksort’s partition is the standard bad case. Each element is compared against the pivot and branched on, the outcomes are essentially a coin flip on random data, and no predictor does better than chance. Merge sort’s inner loop branches the same way, and a binary search’s does too — which is why a search with no branch to miss exists at all, doing strictly more work by every count in this table and winning on the column the table does not have.

So the honest statement of this essay’s finding is that the vocabulary has at least seven words, the seventh is independent of the other six, and the frontier is larger still. Every column added so far has made the answer less decisive rather than more, which is what it looks like when a question was never a question about algorithms in the first place.

The rung this sits on #

This is the fourth essay in the counting field and it exists because the field’s first three each added a quantity and none of them stepped back.

Counting instead of timing established that an operation count is exact, reproducible and machine-independent where a duration is none of those. Fitting a class established that a complexity class is a claim about counts that can be refused. One run, four counts established that there are four of them and they disagree.

What is new here is the shape of the conclusion. The earlier essays are about getting a number right. This one is about there being no number: the measurement is a vector, the vector’s components genuinely conflict, and collapsing it requires information that lives in the workload rather than in the algorithm.

That is not a counsel of despair and it is not relativism about performance. Every one of these numbers is exact and reproducible, several algorithms are dominated on every axis at once and can be discarded outright, and the frontier between any two columns is a short list. What cannot be done is the last step — turning the short list into a single name — without saying what the data looks like. Every summary that produces a single name has made that step and has usually not noticed.