A record the size of a pass's minima

The questions a sort asks twice found that selection sort asks most of its questions more than once. On 256 keys it makes 32,640 comparisons, and 19,561 of them have answers it already holds. The price of remembering an answer gave it a table of every pair it had compared, two bits a pair, which caught all of those repeats. The record that forgets on purpose gave it a direct-mapped cache of 1,024 pairs instead, which caught nine tenths of them in an eighth of the space. Then the record measured where it would run replayed every access through a cache of 64-byte lines. At 1,024 keys through 32 KB, the table as specified missed 477,824 times to save 258,290 comparisons. The same table, indexed by the ordered pair — each question recorded once, in the row of its smaller key — missed 3,079 times.

The ordered table works because selection sort’s questions in a pass share an operand. Each pass scans the unsorted keys comparing each one to the current minimum, and the smaller of the two keys in a question is almost always that minimum. So almost every question the sort records, and almost every repeat it catches, lives in the row of whichever key is the minimum at that moment.

That page’s closing section drew the conclusion: throw the rest of the table away. Keep a ring of $r$ rows, one for each recent minimum, and ask what share of the table’s skips each $r$ catches, what it costs in misses, and whether a few rows beat the cache of pairs on both axes. It predicted that about $\ln n$ rows would catch most of the repeats, since a pass revisits roughly the minima the previous pass passed through.

The ring beats the cache on both axes, and by a wide margin. The number of rows it needs does grow with the logarithm, and is a few rows more than the prediction. The rule for choosing which row to give up turns out to matter as much as the count.

A dozen rows do the table’s work #

The ring holds $r$ rows of the ordered table. A question about keys $lo < hi$ is looked up in $lo$’s row if $lo$ has one. If the pair was asked before, the comparison is skipped and its answer read from the row. A question that has to be asked is recorded in $lo$’s row. If $lo$ has none, it takes the ring’s least recently used row, and every word of that row is cleared. The clearing is charged as writes. Each row is one key’s row of the table, 1,024 bits at 1,024 keys, stored as the table stores it: 32 pairs to an 8-byte word, 256 bytes a row.

At 1,024 keys a ring of 12 rows — 3 KB — catches 99.1% of the comparisons the 256 KB table skips. Eight rows catch three quarters, four catch an eighth, and one row catches nothing at all. The curve is a step, not a slope, and the step sits just above the number of keys that are the minimum at some point during one pass.

That number is known exactly for random keys. As a pass scans the unsorted part, the current minimum changes each time a key smaller than every key before it appears — a left-to-right minimum of the sequence scanned. In a random sequence of length $m$ the expected number of those is the harmonic number $H_m = 1 + \frac{1}{2} + \cdots + \frac{1}{m}$, about $\ln m + 0.58$. At 1,024 keys that is 7.5 for the first pass, and fewer for later passes, which scan less.

A single row catches nothing, and the reason is in how a repeat happens. A question is asked again in a later pass, not the same one: within a pass each key is compared once. For the repeat to be caught, the row of the key that was the minimum then must still be held now, and the ring must also have held a row for every minimum in between. With one row, every new minimum clears the only row there is.

Why a pass’s minima recur #

The rows are worth keeping because the minima of one pass are mostly the minima of the next.

A pass ends by swapping its minimum to the front. The next pass scans the same keys, minus that one and minus one displaced key, in almost the same order. So its left-to-right minima are almost the same chain: the previous chain with its last element removed, and perhaps a new key that the swap moved into a position where it now comes first. On 48 keys, 29 of the 54 minima of passes two to sixteen were minima of the pass before. The new ones come at the two ends of the chain: at its start, where the key displaced by the swap can land, and at its end, where the pass now continues past the removed minimum to the smallest keys left.

At full size the pattern holds and can be counted. Over all 1,023 passes on 1,024 keys, a pass’s chain of minima averages 6.5 keys and is at most 14; nine passes in ten have nine or fewer. Of the minima in each pass after the first, 70% were minima in the pass before. Every one of the 1,024 keys is a minimum at some point, since each ends up as a pass’s final minimum, but most are a minimum only briefly: the median key is in the chain for 4 passes, and the longest-lived for 61. Those long-lived keys are the ones a row is most worth keeping for, since each pass they survive asks their questions again.

