The lines a constant-time query lands in

Where a crossing moved to replaced the document listing’s segment tree with the range minimum the method is published with — a parenthesis sequence of two bits a value, answered in a constant number of lookups — and measured what the swap was worth. The listing finds the documents holding a pattern by asking a range minimum over a chain of previous occurrences: twice the answer’s size in queries, plus one, whatever the number of occurrences. Its rival reads every occurrence. Priced in node visits and table reads, the chain had been paying about 25 reads a query to the tree and paid about 10 to the succinct structure, and the point where it overtook the scan moved from 257 occurrences to 86 — from 32 a document to 10.8, on eight documents.

That essay ended by naming the unit it had used and not defending it. A read is one access the structure chose to make. It is not what a machine charges for. The count is not the time is where this collection first separated the two: a processor fetches memory in lines of 64 bytes, a read that lands in a line already fetched costs almost nothing, and a read that lands in a new one costs what a trip to memory costs. Two structures that make the same number of reads can differ by a large factor in lines, in either direction. So the question here is the old crossing asked in the unit the machine bills: how many distinct lines does each structure’s query touch, and where does the listing cross the scan when both are priced that way?

A layout has to be stated before a line can be counted #

A line count is a property of where things sit, so the first thing to fix is a layout, and the one used throughout is the plainest that is faithful to each structure’s own size accounting.

The segment tree is one array of $2n$ nodes in breadth-first order, each node $\lceil \log_2 n \rceil$ bits wide — the width the cost that is the size of the answer charged it. At 32,768 values that is fifteen bits, so a 512-bit line holds 34 nodes, and the root’s line holds the whole of the top five levels.

The succinct structure is the parts two bits a value, and what undoes them weighed it in, each packed at its own width and each starting on a line of its own: the parentheses, the select support’s samples and offsets, the rank directory, the in-block answer table the table that fits inside a block built, the superblock minima and their sparse table, the block minima and the per-superblock tables over them, and the array of values the caller holds. A read of entry $i$ of an array $w$ bits wide lands in line $\lfloor iw/512 \rfloor$ of that array; a read of a run of bits — a block of parentheses, the tail of a rank inside its block — lands in every line the run crosses.

Two choices in that list are charged as the published structure would be, not as the implementation stores them. The excess at a position is not stored in the published structure; it is $2\,\mathrm{rank}_1(t) - t$, so every excess the query consults is charged here as the rank it is — a directory entry and the parenthesis bits up to $t$. And a block’s shape is not a separate array either; it is the block’s own parentheses, so reading it is reading the payload.

Every replayed query is required to return the position the real structure returned, on every query of every measurement below. A replay that drifted from the walk it claims to describe would be counting lines for some other walk, and the check makes that a failure rather than a number.

Two and a half times apart in reads, one in lines #

The first plate is one query, priced both ways, at four array sizes.

In reads the picture is the one where a crossing moved to drew. The tree climbs from 23.3 to 41.7 reads across a sixty-fourfold growth in the array, which is its two logarithms — the descent to the range’s boundary and the descent to the minimum’s leaf. The succinct structure sits at 15.5 to 16.9, flat, which is what a constant number of lookups looks like on random ranges. At 32,768 values they are 2.47 times apart.

In lines the gap is almost gone. At 32,768 values the tree touches 19.8 lines a query and the succinct structure 17.9, a factor of 1.11. Below that the order reverses: at 8,192 the tree touches 15.8 to the succinct structure’s 16.6, at 2,048 it is 11.2 to 14.4, and at 512 it is 6.9 to 11.9. On every array smaller than about twenty thousand values the structure built to answer in constant time touches more lines than the one that answers in logarithmic time. It still grows less: the tree’s lines nearly triple across the sweep and the succinct structure’s rise by half. Somewhere past the largest size measured the constant must win, because a logarithm does not stop. But the size at which a reader would notice is not where the asymptotic reading puts it.

The reason is visible in the ratio of each structure’s two curves. The tree spends 41.7 reads to touch 19.8 lines — about two reads a line — because its reads are concentrated: the top of every descent is the same few nodes, those nodes sit together at the front of the array, and a descent’s last few steps move between siblings that share a line. The succinct structure spends 16.9 reads to touch 17.9 lines, which is more lines than reads, because several of its reads are runs of parenthesis bits that cross a line boundary, and because almost nothing it reads sits next to anything else it reads.

Where the seventeen lines are #

Splitting the succinct structure’s lines by the array they fall in shows why no single improvement fixes it.

