The price of remembering an answer

The questions a sort asks twice counted, for each sort, how many of its comparisons asked something its earlier answers already settled. Selection sort on 256 elements makes 32,640 comparisons, and 19,561 of them have answers it already holds. Merge sort repeats almost nothing. Bubble sort, with its repeated questions taken away, makes exactly as many comparisons as insertion sort.

That essay stopped at a question it could state and not answer. Removing a repeat requires knowing it is a repeat, and knowing takes memory that has to be consulted before every comparison and updated after each new one. A comparison of two integers costs about one machine instruction, while a table big enough to hold the answers is larger than the array being sorted. The prediction was that no sort would come out ahead at any exchange rate a real machine offers. That prediction can be checked by pricing the memory and the comparisons in the same unit.

Two kinds of memory #

There are two natural records, and they remember different things.

A table of the pairs asked. For each pair of elements, one bit saying whether they have been compared and one bit holding the answer. Before a comparison the sort reads the pair’s entry, and if the pair has been compared it uses the stored answer. After a real comparison it writes the entry. That is one read per attempted comparison and one write per real one, and the table holds $2n^2$ bits. It removes exact repeats only. Having learned $a < b$ and $b < c$, it still asks about $a$ and $c$.

The transitive closure. For each element, a bitset of everything known to be above it and a bitset of everything known to be below. A comparison is skipped whenever its answer follows from any chain of earlier answers. The upkeep is where the cost sits. Learning $a < b$ means every element at or below $a$ is now below every element at or above $b$, so the update scans two bitsets to list those elements and ORs a whole bitset into each of them. With words of 32 bits, one learned relation costs a number of word operations proportional to the elements it touches times $n/32$.

The sorts themselves are not changed. Each one sees the record only through its comparator, which answers from the record when it can and compares the data when it cannot. Every read, write, scan and OR is counted as a word operation, and every comparison actually made on the data is counted separately. Both are counts rather than timings, for the reason counting instead of timing gives: a count reproduces on every machine, and a rate between two counts is a statement about the algorithms rather than about the laptop. So the trade can be written as a rate: the word operations the record costs, divided by the comparisons it saves, is the price a comparison must have for the record to break even.

The comparisons saved sort the six algorithms into three groups.

Selection and bubble sort lose about half their comparisons to the table of pairs alone. Bubble sort loses nothing more to the closure, because every question it repeats is an exact repeat. Selection sort loses another 3,726 to the closure, because it also asks questions that follow by transitivity. Bubble sort with repeats removed makes 16,552, which is insertion sort’s 16,552, as the earlier essay found. The table of pairs is the record that turns one into the other.

Heapsort and median-of-three quicksort lose little to the table and more to the closure. They seldom compare the same pair twice, but they often compare a pair whose order already follows.

Insertion sort and merge sort lose nothing to either record. Their comparisons are never implied by their earlier ones, so a record costs them upkeep and returns nothing.

The rate at which it pays #

Saving comparisons is one half of the trade and the upkeep is the other.

For the two quadratic sorts, the table of pairs breaks even at about three word operations a comparison, and that price does not grow with the size of the input. The reason is plain arithmetic. The table costs one read for each attempted comparison and one write for each real one. The sort saves about half of its attempts, so the price of a saving is the attempts plus the writes, divided by about half the attempts: close to three. The table grows as $n^2$ and the count of repeats grows as $n^2$, so the ratio stays put.

The closure’s price grows with $n$ for every sort, and quickly. Doubling the input multiplies selection sort’s break-even price by two to four: 16, 38, 130, 425, 1,659. Each learned relation updates bitsets whose length grows with $n$, and each update touches a number of elements that also grows with $n$. The closure saves more comparisons than the table, but not enough more to cover that.

For heapsort and quicksort the table’s price climbs too, from single digits towards fifty, because those sorts make few exact repeats and the table charges for every lookup regardless. A record that removes little cannot pay for being consulted on every comparison.

What the rate means #

A break-even price is only useful against a price someone actually pays for a comparison, and several such prices have been measured.

A comparison of two machine integers is about one word operation, so neither record pays for integers. That part of the prediction holds.

