What a window costs in bits

An exact count over a window of $W$ arrivals needs $W$ bits and there is a proof of it. An exponential histogram accepting a relative error of $\varepsilon$ needs about $\frac{1}{\varepsilon}\log^2 W$ bits. The second grows more slowly than the first, so for a large enough window the approximation wins by an arbitrarily large factor.

This essay is about how large, and the answer is larger than anybody would guess from the asymptotics.

The crossings, measured #

The first window length at which the summary is smaller than the window, per tolerance:

A 2% tolerance does not pay for itself until the window holds six thousand arrivals, and even there the saving is 11%. To get a factor of two the window has to reach about thirty thousand.

This is not a defect of the structure. It is the ordinary situation whenever an asymptotically better method carries a larger constant, and this site has recorded it four times already: insertion sort wins below a threshold, the external-memory advantage arrives at a cliff, the bit-parallel column loses below a pattern of fifteen characters, and a bound is not a prediction. The shape recurs because it is what “asymptotically better” means and not what it is usually heard to mean.

Where the bits actually go #

Each bucket stores two things: a timestamp saying when its most recent arrival came, and a size, which is a power of two and so is stored as an exponent.

At $W = 1{,}000$ the timestamp needs $\lceil \log_2 2W \rceil = 11$ bits and the exponent needs 4 — sixteen possible sizes is more than enough. Fifteen bits per bucket, of which 73% is the timestamp.

That proportion is the whole explanation for the crossings above. The exact structure spends one bit per slot of window, which is the cheapest possible way to store a bit. The summary spends fifteen bits per bucket, and it needs fifty-four buckets at this setting, and $54 \times 15 = 810$ is only slightly under 1,000.

The asymptotic advantage is in the number of buckets and the constant is in what a bucket costs, and at the sizes people actually use, the constant is in charge.

The number of buckets grew by 57% while the window grew eightfold, which is the logarithmic behaviour working exactly as advertised. It simply started from a long way behind.

The exact structure costs W bits only if somebody packs it #

There is a large asterisk on the dashed line in every plot here, and it moves every crossing.

“$W$ bits” assumes the window is stored as a bit vector — one bit per arrival, packed. That is what the floor says is necessary and it is achievable, and it is not what most implementations do. A circular buffer of booleans in a typical runtime is a byte per slot; one of integers is four or eight. At a byte per slot the exact structure costs $8W$ and every crossing moves left by a factor of eight:

So the honest statement of the comparison depends on an implementation detail of the baseline, and the factor of eight between two reasonable baselines is larger than the factor between the two structures at most of the sizes measured. A comparison against “keeping the data” is a comparison against a particular way of keeping it, and this site has made that mistake nowhere yet only because the eighth counter reports state from the shape of the structure rather than from the host’s objects, on both sides.

The reason the plots above use the packed figure is that it is the one the floor is about. A crossing against a lazier baseline is a fact about the baseline.

The buckets count ones, not arrivals #

One more asymmetry, and it is in the summary’s favour.

The exact window costs $W$ bits whatever is in it — a window of a million arrivals containing three ones still costs a million bits, because the positions of the three are what must be known. The histogram’s state depends on the number of ones, not on the number of arrivals: it is $k\log_2(N/k)$ buckets where $N$ is the count in the window.

So on a sparse stream the gap widens sharply. At $W = 8{,}000$ with ones at 30% the summary holds 85 buckets; at the same window with ones at 5% it holds far fewer, because there is less to record.

That is the reverse of the usual relationship between a summary and its data, and it is worth naming: this structure is cheap exactly when the answer is small, which is the same output-sensitive shape Ukkonen’s band has in a completely different field. A structure whose cost tracks its answer rather than its input is the one to reach for when the answer is usually small and the input is not.

What could be done about the timestamp #

Three repairs are available and it is worth saying which are real.

Store timestamps relative to the previous bucket. Buckets are in order, so a difference suffices, and the differences are small for the recent buckets and large for the old ones. With a variable-length encoding this is a genuine saving — roughly the entropy of the gap distribution rather than $\log_2 2W$ per bucket — and it is what a production implementation does.

