A cache the listings share

Two lines a superblock priced every document listing cold. A listing touched some set of 64-byte lines, each line was one miss, and a line touched twice was fetched once. That is the cheapest a single listing can ever be — no cache of any size makes one listing cheaper than its own distinct lines — and it says nothing about an index that answers listings all day, one pattern after another, through a cache nobody empties between them.

That essay ended by asking what a structure keeps between listings, and it made a prediction with a mechanism in it. The succinct range minimum laid out as ten separate arrays has two small directories that every query reads: at 32,768 values a rank directory of 25 lines and select samples of 16. They should stay resident across listings, so a listing would pay only for its parentheses, its tables and its values, about half its cold price. The segment tree would keep its top levels. The interleaved records, which put what every query needs in the same line as what only one query needs, would keep the least. It named one way the prediction could fail: patterns drawn from real text land all over the suffix array, and a cache of a few hundred lines might hold nothing a scattered workload reads twice.

Two thousand listings on twelve essays #

The collection is the frozen prose corpus that the crossing that never arrives listed against: twelve essays, cut together to 32,773 characters, so the range structure sits over the same 32,768-odd values the prediction’s arithmetic was done at. The patterns are its own words. A word is a run of three or more letters, and the text holds 4,312 of them, 1,176 distinct. A listing is drawn one of two ways. By occurrence: a random position in the text and the word that covers it, so a word is asked for as often as the text uses it, which is what a search box over these essays would see. By type: a random distinct word, every word equally likely, so most listings ask for something that occurs once or twice — the scattered workload the prediction was afraid of.

The median listing drawn by occurrence finds 11 occurrences, the ninetieth percentile 215, the largest 444. Its answer averages about four of the twelve documents, so the chain walks about nine range-minimum queries a listing.

Four ways of answering run the same workload, each through its own fully associative LRU cache of $K$ lines that is held across every listing. The scan reads the document array over the pattern’s rows and marks each document in a bitmap. The three chains walk the previous-occurrence chain with a range minimum — the segment tree, the succinct structure as separate arrays, the succinct structure as two lines a superblock — reading the document array at each answer. Every chain is replayed against its layout and must list exactly the documents the index lists; a replay that lists anything else fails rather than pricing a different walk. A thousand listings run first and are charged to nobody, so the caches start the measured two thousand already warm, the way a running index would.

Finding the pattern’s rows in the suffix array is charged to nobody either. All four methods need it, and it is the same search.

What a held cache takes off #

The cold prices are the ones the lines a constant-time query lands in and its successor would predict: the tree’s chain touches 16.2 lines a listing, the separate arrays’ 14.3, the interleaved records’ 11.9, and the scan 2.6. Every chain is between four and a half and six and a half times the scan before anything is held, which is where a crossing moved to again — on real prose the occurrences a document are too few for an output-sensitive listing to pay for itself.

Holding the cache changes every chain’s price by a large factor. With 256 lines held the tree’s chain misses 3.9 lines a listing, the separate arrays’ 4.9 and the interleaved records’ 3.8. With 512 lines held they are 1.5, 1.6 and 1.4. With 1,024 they are all about a twentieth of a line, because the whole workload — two thousand listings over 1,176 words — never touches more than about 940 distinct lines of any chain’s apparatus, and a cache of 1,024 holds every one of them.

The order changes along the curve. At 64 lines the separate arrays are the worst by a long way, 11.1 against 8.7 for the tree and 8.8 interleaved; at 256 the interleaved records and the tree are six hundredths apart and the separate arrays are a line behind; at 512 the interleaved records lead by a twelfth of a line. Nowhere on the curve are the separate arrays the cheapest chain, which is where the prediction put them.

And the scan’s line is on the floor. From 128 lines held it misses a hundredth of a line a listing.

The share each structure keeps #

The prediction was about shares — the separate arrays would pay about half their cold price, more than they would on any other layout — so the plate that tests it divides each held price by the same method’s cold one.

On words drawn by occurrence, the tree’s chain pays 24% of its cold price, the interleaved records 32%, the separate arrays 34%. On distinct words the tree pays 26%, the separate arrays 41% and the interleaved records 44%. The separate arrays did better than “about half”. They did worse than either other layout, on both workloads, and on the scattered workload the gap widens.