Every question in the next pass that involves one of the recurring minima is a question the previous pass already asked: the same minimum against the same key, for every key the two passes both scanned while that minimum was current. That is where the repeats come from, and why they live in so few rows. The whole table holds a row for every key. The only rows the sort ever reads again are those of keys that were a minimum in two consecutive passes, and at any moment there are about $H_n$ of those.

Against the cache of pairs, and against the table #

The earlier pages compared records by what they skip and what they cost. The ring can be placed on the same axes.

A ring of 12 rows skips 255,881 comparisons for 176 misses. The cache of 1,024 pairs skips 155,420 for 192. The ring is ahead on both axes: 65% more comparisons skipped, 16 fewer misses, in three quarters of the bytes. It skips 99.1% of what the ordered table skips and misses 5.7% as often.

The ring’s misses are all first touches. The array is 128 lines and each row is four, so twelve rows add 48 lines, and 128 + 48 = 176 is exactly the measured count. After the first pass nothing the sort touches is ever evicted from a 32 KB cache. The ring’s row clears are also cheap: 1,663 of them at 12 rows, 53,216 word writes over the whole sort, against 255,881 comparisons skipped.

The cache of pairs loses because it forgets the wrong things. It holds the 1,024 most recently recorded pairs, whatever rows they are in, so a pass that records more than 1,024 questions pushes out the start of the previous pass before the next pass can ask them again. At 1,024 keys an early pass records about a thousand questions. The ring forgets by row, and the rows it forgets are the ones whose owners stopped being minima. That is the structure of selection sort’s repeats, which a hash of recent pairs cannot see.

The prediction said the ring would miss “no more than the cache of pairs does”. It misses less, because a cache of pairs scatters its entries across 4 KB by hash while a ring’s lookups walk along a few rows in key order.

Both small records sit at their compulsory misses, and that is the regime the count is not the time calls the easy one: once a record fits, its misses stop depending on how it is used. The table sits in the other regime at 1,024 keys, where its 256 KB cannot stay resident in 32 KB and every pass reloads the rows it needs. The ring gets the table’s catch at the small records’ cost because it is the part of the table that selection sort actually touches — its working set, in the sense the record measured where it would run used for the lines the ordered table fetched. The ordered table’s 3,079 misses were bounded there by the first touches of the minima’s rows, four lines each. The ring keeps those same rows and refuses to hold any others, so it never has to fetch one twice.

How many rows, as the input grows #

The rows needed for nine tenths of the skips track the expected minima a pass, two to four rows above them. From 128 keys to 2,048 they go from 8 to 12 while the harmonic number goes from 5.4 to 8.2. So the prediction’s scaling is right and its constant is a little low. The ring must hold every minimum of the current pass plus the ones from the previous pass that have not yet recurred, and a pass’s chain of minima varies around its mean: sometimes it has twelve links, not seven.

The requirement for 99% behaves differently at small sizes: 38 rows at 128 keys and 35 at 256, against 12 at 1,024. At 128 keys the table skips only 3,674 comparisons, and the last 1% is about 37 repeats of questions whose minimum was current a long time before. Those are rare, scattered across old rows, and worth nothing. At larger sizes the repeats are overwhelmingly the recurring-chain kind, and the 99% line sits a few rows above the 90% line. Either way the ring is a few kilobytes. At 2,048 keys 16 rows are 8 KB against the ordered table’s 1 MB.

That makes the record’s size grow as $n \log n$ bits — $\ln n$ rows of $n$ bits — where the table’s grows as $n^2$ and the cache of pairs is whatever size was chosen. Selection sort makes $n(n-1)/2$ comparisons whatever its input, a count that has no distribution in the sense the sort whose count has no distribution measured for a sorting network; this record removes half of them in memory of the order of a single row of the table times its logarithm.

