Two lines a superblock

The lines a constant-time query lands in priced the succinct range minimum in the unit a machine bills — distinct 64-byte lines — and found its advantage over the segment tree nearly gone. Counted in reads, a query cost the succinct structure 16.9 against the tree’s 41.7 at 32,768 values. Counted in lines, it cost 17.9 against 19.8, and below about twenty thousand values the tree touched fewer. The reason was a plate of ten bars: the succinct structure is assembled from ten arrays — select samples and offsets, a rank directory, the parentheses, a shared table of in-block answers, two levels of minima and two levels of sparse tables, and the caller’s values — and its query reads nearly every one of them, each in a different place. The tree is one array whose top levels share a line.

That essay ended by proposing the obvious repair. Most of those arrays are indexed by the same thing: a position in the parentheses, which belongs to a block and a superblock. Put everything a query reads about one superblock into the same place and the ten arrays become a few records. It predicted that a query would fall from about 17.9 lines to about 8, and that the document listing’s crossing, which pricing in lines had pushed out to 12,143 occurrences, would come back under the tree’s 7,952, near 5,000. It named the way it could fail: padding.

What goes in a record #

The ±1 structure at the centre of the succinct range minimum cuts the parentheses into blocks of eight and groups seventeen blocks into a superblock, so a superblock covers 136 parentheses. Everything a query reads can be sorted by what it is indexed by.

Record A holds what is indexed by position inside the superblock: its 136 parentheses, the number of ones before it, and the minimum of each of its seventeen blocks — 306 bits, in one line. The count of ones replaces the rank directory entirely: a rank is that count plus a population count of the parentheses up to the position, both inside the line already fetched. It also replaces the select support’s offsets: a select now reads a sample naming the superblock its one falls in, and walks forward through the records’ counts to the superblock that holds it.

Record B holds what is indexed by the superblock itself: the sparse table over its seventeen blocks (59 entries of five bits), its own minimum and where it lies, and its column of the superblock sparse table — the entry at every level that starts at this superblock. That is 393 bits, in a second line.

Two things stay where they were. The table of in-block answers that the table that fits inside a block built is shared by every structure of the same block length and is indexed by a block’s shape, not its position, so it has no superblock to belong to. The caller’s values are the caller’s.

The structure is unchanged. The same blocks, the same tables and the same query rule answer every range, and the replay that prices each query is required to return the position the real structure returns; the only thing that differs between this layout and the previous one is where each entry the query reads is kept.

Twelve and a half, not eight #

At 32,768 values a query now touches 12.5 lines, against 17.9 for the separate arrays and 19.8 for the tree. That is a cut of 30%, and it is real, but the prediction was 55%. The interleaved layout passes under the tree between 2,048 and 8,192 values — at 8,192 it is 12.3 to the tree’s 15.8 — where the separate arrays never got clearly under it at any size measured. At 2,048 it is 11.8 to the tree’s 11.2, and at 512 it is 10.9 to 6.9: a small array still favours the structure whose whole top fits in a few lines.

The interleaved layout’s line count barely grows with the array — 10.9 to 12.5 across a sixty-fourfold growth — which is what a constant-time structure was promised to do in operations, now done in lines. What it does not do is reach the floor the prediction assumed.

Why a small array still belongs to the tree #

The left-hand end of the plate is worth reading on its own, because it is where most range minima actually run. A document listing over a collection of a few dozen short documents asks its queries of an array of a few thousand values, and the structures there are tiny.

At 512 values the whole segment tree is 20 lines. Its root’s line holds the top five levels and part of the sixth, the next lines hold the rest, and a query touches 6.9 of the 20 — a third of the structure, read along two paths that share their first several nodes. The interleaved succinct structure at the same size is 55 lines, values included: nineteen superblocks of 55 parentheses at a block length of five, two lines each, a shared table of seven lines and a line of select samples. A query touches 10.9 of them.