That second number answers the risk the prediction named, and it splits the structures. The scattered workload costs the tree almost nothing — 24% becomes 26% — and costs both succinct layouts a great deal: their held price rises by seven and twelve points of their cold price. The tree’s held price does not much care which words are asked for, and the succinct structure’s does. The reason is the same one that decided the cold prices, read from the other side.

What stays, and what it was worth #

The mechanism the prediction named is there. The rank directory costs a listing 1.00 lines cold and 0.16 held; the select samples — the sampled answers of the support that select is not rank backwards priced — 1.00 and 0.11; the superblock minima and the superblock table, at 17 and 68 lines, practically nothing held. Every query reads those parts at places that depend only on where its range falls in a small directory, so successive listings read the same few lines and those lines stay.

What the prediction did not do was add up what they were worth. Together the resident parts were about two and a third lines of a cold price of 14.3. Keeping all of them could never have halved it. The rest of the price is in parts a listing reads where its own answers and its own blocks fall:

• the shared table, 5.09 lines cold and 1.25 held. It is the table the table that fits inside a block built, every in-block answer for every shape of block, 162 lines here. A query reads it at the shapes of its two end blocks, and a block’s shape is whatever its parentheses happen to be, so two listings for different words read unrelated entries. 162 lines is small enough to stay resident only if nothing else wants the cache, and here everything else does;
• the values, 1.51 lines cold and 1.02 held: the chain’s value at each answer, read out of 1,025 lines of the caller’s array at a position the answer decides. A listing for one word and a listing for another find different answers;
• the document array at each answer, 1.22 and 0.66, and the parentheses at the query’s two ends, 1.21 and 0.50, both indexed by where in the suffix array the pattern’s rows fall.

So the separate arrays’ held price is mostly a price for reading the structure at places a particular listing chose, and the interleaved records are not much different — their held price is the values and the shared table again, 0.94 lines each. The tree has no part of that kind. Every node it reads is on a path from the root, every path from the root shares its first lines with every other, and a listing’s nested queries share their subtrees with each other as well. Its tree region costs 15.0 lines a listing cold and 3.3 held. On a scattered workload the paths go to different leaves, but they still begin at the same root, and the top nine levels are sixteen lines.

That is why the order inverted. A structure whose reads are a descent from a shared root keeps the most of its price in a cache, because its reads are shared by construction. A structure whose reads are a fixed number of lookups at content-determined places keeps what is small and loses what is indexed by content, and where an algorithm looks is the general form of that observation: the picture of an algorithm’s accesses decides what a cache can do for it, and no count of operations contains the picture.

The apparatus that fits #

The scan is the method nobody predicted anything about, and it is the one the cache decides.

Its apparatus is the document array and a bitmap: 32,773 entries of four bits, 257 lines, and one line of bitmap. Every chain carries that same document array — the chain reads it at each answer — and a range structure on top, the overhead two bits a value, and what undoes them found was five times its own payload: the separate arrays 1,965 lines more, the interleaved records 2,161, the tree 4,096. So the scan’s footprint is part of every chain’s, and the smallest of the four by a factor of eight.

And its working set is smaller again. Over the two thousand listings the scan touches 130 distinct lines; the chains touch 922 to 941. A cache of 128 lines holds nearly the whole of what the workload asks the scan for, and from there on a listing costs a hundredth of a line. With 64 lines held it is still under a third of a line a listing, a twenty-ninth of the cheapest chain’s 8.7.

Listing by listing it is no closer. With 64, 256 or 1,024 lines held, no chain misses fewer lines than the scan on any of the two thousand listings, on either workload. A rule that scans below some occurrence count and walks a chain above it, with the count chosen afterwards on this very workload, never walks a chain. The crossing that never arrives reached that conclusion for the cold price on these twelve essays; a held cache makes it more true, not less.

The whole corpus #

Twelve essays at 32,773 characters is a small index, and a cache of a few hundred lines is a large share of it. The corpus the collection is cut from runs to 144,617 characters — the same twelve essays, uncut — and the same workload on all of it puts every footprint four or five times further past the caches.

Cold, a listing now costs the tree’s chain 20.4 lines, the separate arrays’ 18.8, the interleaved records’ 16.1 and the scan 4.3. With 256 lines held they are 9.1, 11.9, 9.3 and 0.18: shares of 45%, 63%, 58% and 4%. The separate arrays are again the chain that keeps least, and by a wider margin.

