The table that fits inside a block

Two essays ago a range minimum became a question about a parenthesis sequence, and one essay ago that sequence acquired a bill. Neither has yet answered a query. The rule says find the rightmost lowest point of the excess between two positions, and finding the lowest point of a range is a range minimum — which is the problem that was being solved.

The circle is broken by one property of the new problem that the old one did not have. The excess moves by exactly one at every step, and a sequence with that property has only so many shapes.

What a block is #

Cut the sequence into blocks of b positions. Inside a block the excess is decided by two things: where it started, and which of the b parentheses are openings.

The starting value shifts every excess in the block by the same amount, so it cannot change where the minimum is — only what the minimum is worth. So the position of the lowest excess between two offsets inside a block depends on the block’s bit pattern and on nothing else.

A block of b parentheses has 2^b patterns. Inside each there are (b+1)(b+2)/2 pairs of offsets to ask about. Every one of those answers is an offset, which fits in ⌈log₂(b+1)⌉ bits.

At b = 6 that is 64 patterns, 28 questions each, and 1,792 answers of four bits: 9,408 bits, computed once.

It is worth pausing on how strong that statement is. Every question about every arrangement of six parentheses has already been answered, for every sequence anyone will ever build at this block length, in nine thousand bits. Nothing about the data is consulted, because the data cannot affect the answer: two sequences whose fourth block happens to have the same six parentheses get the same offset back, and both are right.

That is the difference between this and the structures above it, and it is why the phrase “the table” is doing so much work in accounts of the method. The table is the part that does not scale with the input at all.

Why the block length is half a logarithm #

The table is exponential in b, so b cannot be large. The queries inside a block are answered in one lookup whatever b is, so b should not be small — a shorter block means more blocks, and more blocks means a larger structure above them.

The choice that balances these is b about half a logarithm of the sequence’s length, because then 2^b is about the square root, and a table of √N entries is o(N) by a wide margin. At sixty-five thousand values the sequence is 131,072 parentheses, half its logarithm is eight, and 2⁸ is 256 — a table of a few tens of thousands of bits against a payload of a hundred and thirty-one thousand.

Get that wrong in the obvious direction and the structure stops being succinct without anything in the code saying so. A block length of thirty-two would make every question inside a block one lookup and the table 4 billion entries. Nothing about the query changes; the structure has simply become larger than the machine.

The table belongs to the block length, not to the structure #

This is the only term in this strand that is not a property of the data.

The table is indexed by a bit pattern. It knows nothing about which sequence produced that pattern, so two range minima built at the same block length answer their in-block questions out of the same table. A collection holding a hundred of them — a document index per shard, say — pays 9,408 bits in total, not 940,800.

Charging it to a single structure makes one structure look worse than it is. Not charging it at all lets “constant time” be bought with an exponential table nobody mentions. So every plate here prints it beside the total and sums it into none of them, and the checks require that two structures of the same block length report the same figure and be holding the same table — a per-structure table would be correct, would change no answer, and would quietly make the o(N) claim false.

There is one more reason to keep it separate, and it is about honesty rather than accounting. The table’s size depends on b and b depends on the logarithm of the sequence’s length, so the table grows in steps: it is one size for every sequence between four thousand and sixteen thousand parentheses and a different size above that. A term that jumps like that is a term whose contribution to a growth curve is meaningless, and averaging it into a per-value figure would produce a line with steps in it that no reader could interpret.

The convention the table has to be built to #

A general-purpose range minimum returns the leftmost of several equal minima, because that is the convention almost everything else uses and because the shape a range question is about needs the leftmost minimum of the array.

The table here returns the rightmost minimum of the excess, and the two are not in conflict — they are the same requirement seen through the rule. The rule says the answer is the opening where the excess was last at its lowest, so a table that returns the first such point returns a different opening: a real position, inside the range asked about, which is not the range’s minimum.

Building the table the other way is a two-character change, and it is kept in the checks as a case that must be rejected. It gets 211 of 2,997 ranges wrong — about one in fourteen — and only where the excess reaches its minimum twice inside one block of six. The top-level rule still compares the three candidates it always compares and still takes the rightmost of them, so nothing about the query’s shape reveals it.

