The digit a pass chooses for itself

The sort that makes none of them counted radix sort in the same four primitives as every comparison sort and found the dial that decides its cost. A pass counts how many keys have each value of a $b$-bit digit, turns the counts into starting positions, and scatters every key to its digit’s position, so it writes into $2^b$ separate streams at once. A wider digit means fewer passes and more streams, and the misses do not fall monotonically with the width. The page’s closing section asked for the width that minimises misses, whether the cache’s capacity in lines predicts it, and whether a sort could find it without being told the cache size — by widening its digit whenever the previous pass’s counts were concentrated in a few buckets.

That last proposal cannot work as stated, and the reason is structural rather than empirical. A least-significant-digit radix sort sorts on the lowest digit first and the highest last. The counts of one pass describe one digit of the keys, and the next pass’s digit is a different, higher set of bits. On keys confined to a small range the low digits are spread evenly and the high digits are concentrated, so the pass that reports concentrated counts is the last one, when nothing is left to widen. The information the rule needs does exist, and it can be had in one read. It just has to be gathered before the first pass rather than after each.

This page gathers it, charges for it, and measures what it buys against every fixed width.

Every access in the trace, the counters included #

The earlier page traced the keys and the scratch array and left the counters out, and its figures were drawn through a cache of 64 lines. Both matter here. A pass with a 16-bit digit keeps 65,536 counters, 256 KB of them at four bytes each: a structure larger than the keys, read and bumped once for every key the pass places. A trace without it charges a 16-bit pass nothing for the one structure whose size is the reason a digit cannot simply be widened.

So every access goes in: each key read, each counter incremented while counting, the counters’ prefix sum, and, while scattering, each key read, its counter read and bumped, and its write to the output. The sort ping-pongs between the input and one scratch array, as real implementations do, rather than copying back after every pass. Words are four bytes, lines 64 bytes, and the cache is exact LRU at 512 lines (32 KB, a first-level cache) or 4,096 (256 KB, a second level). There are 65,536 keys of four kinds: uniform 32-bit keys, keys below $2^{20}$, heavy-tailed keys whose values are mostly small, and keys drawn from only 64 distinct values. Every sort is checked sorted.

The best width depends on the cache #

On uniform keys through 32 KB the best width is 8 bits, at 0.76 misses a key. Through 256 KB it is 11 bits, at 0.57. The same keys want a different digit on a different machine, and each best width is disastrous on the other machine. Eleven bits through 32 KB misses 2.76 times a key, three and a half times the best. Sixteen bits misses 5.91 through 32 KB and 2.72 through 256 KB — the worst setting on both, with only two passes.

The cache’s capacity predicts the best width almost exactly. A pass’s scatter writes into $2^b$ streams, and each stream needs its current line resident until the next key lands in it; the counters need their lines too. At 8 bits there are 256 streams and a 32 KB cache holds 512 lines. At 11 bits there are 2,048 streams and a 256 KB cache holds 4,096 lines. The best width in both cases is the widest whose streams fill half the cache’s lines, leaving the other half for the counters and the reads. One stream a line, the obvious rule the earlier page proposed, overshoots by a bit. One stream per two lines lands on the measured optimum at both sizes, among the widths measured; widths of 9, 10, 12 and 13 bits were not swept, so the rule is located to within a bit or two.

That also explains the sixteen-bit result the earlier page saw, where sixteen bits came out best. Its trace omitted the 65,536 counters, and a 16-bit pass’s cost is mostly those counters: every key reads and writes one of 4,096 lines of counters in a random order. Charged for them, sixteen bits is the worst width measured.

A plan read off the keys #

The plan gathers what the widening rule was reaching for, in one extra read, before the first pass.

Correctness and cost come from different evidence, on purpose. One read of the keys counts all four bytes’ values at once, 4 × 256 counters. That is exact, and it is the only thing allowed to remove a pass. A byte whose histogram has one occupied bucket is the same in every key, and a pass over it would move every key to where it already is. Skipping it can never produce an unsorted output. Widths are chosen differently: from the lowest unsorted bit upwards, take the widest field, up to sixteen bits, whose number of distinct values stays within a budget of streams. The distinct count comes from a sample of 2,048 keys, corrected for the fact that a sample of 2,048 can never show more than 2,048 values. A wrong estimate there costs misses and never correctness.

