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

The thread: Two counts, two rankings — page 3

Page 3 of 3, continuing the same thread in the same order.
keys sortedword reads for each comparison saved (log scale)141664256break-even of a pair table2561,0244,096runs of 4runs of 16runs of 64dashed: without registersa pass firstlogarithmic scale Counting

A run end kept in a register

A selection sort's record of adjacent order spends about a word read on every question it is asked, and on short runs it is asked 184 questions for every comparison it saves, so no filter read in that word can make it pay. Every question starts from one of the sort's two current extremes, and what the record can say about all of them is one number: where the run from that extreme ends. Kept in a register beside each extreme and refreshed only when it changes, that number cuts the reading to a forty-fifth on 1,024 keys in runs of four, and the price of a saved comparison from 201 word reads to 4.5, where it stops growing with the input.

 keys in each sorted run of the inputwords read a question (log scale)0.111048163264128256512sortedregisterskept past a breakanswering from insidetwo bits a pair, plain1,024 keys, a pass firstlogarithmic scale Counting

A register dropped by what it already knew

Two registers beside a two-ended selection sort's extremes cut the reading of its record of adjacent order to a forty-fifth on short runs, and made it worse than reading the record plainly on long ones: 53.5 words a question on a sorted array of 1,024 keys against 22.1. The swaps were blamed, and the proposed repair kept the part of a broken run beyond the break as a register of its own. It changes the reading by under 1% anywhere. On the sorted array the survivors are kept 523,775 times and asked 1,022 times, and the sort makes no swap at all: every one of the 263,167 relearning drops there is a pair the record already held, rewritten at the same value by a neighbour's question that the previous scan's chains answered. The swap never broke the register. Learning what it already knew did.

 01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4 What the machine does

Twenty bits apart

Two representations of one sparse set, six thousand seven hundred and forty-five bits against six thousand seven hundred and sixty-five. One exploits sparsity and the other exploits runs, and on this set at this density they price identically.

 keys in each sorted run of the inputreads a question (log scale)0.111048163264128256512sortedregisterstwo bits a pair, plainrun list's searchkept through a relearning1,024 keys, a pass firstlogarithmic scale Counting

A register kept through a confirmation

Two registers beside a two-ended selection sort's extremes, holding where the run of known order from each one ends, read 53.5 words a question on a sorted array of 1,024 keys, more than reading the record plainly — because 263,167 times a neighbour's question, answered by the previous scan's chains, rewrote a pair at the value it already held, and each rewrite dropped a register. Kept through such a confirmation and dropped only when a pair is forgotten or turns round, the registers read 0.347 words a question on that array, a 154th, and 0.345 on 4,096 keys: the reading stops growing with n. They become the cheapest record at every run length, 49 to 73 times under the next on runs and 5.75 times under the run list's search on the sorted array, and the price of a saved comparison now falls as runs lengthen, from 3.97 word reads at runs of four to 0.35. The dearest saving is now the short run's, and it is still above the 3.1 at which a table of compared pairs breaks even.

 Thompson's NFA, a set of states43.724 to buildthe subset DFA, built in full1.011,297 to buildthe subset DFA, built on demand41.824 to buildthe state set in machine words37.224 to buildoperations per character; the note is what was paid once, before the first character4,096 characters · k = 643.7 down to 1 What the machine does

What a character costs on four machines

Forty-four operations, one, forty-two, and a number that moves. Four machines for one language, with the construction charged separately from the steps, because a machine that is free per character paid eleven thousand operations before the first one.

 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 What the machine does

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.

 linear probingchainedcuckoo, two tables0240.10.20.30.40.50.60.70.80.9load factorentries read per lookup0120.10.20.30.40.50.60.70.80.9load factorcache misses per lookup8,192 slots, 64 cache lines of 8a probe is an entry read; a miss is a line fetched What the machine does

Two probes are two misses

Cuckoo hashing's lookup reads at most two slots, and at a load of 0.45 it reads 1.27 on average where linear probing reads 1.39. Replayed through a cache, it misses 1.18 times a lookup where linear probing misses 0.98. The table that wins the count the analysis uses loses the count the machine charges, because two slots in unrelated places are two cache lines, and a run of adjacent slots is usually one.

 run together1.00xsigma 21 · 5 bitsone separator1.00xsigma 22 · 5 bitsa separator each1.20xsigma 36 · 6 bitsruns 1.00xruns 1.00xruns 1.02x16 documents of 512 characterspacked bits, against running them together The other axis

Two currencies for one separator

Giving every document its own boundary marker costs a fifth of the packed text and three per cent of the run count. Both numbers are right, they are about the same change, and which one a collection pays depends on a structure nobody named.

 linear probingcuckoo, two tablescuckoo, buckets of 8024680.30.450.60.750.850.95load factorentries read per lookup00.511.50.30.450.60.750.850.95load factorcache misses per lookup8,192 slots, 64 cache lines of 8a probe is an entry read; a miss is a line fetched What the machine does

The bucket that fits a line