No array dominates. The select samples take 1.84 lines a query, the select offsets 1.98, the rank directory 1.91, the parentheses 2.06, the shared table 1.99, the superblock minima 1.56, the superblock table 1.42, the block minima 2.12, the block tables 2.00, and the value at the answer 1.00. Each of the structure’s two selects lands in the samples, the offsets and the parentheses; the ±1 query lands in the parentheses again, the table, two levels of minima and two levels of tables; the final rank lands in the directory and the parentheses. A query’s two endpoints are, on random ranges, far apart, so each of those arrays is visited twice in two different places.

That is the arithmetic of a structure assembled from parts, and it is not a defect of any one part. Every part is small — the whole structure occupies 936 lines at 32,768 values, 1,896 with the array of values it reads its answer from, against the tree’s 2,048 with its values in its leaves — and every part was designed to be small, not to be read alongside the others. The published description calls the query “constant time” and counts it in word operations, which is the right count for the claim being made. It says nothing about how many separate places in memory the constant number of operations are scattered over, and the answer is about as many as there are operations.

The tree, by contrast, is one array, and a descent through one array in breadth-first order spends its first five levels inside a single line. Its weakness is depth, and depth costs lines only at the bottom of a descent, where a node and its children stop sharing a line. The bucket that fits a line made the same observation about a hash table from the other side: a structure whose every operation is two reads still costs two lines only if each read is a line, and laying the reads out together is a separate decision from deciding how many there are.

A stream of queries, and what each structure keeps #

The cold price — every line a miss — is the price of one isolated query. A structure queried continuously keeps what it re-reads, so the second measurement replays a stream of 2,000 random queries through a fully associative cache of lines with least-recently-used replacement, and counts misses.

With no cache at all, every read is a miss, and the plate’s first point is simply the reads: 46.1 for the tree, counting both children at each step of its descent, against 34.7 for the succinct structure. With eight lines the succinct structure still misses fewer, 20.3 against 23.3. From 32 lines the order turns: 14.5 for the tree against 16.8, then 10.0 against 13.0 at 128 lines, and 5.0 against 5.4 at 512. Only when the cache holds nearly all of both structures, at 2,048 lines, does the succinct structure miss less again, because it is slightly smaller.

What the tree keeps is easy to name. Every query passes through the root and most pass through the first ten levels, which occupy a few dozen lines; once those are resident, a query misses only on the lines of its two descents that are deep enough to be specific to it. The succinct structure has no equivalent. Its directories are shared by every query but are each indexed by position, so a query near one end of the array and a query near the other read different lines of every one of them. The only part read by every query is the shared table of in-block answers, and at the block length of eight used here that table is 162 lines — more than a small cache holds, and read at a different entry by almost every query.

This is the regime the layout that is told nothing is about: a cache of some size nobody chose, holding whatever the access pattern makes popular. A structure whose popular part is its top is well served by any cache; a structure that has no popular part is served only by a cache that holds all of it.

The listing, priced in lines #

The crossing is where all of this was supposed to matter, so the third measurement is where a crossing moved to’s own sweep: eight documents of 2,048 characters, a six-character pattern planted at rising density in three of them, the answer fixed at eight documents while the occurrences rise from 32 to 792.

The scan’s price is the lines of the document array it reads. Those are contiguous rows of the suffix array, one document number each, and with eight documents a document number is three bits — so a line holds 170 of them. It also marks each document in a bitmap of eight bits, one line in all. The chain’s price is every line its range structure reads across the whole listing, plus the chain value at each answer and the document it reports.

Neither crossing survives. At 32 occurrences the scan reads 2 lines, the tree’s chain 13 and the succinct chain 12; at 792 occurrences the scan reads 7, the tree’s chain 24 and the succinct one 31. The scan is cheaper at every point of the sweep, by a factor of three or more, and the plate has no crossing on it to mark.

Two things changed at once, and they are worth separating. The scan got cheaper by a factor that grows with the occurrences — at 792 of them, 792 reads became 7 lines — because 170 consecutive reads are one line. The chain did not get cheaper by anything like that. Its eleven or twelve queries are nested inside one range and share many of their lines, but each still reaches arrays and depths the others do not. And the chain’s price, flat in reads, is not flat in lines. It rises from 13 to 24 with the tree and from 12 to 31 with the succinct structure, because a wider range sends the listing’s queries to positions further apart, and positions further apart share fewer lines. The output-sensitive claim — the cost follows the answer, not the range — holds in queries and in reads. In lines it holds only approximately, and the succinct structure, with ten arrays to land in, pays for the spread more than the tree does.

How far the crossing moved #