Store the timestamp modulo $2W$. Already assumed here: the field is $\lceil\log_2 2W\rceil$ rather than a global clock, which is why it is 11 bits and not 64. Timestamps older than $2W$ are gone, so wrapping is safe.

Drop the timestamp for all but the oldest bucket. Tempting and wrong: expiry has to be checked against each bucket in turn as the window slides, and a bucket with no timestamp cannot be expired. What can be dropped is precision — a timestamp accurate to within the bucket’s own size is enough, since a bucket of size 32 is already uncertain to within 32 arrivals, and that saves the low bits of the old buckets’ timestamps.

The third of those would bring the fifteen bits per bucket down to about nine for the old buckets, moving the crossings left by roughly a third. It would not change the shape and it would not change the conclusion, which is that this structure is for large windows and there is no arrangement of its constants that makes it the right answer for a window of two hundred.

The other resource this field has spent #

It is worth putting the phase’s structures on one page, because they are measuring different resources with the same unit and the comparison is only meaningful when the question is fixed.

The rows are not competitors and the table is not a ranking. It is here to make one point: the cost of a summary is decided by the set of questions it must answer, and the four questions above differ by two orders of magnitude in what they cost before any structure is chosen. A structure answering about every key costs the most; one answering a single aggregate costs the least; and the windowed one is expensive relative to its question because expiry forces it to keep positional information that none of the others need.

The saving, where it exists #

None of the above is an argument against the structure. At the sizes it is built for it wins comfortably, and the win compounds.

Each doubling of the window adds about 230 bits to the summary and doubles the exact structure, so the ratio doubles too. At a window of a million — which is an entirely ordinary requirement for a metrics pipeline — the summary is a few thousand bits against a megabit.

And the multiplier that makes it matter is the one this table does not show: a real system keeps a windowed count per key, or per endpoint, or per customer. Ten thousand of them at a megabit each is a gigabyte; ten thousand at three thousand bits is four megabytes.

The crossing moves with the stream as well as with the tolerance, and it moves in the direction a capacity plan is least likely to guess. What a histogram keeps buckets for is the ones, so a sparse stream produces a smaller summary while the exact structure stays at $W$ bits exactly.

Several windows at once #

The requirement that actually arrives is never one window. It is the last minute, the last hour and the last day, on the same stream, reported together.

Three histograms is the answer and there is no sharing between them worth having. The coarse one has already merged away the detail the fine one needs, and the fine one cannot answer about a longer window because its buckets are discarded as soon as they leave. So the state is the sum:

Which is still a rounding error against keeping the largest window exactly — a day of per-second arrivals is 86,400 bits packed — and it is worth saying plainly, because the three-structure answer looks wasteful and is not.

The alternative that seems obvious and is not available: keep the longest window’s structure and answer shorter windows from a prefix of it. The buckets in the recent part of a long-window histogram are size one and size two, so the recent detail is there — but the boundary of the shorter window falls inside some bucket, and that bucket’s uncertainty is a large share of the shorter window’s total rather than of the longer one’s. The error for the short query is then governed by the wrong denominator, and it can exceed 100%.

Two of these do not add #

Every other summary named in the table above can be merged. Two HyperLogLog registers combine by taking the larger of each pair, two Count-Sketches combine by adding their cells, and the $F_2$ estimate combines because the sketch is linear in the stream — summaries that add are what make a fleet of machines answerable as one. Each node keeps its own state, and the answer for the whole system is assembled at read time from state that never had to travel in order.

The exponential histogram does not have that property, and the obstruction is the timestamp rather than the counts.

Two nodes summarising one logical stream hold buckets stamped in their own arrival order. Merging them means interleaving the two bucket lists by time, and the interleaving is defined only if the two clocks agree — not roughly, but to within the resolution the timestamps are stored at, which is the eleven bits counted above. Two machines whose clocks differ by a second, on a stream arriving at ten thousand a second, disagree about where the window ends by ten thousand arrivals. The window in the merged answer is then not a window.

