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

Cache oblivious — where it appears

An algorithm or layout that runs well on a memory hierarchy without being told the size of its blocks or its cache. It gets there by dividing its work at every scale, so that at some scale the pieces it works on fit whatever cache it meets.

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

1010010B (elements per block)block transfers per searchtuned for B = 64Sorted arrayB-tree tuned for B = 64van Emde Boas — told nothingM = 16,384, B as drawnone layout, 7 block sizes, no parameter

The layout that is told nothing

A B-tree is built around a block size somebody looked up. The van Emde Boas layout is given neither the block size nor the memory size, and across seven block sizes spanning a factor of 64 it tracks the best structure that was told them. An algorithm with no parameters making a claim at every level of the hierarchy at once is a strange thing to be able to measure, and this is what it costs.

applied · Transfer 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 programmingInterval dpLocalityMemory layoutB-treeBlock transferCacheCost modelDesign parameterDivide and conquerEvaluation orderExternal-memory model

All concepts