The permutation that moves almost nothing

Permuting is the harder problem here measured the cost of rearranging a file by a permutation that was drawn uniformly at random, and found that moving one element at a time costs about a transfer an element while sorting the elements by their destinations costs a few passes over the file. It ended on a question it could not answer with a random permutation: a permutation that moves almost nothing ought to cost almost nothing, and nothing in this field had a way to say what “almost nothing” means.

There is a standard answer, and it comes from the comparison model. The disorder of a permutation is counted by its inversions — the pairs of elements whose order it reverses — which is zero for the identity, $n(n-1)/2$ for the reversal, and about $n^2/4$ for a random permutation. Adaptive sorting is built on it: insertion sort’s cost is $n$ plus the number of inversions, and a whole family of sorting algorithms promise to be fast on inputs with few.

This page measures whether the number that measures disorder for a comparison sort also measures it for a file. It does not, and the way it fails says what the right number is.

Two ways to be almost sorted #

The measurement needs permutations with controlled disorder, and there are two natural ways to make one — which turn out to be the whole of the argument.

A window shuffle. Cut the array into consecutive windows of $w$ elements and shuffle each window independently. Every element stays within $w$ of where it started; the permutation has about $n w / 4$ inversions, growing with the window; and no element ever leaves its window.

A far swap. Choose $s$ pairs of positions uniformly at random from the whole array and swap each pair. All but $2s$ elements stay exactly where they were; the ones that move go an average of a third of the array away; and because each such element jumps over about $n/3$ others, the permutation has roughly $s \cdot n$ inversions — a lot, for very little movement.

Each permutation is carried out the way the random one was: read the source file in order, and write each element to its destination. The model is the ideal-cache model with blocks of $B = 64$ elements and a memory of $M = 512$ elements, which is eight blocks, managed by least-recently-used eviction. The counted quantity is block transfers, reads and writes together, and it cannot be less than 768 on this file: 256 source blocks read, 256 destination blocks read before they are modified, and 256 written.

That model is the one one access, eight kilobytes set up for this field, and it is worth being clear about what it charges for, because the whole result depends on it. A transfer is charged when a block has to be brought into memory and when a modified block is written back. Nothing is charged for reading or writing an element inside a block that is already present. So the cost of any pass is a statement about which blocks it needs and when, and the order in which it touches elements matters only through that.

What inversions were measuring all along #

Before the measurements it helps to say what kind of cost inversions are a good model of, since they were not invented arbitrarily.

An inversion is exactly one adjacent swap’s worth of work. Insertion sort moves each element left past every larger element before it, and each such step removes one inversion, so its running time is the number of inversions plus $n$. Bubble sort’s is the same count up to a constant. So the inversion count is the right measure of disorder for any process whose unit of work is moving an element one position past a neighbour — and it is the right measure precisely because in that process a long move is a long sequence of short ones, each paid for.

The other classical measures belong to the same family. The Spearman footrule, the sum over elements of how far each one is from its place, is within a factor of two of the inversion count for every permutation — a theorem of Diaconis and Graham — so any argument about inversions is also an argument about total displacement. Both measures charge a move in proportion to its length.

A block transfer does not. Moving an element one position and moving it ten thousand positions each cost at most a pair of transfers, and moving it within a block already in memory costs nothing. That is a cost with a threshold in it rather than a slope, and a measure that charges by length will misprice it on any family of permutations that trades many short moves for a few long ones. The measurements below are those two families, chosen to sit on either side of the threshold.

The window shuffle costs nothing until the window is wider than memory #

The flat stretch is the first thing to explain, because it contradicts the adaptive-sorting intuition directly. The permutation with half a million inversions costs exactly what the permutation with twenty-eight thousand costs, and both cost what the identity would.

The reason is that inversions measure how many pairs are out of order, and the pass does not care about pairs. It cares about which blocks it needs at the same moment. A window of 128 elements is two blocks; carrying it out needs the two source blocks and the two destination blocks for that window, four blocks together, and memory holds eight. So every element’s read and write lands in a block already present, and the pass performs exactly the transfers a sequential copy would. Inside that window the elements may be in any order at all.