The budget is half the cache’s lines, the rule the sweep just measured. That means the plan is told the cache size. The earlier page hoped for a rule that is not, and the section after the next one says why that hope does not survive.

The plans say what the counts saw. Keys below $2^{20}$ have a constant top byte, so the plan makes three passes where every fixed 8-bit sort makes four. Heavy-tailed keys have plenty of distinct values in their low bytes and few in their middle, because most keys are small, so the plan spans the middle two bytes with one 16-bit field. Keys drawn from 64 values have about 55 distinct values in every byte, and any 16-bit window over them still holds at most 64. So the plan takes two 16-bit passes, which only a width chosen for exactly this input would have taken.

On the keys a fixed width was not chosen for #

On keys confined to a small range the plan beats every fixed width through both caches: 0.66 misses a key against the best fixed width’s 0.76 through 32 KB, and 0.45 against 0.54 through 256 KB. It is not choosing a better width. It is doing one pass fewer, because a fixed width must cover all 32 bits whether or not they vary, and only the counts know they do not. A caller who knew its keys were below $2^{20}$ could tell a fixed-width sort to stop at 20 bits and get the same saving. A general-purpose sort is not told, and the pre-pass is how it finds out.

No fixed width is best everywhere. Eight bits is best through 32 KB on three kinds of key and 49% worse than 16 bits on 64 distinct keys. Eleven bits is best through 256 KB on three kinds and three and a half times the best through 32 KB. The plan is never the worst and never more than 23% above the best, and it pays for that with its pre-pass and its sample. On uniform keys through 32 KB those two cost 0.10 misses a key, and that is the whole of its gap there.

A plan cannot avoid being told the cache size #

The earlier page hoped for a rule that finds the width without knowing the cache, and the plates say where that hope fails. The counts tell a sort how many streams a digit would open: 256 for a uniform byte, 16 for a nearly constant one, 64 across any window of the few-values keys. They cannot tell it how many streams the machine can hold, because that is a property of the machine, not of the keys. Uniform keys produce identical counts on both caches, and they want 8 bits on one and 11 on the other.

So a sort that knows nothing about the cache can use the counts for exactly one thing: skipping digits that do not vary, and choosing wider fields where the keys have few values. Both help on every cache. Choosing how wide — the step from 8 to 11 bits on uniform keys, worth 19% through 256 KB — needs the cache’s size in lines, and there is no count that supplies it. The layout that is told nothing measured the other kind of answer: a structure that performs within a constant factor of the tuned one on every cache without being told any size. Radix sort has no such form, because its one parameter is a count of streams and the right count is the cache’s.

Where counts could steer pass by pass #

The widening rule is not wrong in every radix sort, only in this one, and the other kind is worth naming because it is where the rule belongs.

A most-significant-digit radix sort works the other way up. Its first pass splits the keys by their top digit into buckets, and every later pass works inside one bucket. There the previous pass’s counts are exactly the information the next pass needs: a bucket holding 40 keys needs no 8-bit pass at all, and a bucket whose keys share their next byte can skip it. Production sorts of this kind switch to a comparison sort for small buckets and choose each bucket’s next digit from its size. That is a threshold somebody typed, of the kind the sort the library ships measured in the sorts real programs call.

The least-significant-digit sort measured here has no buckets to steer, which is why its plan has to be made in advance. Every pass sorts the whole array stably, and the only thing a pass learns is the distribution of one digit across all the keys. The price of that is visible in the plan’s pre-pass, one extra read of every key. The gain is that each pass is a single sequential read and a scatter, with none of the most-significant sort’s recursion. Where an algorithm looks drew the difference between the two shapes of access, and the choice between them is a choice about which kind of adaptivity a sort can afford.

