Algorithms & Data Structures
the bound is a claim, and it is checkable
The other axis

The table nobody has to keep

A million-cell table, computed cell for cell in the same order, holding two thousand cells at its peak instead of a million. The saving is exactly (n+1)/2, it costs nothing on any operation counter, and what it buys is paid for with the one thing the table was for.
23 min read 8 figures Space is the other axisThe order is the algorithmIn place is a claim

A row of the edit-distance table depends on the row above it and on nothing else.

That is a one-line observation and it is worth stating carefully, because everything in this essay follows from it and nothing else does. Cell (i,j)(i, j) reads (i−1,j−1)(i-1, j-1), (i−1,j)(i-1, j) and (i,j−1)(i, j-1). Two of those are in the previous row and one is in the current one. No cell ever reads a row two above it.

So once row ii is complete, row i−1i-1 can be thrown away. On two thousand-character strings that takes the memory from 1,050,625 cells to 2,050, and it changes no other number: the same cells are computed, in the same order, considering the same transitions, arriving at the same answer.

Edit distance between intention and execution: 5Each cell holds the distance between a prefix of intention and a prefix of execution. The shaded run from the top left to the bottom right is one optimal alignment; where the table has ties there are others, and this one breaks them towards the diagonal. 100 cells computed, 20 held at once.—execution—intention87777776569888888765one unit = one subproblem given a value100 cells computed, 20 held at once
Fig. 1 Intention against execution, with the released rows drawn as they are held — which is to say not at all. The two rows at the bottom are what the computation has in memory when it finishes; the eighty cells above them were computed, were read exactly as often as they would have been otherwise, and were dropped. The distance is five and it is in the bottom right corner, which is the only cell anybody asked for.

Two resources, and the reason they are counted separately

This site has been here twice before and each time the second resource turned out to rank things differently from the first.

Two counts, two rankings put comparisons against cache misses and found two traces of identical length with wildly different miss counts. Space is the other axis put auxiliary slots beside operation counts and found that “sorts in place” covers three behaviours differing by a factor of nn. The pattern is the same here and the pair is new: cells computed against cells held.

The counter in this field reports both, and the plate below is the whole argument for the separation. Two runs, identical in every count except one, and the one they differ in is a factor of five hundred.

Cells held at once, against the length of the stringsFull table at a measured slope of 1.99; Rolling frontier at a measured slope of 0.99. The strings are unrelated, over an alphabet of 4. On these axes a slope of 2 is a rectangle filled and a slope of 1 is a line.10010³10³10⁴10⁵10⁶length of each stringcells held at onceFull table · 1.99Rolling frontier · 0.99one unit = one subproblem given a valuecells held at once, n from 64 to 1024
Fig. 2 Cells held at once. The full table’s line has slope 1.98 — it is the rectangle — and the rolling frontier’s has slope 0.99, because two rows of a table mm wide is 2(m+1)2(m+1) cells whatever nn is. The gap at each size is exactly (n+1)/2(n+1)/2: 32.5 at sixty-four characters, 512.5 at a thousand and twenty-four. Neither line is a measurement of anything that happened faster.

There is a third thing the counter has to keep straight and it is the reason live is decremented by a release rather than recomputed from the table. A cell that has been released is gone; a cell that has never been written is not there yet; and a cell holding zero is an answer. Three states, and only the first two are usually conflated — an implementation backed by a plain array has one state for all three, which is what makes the failure it produces silent.

What the saving is actually worth

The factor (n+1)/2(n+1)/2 is not a constant and it is not asymptotically negligible, which is the thing that makes this worth a page rather than a footnote.

Two sequences of ten thousand characters each — a modest size for the problems this recurrence is used on — give a table of 100,020,001 cells. At eight bytes a cell that is eight hundred megabytes, which is a program that does not run on most machines and does not run at all on a machine with other work to do. Two rows of it is 20,002 cells, or 160 kilobytes, which fits in a level-two cache.

The computation is identical. What changed is whether it is possible.

That is the same argument the external-memory field makes about block transfers and the same one the streaming field makes about state: past a certain size, space is not a cost that trades against time, it is a gate. The cliff where the data stops fitting measured what happens at the edge of it, and the shape here is starker because there is no gradual degradation — the table either fits or the program stops.

What it costs, and the cost is the whole point of the table

The rolling frontier gives up the answer.

Not the number: the distance is in the last cell and the last cell is in the last row, which is kept. What is lost is the alignment — which characters matched, which were substituted, where a gap was opened — and recovering that means walking backwards from the corner through cells that no longer exist.