That is the same failure mode the leftmost-rule rejection has one level up, and having both is deliberate: a convention that has to hold at two levels can be broken at either, and a check at one level says nothing about the other.

The rejection is also a reminder of why the rule was checked exhaustively before anything was built on it. A convention that is only implicit — “the minimum” — is a convention that two pieces of a structure can hold differently, and neither piece is wrong on its own. The invariant that was wrong for seven years is this collection’s longest-running example of exactly that shape.

What a query actually touches #

With the table in place a query is a fixed sequence of lookups, and it is worth writing the list out because “constant time” hides how many.

The two endpoints’ openings are found by two selects. Their positions fall in two blocks. If those are the same block, one table lookup finishes it. Otherwise: a table lookup for the partial first block, a table lookup for the partial last block, and a range over the whole blocks between them.

That last range goes through both layers. If the whole blocks lie inside one superblock, one lookup in that superblock’s own table. Otherwise a lookup in the first superblock’s table, one in the last’s, and one in the table over the superblock minima — then a read of each candidate’s stored minimum to compare them.

Nine or ten memory accesses, against a segment tree’s descent of two logarithms. Measured over eighty random ranges at each of four sizes: the tree reads 41.7 entries a query at thirty-two thousand values and the succinct structure reads 16.8, and across a sixty-fourfold growth in the array the tree’s figure rises by 1.81 and the succinct structure’s by 1.09.

The unit, and why it is stated every time #

A node visit in a segment tree and a table lookup in a block are not the same act. One follows a pointer into an array of minima and compares; the other computes an index and reads. Calling both “an operation” is a choice, and this collection’s convention since the operations a candidate count leaves out is that a comparison must say what one act is on each side.

Here the unit is a memory access the structure decided to make. Neither figure is a duration and neither is a machine instruction — the count is not the time is the essay about the gap between those, and it applies with full force: the succinct structure’s accesses are scattered across four arrays and the tree’s are a descent with good locality, so a modelled cache would not rank them 41.7 to 16.8.

What the measurement does establish is the shape: one figure rises with the array and the other does not. That is the claim the structure is built to support, and it is the claim the unit can carry.

The same care is why two bits a value, and what undoes them reports bits from a structure’s shape rather than from what a language allocates, and why one run, four counts, four answers exists at all: a measurement is a number and a statement of what was counted, and the second half is the part that travels.

The excess, drawn once at the size the table sees #

It is easy to lose track of how small a block is. Six parentheses is three array positions on average — the excess goes up once and down once per node — so a block is a handful of tree nodes, and the table is answering questions about a fragment.

Everything interesting therefore happens above the block level, which is where the previous essay found the whole of the overhead. The table is 9,408 bits and is shared; the structures above it are 651,800 bits and are not.

That inversion is worth carrying, because the block table is the part of this construction that gets the attention. It is the clever bit, it has a name, and it is the thing an account of the method spends its space on. It is also, by a factor of seventy, the part that costs least.

What the four-Russians idea is actually doing #

The technique — enumerate every small input, answer it in advance, replace computation with a lookup — is old and appears in three places in this collection under three names. It is worth naming what it needs, because the requirement is stricter than “small inputs”.

It needs the answers to depend on less than the input does. Here the excess inside a block depends on the starting value and the pattern; the position of the minimum depends on the pattern alone. That is the whole trick, and without it there would be 2^b patterns times as many starting values as there are excesses, which is not a table.

The same requirement is what makes the packed-word table in a column computed in machine words work and what a naive attempt at it gets wrong: the answers have to be a function of the part of the input that is small.

The block minima, which are not free either #

Between the table and the two layers above it sits an array nobody talks about: one minimum per block.

There are N/b blocks, and each stores its minimum excess. Stored as a position in the whole sequence that is ⌈log₂ N⌉ bits an entry, and N/b entries of ⌈log₂ N⌉ bits is about 2N — the payload again, in the term that was supposed to be small.

