Space time trade — where it appears
Named by 36 essays across 7 fields — each of them below, with the objects they name alongside it.
Two passes or one, and what the second one costs
Kosaraju's algorithm and Tarjan's find the same strongly connected components of the same graph, in the same class, and one of them examines three times as many arcs as the other. The extra pass everybody counts is not where the difference is — building the reversed graph is, and no statement of "two depth-first passes" mentions it.
A guarantee that depends on an allocation
The C++ standard promises std::stable_sort N log₂ N comparisons if enough extra memory is available, and N (log₂ N)² otherwise. On 65,536 keys the library's own structure, denied its buffer entirely, makes 1,366,510 comparisons — a third more than with it, and twelve times under what the standard allows. What it spends instead is moves: 10.4 million against 1.2 million, 94% of them rotations. The standard bounds the count that barely changes and says nothing about the one that grows as n log² n.
The order equal keys keep
Four of the eight sorts here leave every pair of equal keys in the order it arrived in and four move between 1,209 and 2,403 pairs, and none of the four counts every plate here reports can tell them apart. Decorating each record with its arrival position makes any of them stable, for four thousand words and between 0.05 and 1.64 times its comparisons — a charge of 64% on Shellsort and a saving of 95% on quicksort, because the ties stability has to break are the ties a two-way partition chokes on.
The sort that makes none of them
Every count on this collection is a count of comparisons, swaps, reads or writes, and radix sort makes zero of the first. On 65,536 keys it moves five times less data than merge sort, misses the cache three times more, and sits 954,037 comparisons under the floor no comparison sort can go beneath — which is not an achievement, because the floor was never a statement about it.
The sibling a full leaf asks first
The rule databases use to fix ascending inserts fills their leaves completely and collapses to 53.4% when one key in a hundred arrives late. A leaf that offers a key to a sibling before it splits, and splits two full leaves into three when neither will take one, holds 84.2% on the same stream — and is better with a trickle of late keys than without one, because a perfectly ascending stream has no sibling with room.
Where the landmarks stand
Four tables of exact distances, each from a chosen cell, turn a straight-line estimate that barely helps on rough terrain into one that cuts a search by a factor of six. Averaged over 1,200 queries on eight maps, the same four tables expand 126 cells a query when their cells are the map's corners and 423 when they are near its centre. The standard choice, each landmark as far as possible from the ones before, expands 141 and loses to the corners on all eight maps. Moving four landmarks to the right places buys more than doubling their number.
The bits given to the wrong keys
A fingerprint table that gives later arrivals longer fingerprints holds 3.6% where a table that reserves nothing holds 21.1%, and it never runs out of reserve because it has none. It also dies at exactly the same size as the table that reserved nothing — 32 times its forecast, on the same key — because every generation shares one quotient, and the generation with the shortest fingerprint is the one that arrived first.
The read a filter has no key for
A Bloom filter on every run of a log-structured store turns a lookup for a missing key from a read of every level into a fraction of one — 0.72 transfers across eight levels at five bits a key, and 0.00027 at twenty. A range query over the same store reads nine transfers at five bits and nine at twenty, because a filter answers whether one named key is in a run and a range has no key to name.
The price of remembering an answer
Give selection sort a table of the pairs it has already compared and it makes 16,805 comparisons on 256 elements instead of 32,640. The table pays for itself once a comparison costs more than 3.1 word operations, and that price stays near three at every size measured. Give it the full closure of everything its answers imply and it makes 13,079. The closure pays only past 425 operations a comparison at that size, and past 1,659 at twice the size. The cheap memory is worth having on long keys. The complete one is worth having almost nowhere.
A stop that is correct and never sooner
A two-ended search can stop when the two frontiers' keys together reach the best route found, and it can also stop when either frontier's own estimate reaches it alone. Both rules are safe, so a search may use whichever fires first. On forty weighted grids the second never fires: at the moment the first one stops the search, the larger of the two own-keys stands at 64% of the route. The extra rule costs 60% more counted work and a second priority queue to find that out.
Positions confined to one line
A Bloom filter lookup reads 5.55 cache lines because its six positions are scattered across the whole filter. Confining them to a 512-bit block makes it exactly one, and costs 7% more false positives at eight bits a key. At sixteen bits a key the same block costs 91%, and the two-value trick that is free across a whole filter costs another 135% inside one — because a block is a small filter, and small filters are where the penalty lives.
The record that forgets on purpose
A table of every pair selection sort might ask is 131,072 bits at 256 elements and catches every repeated question. A direct-mapped cache of 1,024 pairs is 16,384 bits and catches 91% of them, at a break-even of 3.53 word operations a comparison against the table's 3.12. What decides the cache is not how long the sort waits before asking again — 98% of its repeats come within one pass — but how many other questions it asks meanwhile, and a model with nothing in it but collisions predicts every measured share to within 2.6%.
How long a reweighting stays true
Johnson's one Bellman–Ford run costs under one per cent of an all-pairs computation because it is divided over every source. Asked one query at a time it is divided over nothing, and it still repays itself after 2.7 queries — because the preparation is one Bellman–Ford and every query saves a third of another. What decides the trade is not the query count but whether the graph holds still: at half a per cent of arcs redrawn between queries the stored potential is worth exactly nothing, and its life is geometric at a per-arc failure rate of 6.6%.
A lookup that stops caring how wide an entry is
Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.
Two blocks and the chances they add
Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 35 keys instead of 51. The false-positive rate gets worse: 0.0997% against 0.0854%. At eight bits a key it nearly doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. At every density a filter is commonly built at, the repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.
A block the lookup can work out
Sending each key to the emptier of two blocks flattens the load and doubles the chance of a false positive, because a lookup cannot know which block was chosen. Give each block a threshold on a hash of the key instead and the lookup can work it out: one block read, one chance, and 46% of the load balance kept. At sixteen bits a key that is 0.0618% against one block's 0.0854% and two blocks' 0.0997%. The threshold costs 1.5% of the budget and two bits of it are nearly as good as sixteen.
The runs a range query can skip
A Bloom filter over key prefixes can tell a range query that a run holds nothing it wants, which a filter over keys cannot. On a four-level store of a million keys, a range expected to hold one key costs 4.76 transfers with no such filter and 2.41 with one built on 20-bit prefixes. The best length moves two bits for every tenfold longer range. By a hundred keys the most any range filter could save is a fifth of a transfer, because only the smallest level is ever empty. And the same memory spent on 20-bit prefixes makes a lookup for an absent key three times dearer.
The record measured where it would run
A table of every pair selection sort has compared saves half its comparisons at 1,024 keys, and priced in word operations it was the better record at every size. Replayed through a 32 KB cache it misses 477,824 times to save 258,290 comparisons — nearly two misses for every comparison it removes — while a cache of 1,024 pairs misses 192. The table's size is not the problem. Its layout is: it looks up and writes each question at [key][minimum], a new row every time. Indexed by the ordered pair instead, the same bits miss 3,079 times, and that repair works only for a sort whose smaller operand stays put.
The day a filter cannot grow
A fingerprint table dies when its quotient reaches its shortest fingerprint, and a filter cannot lengthen a fingerprint because it does not keep its keys. The store it filters does. Rebuilt from that store whenever its own count says its rate has passed 1%, a table grown a thousandfold never exceeds 1.05% and ends holding exactly what a reserve of ten bits holds — 18.9 bits a key — having read the store 1.34 times over. The reserve paid its bits early: 34.8 a key at four times the forecast, where the rebuilt table held 18.4. Which one is cheaper depends on whether the growth arrives.
The small levels' share of a range filter
Prefix filters on a four-level store were proposed a prefix length each, on the reasoning that one length is a compromise between levels whose densities differ 43-fold. Each level does want its own length, 18 to 22 bits, and that recovers a quarter of the gap to a perfect range filter. The gap is mostly not about length. Three fifths of it is false positives. Moving filter bits from the largest level to the small ones — 12, 12, 8 and 3 bits a key instead of 5 each — recovers more than half of it at the same memory, and matches one shared length given twice the memory.
A record the size of a pass's minima
Selection sort's table of every pair it has compared is 256 KB at 1,024 keys, and indexed by the ordered pair it lives almost entirely in the rows of the current minima. Keep only those rows — a ring of r rows, the least recently used given up — and 12 rows, 3 KB, catch 99% of the comparisons the whole table skips, with no misses beyond the first touch of each row. The ring beats the cache of 1,024 pairs on both axes at once. The rows it needs grow with the logarithm of the input, a few more than the minima one pass passes through, and which row it gives up matters as much as how many it has.
A record of stretches, not pairs
Selection sort asks many of its comparisons again, and a record of past answers can skip them. A table of every pair skips them all in 256 KB at 1,024 keys, and a ring of the recent minima's rows in 3 KB. The questions a pass repeats have more structure than rows record: each minimum of the previous pass was compared with one contiguous stretch of positions. Kept as a list of stretches — each minimum's position, where its stretch began, and where the key that beat it stood — the previous pass's chain answers 99.3% of what the table would, in 312 bytes. The failure predicted for it, a key the swap moves into a stretch, costs 0.04%. What the chain cannot do is stay small on every input: on reversed keys it needs a link for every key.
Two swaps a pass, and the stretches hold
Bidirectional selection sort finds the smallest and the largest key in one scan and places both, so a record of its past answers has to keep two chains, and each pass makes two swaps that land where the other chain reaches. The prediction was that the second swap would break stretches at a rate of whole per cent. It does not. Each chain answers its own side's repeats as the one-sided chain does — 99.1% and 99.2% at 1,024 keys — and a swap spoils about a tenth of a question whichever sort makes it, so the broken share falls as 1/n for both. What the second chain changes is the input that makes a record long: sorted keys, which the one-sided sort never repeats a question on, cost the two-ended record a link a key.
A run answers what nobody asked
Bidirectional selection sort remembers its past comparisons in two chains, and on sorted or reversed keys the chains need a link for every key. Keeping instead what is known about adjacent positions — which of each neighbouring pair is larger, forgotten when a swap moves either — turns a monotone stretch into a single run with a direction. On reversed keys one run replaces 1,025 links. On sorted keys the run does more than remember: it answers 260,610 questions the sort had never asked, from two keys' positions alone, and the sort makes 2,045 comparisons at 1,024 keys where the chains leave 263,167. On organ-pipe keys it cuts a quarter of the comparisons; on random keys, nothing.
A pass repaid by the scans after it
Give the two-ended selection sort one pass between neighbours before it starts, n − 1 comparisons, and sorted and reversed keys cost exactly that pass. The pass was predicted to be repaid in the first scan, and almost none of it is. On organ-pipe keys it saves 43,776 comparisons at 1,024 keys, 97% of them in the scans after the first. On random keys it costs 236, not 1,023, because later scans use the short runs it found. It breaks even on runs of four keys at every size — and the sort stays quadratic on every input that is not one run.
The runs too short to drop
A pass between neighbours leaves the two-ended selection sort a record of 674 runs on 1,024 random keys, and the scans after it use them to repay three quarters of the pass. Keeping only runs of three keys or more was predicted to cut the record by two thirds and give back under a tenth of what it repaid. It cuts the record by 63%, and gives back 69%: runs of two keys answer half of everything the record answers, because three quarters of its answers are about two neighbouring positions — the question a scan asks about the key beside the extreme it has just found. The record's cost was never in its short runs. It was in writing each run as three words: every neighbouring pair at two bits a pair is 64 words, a thirty-second of the run list, and keeps all of them.
What it costs to consult two bits a pair
The two-ended selection sort's record of adjacent order can be kept as two bits a neighbouring pair or as a list of runs, and the page that compared them counted both as free to read. Priced, the bits read 1.09 words a question on 1,024 random keys — under the two predicted — and a binary search of the run list takes 8.8 steps, because the pass leaves 503 runs to search. The run list was predicted to win from runs of sixteen keys; it wins only from runs of 512. Both prices are small and neither is small enough. Asked every question the sort makes, the bits spend 201 word reads for every comparison the record saves on runs of four keys, 764 at 4,096 keys, where a table of compared pairs broke even at three. The record repays its reading only on long runs, and the pass that finds them is also the cheapest place to decide whether to consult at all.
A filter that reads the word it saves
A selection sort's record of adjacent order, two bits a neighbouring pair, costs 1.09 word reads a question and spends 201 of them for every comparison it saves on 1,024 keys in short runs, because it is asked everything and answers almost nothing. A filter bit beside each pair, set only where a run could start, was predicted to turn away three quarters of the questions and cut that price to under sixty. It turns away two thirds and cuts the price to 185. The questions it turns away were already refused in the first word, the filter is read in that same word, and one read a question is a floor no filter can go under.
A run end kept in a register
A selection sort's record of adjacent order spends about a word read on every question it is asked, and on short runs it is asked 184 questions for every comparison it saves, so no filter read in that word can make it pay. Every question starts from one of the sort's two current extremes, and what the record can say about all of them is one number: where the run from that extreme ends. Kept in a register beside each extreme and refreshed only when it changes, that number cuts the reading to a forty-fifth on 1,024 keys in runs of four, and the price of a saved comparison from 201 word reads to 4.5, where it stops growing with the input.
A register dropped by what it already knew
Two registers beside a two-ended selection sort's extremes cut the reading of its record of adjacent order to a forty-fifth on short runs, and made it worse than reading the record plainly on long ones: 53.5 words a question on a sorted array of 1,024 keys against 22.1. The swaps were blamed, and the proposed repair kept the part of a broken run beyond the break as a register of its own. It changes the reading by under 1% anywhere. On the sorted array the survivors are kept 523,775 times and asked 1,022 times, and the sort makes no swap at all: every one of the 263,167 relearning drops there is a pair the record already held, rewritten at the same value by a neighbour's question that the previous scan's chains answered. The swap never broke the register. Learning what it already knew did.
A register kept through a confirmation
Two registers beside a two-ended selection sort's extremes, holding where the run of known order from each one ends, read 53.5 words a question on a sorted array of 1,024 keys, more than reading the record plainly — because 263,167 times a neighbour's question, answered by the previous scan's chains, rewrote a pair at the value it already held, and each rewrite dropped a register. Kept through such a confirmation and dropped only when a pair is forgotten or turns round, the registers read 0.347 words a question on that array, a 154th, and 0.345 on 4,096 keys: the reading stops growing with n. They become the cheapest record at every run length, 49 to 73 times under the next on runs and 5.75 times under the run list's search on the sorted array, and the price of a saved comparison now falls as runs lengthen, from 3.97 word reads at runs of four to 0.35. The dearest saving is now the short run's, and it is still above the 3.1 at which a table of compared pairs breaks even.
A floor under a product
Every lower bound written here so far puts a floor under one quantity. The published time–space bound for sorting puts one under a product: T·S is Ω(n²), so buying time with space and space with time cannot both be done. Measured, heapsort's product is 0.0028 n² — four hundred times under a bound nothing can beat. The bound is not wrong. It is stated in a model where the input may not be written, and every sort here writes to the input, which is where its working memory actually is.
A product paid for in blocks
The published floor under sorting puts a bound on time times space, and a read-only family that scans its input over and over meets it, while every in-place sort sits far above it. Counted in block transfers rather than reads, the floor itself moves to n²/B: the family meets it at every block size, and so does every sort once memory holds the whole array. With a memory of 512 cells, quicksort sits a fixed eight times above the family at every block size, because partitioning is itself a scan. Only heapsort's distance grows with the block, from ten times at a line of one to 285 times at 64. The prediction that the family's lead would widen towards B holds against heapsort and nothing else.
The request no price of memory would make
libstdc++'s stable_sort asks for a buffer of half the input. Priced in element moves against the memory held, every buffer from nothing to a buffer as large as the input has a range of memory prices at which it is the cheapest — except that one. A quarter of the input costs 1.4% more moves; a full buffer, merging out of place, saves 8% more for twice the memory; and the half-sized request sits above the line between them at every size measured. The record size, predicted to move the answer, does not: moves and memory both cost in proportion to it.
A request that reads the input first
A stable sort that asks for its buffer before it has looked at the input asks for half of it, whatever the input is. One pass to find the input's natural runs lets a merge ask only for the shorter run of each merge it will make. On input of four long runs that takes the moves from 17 a key to under 3, and on a sorted file it makes no moves at all. The buffer it needs barely falls: on anything from two runs to four thousand it asks for 36 to 45% of the input, because a balanced schedule's last merge joins two halves of the file. The request falls only where one run dominates. On a sorted file with a tenth of it appended at random, it asks for 3.7% of the input.
The buffer a schedule cannot bend
A stable merge sort that reads its input's runs first needed 36% to 45% of the input as buffer, because a balanced schedule's last merge joins two halves of the file. The repair proposed was to set the buffer first and choose a schedule whose merges fit it. No schedule can: merging the smallest pieces first still ends with two large pieces on almost every input, and every merge that does not fit is split by rotation. The extra moves are all rotations, six to eight and a half a key at a sixteenth of the input on every input, so the two costs simply add. Reading the runs still beats the library at every buffer on every input made of runs, and the schedule matters only where one run is most of the file.
Named alongside it
The objects these essays reach for when they reach for this one.
Comparison countDesign parameterPredictionSelection sortHonest limitLocalityNatural runBloom filterCacheMeasured countFalse-positive rateBit vector