The succinct structure’s fixed cost is the number of places it must look, and that number does not shrink with the array. Both ends of the range, the select samples, the shared table at both ends, the block tables and the value are six or seven places at 512 values just as at 32,768; only the sparse table over superblocks, with nineteen superblocks to choose among, is cheaper. The tree’s cost is its depth, and at 512 values its depth is nine, five of which are inside one line. So below a few thousand values the comparison is between a structure that pays per place and has six of them, and a structure that pays per level and has four levels that are not free. The crossing between those two descriptions is somewhere between 2,048 and 8,192 values, and nothing about the structure’s asymptotic description says which side of it a given index is on.

Where the twelve lines are #

The prediction counted one line per superblock the query touches and then forgot how many superblocks a query touches. A range minimum over a wide range reads at least four of them.

The two ends account for 2.85 lines of record A: the superblock holding the range’s start and the one holding its end, each read for its parentheses, its count and its block minima — and occasionally a neighbour, when a select’s walk has to step forward. The middle costs record B 3.88 times: the block tables of the start’s and the end’s superblocks, and then the superblock sparse table, which answers “the smallest superblock between these two” by reading two entries — one in the column of the first superblock of the middle span and one in the column of a superblock a power of two before its end. Those two entries are in two different superblocks’ records by construction; that is how a sparse table works. The winner costs record A of a third superblock, 1.02 lines, because once the middle span has named its smallest superblock the query has to read that superblock’s block minima to find the block. And the shared table costs 1.99 lines, because the in-block answers at the two ends are two entries of a 162-line table indexed by the blocks’ shapes, which are unrelated.

So the floor is not one line per part but one line per place the query has to look, and a range minimum over a wide range looks in five or six places: both ends, two ends of a sparse-table lookup, the superblock it names, and the table. Grouping by position brings everything about one place into one line. It cannot bring two places together, and a sparse table is two places by design.

Two probes are two misses found the same floor for cuckoo hashing: two candidate slots that are independent by construction are two lines however each is laid out, and the bucket that fits a line bought its improvement by making each place hold more, not by making the places fewer.

A stream of queries #

On a stream of random queries the interleaved layout’s advantage is largest where the cache is smallest. With eight lines cached it misses 12.7 lines a query, against 20.2 for the separate arrays and 23.3 for the tree; with 32 lines, 11.5 against 16.8 and 14.5. At 128 lines it has nearly lost its lead over the tree, 9.7 against 10.0, and at 512 it is the worst of the three, 6.0 against the tree’s 5.0 and the separate arrays’ 5.4.

The large-cache end is the price of the layout showing up as misses. A cache of 512 lines holds a quarter of each structure, and what it can keep resident depends on how much of what the query re-reads fits. The interleaved structure, padding included, is the largest of the three at 2,095 lines; the tree’s re-read part, its top levels, is compact. Across the middle of the plate the interleaved layout wins because each query needs fewer distinct lines, and at the right-hand end it loses because each line it keeps carries less of what the next query needs.

Queries that arrive together #

The document listing does not ask random queries. It asks a range minimum over the pattern’s rows, then over the part left of the answer and the part right of it, recursively — so its queries are nested inside one range and land near one another. The next measurement isolates that: batches of sixteen random queries confined to a window of $w$ positions, each batch charged its distinct lines, for windows from 64 positions to the whole array.

In every window narrower than the array, the tree touches the fewest lines: 3.46 a query in a window of 1,024 positions, against 4.25 for the separate arrays and 4.26 interleaved; 1.64 against 2.60 and 2.43 in a window of 256. Only when the window is the whole array — sixteen unrelated queries — does the interleaved layout win, 10.55 against 11.44. Inside a window it is no better than the separate arrays, and at 1,024 positions it is a hundredth worse.

What changed is which sharing counts. An isolated query shares lines only with itself, and grouping by superblock makes it share more. A batch of queries in one window shares lines with the other queries in the batch, and here the separate arrays’ compactness is the asset: one line of the rank directory covers 2,560 parentheses, one line of select offsets covers forty-odd samples, and sixteen queries inside a thousand positions find most of what they need already fetched. A record covers 136 parentheses, which is 68 values, so a window of 1,024 values spans fifteen superblocks and sixteen queries inside it reach most of their records, each a line of its own. The tree shares best of all, because every query in the window descends through the same subtree.

The listing, priced again #