The jump comes when the window’s blocks no longer fit. A window of 512 elements is eight blocks of source and eight of destination, sixteen blocks needed at once against eight available, and the pass begins to evict blocks it will need again a few elements later. It pays 3,095 transfers — four times the floor — for a permutation whose elements still move no more than 512 places. A window of 2,048 is thirty-two blocks on each side and costs 13,465, and past that the pass is effectively random.

So on the window family the cost is a step function of one quantity, the number of blocks the window spans set against the number that fit, and the inversions — which grow smoothly through the whole range — are merely correlated with it.

The same step appears in where insertion sort actually wins, where the crossover everybody attributes to comparisons turns out to be in memory traffic instead: an algorithm whose working set fits wins on traffic and loses on comparisons, and the counted quantity decides which of those is the win. Here the counted quantity is transfers, and the working set is measured in blocks, but it is the same observation — cost changes character at the point where the pattern stops fitting.

The far swap costs little however many inversions it makes #

The far swaps are the opposite case. The inversions are enormous: a thousand swaps produce seven million inversions, fourteen times as many as the window of 128 that cost the floor. And the cost barely leaves the floor at all — 1,189 transfers, 421 above it, for 2,048 displaced elements.

Each displaced element costs a fraction of a transfer. When the pass reaches an element whose destination is far away, it must fetch the destination block, write to it, and later fetch its own region back. But there are only a few of these among thousands of elements that stay in place, so most of the time the pass is copying sequentially and the far fetches are isolated interruptions. The working set of the pass is two blocks of steady copying plus an occasional visitor, and memory absorbs the visitors.

The two families, on one axis #

This is the plate the page is for. On one axis — inversions, the measure of disorder every adaptive sorting analysis uses — the two families interleave, and at the crossing point they are in the wrong order: the permutation with three and a half times fewer inversions is two and a half times more expensive.

The dashed line makes the practical consequence concrete. Sorting by destination costs 1,536 here, independent of the permutation. A rule that said “carry out a nearly-sorted permutation directly, and sort a disordered one” would need a threshold on disorder, and a threshold on inversions would choose wrongly on both of these: it would sort the far swap, which was cheaper to carry out, and carry out the window shuffle, which was cheaper to sort.

The measure that does order them is not complicated to state. What decides the cost is, for each stretch of the pass, how many distinct blocks it needs within a short span of elements — the working set of the access pattern, in blocks — compared with $M/B$, the number of blocks memory holds. A window shuffle’s working set is the window’s width in blocks, on both sides. A far swap’s is the width of the sequential copy plus the scattered destinations, which are few. Where an algorithm looks measures the same distinction on cache lines rather than disk blocks, and it is the same distinction: an access pattern is priced by its locality, and locality is not a count of anything out of order.

It is worth checking the obvious rescue before accepting that. If the sum of displacements misprices these families, perhaps the largest displacement does better, since a window shuffle’s largest move is bounded by the window while a far swap moves elements across the whole array. It does worse. The window of 512 has no element more than 511 places from home; the far swaps have elements sixteen thousand places from home; and the far swaps are the cheap ones. Maximum displacement ranks them in the same wrong order as inversions do, and for the same underlying reason — it measures length, and the cost is not paid by length.

What does order them is a count with the machine inside it: how many elements must move further than the pass’s working memory can span. For the window shuffle below the step that count is zero, and above the step it is nearly every element. For the far swaps it is the $2s$ elements that were swapped, and no more. This collection’s theme for results of this shape is that the measure is chosen by the structure it is meant to predict, and a measure of disorder for a file has to mention the file’s memory, since nothing else would let two permutations with the same inversions cost different amounts on different machines.

The same thing turns up far from sorting. A list and a block of memory measures a graph traversal whose cost depends on whether neighbours are stored near each other, and finds that two layouts of the same graph, identical in every combinatorial property, cost very different amounts to walk. A permutation is a layout; carrying it out walks it.

Memory moves the step, and the block size moves the floor #

The last two plates vary the two parameters the argument above says matter, and each should move exactly one feature of the picture.

