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

Interval dp — where it appears

A dynamic program whose subproblems are the contiguous ranges of a sequence rather than its prefixes. The table is triangular and a cell considers every split point inside its own range, so the cubic in its cost sits inside the cell rather than in the table's shape.

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

01234567891011120123456789101112123456789101112123456789101112345678910123456789123456781234567123456123451234123121one unit = one subproblem given a value91 cells, 364 transitions, 4.0 per cell

The cells are not the cost

This field opened by pricing a dynamic program in subproblems — 29,737 calls became 56 cells and the class changed. That is right when a cell is cheap. A table over intervals has 8,385 cells and considers 349,504 transitions to fill them, and the cubic in its bound is inside the cell rather than in the table.

tables · Table 01234567891011120123456789101112122332223333122222332231222222223122222233122222221222222122222122221222122121one unit = one subproblem given a value91 cells, 156 transitions, 1.7 per cell

The argmin that cannot go backwards

The same triangular table, the same ninety-one cells, the same tree at the end of it — and 364 transitions one way against 156 the other. At 256 keys the ratio is 38. What removes the factor is not a property of the recurrence but a property of the numbers it is given, and the recurrence does not mention them.

tables · Table 01234567801234567891724303539424410182531364043111926323741122027333813212834142229152316one unit = one subproblem given a valueeach number is a storage offset, of 45 slots

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.

tables · Table cache misses per split point consideredsquare array, by length1.1063,128,465 missestwo copies, by rows0.212598,455 missessquare array, split scans0.095268,386 missesfully associative · 32 lines × 8 elements · LRU256 keys, 32,896 cells

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.

tables · Table 1632649612810³10⁴10⁵table sizesplit points appliedevery splitbounded per blockbounded per cell, by lengthweights satisfying the quadrangle inequalityall three compute the same table

The bound a block can and cannot have

Knuth's condition turns an interval table's cubic fill into a quadratic one by bounding each cell's best split between its two neighbours'. A blocked fill cannot use it a cell at a time, and the two cells that bound a block lie outside the block — one to its left, one below it. The schedule has finished both for ten per cent of the blocks, the bound then removes eleven per cent of the splits, and it removes half a per cent of the cache misses, because the splits it skips are the ones already in the cache.

tables · Table

Named alongside it

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

Dynamic programmingSubproblemLocalityMemory layoutCacheCache obliviousComplexity classCost modelEvaluation orderMeasured countMiss rateMonotonicity

All concepts