The fading nobody computes

The counter with no window in it gave the reason the decayed family is what gets deployed and left the mechanism as one clause: a decayed counter’s value at any instant is a function of its stored value and the elapsed time, so it can be computed on the way past.

This is that clause, measured.

What eager decay would cost #

Write the structure the obvious way. Every tick, walk the table and multiply each counter by $2^{-1/H}$. Then an arrival is a lookup and an increment, and a query is a lookup, and the value is always current.

The cost is $k$ multiplications per tick, forever, whether or not anything arrived. Over twelve thousand arrivals at a mean gap of ten ticks that is 120,000 ticks × 32 counters = 3,830,256 multiplications, and the number does not depend on the arrival rate at all — a table watching a silent stream does exactly the same work as a table watching a busy one.

That is the property that makes it undeployable. A monitoring system holding a million decayed counters at millisecond resolution would perform a billion multiplications a second to age counters nobody is reading.

The number is worth holding onto because of what is not in it. It does not depend on how many keys are hot, on how bursty the arrivals are, or on how often anybody reads the table. It depends on the table’s size and the clock’s resolution, and both of those are configuration.

An eager structure’s cost is a property of its parameters rather than of its workload, which sounds like a virtue — predictable, easy to capacity-plan — and is the reason it is unaffordable. A cost that does not fall when the system is idle is a cost paid for the idleness.

What lazy decay costs instead #

Store, per counter, the value and the time it was last touched. On an arrival at $t$, fade that one counter by $2^{-(t - \text{last})/H}$, add one, and set last to $t$. On a read at $t$, apply the same fade without the increment and do not store it.

Nothing else is touched. A counter nobody has looked at since the previous half-life is stale in storage and correct on demand, because the correction is a function of the gap.

Measured over the same run: 382,976 fades, a factor of exactly ten fewer.

The ten is not a coincidence and it is worth chasing, because it says what the saving actually depends on. The mean gap between arrivals in that run is ten ticks. An eager implementation does $k$ multiplications per tick; a lazy one does its work per arrival. So the ratio is the number of ticks per arrival, which is the mean gap — and the saving is therefore proportional to how idle the clock is relative to the stream.

Refine the clock and the eager cost rises while the lazy cost does not. At microsecond resolution the ratio would be ten thousand. That is the same asymmetry as the stamp width in the clock that cannot see the burst, arriving in the time domain instead of the space one: an eager structure pays for the instrument’s resolution and a lazy one pays for the stream.

The operation that cannot be lazy #

There is one place the laziness has to be paid back, and it is the operation that makes a table of counters a summary rather than a dictionary.

A bounded table holds $k$ counters and has to evict when a new key arrives. Evicting means finding the smallest — and smallest is a comparison between counters, which is only meaningful at a common instant. Two counters last touched at different times hold values on different scales, and comparing the stored numbers directly is comparing a fresh count against a stale one.

So an eviction fades every counter in the table to now, compares, and evicts. That is $k$ multiplications at one arrival, which is exactly the eager cost for one tick, incurred once per eviction rather than once per tick.

Over the run above there were 11,968 evictions in twelve thousand arrivals — nearly one per arrival, because the stream’s key space is twice the table’s capacity — and those evictions are most of the 382,976 fades. The per-arrival work is therefore not $O(1)$; it is $O(1)$ amortised over arrivals that hit an existing key and $O(k)$ on the ones that do not.

That is what amortised means’s subject applied to a structure that looks like it has no amortisation in it. The lazy decay is genuinely constant-time; the eviction it enables is not, and a description of the structure as constant work per arrival is describing the half of it that the laziness fixed.

Where the eviction rule came from #

The eviction is Space-Saving’s, and the borrowing is worth making explicit because it carries an assumption across a model boundary.

The items that survive k counters established the rule: when a new key arrives and the table is full, evict the smallest counter and give the new key that counter’s value plus one. The value is inherited, so the new key’s count is an upper bracket — it may have arrived up to the evicted counter’s value times before, and the structure charges for that possibility rather than pretending it away.

Under decay the same rule is applied to faded values, and the bracket argument still works: the evicted counter’s faded value is what any unheld key could have accumulated, weighted the same way. So the structure keeps its one-sidedness.