Quadrupling memory moved the step by a factor of four in window width and did nothing to the far swaps, which is what the working-set account predicts and what an inversion account cannot: the inversions of every permutation on this plate are identical to the previous one, and the cost of one family moved while the other did not. The reversal of order between the two families is gone on this plate — not because inversions started to work, but because the only window that was expensive is no longer on the far side of the step.

Shrinking the block shrank everything that is measured in blocks: the step now falls at a window of about sixty-four elements rather than about five hundred, and the ratio between the two families at the crossing grew from 2.6 to 3.6. The permutations themselves are the same seeded permutations as before, with the same inversions. Everything that changed is a property of how the file is cut into blocks, which is the point — the cost of a permutation on a disk is a property of the permutation and the block structure together, and inversions only see the first.

What this does to “adaptive” #

A sort is called adaptive when it is faster on inputs that are closer to sorted, and “closer to sorted” is always made precise with a measure of presortedness — inversions, runs, the number of elements that must be removed to leave a sorted sequence, the largest distance any element is from its place. The comparison-model literature has a whole lattice of these measures, and a sort is optimal with respect to one of them if its cost matches the information-theoretic bound for inputs at that level of disorder.

The measurements here say that the measure is part of the model. A pass over a file is adaptive — it costs the floor on a whole family of disordered inputs — but it is adaptive to displacement relative to memory, and it is not adaptive to inversions at all. The runs a permutation does not leave makes the neighbouring point about runs: a measure that suits one algorithm’s structure can be blind to what another exploits. Inversions suit insertion sort because insertion sort pays one comparison per inversion. Nothing about a block transfer is paid per inversion.

That also explains the result sorting what will not fit relies on without saying so. External merge sort does not care how disordered its input is, in any measure, because it reads every run sequentially and writes every run sequentially; its cost is set by the number of passes and nothing else. It is the dashed line on every plate, flat, and the question of whether to use it is the question of whether the input’s working set exceeds memory — not whether the input is sorted.

A run is a property of the input argues that the presortedness a production sort exploits is a feature of real data rather than of the algorithm. The same holds here, and it suggests which real permutations are cheap on a disk: those produced by local edits — an insertion that shifts a neighbourhood, a correction to a few timestamps — rather than those produced by global operations that change few elements a long way. A log that is mostly in order with a handful of late arrivals is a far swap. A buffer flushed out of order within each batch is a window shuffle.

What the model leaves out #

Eviction is least-recently-used and memory is managed perfectly otherwise. A real buffer pool has a policy and a size that change under load, and prefetching that rewards sequential reads further. Both would make the flat stretch flatter and the step steeper, without moving where the step falls.

The pass is naive. A permutation algorithm that knew the working set could buffer each window’s destination writes in memory and flush them in order, which would make the window of 512 cost the floor again at the price of a buffer. The point of measuring the naive pass is that its cost is the cost of the access pattern with nothing clever in between, and anything clever is a way of changing that pattern.

Both families are extreme. Real permutations mix local and far movement, and a measure for them has to combine the two. What these families establish is that the combination cannot be the inversion count, since the inversion count ranks the pure cases backwards.

Where this ladder goes next: the sort that knows how far things moved #

The working-set account on this page predicts a method as well as a cost. If a permutation’s elements move no further than a window that fits in memory, the whole problem splits: read a memory-sized stretch of the source, arrange it in memory, and write it out, one stretch at a time — one sequential pass, at the floor. If only a few elements move far, split them out instead: carry out the local part by the pass and the far elements by a small sort of their own.

Neither is new as an idea, and neither has been measured here against the two methods this ladder already has. The rung that follows should build the obvious hybrid — measure the permutation’s displacement in blocks, then choose a pass, a sort, or the split — and price it on the two families above and on their mixtures. The measurement that matters is not whether the hybrid wins on its own chosen inputs, which it must, but how much it loses on a random permutation to the plain sort, since a method adaptive to a new measure owes an account of what that measure costs to compute. Along the way it can answer the transpose question permuting is the harder problem here left open, because a transpose is a permutation whose displacement is large and perfectly structured, and a working-set account ought to say where on this plate it falls.