So the listing barely moves. With the interleaved layout the succinct chain touches 22 lines at 441 occurrences and 70 at 12,552, against 26 and 73 with the separate arrays, and it crosses the scan at 11,274 occurrences — against 12,143 before, and still behind the tree’s 7,952. The second half of the prediction, a crossing near 5,000 and under the tree’s, failed outright.

The reason is the batch plate. A listing’s queries are a batch in a narrow window, and the narrower and more numerous they are the more the tree’s shared descent and the separate arrays’ compact directories are worth. The interleaved layout helps most where the listing is cheapest anyway, on its first few wide queries, and helps least on the many narrow ones that make up the rest. The scan, which the crossing that never arrives found already wins on most real collections, reads 170 document entries a line in every layout, and none of this touches it.

What the records cost #

The size result runs in two directions. The interleaved records hold less content than the separate arrays — 10.4 bits a value against 12.0 — because a count of ones in each record replaces two directories outright: the rank directory and the select support’s offsets, which come to 1.5 bits a value here and are most of what select is not rank backwards found a constant-time select costs. And they occupy more, 15.2 bits a value against 12.1, because record A uses 306 bits of its line and record B 393 of its, and the 325 bits left over in every superblock are 4.8 bits a value of padding.

That is a rise of a quarter in what two bits a value, and what undoes them found was already five times the payload, and it is not obviously worth it. The padding could be spent — a larger superblock fills record A, a smaller one empties record B — but each choice moves a different part of the line count, and the superblock size is also what sets the sparse tables’ size. A layout tuned to fill its lines is a different structure from the one measured, and this one is the plainest grouping that fits each record in a line.

The tree, at 32 bits a value, is still more than twice either.

What the layout decides, and what it does not #

The ten-array layout and the two-line layout are the same structure. They answer every range identically, they make the same reads in the same order, and a description of the structure in terms of operations cannot tell them apart. Measured in lines, one costs 30% less than the other on isolated queries, both lose to a logarithmic structure on clustered ones, and the cheaper one is a quarter larger.

That is the position the layout that is told nothing describes from the other side, where the van Emde Boas layout made a search tree cheap at every block size without knowing any of them. Here the layout knows the line size exactly and is tuned for the isolated query, and the access pattern that matters — the listing’s batch of nested queries — is not the one it was tuned for. A heap that keeps its levels in a line found the same shape of result with a different structure: blocking a heap’s levels cut the lines of a sift and made the heap worse at the one buffer size where its blocks were mostly empty.

A layout is a bet on an access pattern. The succinct structure’s description does not choose one, which leaves the choice to whoever builds it, and the right choice for an index serving isolated lookups is the wrong one for an index serving a document listing.

What the replay leaves out #

The cache model has no prefetcher, so neither layout is credited for the sequential walk a select makes through consecutive records, and the scan is not credited for reading consecutive lines of the document array. A real processor would make the scan cheaper and the interleaved select’s walk slightly cheaper, and neither change would move the order of the results.

A population count inside a line is charged nothing beyond the line. It is one or two instructions on any processor built in the last fifteen years, but it is still an operation the separate arrays’ rank did not need for the part its directory covered.

Still open: what a structure keeps between listings #

Every listing here is priced cold: each distinct line it touches is one miss, and a line it touches twice is fetched once. That is already the most generous price a single listing can have — no cache of any size could make one listing cheaper than its distinct lines — so the next question is not inside a listing but between them. An index answering document queries answers thousands of them, one pattern after another, and what matters is what each structure still has in cache when the next pattern arrives.

The measurement that follows runs a workload of listings for patterns drawn from the collection’s own vocabulary, through an LRU cache of a few hundred lines held across the whole workload, and charges each listing its misses. The prediction is that the separate arrays gain most: at 32,768 values their rank directory is 25 lines and their select samples 16, small enough to stay resident across listings, so a listing would pay only for its parentheses, its tables and its values — about half its cold price — while the tree keeps its top levels and the interleaved records, which mix what every listing needs with what only this one does, keep least. It could fail on the vocabulary: patterns drawn from real text land all over the suffix array, and a cache of a few hundred lines may hold nothing a scattered workload re-reads. The question is whether a structure’s resident part — the part every query shares — is what decides its price in a running index, rather than anything a single query measures.