The bits that say when

Build a cardinality estimator that answers about the last four thousand arrivals rather than about the whole stream, give it two hundred and fifty-six registers, and weigh it. It holds 4,592 bits.

Ask what those bits are for and the answer is: 920 of them are the estimate, 1,280 are a directory, and 2,392 are clocks.

More than half the structure is spent on knowing when things happened. Not on the answer, not on the keys, not on the hash — on timestamps, which are the one part of a windowed structure that nothing in the accuracy parameter touches and nothing in the published analysis mentions by name.

What was being counted, and what was not #

Every summary in this collection reports bits(), and every one of those numbers is computed from the shape of the structure rather than measured off a language runtime’s objects — a hash map of eight entries does not occupy the bits reported for a Misra-Gries table with eight counters and never could. That convention has held since the field opened, and it is the right one.

What it cannot do is show what the bits are for. A total of 4,592 is consistent with any story about where they went, and the story turns out to be the interesting part.

So each structure here answers a second question. stateParts() returns named components; the total is required to equal them summed, checked on every call and on every build; and the names are fixed across the family so that a reader learns them once:

• payload — bits spent on the answer. Registers, counters, stored values, codes.
• stamps — bits spent on knowing when, and on nothing else.
• keys — bits spent on knowing which item. Kept apart from the payload because a counter-based structure is mostly keys and a register-based one has none at all.
• directory — lengths, offsets, bucket counts: the bookkeeping that is neither the answer nor the time.

An earlier structure in this collection already paid the third of these and did not say so. The exponential histogram from the summary that has to forget stores a timestamp per bucket and adds it into its reported size beside the bucket’s exponent. The arithmetic was correct and the finding was hidden, because a total cannot show that one of its terms is the majority of it.

A stamp costs the logarithm of the window, plus one #

The width is not a free choice and it is not thirty-two bits either.

A structure in this model expires an entry by comparing its stamp against $t - W$. For that comparison to be right the stamps have to stay in order across a wrap, and the smallest counter that does is one modulo $2W$: $\lceil \log_2 2W \rceil$ bits. Charging $\lceil \log_2 W \rceil$ instead would be charging for a structure that expires the wrong arrivals once per window.

Seven bits at a window of sixty-four, thirteen at four thousand, seventeen at sixty-five thousand. Against a HyperLogLog register of five bits, that is between one and a half and three and a half times the thing it is attached to, at every window length anybody uses.

A real system storing an epoch millisecond in sixty-four bits is spending far more than this, and saying so would be a different essay. What is charged here is what distinguishing the arrivals in a window costs, which is the smallest honest number and the one a bound would be stated in.

The accuracy dial does not trade against the clock #

The interesting property is not that the stamps are large. It is that there is no setting at which they can be made smaller.

Raise the register count and the answer gets better; the payload grows, and the stamps grow with it, in exact proportion, because both are charged per live entry. There is no configuration of this structure in which knowing the answer better is paid for by knowing the time worse.

The share does drift downwards across the sweep, from 64% to 52%, and the reason is the third band rather than the second: the directory is a length per register whether that register holds anything or not, so it grows linearly in $m$ while the entries do not. That is a real effect and it is not the clock getting cheaper. Both assertions are made on every build — that the stamps exceed the payload at every setting, and that raising the payload never lowers the stamps — and the second is the one that could fail.

There is one more thing the second assertion protects, and it is the reason it is written as a comparison between consecutive settings rather than as a claim about the ratio. The ratio between the stamps and the payload is 2.6 at every register count for a trivial reason — thirteen over five, fixed by the two widths — so asserting that would be asserting arithmetic. What is not arithmetic is that both quantities are charged per live entry, and a structure that had found some way to keep fewer clocks than candidates would break it.

Three ways to pay, and each structure picks one #

Four structures on the opening plate, answering questions about the same window, and the accounting separates them more sharply than their sizes do.

The ring buffer pays keys and nothing else. Keeping the last $W$ arrivals is the structure with no cleverness in it, and it needs no clocks at all: position in the buffer is the time. 131,072 bits, every one of them a key, and it is the only structure here whose stamps are genuinely zero rather than small.

A stamp per live key pays both, roughly two to one. The smallest exact distinct-counter is a map from each key to the position of its most recent arrival — nothing older matters, because a key is in the window exactly when its last arrival is. 8,775 bits: 6,240 of keys and 2,535 of stamps, 29% of the structure. This is the honest denominator for anything the approximate structures claim.

A block of summaries pays almost no stamps at all. Cut the window into eight blocks, give each its own Misra-Gries table, and drop a block whole when its last arrival leaves. There is one stamp per block rather than per item — 117 bits of the 18,549 — and what it buys is coarseness: the answer is about between $W$ and $W + W/8$ arrivals and the structure cannot say which. The clock got cheap by being consulted eight times instead of four thousand.

And the register-list pays more clock than answer. 4,088 bits, half of them stamps.

Why the cardinality estimator is the extreme case #

The structure spending most on clocks is the one whose payload is smallest, and that is not a coincidence — it is the whole shape of the thing.

A HyperLogLog register holds one number: the largest $\rho$ any key hashing there has produced, where $\rho$ is the position of the first one-bit. Five bits, because $\rho$ is at most about twenty-five and rarely above ten. That extreme compression of the answer is why the estimator works at all.

Over a window that one number is not available, because the largest $\rho$ may have arrived and left. So the register becomes a list: every arrival that has not yet been made irrelevant by a later one.

Chabchoub and Hébrail introduced this in 2010 and call it a list of future possible maxima. What the accounting adds is where the bits went. The structure that replaced a number with a list did not mostly buy a list — the lists are short, two or three entries on ordinary data — it mostly bought clocks, because each entry needs one and each is nearly three times the width of what it is attached to.