Edit distance between intention and execution: 5Each cell holds the distance between a prefix of intention and a prefix of execution. The shaded run from the top left to the bottom right is one optimal alignment; where the table has ties there are others, and this one breaks them towards the diagonal. 100 cells, 100 held at once.—execution—intention0123456789112345667822234567773333455678434345667854444567776555555678766666656787777776569888888765one unit = one subproblem given a value100 cells, 100 held at once
Fig. 3 The same pair with the whole table kept, and the path traced. Reading the outlined cells from the top left gives the alignment: five substitutions and then four matches, in this tie-breaking. Every cell on that path except the last two is in a row the rolling version released, so this figure is not something the previous one could have produced from what it had left.

This site’s table enforces that rather than describing it. A released cell is not unwritten and it is not zero — it is a third state, and reading it raises a different error from reading a cell that has not been computed yet, because the two are different mistakes. An algorithm that keeps a frontier and then reads behind it is not making an ordering error; it is making a claim about its own space that is false.

So the honest statement of the trade is not “linear space instead of quadratic”. It is: the number, in linear space; the number and the alignment, in quadratic space; or the number and the alignment in linear space and twice the cells, which is the third essay along and is a genuinely different algorithm rather than a change of bookkeeping.

The other reason to want it, which is not about fitting

There is a second effect, smaller and worth naming because it is the one that shows up before the memory runs out.

Two rows of a table are contiguous and are read in order. The whole table is contiguous too, but a run over it touches cell (i−1,j)(i-1, j) and cell (i,j)(i, j) one row apart in memory, which at m=10,000m = 10{,}000 is eighty kilobytes apart — far enough that the two are never in the same cache line and, past a certain width, never in the same level of cache either. Where an algorithm looks measured what that costs a traversal, and the shape is identical here: the counts do not move and the machine does.

The rolling version has a working set of two rows regardless of nn, so once 2(m+1)2(m+1) cells fit in cache the whole computation runs out of cache no matter how long the strings are. This site does not report durations, so the claim being made is narrow and it is the one the cache model can support: the number of distinct memory lines touched between one read of a cell and the next is bounded by the frontier, and the frontier is what the rolling version bounds.

Both of the halvings above are decisions about the order in which cells are visited rather than about what is computed, which is the property the rest of this section is about.

The order is what makes it possible

Row order permits this. Column order permits the transpose of it, keeping two columns. Anti-diagonal order permits keeping three diagonals, which is fewer cells still on a square table and is the order a band uses.

A top-down recursion permits none of it. It cannot release anything, because it does not know which cells it will be asked for again — that is the same property that lets it skip unreachable cells, seen from the other side, and it is why neither strategy dominates.

The same table filled in row order: 100 cellsThe same 100 cells as the plate above, shaded by when they were filled rather than by what they hold. The recurrence says only what a cell depends on; it does not say when to compute it, and row order is one of at least three that work. Every one of them produces a table agreeing cell for cell, which is asserted in the gate rather than assumed.—execution—intention0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899one unit = one subproblem given a value100 cells, filled in row order
Fig. 4 The fill order that makes a frontier possible, shaded by step. Every dependency arrow points into the row above or one cell to the left, so at the moment a row is finished, everything still needed is inside it. That property is a fact about this recurrence, not about tables in general, and a recurrence reaching two rows back would need three rows kept.

The general rule is worth stating in that form, because it is what carries to other problems: a recurrence whose dependencies reach back kk rows can be run in k+1k+1 rows. Edit distance and its relatives reach back one. A recurrence with a long-range dependency — one where cell (i,j)(i, j) can read (i−j,0)(i - j, 0), say — reaches back arbitrarily far and cannot be rolled at all, and no amount of care with the loops changes that.

The knapsack, where the same move goes one step further

The knapsack table has the same property one dimension over: row ii depends only on row i−1i-1, so two rows suffice.

The knapsack table: 6 items against a capacity of 20Every cell is the best value obtainable from the first i items within a capacity of c. There are 147 of them, and the width of the table is the capacity written in the input rather than the number of things in it.01234567891011121314151617181920—2/905/162/883/6010/110/460000000000000000000000090909090909090909090909090909090909090009090909090106106106106106106106106106106106106106106009090178178178178178194194194194194194194194194194194194009090178178178238238238238238254254254254254254254254254009090178178178238238238238238254254254254254254254254254009090178178178238238238238238254254254254254284284284284one unit = one subproblem given a value147 cells = (n+1)(W+1)
Fig. 5 Six items against a capacity of twenty, kept whole: 147 cells. Rows are items labelled by weight and value; the value in a cell is the best obtainable from the first ii items within capacity cc. As with edit distance, the whole table is needed to recover which items were taken, and only the last cell is needed for the value.
The knapsack table: 6 items against a capacity of 20Every cell is the best value obtainable from the first i items within a capacity of c. There are 147 of them, and the width of the table is the capacity written in the input rather than the number of things in it.01234567891011121314151617181920—2/905/162/883/6010/110/46009090178178178238238238238238254254254254254254254254254009090178178178238238238238238254254254254254284284284284one unit = one subproblem given a value147 cells computed, 42 held at once
Fig. 6 The same computation holding forty-two cells instead of 147. The ratio here is (n+1)/2=3.5(n+1)/2 = 3.5, which is small because there are only six items; with a hundred items and the same capacity it is fifty.