The fix is the one the two-layer construction already uses for its tables: store the minimum as an offset within its superblock rather than as an absolute value. A superblock spans b·log₂ N positions, so an offset inside one fits in about log₂ log₂ N bits, and the array falls from 2N to a few tenths of N. At sixty-five thousand values it is 147,000 bits — a fifth of the overhead, and the second-largest term after the within-superblock tables.

It is the same trick as the tables and the same trick as rank is the only thing it does uses for a rank directory: a two-level decomposition exists so that the lower level’s entries can be relative, and the saving is entirely in the width of an entry rather than in the number of them.

The same idea, at three sizes, in three places #

It is worth noticing how often this collection has reached for the same move, because the pattern is more general than any of its instances.

A rank directory cuts a bit vector into blocks and stores a count per block, so a rank is a stored count plus a short scan. A sampled suffix array keeps one position in every thirty-two, so a locate is a stored position plus a short walk. And this table answers every question about a block in advance, so an in-block range minimum is a lookup and no scan at all.

All three replace work proportional to something large with work proportional to something small plus a stored answer, and all three pay for it in a term that is a fraction of the payload. What separates this one is the direction of the exponential: a rank directory’s cost is linear in the number of blocks, and this table’s is exponential in the block length. That is what pins the block length to half a logarithm and what makes the choice load-bearing rather than a tuning parameter.

The 1.09 is a mixture, and it says the ceiling has been reached #

Two growth figures sit beside each other — 1.81 for the tree and 1.09 for the succinct structure, across a sixty-fourfold growth in the array — and only the first is what its shape predicts.

The tree’s is. A descent costs two logarithms, and $\log_2 32768 / \log_2 512$ is $15/9 = 1.67$ against a measured 1.81, the excess being the constant work at each end of the descent. Nothing surprising: the tree grows because its depth does.

The succinct structure’s 1.09 is more interesting because a genuinely constant-time query would give 1.00, and nine per cent over six doublings is small enough to wave at and large enough to have a cause.

The cause is a mixture rather than a growth. The query’s path has a fixed maximum — two selects, two partial-block lookups, three superblock-level lookups and a handful of candidate reads — but a range that happens to fall inside a single block short-circuits to one lookup. On a short array with blocks of five, a fair share of random ranges are short enough to do that; on a long array with blocks of eight, almost none are. So the mean rises as the cheap case becomes rare, and it rises towards the full path rather than without limit.

That reframes what the measurement establishes. The claim is not that the query is constant; it is that the query is bounded, and the mean at thirty-two thousand values — 16.8 reads against a full path of seventeen or eighteen — says the mixture has nearly finished shifting. There is very little cheap case left to lose, so the next six doublings should move the figure by a per cent or two rather than by nine.

Which is a prediction the sweep can be extended to check, and it is a different kind of claim from the one the plate makes. A curve rising by 1.09 over the measured range is consistent with a slow growth and with a saturation, and the two disagree completely about what happens next — a limit is not a prediction in its usual form. What separates them here is not the fit but the mechanism: the path’s length is a fixed list of lookups, and a mean cannot exceed its maximum.

It also sharpens the essay’s own caution about the crossing. A constant number of lookups is nine or ten of them is the warning; the mixture says the figure a reader should carry is the ceiling rather than the mean, because the mean is a statement about the range of array sizes that was swept and the ceiling is a property of the construction. At sixteen-point-eight against a ceiling of about seventeen those are nearly the same number, which is convenient and is not something the plate says.

So the two structures’ figures are not the same kind of quantity at all. The tree’s 41.7 is a mean of a distribution whose whole shape moves with the array; the succinct structure’s 16.8 is a mean that has converged on a fixed maximum and will stay there. Where a crossing moved to compares them at one size, and the reason the comparison holds at larger sizes is this asymmetry rather than the ratio measured at any one point.

What this leaves #

A structure that is 2.85 times smaller than a segment tree and answers a query in a fixed number of reads whatever the array’s size. That is the whole of the machinery, and the strand’s last essay is what it does to the method it was built for.

The prediction on record is that it would move the document listing’s crossing “from thirty-one occurrences per document to a handful”. Where a crossing moved to is the measurement, and the two halves of this essay say in advance why the prediction is optimistic: a constant number of lookups is nine or ten of them, not one.