What this does to a comparison #

Two structures answering the same question over the same window, one exact and one approximate, and the sizes are 8,775 and 4,088.

A factor of two, for an answer that is wrong by a few per cent. In the model where nothing expires the same estimator against the same exact structure is a factor of thirty-nine. That collapse is the next essay’s subject, and the accounting above is most of the explanation: the exact structure sheds keys when they leave, and the approximate one gains clocks it did not need.

What a block buys, and what it costs #

The block structure is the one that escapes the clock, and it is worth being precise about what it pays instead.

At one block the structure is a Misra-Gries table over the last $W$ arrivals plus however many have accumulated since the block began — up to $2W$, so the answer can be about twice the window asked for. At thirty-two blocks the slack is down to 128 arrivals and the state is 16.5 times larger, 8,218 bits against 135,597. The measured error on the three heaviest keys falls from 42% to 5% across that sweep, and the reason is both effects at once: more blocks means less slack and also more counters in total.

A stamp per block is a coarse clock, and coarse is exactly what makes it cheap. That is the general shape and it is worth stating on its own, because it is the design decision every windowed structure makes: how finely does the structure need to know when things happened, and what does it give up by knowing less?

• A ring buffer knows to the arrival, and pays with the arrivals themselves.
• A stamp per key knows to the arrival, and pays a clock per key.
• A register-list knows to the arrival, and pays a clock per candidate maximum.
• A block knows to the block, and pays with an answer that is about the wrong number of arrivals.

The clock bill is a headcount, not a width #

Two facts from the sections above are worth putting together, because together they say where the only available lever is.

The width of a stamp is $\lceil\log_2 2W\rceil$ and there is nothing to be done about it: it is the smallest counter that orders correctly across a wrap, and charging less would be charging for a structure that expires the wrong arrivals. Thirteen bits at a window of four thousand, and seventeen at sixty-five thousand — a range of four bits over a factor of sixteen in window length.

So the clock bill is the number of stamped entries times a number that barely moves. It is a headcount rather than a width, and every design decision that reduces it is a decision about how many things the structure keeps stamped:

• a ring buffer stamps nothing, and keeps $W$ arrivals;
• a stamp per live key stamps one thing per key in the window;
• a register list stamps one thing per candidate maximum, which is about two per register;
• a block stamps one thing per block, and there are eight.

Read down that list and the clock costs fall by orders of magnitude while the structures get coarser about time — and the coarseness is what is actually being bought. The block structure’s answer is about somewhere between $W$ and $W + W/8$ arrivals precisely because it stamped eight things instead of four thousand.

That reframes the accuracy sweep as well. Raising the register count raises the clock bill because it raises the number of live entries, not because anything about time got more expensive. A structure cannot buy a cheaper clock; it can only decide how many clocks to own, and every windowed structure in this field is a different answer to that question wearing different clothes.

The same split, in a field with no clock in it #

The division this essay draws — bits that hold the answer against bits that locate it — is not about time, and the strongest evidence for that is that the same accounting has already produced the same finding somewhere with no clock in it at all.

A compressed self-index spends its bits on a transform, a rank directory and a set of sampled positions. The samples are not the answer to anything; they exist so that a row of the sorted rotations can be turned into a place in the text. They are bits that say where, and in a run-length index over a repetitive collection they turn out to be half the structure — with the same signature as the clocks here: they do not shrink when the answer-carrying part does, so making the payload small makes them the majority.

Set the two side by side and the pattern is the same twice:

Two fields, two structures with nothing in common, and in both the term that dominates is the one that answers which position rather than what value. In both, it is absent from every published statement of the size. And in both, it became the majority precisely because somebody succeeded at compressing the other half.

So the general form is not “clocks are expensive”. It is that a structure has bits that carry its answer and bits that carry an address into whatever the answer is about, that the second kind is governed by the logarithm of the address space and by how many addresses are kept, and that the second kind is what nobody counts. Naming it once per field, as this essay does for time and that one does for position, is the only thing that has ever made it visible.

What is not measured here #

A clock that is not a counter. Every stamp above is a position in the stream, and the model is a count-based window: the last $W$ arrivals. A time-based window — the last thirty seconds — needs a stamp whose width is set by the clock’s resolution and the window’s duration rather than by the arrival rate, and the two coincide only when arrivals are evenly spaced. Nothing here measures that, and the arithmetic would be different rather than merely larger.

The cost of comparing them. Expiry is a comparison per stored entry per arrival in the worst case, and the structures here are counted for the state they hold rather than for the work they do maintaining it. That is the same choice this collection makes everywhere — a count and a size are different resources — but it is worth saying, because a structure that is small and re-scans its whole state on every arrival is not obviously the better one.

Compressed stamps. The entries in a register’s list arrive in increasing order of time, so the differences between consecutive stamps are smaller than the stamps themselves and could be coded as such. That is a real saving and it is not taken here, because taking it would make the reported size a property of an encoding rather than of the structure — the same reason the sizes throughout this collection come from a structure’s shape and never from a serialisation.

And a share is not a ranking. The plates above say what fraction of each structure is clocks, and a reader looking for a recommendation will be tempted to read a low fraction as a good design. It is not one: the ring buffer’s share is zero and it is the largest structure on the plate by a factor of thirty, because it pays for time by keeping every arrival rather than by keeping a clock. A structure spends nothing on stamps either by being coarse about time, like the blocks, or by being exhaustive about data, like the buffer. The share is a description of where a structure’s bits went, and the totals beside it are what a choice would actually be made on.

The point of naming a resource is that it can then be traded. Four structures here spend between 0% and 64% of themselves on knowing when things happened; before the split existed, all four were simply bits, and the one that spends the most was the one being recommended as the small option.