There is a further halving that every implementation uses and that this site’s table refuses to express, and the refusal is informative. A single row suffices if it is updated in place — with the capacity loop running downwards, so that a cell reads the previous row’s value at a lower capacity before that value is overwritten.

That is correct, it is standard, and it halves the space again. It also means a cell is written twice, which DpTable throws on, and the reason it throws is exactly the reason the trick is dangerous: run the capacity loop upwards and the code is still short, still plausible, and computes something else entirely — an unbounded knapsack, where each item may be taken repeatedly. Both loops sort correctly in the sense that both produce a number. One of them answers the question that was asked.

That is the second time in this field that a single character in a loop header changes the problem rather than breaking it, and both times the failure is silent. A table that distinguishes written from not yet written catches the first; nothing catches the second except knowing the answer in advance, which is why this site’s gate computes the same knapsack two ways and compares.

Edit distance between abracadabra and abrocadabro: 2Each cell holds the distance between a prefix of abracadabra and a prefix of abrocadabro. The shaded run from the top left to the bottom right is one optimal alignment; where the table has ties there are others, and this one breaks them towards the diagonal. 144 cells computed, 24 held at once.—abrocadabro—abracadabra109877654321211109887654322one unit = one subproblem given a value144 cells computed, 24 held at once
Fig. 7 One more frontier, on a pair with heavy shared structure: abracadabra against abrocadabro, distance two. A hundred and forty-four cells computed and twenty-four held. The two cells that carry the whole answer are the two substitutions — one at the fourth character and one at the last — and the first of them is in a row released long before the run finished — which is the argument for the next two essays in one picture. Most of this table is not needed, and knowing that in advance is worth more than throwing it away afterwards.

The same question asked of a different table

The longest-common-subsequence table has the identical dependency structure, so it rolls the identical way, and it makes the loss sharper because the thing that is lost has a name people ask for.

The length of the longest common subsequence is one number and it is in the last cell. The subsequence itself is recovered by walking backwards, and the walk needs the table. A program that reports “these two documents share 4,180 characters in order” can run in two rows; a program that highlights which characters, which is what every file-comparison tool does, cannot.

The longest common subsequence of intention and execution: 5 charactersEach cell holds the distance between a prefix of intention and a prefix of execution. The shaded run from the top left to the bottom right is one optimal alignment; where the table has ties there are others, and this one breaks them towards the diagonal. 100 cells, 152 transitions.—execution—intention0000000000000000011100000001120000001112011111111201111111120111112222011111233301111123440111112345one unit = one subproblem given a value100 cells, 152 transitions
Fig. 8 Intention against execution again, asking for the longest common subsequence rather than the distance. Five characters — e, t, i, o, n, in that order — and the answer is in the bottom right. The route to it is the same kind of monotone walk the distance table has, and it uses the same cells, which is why the two computations have the same space behaviour and the same thing to give up.

The general statement is that a rolling frontier costs the witness. Every optimisation problem here computes an optimum and, implicitly, an argument for it; the frontier keeps the optimum and discards the argument. Where the argument is the deliverable — an alignment, a subsequence, a set of items, an edit script — the saving is not available for free, and the honest options are the three at the end of the previous section rather than the two that are usually offered.

What a frontier is, stated generally

The rule is worth extracting from the strings, because it applies to every table in this field and to several outside it.

At any point during a fill, the frontier is the set of computed cells that some future cell can still read. Everything outside it is finished — it has contributed what it is going to contribute — and everything inside it must be kept. The frontier is derived from the dependency arrows and from the evaluation order together, and from nothing else: change either and it changes.

For edit distance in row order the frontier is two rows. In column order it is two columns, which on a wide table is smaller and on a tall one is larger, so the choice of order is a space decision as well as a correctness one. In anti-diagonal order it is three diagonals, which on a square table is about 323\sqrt2 times the side and therefore smaller than either — a fact worth having when the strings are long and equal in length.

Three orders, three frontiers, identical cells and identical answers. That is the strongest form of the argument this essay makes: the space an algorithm needs is not a property of the problem, and it is not a property of the recurrence either. It is a property of a decision that the recurrence does not record.

Which string goes along the rows

