Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Parallelism — where it appears

Doing several steps at the same time, which is possible only for steps that do not depend on each other's results. The number of rounds a computation needs is its dependency depth, and an order that minimises rounds need not be the order that uses memory well.

Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.

—execution—intention0136101521283645247111622293746555812172330384756649131824313948576572141925324049586673792026334150596774808527344251606875818690354352616976828791944453627077838892959754637178848993969899one unit = one subproblem given a value100 cells, filled in diagonal order

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.

tables · Table 0102030comparisons on one orderingfloor 16Insertion sort7 to 28 · mean 19.28Merge sort12 to 17 · mean 15.73Heapsort21 to 29 · mean 25.81First-element quicksort13 to 28 · mean 16.92Median-of-three quicksort25 to 29 · mean 26.30Batcher's network19 on all 40,32040,320 orders of 8, enumeratedfloor ⌈log₂ 8!⌉ = 16

The sort whose count has no distribution

Batcher's network makes nineteen comparisons on every one of the 40,320 orderings of eight elements — sorted, reversed, adversarial or random — because it decides which pairs to compare before it sees any of them. That is two above merge sort's worst case and four below heapsort's best. At 65,536 elements the same refusal to adapt costs 4.07 times merge sort's worst case, and it buys three things no adaptive sort has, one of which is a proof of correctness that takes 65,536 inputs instead of twenty trillion.

counting · Count rounds, if every ready cell ran at oncerow by row65,793column by column65,793anti-diagonal by anti-diagonal513reads that miss the cacherow by row6.3%column by column28.2%anti-diagonal by anti-diagonal31.1%fully associative · 32 lines × 8 elements · LRU263,169 reads and writes per order

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.

machine · Machine rounds, if every ready cell ran at oncerow order, stored by rows65,793anti-diagonal order, stored by rows513anti-diagonal order, stored by diagonals513reads that miss the cacherow order, stored by rows6.3%anti-diagonal order, stored by rows31.1%anti-diagonal order, stored by diagonals8.7%fully associative · 32 lines × 8 elements · LRU263,169 reads and writes per order

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.

machine · Machine 124816326410step width, cellscache lines a stepstored by diagonalsby diagonals, each line-alignedstored by rows512 × 512, lines of 8 cellsone step of an anti-diagonal

Eight cells at once

The anti-diagonal fill order exists because its cells do not depend on one another, and every table filled here has been walked one cell at a time anyway. Computed eight at a time, a step touches 5.71 cache lines on the layout that stores the table by diagonals and 10.87 on the one that stores it by rows — and per cell the first keeps falling to 0.42 while the second stops at 1.27. The prediction that a diagonal step would touch three or four lines was wrong, and line-aligning each diagonal only takes it to 4.94.

machine · Machine

Named alongside it

The objects these essays reach for when they reach for this one.

DepthEdit distanceEvaluation orderLocalityMemory layoutTrade offWorking setAccess patternCacheDynamic programmingMiss rateAlignment

All concepts