Given one clock it still fails, on the invariant. The error bound rests on the bucket sizes being non-decreasing into the past with at most $k$ buckets of any one size; interleaving two lists that each satisfy that gives one that satisfies neither. Restoring it means merging adjacent buckets, and merging two buckets that came from different nodes discards exactly the ordering the interleave was performed to recover.

So the windowed count is the one question in this field that does not decompose across machines. The summary has to be built where the arrivals are ordered, what crosses the network is an answer rather than a state, and the loss of that one node loses the whole window rather than a share of it.

What production systems do instead is move the ordering into the query. Each node keeps a coarse fixed grid — one bucket per second, not an exponential ladder — and the reader sums the intervals inside the window and eats the error on the partial interval at the edge. That is the boundary that hides the burst, chosen deliberately and sized so the edge is a small share of the total. It merges precisely because it has given up the sliding boundary this structure exists to provide, which is the trade stated plainly: mergeability is bought with the window’s own resolution.

The bits are smooth and the work is not #

Every table here measures state, and state is the well-behaved quantity — it moves by a couple of hundred bits per doubling and never jumps. The work per arrival does jump, and a pipeline that sizes its latency budget from the plots above will be surprised by its own tail.

An arrival of a one creates a bucket of size one. If that makes $k+1$ buckets of size one, the two oldest merge into a bucket of size two, which may make $k+1$ of those, and so on up the ladder. The cascade stops at the first size class with room.

The number of classes is the logarithm of the largest bucket, and the largest bucket is about $W/k$ — at $W = 1{,}000$ and $\varepsilon = 0.1$ that is a hundred, so seven classes. One arrival can therefore cost seven merges and the next fifty can cost none. The mean is under one merge per arrival, because a cascade that reaches class $j$ needs $2^j$ arrivals to have set it up, and that is the whole content of the amortised claim: it is the shape amortised analysis exists for, and it is the shape a 99.9th-percentile target does not care about.

The comparison worth making is against the growth factor, because the two look alike and are not. A doubling array’s rare expensive operation costs $\Theta(n)$ — it grows without bound as the structure does, so the cost of the rare event is what the choice of factor is about. Here the rare event costs $\log(W/k)$ merges, which is seven now and ten at a window of a million. The tail is bounded by a logarithm rather than by the size of the structure, so the worst arrival is a small multiple of the average one and stays that way.

That distinction changes what deamortisation is worth. Spreading a doubling array’s copy across the following insertions removes a genuine hazard. Spreading this cascade removes seven bucket merges, and the bookkeeping to do it costs more per arrival than the cascade it smooths. The measured version of the same judgement is elsewhere on the site: the structure paid for before the first query is worth deamortising because the up-front cost is proportional to the input, and this one is not.

One expense genuinely is per-arrival and is easy to miss in the tables. Expiry is checked on every arrival, not on every query — the oldest bucket carries the only timestamp that can retire it, so something must look at it as the window slides. It is one comparison, it never cascades, and it is the reason the timestamp cannot be dropped from the old buckets however tempting the bits look.

The rule this leaves #

Three sentences, and the third is the one worth carrying past this subject.

A structure whose state grows like $\log^2 W$ beats one that grows like $W$, eventually. Where eventually begins is decided by the two constants and by nothing in the asymptotic statement.

So the question “is the approximate structure smaller?” has no answer until $W$ and $\varepsilon$ are both named, and the honest form of the recommendation is a crossing point rather than a preference. This site has now measured five of them — a sorting cutoff, a memory cliff, a pattern length, a band width and a window — in five unrelated fields, and in every case the number was further out than the shape suggested.

One further consequence is worth stating because it is the opposite of the usual advice. When a window is small, the right structure is the array — exact, simpler, smaller, and with no tolerance to choose. The approximate structure is not a safe default that occasionally wastes a little; below its crossing it is worse on every axis at once, and the only thing it has over the array is that it will still be the right answer when the window grows.