Cache line — where it appears
Named by 9 essays across 2 fields — each of them below, with the objects they name alongside it.
A lookup that stops caring how wide an entry is
Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.
A code that has to fit its worst line
A blocked Bloom filter's four-bit thresholds are far from uniform: two blocks in five never close, and the rest crowd into the upper values, an entropy of 2.4 to 2.8 bits. A table coded from that distribution was predicted to match the four-bit rate on under three bits a block. Packed end to end it does, at 2.65 to 3.03 bits, and it costs every lookup a second read for the index. Packed a fixed number to a cache line it needs no index, but every line must hold its worst run of long code words, which costs 3.19 bits at 64-bit blocks and eighty-three code words decoded a lookup. Where the table is large enough for the saving to show, a plain three-bit table gets part of it with none of the costs.
A bit for whether it closed
Almost half of a blocked filter's threshold table says one thing: this block never closed. Store that answer as a bit a block, and a closing value only for the blocks that did, found by counting the ones before it. At 64-bit blocks the prediction was 3.1 bits a block and two cache lines. Packed end to end it lands at 3.15 bits and 2.5 lines; packed a line at a time it reads two lines and counts one word, and costs 3.64 bits, because every line must hold the most closings any line happens to draw. At 512-bit blocks, where three blocks in five close, it saves under a tenth of a bit.
The worst of more lines
A blocked Bloom filter's threshold table, stored as a bit for whether each block closed and a value for each block that did, packed a fixed number of blocks to a cache line, costs 3.64 bits a block at 64-bit blocks because every line must hold the most closed blocks any line draws. Sizing the line for the mean plus one standard deviation, and moving a line's excess values to a shared overflow, was predicted to cost about 3.25 bits and send under one closed lookup in a hundred to a third line. The lookups behave as predicted: 0.6% read the overflow, 2.003 lines a lookup. The bits land at 3.38, because every line must carry the offset where its moved values begin. What the measurement found instead is that the worst line is a property of how many lines there are: 3.38 bits at two thousand blocks and 3.62 at a hundred and twenty thousand, while the line sized for the usual line costs the same at every size.
An offset that only has to reach its neighbours
A blocked Bloom filter's threshold table, its cache lines sized for the mean number of closed blocks plus one standard deviation and their excess values moved to a shared overflow, cost 3.38 bits a block where 3.25 was predicted, because every line carries a nineteen-bit offset into the overflow. Grouping lines, each line's offset reaching only its group's part and each group's position held once in an array of its own, was predicted to cost 3.31 bits a block for 2.0064 lines a lookup. It costs 3.301 for 2.0060, as predicted. But the nineteen bits were mostly an offset sized to address a table of moved values, when the overflow this table has needs eleven: sized for the overflow it has, the ungrouped line costs 3.337 for no extra line at all. Grouping's further three hundredths cost a line a moved lookup, and spent on room instead, that line buys more. At equal lines a lookup the grouped table is the dearer, by a hundredth to nine hundredths of a bit.
A reserve sized for the spill
A split threshold table gives every line the same room, the mean number of closed blocks plus some standard deviations. Giving each line room for the mean and each group of 64 lines a shared reserve at one standard deviation of the group's total was predicted to cost about 3.24 bits a block for 2.006 lines a lookup, under the best ungrouped line. The reserve it predicts holds 52 values where the group's lines spill 145: it is full in every group, the spills go on to a third line, and the table lands on the ungrouped curve. Sized for the spill instead, the reserve puts the table under that curve at every room, by two to three hundredths of a bit a block.
The room the lines lend
A blocked filter's threshold table gives each 512-bit line room for its closed blocks' values, and a group reserve sized for the spill had just put it under the ungrouped curve. A line under its room leaves slots empty that are already paid for, so its neighbours' spills could be carried forward into them, with no reserve at all: predicted at about 3.12 bits a block for 2.012 lines a lookup. The bits are right and the lines are not. At room for the mean a carried value passes 12.8 lines before it finds a slot, because a run of lines that is room-for-the-mean on average is a queue with nothing to spare. Given three quarters of a deviation of room, the walk falls under two lines and the carried table lands a hundredth of a bit under the reserve.
A walk that stops at two lines
A blocked filter's threshold table, its lines sized for the mean number of closed blocks and each line's surplus carried forward into the next lines' empty slots, was cheapest in bits — 3.113 a block — and dear in lines, 2.183 a lookup, because a carried value joins a queue with no slack and walks 12.8 lines. Capping the walk was predicted to keep most of the bits, about 3.13, for under 2.02 lines, two hundredths under a reserve sized for the spill. Capped at two lines, the walk sends 53% of its carried values to overflow, and the table costs 3.180 bits a block for 2.027 lines. That is a hundredth under the spill-sized reserve at the same lines and a few thousandths under the uncarried line's curve: at room for the mean most of what joins the queue would wait more than two lines, so the overflow becomes the reserve by another name. With room to spare, every cap loses to the reserve.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Design parameterBlocked filterThresholdBit vectorFalse-positive ratePredictionRankVarianceAlignmentHuffman codingLinear probingLocality