That gives the earlier page’s question a sharper answer than it asked for. A radix sort can choose its digit from its own counts, but only where the counts come before the decision. In a least-significant-first sort that means one pre-pass over the whole key; in a most-significant-first sort it happens bucket by bucket for free. The rule that failed here was not a bad rule. It was a most-significant-first rule applied to a least-significant-first sort.

The worst each rule does #

Summarised as each rule’s worst case over every combination measured, the plan is the only rule never more than a quarter above the best: 1.23 at worst, 1.06 on average. The best single fixed width, 8 bits, is 1.50 at worst, on 64 distinct keys. Its worst case is a missed opportunity rather than a disaster, which is why 8-bit radix sorts are the common default. Eleven bits, which looks best on a large cache, is 3.61 at worst, and sixteen bits, which saves passes, is 7.73.

The plan’s worst case is heavy-tailed keys through 256 KB, 0.66 against 11-bit digits’ 0.54. It spans the middle two bytes with one 16-bit field because the sample saw few distinct values there. The keys the sample is least likely to contain are the rare large ones that give a heavy tail its tail, and the scatter’s streams include them whether the sample saw them or not. A sample-based estimate of distinct values is weakest on skewed data, and here that weakness costs 23%. A result the size of its own noise is the page on what a sample can and cannot say about the rare values it is least likely to contain.

This is a minimax argument, and it has the shape a budget split before the question arrives found for sketches: a choice made before the input is known cannot be best for every input, but it can be never far from the best, and that property is what a default should be judged on. A fixed width is a bet on one kind of key and one machine; the plan reads the keys and is told the machine, and its worst case is set by how well a sample estimates distinct values rather than by which bet was made.

What was measured and what was not #

One size of array. 65,536 keys, 256 KB of them. The array itself fits in the larger cache and not the smaller, which is part of why the two caches want different widths; at millions of keys neither cache holds the array and the best widths would move. The earlier page found its miss rates nearly independent of $n$ at its cache size, and that is not checked here.

Exact LRU, fully associative. Real caches are set-associative, and a scatter into 2,048 streams whose lines are a power of two apart can conflict in sets long before the capacity is full. That would pull the best width on the large cache below 11 bits, and the half-the-lines rule would become a rule about associativity. The cliff where the data stops fitting is the page on how sharply capacity binds; associativity is not modelled anywhere in this collection.

No prefetching, no write-combining buffers. Real radix sorts often scatter through a small buffer per stream and flush whole lines, which turns the scatter’s random writes into sequential ones and moves the best width up. That is a different algorithm with a different trace, and it is the usual way production code widens its digits.

Misses, not time. The plan’s pre-pass and sample are charged their misses. Their arithmetic — four histogram updates a key and a distinct count over a sample — is charged nothing, as the passes’ arithmetic is not, which is the standing gap the count is not the time describes.

Still open: the scatter that buffers its streams #

Every plate here charges a scatter as $2^b$ streams writing directly into memory, and the half-the-lines rule is a consequence of that. Production radix sorts usually do something else: each stream writes into a small buffer of one line in a fixed region, and when a buffer is full it is flushed to its stream’s place in the output as one whole line. The random writes then hit $2^b$ buffer lines that stay resident, and the output is written a line at a time.

The measurement that follows adds that buffering to the traced sort, with the buffer region charged like any other memory. It asks whether the best width moves from half the cache’s lines towards all of them, and whether the plan’s budget should follow. The prediction is that buffering helps most at the widest digit whose buffers still fit: through 256 KB, 11-bit digits need 2,048 buffer lines of the 4,096 there are, so they should gain the most there, and 12 bits, which needs all 4,096, should become the new edge. Through 32 KB the 256 buffers of an 8-bit digit fit and the 2,048 of an 11-bit digit do not, so the unbuffered 11-bit figure of 2.76 misses a key should barely move. If that holds, buffering does not remove the cache from the choice of width. It makes each stream cheaper, which lets the width grow until the buffers themselves fill the cache, and moves the rule from half the lines to nearly all of them.