What does not carry across is the bound. Space-Saving’s guarantee is stated in terms of the stream’s total, $n$, and there is no $n$ here — the decayed total is itself a decayed quantity, moving continuously, and it is not a count of anything. So the structure inherits the rule, inherits the one-sidedness, and does not inherit a theorem.

That is not an argument against it. It is the reason the essays in this pair have been careful to say what the decayed counter computes exactly and to make no claim about how far its top-$k$ is from the truth: that quantity has not been bounded here and there is no bound in the literature to borrow.

The rescaling trick, and why it is not free either #

There is a well-known way to avoid fading anything at all, and it is worth pricing because it is the first thing anyone reaches for.

Instead of fading stored values, scale every increment up: an arrival at time $t$ adds $2^{t/H}$ rather than 1. Nothing ever fades, comparisons between counters are correct at any instant without touching either, and eviction is a plain minimum over the stored numbers.

It is exact, it removes the $O(k)$ eviction, and it overflows. The scale factor doubles every half-life, so after 1,024 half-lives it is $2^{1024}$ and a double-precision float has run out at $2^{1023}$. At a one-minute half-life that is seventeen hours.

The repair is to rescale periodically — divide everything by the current factor and reset it — which is a sweep over the whole table, which is the eager cost again, incurred rarely. So the three designs are three points on one trade:

The scaled design is the best of the three on this table and it is the least often implemented, for a reason that is not on the table: the rescale is a correctness-critical operation that runs once every seventeen hours, which is to say it runs in production and never in a test.

What the query costs #

One quantity has been left out and it changes the accounting for a read-heavy system.

A query against a lazy table is not free either. Reading one counter is one fade. Reading the top $k$ — which is what a heavy-hitter query is — is $k$ fades, for the same reason an eviction is: the ordering is only meaningful at a common instant, so every counter has to be brought to now before they can be sorted.

So the structure’s cost is $O(k)$ per eviction and $O(k)$ per top-$k$ query, and $O(1)$ for everything else. On the run measured here, evictions outnumbered queries by a wide margin because the figures query a handful of times and the stream arrives twelve thousand times; a dashboard polling every second against a stream arriving every ten milliseconds has the reverse ratio, and its cost is dominated by reads.

Which means the eager design is not absurd for every workload. A table read more often than it is written should age eagerly, because the eager sweep is paid once per tick and the lazy fades are paid once per read per counter. The crossover is at one top-$k$ query per tick, which is a rate no dashboard reaches and some internal control loops do.

The other forgetting #

Floating point does a second kind of forgetting, and it is not the decay.

A counter faded across many half-lives becomes very small: after fifty half-lives a count of one is $10^{-15}$, after 1,074 it is denormal, and shortly after that it is exactly zero. So a key that has not arrived for long enough has a stored value of zero, and adding one to it produces one — a fresh key, indistinguishable from one that has never been seen.

That is almost always the desired behaviour, and it is worth being clear that it is an accident. The decay says the old contribution should be $2^{-1074}$; the float says it is nothing; the difference is unobservable and the second is what the structure does. The implementation forgets completely where the model forgets asymptotically, and every argument in the counter with no window in it about a decayed counter never reaching zero is a statement about the model.

Where it stops being harmless is the comparison. Two counters both faded into the denormal range are both approximately zero and their ratio — which is what a decayed structure’s comparisons are about — is noise. A table whose keys are all stale is a table whose ordering is arbitrary, and it will still return a confident top-$k$.

What to do about all of it #

Three practical statements fall out, and each is checkable rather than advisory.

Charge the eviction, not the arrival. A decayed table’s cost is dominated by evictions, and the eviction rate is a property of the key distribution against $k$. Sizing $k$ to the number of keys that matter — rather than to memory — turns an $O(k)$-per-arrival structure into an $O(1)$-per-arrival one, and the measurement above says how much: 11,968 evictions at $k = 32$ against a key space of 64.

Bound the staleness. A counter last touched many half-lives ago carries no information, and a table that drops such counters instead of fading them loses nothing and gains a defined floor. The threshold is arithmetic: below $2^{-53}$ of the table’s largest value, a counter cannot affect any comparison a double can express.

And state the resolution the fade is computed at. The lazy saving is the mean gap in ticks, so it is a number a system can compute about itself, and a system whose mean gap is one tick is getting no saving at all — the lazy implementation is doing the eager amount of work with extra bookkeeping.

The shape this belongs to #

It is worth naming the pattern, because this collection has now met it in four fields and the name makes the next instance recognisable.