Make each of a cuckoo table's two candidates a bucket of eight slots laid out on one cache line, and no lookup ever touches more than two lines, the table builds past a load of 0.95, and at that load it misses 1.21 times a lookup where linear probing misses 1.79. The prediction that it would lose to linear probing at low loads was wrong — it misses less at every load measured, 0.94 against 0.96 at 0.3 — because a key it holds almost never lives in its second bucket. The guarantee belongs to the alignment, not the bucket; eight slots on lines of four put a lookup on four lines.

 bits heldbalanced49,593huffman41,589the answer comes backbalanced: sorted · 26 operationshuffman: sorted · 24 operations32 documents · zipf lengths83.9% of the ordered tree What the libraries do

The smaller tree hands it back unsorted

A frequency-shaped tree is sixteen per cent smaller and returns its documents in code order. A balanced one is larger and returns them sorted. The trade is d log d comparisons against a saving, which is not close — until the answer is truncated.

 a loop over the alphabet1,478,400the compound walk, inside the loop134,40011xone descent per node18,91678x6 patterns · 1 error · sigma 2155.8% of the extensions were dead The index that replaces the text

Three savings on one structure

A factor of eleven on an extension, a factor of seven on a branching search, and a sixth of the bits. Applied to one bidirectional index they do not give a factor of seventy-seven, and the reason is that two of the three are the same saving.

 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 What the machine does

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.

 both halves locate250,584100.0%the reverse half counts only226,50490.4%and its marks are Elias-Fano210,93484.2%the saving spent on sampling241,47596.4%16,384 characters · one in 3284.2% smaller, or the same size and faster The other axis

The ladder, and the rung that spends

Two hundred and fifty thousand bits, then two hundred and twenty-six, then two hundred and eleven. The fourth rung takes the whole saving and buys a four-times denser sampling with it, landing at ninety-six per cent of where it started and locating several times faster.

 "t than"8 found · set 8 · frontier 4"of her"7 found · set 7 · frontier 4" that "16 found · set 16 · frontier 11" every"31 found · set 31 · frontier 19"the ev"8 found · set 8 · frontier 4"o of c"8 found · set 8 · frontier 5" than "15 found · set 15 · frontier 9"ime ra"7 found · set 7 · frontier 4the visited set, pale; the sweep's frontier, dark17,715 phrases examined either way1.67x on what is held The index that replaces the text

The same occurrences, less bookkeeping

Two traversals examine identically many phrases and report identically many occurrences. What differs is that one holds every occurrence found so far in a set and the other holds an ordered list and a cursor.

 bits heldthe model3,591the structure3,905one rank, in operationsbinary search10 stepsselect and walk1 select + 0.7016,385 rows · one in 32 marked14x on the operation What is taught wrongly

A price with no structure under it

A class in this collection has charged Elias–Fano's price for several strands and stores an array of positions searched by binary search. The accounting is right about space to a bit per thousand and wrong about one operation by a factor of eight.

 factor against the published loopthe compound walk11xthe enumeration78xthe two, multiplied860xnothing measures thisan index with both78xthe shortfall is 11x, and the walk's factor is 11x6 patterns · 1 error · sigma 21the larger of the two, not the product What is taught wrongly

Two factors that do not multiply

Eleven times and seventy-eight times against the same baseline, so an index with both should be eight hundred and sixty. It is seventy-eight, and the shortfall is eleven — the first factor, exactly, because the second operation already contains it.

 a loop over the alphabet107.9the compound walk10.0the cheapest hereone descent per step19.016 exact patterns of 12ranks per step · sigma 21 What the libraries do

The saving that is a loss

An operation that is seventy-eight times cheaper on a branching search costs twice as much on an exact one. It reports every symbol present in order to hand back the one that was asked for, and a search that knows its character needs none of the rest.

 020406080255075100125one sampled position in every …of the plain index, per centsize: 84.7%67.5 steps16,384 characters · 8-character patternssize falls, the walk lengthens Structures

Bits and steps on one frame

The size falls from ninety-nine per cent to eighty-six as the sampling thins, and the walk to a sampled position rises from two and a half steps to sixty-four. Neither line is the answer; the answer is a point on the pair.

 phrases examined per probethe linear scan207.0sorted, with a running maximum10.9 — 19xthe running maximum costs 2,821 bits — 21.6% of the index40 of 40 positions checked, and the two agree at all of them238 phrases · 6,144 characters19x on the scan What the libraries do

The scan the order does not touch

Two hundred and seven phrases examined per probe, against eleven. A running maximum of the source regions' right ends lets a leftward walk stop for good, and it costs twenty-two per cent more bits.

 10010³10⁴10³10⁴10⁵characters of textoperations, construction includedcrosses at 256the NFAthe DFA64 DFA statescrosses at 256 characters What the libraries do

Where the table starts paying

Five thousand and sixty-five operations before the first character, then one per character. Against nothing before the first character and thirty-nine per character. They cross at two hundred and fifty-six characters, and that crossing is what an engine's compile decision actually is.

All threads