The comparison that is not one comparison measured sorting 512 string keys that share long prefixes. Merge sort there made 3,955 comparisons and examined up to 134,409 characters, about 34 characters a comparison. At that price the table of pairs pays comfortably for selection and bubble sort, which break even at three. It pays for median-of-three quicksort at every size up to 512, where the break-even is 15. The closure pays for none of them beyond 32 elements. The exchange rate nobody wrote down found another price for a comparison, the size of the record being compared, and it reached hundreds of bytes. Those prices are within the table’s reach and mostly beyond the closure’s.

The shape of the two curves explains the whole result. Each starts at its upkeep divided by the unrecorded cost and falls towards the share of comparisons it keeps, which is its floor. The table has little upkeep and a floor of 0.515, so it crosses early and flattens. The closure has 170 times the upkeep and a lower floor of 0.401. It crosses late, and at a price of 4,096 operations it has only just passed the table. The closure is the better record only when a comparison is very expensive, and at that price the problem is usually a different one.

That different problem is familiar. A comparison priced in thousands of operations is a comparison made by a person: a judge ranking entries, a user choosing between two options, a test that takes minutes. Those are the settings where systems do keep a full record of which pairs have been decided and infer the rest, because any comparison saved is worth far more than the bookkeeping. The measurement puts a number on where that stops being true. For selection sort on 256 elements it is 425 operations a comparison, and the number doubles and more each time the input doubles.

Heapsort shows the other failure. A sort that repeats little gains little from either record, and paying for a record that removes 6% of its comparisons is only worth it when those comparisons are very expensive. Even at a price of 4,096 operations, the closure saves heapsort about 10%.

The input decides whether there is anything to remember #

Every number so far is on random input. The repeats a sort asks are a property of the sort and the input together, and two ordinary inputs change the picture entirely.

On sorted input selection sort repeats nothing. Its first pass learns that the first element is the smallest, and nothing about how the rest compare to one another. Every later pass asks new questions, so neither record removes any. Bubble sort on sorted input finishes after one pass of 255 comparisons, with nothing to remember.

Reversed input shows the largest effect in the whole measurement. Selection sort with the closure makes 255 comparisons on reversed input, $n - 1$, down from 32,640. Its first pass compares the running minimum against each later element, and on reversed input the minimum changes at every step. The answers form a single chain that orders all 256 elements, so every question in every later pass is implied. With the closure, selection sort on this input learns the whole order in one pass and then confirms it without asking. The table of pairs removes only half the comparisons here, because it cannot follow the chain. Bubble sort on reversed input makes every comparison new under both records. Each pass swaps elements to new positions, so the pairs it compares have never met.

At this input and this size the closure’s upkeep is small compared with what it saves. The same count, exactly $n - 1$, holds at 32, 64 and 128 elements. But reversed input is also the input on which selection sort is easiest to replace. If the input is known to be reversed, one reversal pass sorts it in $n/2$ swaps and no comparisons. The closure has found the structure of that input, at a cost.

The record that costs nothing #

Insertion sort and merge sort gain nothing from either record, and the reason is more interesting than “they happen not to repeat”. They already keep a record, and it costs them nothing, because the record is the array.

Insertion sort’s sorted prefix is everything it has learned. When it places a new element, it compares only against the prefix, and the prefix’s order tells it exactly which comparisons would be redundant: once the new element is found to be larger than one key of the prefix, it is larger than every key before it, and insertion sort never asks. The transitive closure of its answers is stored in positions. Bubble sort learns the same facts and then moves elements in ways that scatter them. A pair it has settled no longer sits where its position would say so, and the next pass asks again. That is why bubble sort plus a table of pairs lands on insertion sort’s count exactly: the table puts back the memory that bubble sort’s swaps destroyed.

Merge sort is the same case at a larger scale. Each sorted run is a record of every comparison made inside it, and the merge asks only questions whose answers the two runs cannot imply. How close anything gets to the floor found merge sort within a couple of per cent of the information floor, and this is the same fact from the other side: an algorithm that keeps its knowledge in its data’s arrangement pays nothing to consult it.