The saving is quoted above as (n+1)/2(n+1)/2 and it is worth noticing what is not in that expression: the width. A rolling frontier holds 2(m+1)2(m+1) cells whatever nn is, so the ratio between the full table and the frontier is (n+1)(m+1)/2(m+1)=(n+1)/2(n+1)(m+1) / 2(m+1) = (n+1)/2, governed entirely by the number of rows.

Which means the peak itself — the number that decides whether the program runs — is governed entirely by the number of columns, and the two strings can be assigned to the two axes either way round.

Take a pattern of a hundred characters against a text of ten thousand. Put the text along the columns and the frontier is 2×10,001=20,0022 \times 10{,}001 = 20{,}002 cells. Put the text along the rows and it is 2×101=2022 \times 101 = 202. A factor of ninety-nine, from a decision that changes no count, no answer and no line of the recurrence — only which argument was passed first.

So the rule is: roll along the longer string and hold rows of the shorter one. It costs nothing, it is not in any statement of the algorithm, and on the lopsided inputs this recurrence is usually given — a query against a document, a read against a reference, a word against a dictionary entry — it is the difference between a frontier that fits in a cache line and one that does not.

It is the same rule the linear-space alignment needs for its recursion, arrived at from a different direction, and it fails the same way when nobody checks: an implementation that takes its arguments in the order the caller supplied them is correct, produces the right answer, and can be off by orders of magnitude on the one resource the method exists to manage.

The row that overwrites itself

Two rows is not the floor. Edit distance can be computed in one row plus a single scalar, and the trick is worth setting out because it is the same trick the knapsack section describes and it fails in the same silent way.

Cell (i,j)(i,j) needs three predecessors: (i−1,j−1)(i-1,j-1), (i−1,j)(i-1,j) and (i,j−1)(i,j-1). Writing row ii into the array that holds row i−1i-1, left to right, the second is the value about to be overwritten and the third is the cell just written — both available. The first has already been destroyed by the previous write, so it must be saved into a scalar immediately before the overwrite happens.

That takes the frontier from 2(m+1)2(m+1) to m+2m+2, a further halving, and it is what every production implementation does.

It also means a cell is written twice, which the table in this field refuses, and the refusal is the right one. The version that saves the diagonal after the write instead of before is one line different, produces a number, and computes something that is not the edit distance — the same shape of defect as the knapsack’s loop direction, where both loops sort and only one answers the question.

Two halvings, both standard, both a single statement’s worth of code, and both undetectable from the output. That is the argument for a table that distinguishes written from unwritten from released rather than an array of numbers: the discipline costs a little at development time and it is the only thing that separates these two implementations before somebody notices the answers are wrong.

What this is an instance of

The move in this essay has a shape that recurs across the whole site, and naming it makes the next four essays shorter.

An algorithm produces more than it is asked for. Edit distance is asked for one number and produces (n+1)(m+1)(n+1)(m+1) of them; a sort is asked for an ordering and produces, on the way, a great deal of information about the ordering it discarded; a coder is asked for a bit stream and computes a model nobody keeps. Every one of those surpluses is an opportunity and a cost at the same time, and the design question is which parts of it are worth retaining.

What makes this case unusually clean is that the surplus is exactly delimited. The frontier is not a heuristic about what is probably needed later — it is the complete set of cells any future cell can read, derived from the recurrence and provable in one line. So the saving is not a trade against a risk of having to recompute something; it is free, up to the single question of whether the alignment is wanted.

That is why the interesting algorithms in this field are the ones that make the alignment cheap again rather than the ones that make the frontier smaller. The frontier is already as small as the dependency structure allows, and the alignment that fits in one line is what it takes to get the other half back.

Where this goes next

—sitting—kitten012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455one unit = one subproblem given a value56 cells, filled in row order The same table, filled two ways Top-down and bottom-up compute identical cells and return identical answers. One of them asks the table half a million questions and recurses four hundred frames deep; the other asks none and recurses none — and on a knapsack it fills twenty-two times as many cells as anything can reach. —execution—intention0123456789112345667822234567773333455678434345667854444567776555555678766666656787777776569888888765one unit = one subproblem given a value110 cells for one divide step, 30 held The alignment that fits in one line Compute the table twice and hold three rows of it. The factor of two is a geometric series and is predicted exactly; measured, it comes down from 2.269 to 2.052 as the strings grow, and the peak is 3(m+1) cells on the nose. peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three22log nQuicksort, random pivot28log nQuicksort, first-element29log nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, random inputone slot = one array element or one stack frame Measuring what an algorithm keeps Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.

What this makes readable

Essays that name this one as a prerequisite.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

The 8 essays that link to this one and share the most of its objects, of 10 that link here.

The objects this essay names

Each one links to every other essay that touches it.

Auxiliary spaceCacheCost modelDynamic programmingEdit distanceEvaluation orderKnapsackMemoisationPeak spaceSubproblemTracebackTrade offWorking set