The small directories stop being small. At 144,617 values the rank directory is 110 lines and the select samples 84, and held at 256 lines they cost a listing 0.67 and 0.60, where on the cut collection they cost 0.16 and 0.11. The part every query shares is resident only while it is a small fraction of the cache, and it grows with the array while the cache does not. The shared table grows to 400 lines and costs 3.8 a listing held. The tree’s top nine levels are still eighteen lines, because a tree four times the size is two levels deeper, not wider at the top.

The scan’s document array is 1,131 lines here, four and a half times the cache, and it still misses 0.18 lines a listing at 256 and 0.03 at 1,024. Words that are asked for often have their rows resident; words asked for rarely have few rows. On the distinct-word workload with 1,024 lines held, exactly one listing in two thousand finds a chain cheaper than the scan. No other combination of collection, workload and cache finds any.

What the resident part decides #

The question the earlier essay left was whether a structure’s resident part — the part every query shares — decides its price in a running index, rather than anything one query measures. It does, and the answer reaches further than the three range structures it was asked about.

Within the chains, the resident part decides the order. The tree’s resident part is its top levels, small and shared by every query by construction; the succinct structure’s is its directories, small and shared by every query too, but worth two lines of a fourteen-line price, with the rest read at content-determined places that a held cache helps only in proportion to how often the same word comes back. One query’s cold price ranked the three as interleaved, separate, tree. The held price ranks them interleaved and tree level, separate behind, and the tree keeps the largest share of the three.

Between the chains and the scan, the resident part decides everything. A cache below the reachable set found a lazy automaton’s cost flat across two orders of magnitude of cache and then falling off a cliff at the size of the set of states the input actually reached. The same cliff is here, at different sizes for different methods: about 130 lines for the scan, about 930 for every chain. A running index with a few hundred lines to spare sits past the scan’s cliff and well before the chains’, and that, not the per-listing arithmetic of output sensitivity, decides which listing method it should run.

That is also the frame a list and a block of memory put on graph traversal: the same work in a different layout, and a factor of several in misses that no operation count can show. Here the work is not even the same. The chain does less of it on every listing with more than a few occurrences a document, and pays more on every listing, because what it does is spread across four thousand lines and what the scan does is spread across two hundred and fifty.

What the replay leaves out #

The cache is fully associative and strictly least-recently-used. A real cache of a few hundred lines is set-associative, so two hot lines that map to the same set evict each other; that costs the structures with many small hot regions — the separate arrays most — and hardly touches a scan reading one array.

Each method has the cache to itself. A real index also searches the suffix array and reads the text to find a pattern’s rows, and those reads compete for the same lines. All four methods pay them, but they push hardest on the methods whose working set is largest, so the replay is generous to the chains.

The listings are drawn independently. A real query log has bursts — the same word several times in a minute — which helps every method, and long stretches of unrelated words, which help the method with the smallest working set most.

And there is no prefetcher. The scan reads consecutive lines of the document array and would be credited for it by any processor of the last twenty years, which would make its cold price smaller still; it would not change a held price that is already a hundredth of a line.

Still open: a document array the cache cannot hold #

Every collection measured here has a document array that a cache of a few hundred lines holds most of, so the scan’s held price is close to nothing and no chain comes near it. That is a fact about small indexes. A document array is $n \lceil \log_2 d \rceil$ bits, and on a collection of a hundred million characters it is hundreds of thousands of lines; the frequently asked words’ rows still recur, but a single listing for a common word then reads more lines than any cache holds.

The measurement that follows holds the cache at 256 lines and grows the collection from 144,617 characters to several million, generated from the corpus’s own vocabulary so the word frequencies keep their shape, with listings drawn by occurrence as here. The prediction is that the scan’s held price grows with the occurrences of the common words, since their rows no longer fit, and that a chain first undercuts the scan on a listing when that listing’s rows outnumber the cache — about 32,768 occurrences at 128 entries a line — which a collection of a few million characters reaches for its commonest dozen words. It could fail on the chains’ side: their resident directories grow with the collection too, faster than the scan’s hot rows, and at that size every chain may keep less than a third of its price. The question is whether there is a collection size at which a held cache makes output-sensitive listing worth its apparatus, or whether a running index on any collection is better served by spending the chain’s space on more cache for the scan.