Selection sort is the opposite. Its first pass finds the minimum and learns a great deal about the others along the way, then keeps only the minimum’s position and discards the rest. The next pass starts with no memory of it. A record helps selection sort for the same reason it helps bubble sort. The algorithm learns and then forgets, and the table stands in for what it forgot.

So the real result is not about tables. The cheapest record is a data arrangement that makes redundant comparisons impossible to ask, and the sorts that already have one are the sorts nobody replaces with a record. A record of pairs pays when a comparison is expensive and the sort throws its knowledge away. Changing to a sort that keeps its knowledge in place is nearly always cheaper still. On 256 random elements insertion sort makes the 16,552 comparisons that selection sort with a table of pairs only reaches at 16,805, with no table, and merge sort makes 1,729.

A count over every input is the page to read beside this one. Its plate of every ordering of eight elements shows the same sorts separating by how much of what they learn they keep. The sort whose count has no distribution is the one sort here that no record can help at all: a sorting network decides its comparisons before it sees any answer, so it cannot skip one.

What the memory costs besides operations #

Both records hold $2n^2$ bits. At 256 elements that is 131,072 bits, about 16 KB, beside an array of 256 32-bit keys that fits in 1 KB. At 512 elements it is 64 KB beside 2 KB. A record sixteen to thirty-two times the size of its data is consulted before every comparison.

The word-operation price ignores where that memory lives, and that is its largest omission. A table of 16 KB fits in a typical first-level cache, but one of 64 KB does not. Its entries are read in the order the sort asks about pairs, which is scattered across the table, and every read that misses the cache costs far more than a word operation. The count is not the time measured how far a machine can depart from a count on exactly this kind of access pattern. The break-even of three operations a comparison is the most favourable reading of the table, a price that assumes every lookup hits.

The closure’s upkeep is kinder to a cache than its lookups are. It ORs whole bitsets in sequence, a pattern a prefetcher follows. It is still the larger cost by two orders of magnitude, so the order of the two records does not change.

What is settled and what is not #

Settled by counting on random, sorted and reversed input from 32 to 512 elements: a table of pairs removes about half of selection and bubble sort’s comparisons and breaks even at three word operations each. That price does not grow with $n$. Bubble sort without repeats is insertion sort at every size. The full closure removes more, and its break-even grows about threefold or more with each doubling, past a thousand operations at 512 for every sort measured. On reversed input the closure leaves selection sort exactly $n - 1$ comparisons. Insertion sort and merge sort gain nothing from either record.

Not settled:

Cache misses. Every price is in word operations. The table’s lookups are scattered and its real price on a machine could be many times three. Nothing here simulates a cache.

Cheaper closures. The closure is kept in full, with an update that touches every related element. A structure that keeps only the chains a sort is likely to use, or updates lazily when a query needs it, would cost less. The measurement says what the complete record costs, not what the cheapest sufficient one would.

Other prices. The string comparison and the record size are two measured prices. A comparison that calls a user-supplied function has a price that depends entirely on the function, and nothing here measures one.

Still open: the record a cache can hold #

The table of pairs pays at three word operations and is sixteen to thirty-two times the size of the array. Between it and no record sits a family of smaller tables: a direct-mapped cache of recently asked pairs, indexed by a hash of the pair, of a fixed size that fits in a first-level cache whatever $n$ is. It would miss repeats that were asked long ago and catch the ones asked recently.

For selection sort, the question is when its repeats happen. The running minimum of one pass is compared again in the next pass against the same elements. So most repeats are asked within about one pass of the original question, which is $n$ comparisons, and a table of a few hundred recent pairs might catch most of them. For bubble sort the repeats come a pass later in the same way.

The measurement that follows gives each quadratic sort a recent-pairs table of 64 to 4,096 entries and counts the repeats it catches, the lookups it wastes on collisions and evictions, and the break-even price. It also replays the table’s reads through the cache model the machine essays use. The prediction is that a table of a few hundred entries catches most of selection sort’s repeats and breaks even near the full table’s three operations, without the $n^2$ memory and the misses that come with it. If that holds, the useful record is a small cache and not a table of every pair.