A sweep that never reaches the crossing cannot say where it is, so the same planting was repeated on documents of 32,768 characters, where a pattern can be planted four thousand times in each of three documents.

The tree’s chain crosses the scan at 7,952 occurrences and the succinct chain at 12,143, interpolated between measured points at 6,419 and 12,552 occurrences. Per document that is 994 and 1,518 — against 32 and 10.8 in reads.

So in lines the swap of range structures moved the crossing the other way. In reads, the succinct structure brought the crossing down by a factor of three; in lines, it pushes it up by a factor of one and a half, because the chain’s line price is set by how scattered its reads are rather than by how many there are, and the succinct structure is the more scattered of the two. The essay that measured the reads was right about what it measured. The unit it measured in was the one that made the structure look best.

The occurrence counts at which either chain wins are not exotic, and the crossing that never arrives listed where they live: a version history, a long book, a log of machine-written records. What changes is the bar. A common word in a book does occur a thousand times. A phrase in a collection of short documents does not, and on a collection whose documents are under a few thousand characters the chain, priced in lines, never pays for itself on any query at all.

The bar, by collection #

The crossing per document depends on two things the eight-document collection fixed: how many documents there are, which sets how many entries the scan gets to a line, and how much the chain’s queries share, which depends on how many of them there are and how close together.

In reads the bar barely moves: the succinct chain needs 8.2, 7.8 and 5.8 occurrences per answered document at 8, 32 and 128 documents, and the tree’s chain about 26 at all three. In lines it moves a great deal: 398, 109 and 50 for the succinct chain, and 284, 73 and 27 for the tree’s. Two effects push it down as the number of documents grows. A document number gets wider — three bits at eight documents, seven at 128 — so the scan’s line holds fewer of them. And the answer gets larger, so the chain’s queries become numerous and close together, and they start sharing lines: at 128 documents the tree’s chain spends a third of a line a query and the succinct chain six tenths.

The order of the two structures does not change. In lines the tree’s chain needs fewer occurrences than the succinct chain on every collection measured, by between 1.4 and 1.8 times.

What constant time was measured against #

None of this contradicts what the succinct structure claims. It answers in a constant number of word operations, and it does: 15.5 to 16.9 across the sizes measured, flat. It occupies close to two bits a value, plus the overhead two bits a value, and what undoes them priced. Both claims are about the structure, and both are true.

What the measurement shows is the position the constant the notation drops describes, one level down. A constant in operations becomes a different constant in lines, and the conversion rate is a property of layout that the operation count does not see. For the tree the rate is about two operations a line, and for the succinct structure about one. At the sizes a document listing runs at, that difference is larger than the logarithm the succinct structure was built to remove.

What O-notation does not say is the general warning, and this is the case where its warning cuts against the newer structure: the asymptotic class is better, the constant in operations is better, and the cost a machine charges is worse until the arrays are larger than any collection measured here.

What the replay leaves out #

The cache model is fully associative with least-recently-used replacement, and real caches are neither. More important for this comparison, real processors prefetch: a scan through consecutive lines is detected and fetched ahead, so its lines arrive before they are asked for. The scan in this essay is charged a full miss for every line it reads, and on a machine with a prefetcher it would cost less than that. Every correction the model leaves out favours the scan, which means the crossings above are low estimates.

The layout is also the plainest one. Each array of the succinct structure starts on a fresh line and is read where it lies; a layout that put each block’s minima, its rank directory entry and its table row in one line would cut the regions plate’s ten arrays to a few. That layout is the published structure’s to choose, and none of its descriptions choose it.

Still open: a layout that puts a block’s parts in one line #

The regions plate is the case for the next measurement. Every one of the succinct structure’s lines a query lands in is in a separate array, but most of them are indexed by the same thing — a block, or the superblock above it. The rank directory entry, the block’s minimum and its offset into the superblock’s table are all read for the same block, and the select sample that lands in a block points into the same parentheses.

The measurement that follows interleaves them: one record per block holding its parentheses, its rank count, its minimum and its in-superblock table row, padded to a line, with the superblock’s parts in a record of their own. The prediction is that a query falls from about 17.9 lines to about 8 at 32,768 values — the two endpoints’ blocks, their superblocks, the shared table, the middle superblock range’s two table rows and the value — and that the listing’s crossing comes back under the tree’s, near 5,000 occurrences on the long collection. It could fail on size: a record padded to a line costs bits the separate arrays did not, and at seven parentheses a block the padding could double the structure. The question is whether a constant-time structure can be made to touch a constant number of lines without giving up the size it was built for.