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

The thread: Measured, not assumed — page 11

Page 11 of 11, continuing the same thread in the same order.
0100200300400102030copies of the basebits held during one querythe visited set: 420the frontier: 2666-character patterns20x to 1.58x What is taught wrongly

A constant factor, not a term

The substitution was expected to remove a quantity proportional to the answer. Both traversals hold a quantity proportional to the answer, and what it removes is a factor of 1.6 that shrinks as the collection grows.

 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.

 10100states the cache holdsoperations a characterthe plain NFA: 52.5the whole set fits: 19.94,096 characters · k = 8the knee is at 512 states What is taught wrongly

A cache below the reachable set

A lazy machine with a cache of two hundred and fifty-six states costs fifty-one operations a character and a plain non-deterministic simulation costs fifty-three. At five hundred and twelve it costs eleven. The line is flat across two orders of magnitude and then falls off a cliff.

 501001500.2000.4000.6000.800load: keys held ÷ slotsbytes held per keythe entry, 32 bytesslotted entriespacked, a pointer a bucketpacked, groups of 4 bucketspacked, groups of 1616,384 slots, buckets of 8, 32-byte entrieslabels at the lowest load What the machine does

Entries found by the rank of their tag

A bucket whose tags are kept sorted is an index: the position a tag is found at is its rank, and a rank can address an entry. Drop the fixed slots and pack each bucket's entries in tag order, and a cuckoo table of 32-byte records holds 36.1 bytes a key at half load where slots hold 66.1, and 34.3 against 36.7 at 0.9. Every insertion pays for it by moving the entries after its rank: 99 bytes against 36 at half load, 586 against 105 at 0.9. The prediction that packing would lose above 70% load was about the wrong quantity.

 1010³10⁴10⁵10⁶characters of textstepsbacktrackingThompson's NFAopen points: capped at4,000,000(a|a)*b12,158x at 20 characters What is taught wrongly

The folklore is about a matcher

Four million steps against three hundred and twenty-nine, on a twenty-character expression matched against twenty characters. One of the two machines doubles with every character of the input and the other does not, and only one of them is what a regular expression is.

 15202530buffer, as a share of the inputelement moves a key0n/4n/23n/4nn/16n/8n/4n/2nthe request65,536 keysline: the lower hull What the libraries do

The request no price of memory would make

libstdc++'s stable_sort asks for a buffer of half the input. Priced in element moves against the memory held, every buffer from nothing to a buffer as large as the input has a range of memory prices at which it is the cheapest — except that one. A quarter of the input costs 1.4% more moves; a full buffer, merging out of place, saves 8% more for twice the memory; and the half-sized request sits above the line between them at every size measured. The record size, predicted to move the answer, does not: moves and memory both cost in proportion to it.

 1248163210010³spare entries a group of 16 buckets keepsbytes moved an insertionslack at the endslack spread, region rewrittenslack spread, nearest gapborrowedslotsload 0.5, groups of 16dashed: the slotted layout What the machine does

The slack an insertion can reach

A cuckoo table whose entries are packed by tag rank holds half the bytes of a slotted one at half load, and pays by shifting entries on every insertion. It was proposed to keep a few spare entries at the end of each group's region. Charged the copies a full region costs, that slack helps only with the copies: at groups of 16 buckets an insertion still moves over a thousand bytes, against 36 for slots. The same slack divided among the buckets, with an insertion borrowing the nearest free entry, moves 347 — and the group size, which multiplied every earlier cost, stops mattering.

 05001e+31.5e+3load when the insertion is madebytes moved an insertion50%70%90%95%spare divided evenlyspare by recent insertionsspare by room leftfixed slots16 spare a region of sixteen bucketsdashed: fixed slots What the machine does

Spare where a bucket can use it

A cuckoo table packed by tag rank keeps a few spare entries in each region of sixteen buckets, and every time a region runs out it divides its spare among the buckets again. Divided evenly, most of the spare ends up in buckets that are already full, which never grow — they kick. Divided in proportion to where insertions have been landing, as proposed, more of it does, and an insertion at 90% load moves 1,159 bytes against 1,005. Divided by the room each bucket has left, only 3% of it is stranded, and at 95% load an insertion moves 10 to 17% less than with an even division. None of the three comes near the half-load figure, because all of the growth from half load to 90% is the cuckoo kicks' own cost.

 01020natural runs in the inputelement moves a key12416642561,0244,096randomlibrary, half the inputlibrary, a quarterout of place, the wholeruns found first65,536 keys, runs of random lengtha swap counts three moves What the libraries do

A request that reads the input first

A stable sort that asks for its buffer before it has looked at the input asks for half of it, whatever the input is. One pass to find the input's natural runs lets a merge ask only for the shorter run of each merge it will make. On input of four long runs that takes the moves from 17 a key to under 3, and on a sorted file it makes no moves at all. The buffer it needs barely falls: on anything from two runs to four thousand it asks for 36 to 45% of the input, because a balanced schedule's last merge joins two halves of the file. The request falls only where one run dominates. On a sorted file with a tenth of it appended at random, it asks for 3.7% of the input.

All threads