Do the work when somebody asks, not when the state becomes stale. A dynamic array does not shrink when elements are removed; it shrinks when the ratio justifies a copy. A self-index does not decompress a text; it reconstructs the part that was asked for. A lazy decayed counter does not age; it reports its age-adjusted value when read.

In every case the saving is the ratio between how often the state could change and how often anybody looks, and in every case the cost is a bookkeeping field — a capacity, a sample, a timestamp — that stores the difference between what is written down and what is true.

Here that field is the last timestamp, and it is worth what it costs. It is also the reason a decayed counter’s state has a stamp in it at all, which connects this family back to the bits that say when’s accounting: a decayed table pays for a clock, per key rather than per item, and it pays for it to avoid doing work rather than to decide expiry.

That is a different reason to store a time from any other structure in this collection, and it is the one that makes the family cheap.

The one-line summary for an implementer #

Three numbers decide whether a decayed table is affordable, and all three are known before it is built.

The mean gap in ticks is the factor lazy decay saves over eager. Ten here. Compute it as the clock’s resolution divided into the mean inter-arrival time, and if it is near one there is no saving to be had.

The eviction rate is what turns an $O(1)$ structure into an $O(k)$ one. It is a property of the key distribution against $k$, and sizing $k$ above the number of keys that recur drops it to nearly nothing.

And the top-$k$ query rate is the cost the lazy design does not remove. One query per tick is the crossover at which eager ageing becomes the cheaper design, which is a rate a control loop can reach and a dashboard cannot.

None of those is in the description of the structure, and all three are in the workload.

The crossover is one comparison, and the table size is not in it #

One top-$k$ query per tick is the stated crossover, and writing it out shows that the table’s size cancels — which makes the decision much easier than the three numbers above suggest.

Both designs pay $k$ multiplications at every operation that needs the whole table at a common instant. Lazy pays it once per eviction and once per top-$k$ query. Eager pays it once per tick. So they are equal when

$$\text{evictions} + \text{queries} \;=\; \text{ticks},$$

and $k$ divides out of both sides entirely.

The run confirms it to the unit. There were 11,968 evictions over 119,696 ticks, so the crossover sits at 107,728 queries — which is 0.90 a tick, the one per tick this page quotes, and it is one per tick minus the eviction rate.

So the rule is a single comparison and needs neither the counter count nor the half-life: add the eviction rate and the top-$k$ query rate, both per tick, and age eagerly if they exceed one. Below one, lazily.

That is a smaller thing to compute than the three numbers this page ends on, and it reorganises them. The mean gap is not part of the decision — it explains the size of the saving and not its sign. The eviction rate and the query rate are the decision, they are in the same unit, and they add.

It also says where the surprises are. A table sized generously has almost no evictions, so its crossover is at one query per tick and lazy wins for anything short of a control loop. A table sized tightly against a large key space evicts on nearly every arrival, and if arrivals are frequent relative to ticks its eviction rate alone can approach one — at which point lazy decay is doing the eager amount of work and paying for a timestamp per key to do it. That is the same degenerate case this page names for a one-tick mean gap, arriving through the other term.

And it sharpens what the timestamp is buying. The last field converts a per-tick cost into a per-sweep-event cost, and the conversion is worth exactly the ratio of ticks to sweep events. When that ratio is ten, as here, the field earns its bits many times over; when it is one, the field is pure overhead and the structure would be cheaper without it. A lazy structure’s bookkeeping is worth the ratio between how often the state goes stale and how often anybody needs it whole — which is what amortised means’s accounting with the sweep as the expensive operation, and the reason the counter with no window in it can call the family cheap without qualification only for the workloads where that ratio is large.

What is not established #

One table, one key distribution. Every number here is from a table of thirty-two counters against a key space of sixty-four, which produces an unusually high eviction rate. A table large enough to hold its key space has almost no evictions and the lazy saving is then the full mean gap.

Multiplications are counted, not timed. The comparison is between two counts of the same operation, which is this collection’s convention and which says nothing about cache behaviour — an eager sweep is sequential over a contiguous table and a lazy fade is a random access, and on a real machine that difference could be worth more than the factor of ten.

And the scaled design is priced rather than measured. Its overflow point is arithmetic and its rescale cost is arithmetic. No implementation of it is run here, so the claim that it is the best of the three is a claim about the table above and not about anything that was executed.