Which row to give up #

The ring gives up its least recently used row. The obvious simpler rule gives up rows in turn, the oldest-allocated first, and it does noticeably worse.

At 12 rows the least-recently-used rule catches 99.1% of the table’s skips and the in-turn rule 88.7%. The in-turn rule needs 32 rows to reach 98%. The difference is the chain’s long-lived members. A key that stays in the chain of minima for many passes is looked up in every one of them and allocated only once. Under the in-turn rule its row is still given up when the ring comes round to it, however recently it was used, and the next pass has to ask all its questions again. The least-recently-used rule keeps it as long as it keeps recurring.

The two rules can be seen in the access pattern itself, the kind of picture where an algorithm looks draws for an array. Plotted as row against time, the ring’s lookups would form a few long horizontal streaks — the long-lived minima, read in pass after pass — and many short ones, keys that were a minimum for a pass or two. The in-turn rule cuts every streak at a fixed period whatever its length; the least-recently-used rule cuts only the streaks that have ended. Selection sort’s repeats are the long streaks, so the rule that preserves them is the one that catches them.

This is the same lesson the record that forgets on purpose found from the other direction. What decides a record for a sort’s repeats is not how long it waits before a question comes back but which questions come back, and a record whose eviction follows that structure needs far less memory than one that does not. The cache of pairs evicts by hash, the in-turn ring by age, and the least-recently-used ring by use. On this sort, use is the structure.

What was measured and what was not #

Selection sort on random keys. The ring works because selection sort has a current minimum and its chain recurs from pass to pass. On sorted input the chain is one key a pass and a single row catches everything; on reversed input the chain is the whole pass and the ring needs as many rows as the pass is long. Neither was measured. Bubble sort, whose smaller operand also tends to stay put within a pass, should behave like selection sort, and insertion and merge sort, which never repeat a question, have nothing for any record to catch.

A fully associative LRU cache. Every miss count is through an exact least-recently-used cache of stated capacity, the model the digit a pass chooses for itself used too. A list and a block of memory found a gap of more than three to one in misses between two layouts of the same traversal, and the ring’s margin over the cache of pairs is a gap of that kind: the same questions, recorded in a different arrangement. Real caches are set-associative, and a ring of rows at regular addresses could conflict in a few sets. At 12 rows of four lines each it is unlikely to matter; it was not checked.

Rows of two bits a pair. The ring’s rows are stored exactly as the table stores its rows, so that the three records are compared at the same layout. A row needs one bit a pair to say the pair was asked, and the answer is implied by the ordered layout. Halving the rows would halve the ring’s bytes and change none of its catches.

Word operations were not charged. The earlier pages priced records in word operations as well as misses, and the count is not the time is the reminder that neither count is a running time. The ring’s lookup is one word read and its record one word write, the same as the ordered table’s, and its clears add 53,216 writes over a sort that skips 255,881 comparisons.

Still open: the chain of minima as the record itself #

The ring stores rows for the chain’s keys, and each row is the whole of a key’s answers against every other key. But the questions a pass asks again are more specific than that. A recurring minimum is compared, in the next pass, against the same keys the previous pass compared it against — the keys scanned while it was current — and those keys lie in one contiguous stretch of the scan. A row records them as scattered bits. A record could instead store, for each link of the chain, only the stretch of positions it covered, and answer every question inside that stretch without a bit per pair.

That is a record of $H_n$ intervals rather than $H_n$ rows: a few dozen words at any size. The measurement that follows gives selection sort such a record — the chain of the previous pass, each minimum with the range of positions over which it was current — and has the next pass answer a comparison from it whenever the key under the scan lies in its minimum’s recorded range. It asks what share of the table’s skips that catches and at what size of input it stops working. The prediction is that it catches nearly as much as the ring. It should fail where a key displaced by the pass’s swap breaks a stretch in two, and the question is how often that happens and whether the ring’s rows or a list of intervals is the right record for a structure that is, in the end, just a chain of a few keys.