Evaluation order — where it appears
Named by 11 essays across 4 fields — each of them below, with the objects they name alongside it.
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.
A band as wide as the answer
If two strings are close, the optimal route stays near the diagonal and nine cells in ten cannot be on it. A band of three finds the right answer on a pair 300 characters long — and a band of thirty-two is needed before anything can prove it.
The precondition that removes the queue
Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.
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.
The order that has a depth
One hundred cells, filled in three orders, producing one table. Row order takes ninety-one steps and anti-diagonal order takes nineteen. Nineteen is not a property of the order — it is the longest chain of cells in the recurrence itself, no schedule can get under it, and every count taken until now was a total that could not see it.
A triangle stored in a square
An interval table has a cell for every range of keys and nothing below its diagonal, and it can be stored as a square array, as packed rows, or as packed diagonals — the last matching the order it is filled in. On sixty-four keys, with every read replayed through a small cache, the square misses 39.7% of its reads, packed rows 38.8%, and packed diagonals 78.4%. Storing a table in the order it is written is storing it in the order it is not read.
The split scan cut into blocks
Every way of filling an interval table one cell at a time stops at about one cache miss per split point considered once the table outgrows the cache — 1.01 at 128 keys, whether the cells go by length, by rows, or in a recursive tiling. Cut each cell's scan into blocks instead, and apply a block of split points to a block of cells whose inputs are all in hand, recursively at every scale, and the same 357,760 split points cost 0.094 misses each. The fill is told nothing about the cache, blocks of one and of four do equally well, and it needs no extra memory, where storing the table twice gets to 0.151 by doubling it.
The bound the search finds for itself
A spelling checker that computes the full edit-distance table against every word in a 2,424-word vocabulary fills 156,714 cells for each misspelt query. Bound each table by the best distance found so far, and abandon it the moment a whole row exceeds that bound, and the same search fills 40,273 and finds the same words. Meet the candidates nearest in length first and it fills 26,203, starting a table for exactly the words a search that knew the answer in advance would start. The last factor of 1.7 is the price of not knowing, and it is largest when the misspelling is smallest.
The columns the candidates share
Three thousand tables against one query, and most of them begin the same way. Stored as a trie, the 2,424-word vocabulary has 7,710 distinct prefixes holding 17,239 letters, and a search that computes one column per prefix reads 61,449 cells against 156,714 — before it applies any bound at all. Apply the bound at a prefix instead of at a word and it reads 16,958, beating a list search that was told the answer in advance.
The order with the best depth
An edit-distance table can be filled row by row, column by column, or one anti-diagonal at a time, and the anti-diagonal order is the one that needs the fewest rounds — 513 against 65,793 on two strings of 256 characters, because every cell on an anti-diagonal is independent of the others. Stored the usual way, row by row, it also misses the cache on 31.1% of its reads, where row order misses 6.3%. The order that is best for parallel work is worst for the memory it runs on.
The table stored the way it is filled
Store an edit-distance table by anti-diagonals instead of by rows, and the anti-diagonal fill keeps its 513 rounds while its cache misses fall from 31.1% of reads to 8.7%. It does not fall to row order's 6.3%, and the gap is not noise — on caches of four and eight lines the two rates are 9.4% and 6.3%, exactly three to two, because a cell reads from two earlier diagonals and only one earlier row. The same layout turns row order into the order that strides, at 28.3%. How a table is stored and the order it is filled in are one decision, and its price is the number of earlier fronts the recurrence reads.
Named alongside it
The objects these essays reach for when they reach for this one.
Dynamic programmingEdit distanceSubproblemTrade offCacheWorking setLocalityMeasured countMemory layoutMiss rateAccess patternCost model