Series

Decay — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. decayedwindowed060120secondscount attributed to key 0half-life 4 s · window 5.77 s · burstythe same key, two questions

    The counter with no window in it

    A counter that fades by half every H settles, on a steady stream, at exactly the count of a window of 1.44H. That correspondence holds in the mean, on a steady stream, and nowhere else — and it is the reason a decayed counter is not an estimate of a windowed count for any window.

    part 1 · streaming
  2. fades a lazy table computed382,976fades an eager table would compute3,830,256fade multiplications (log scale)11,968 evictions, each comparing all 32 counters at one instant32 counters · half-life 4 s · bursty10× fewer

    The fading nobody computes

    Twelve thousand arrivals into thirty-two decayed counters cost 382,976 fade multiplications. An implementation that aged every counter on every tick would have cost 3,830,256, and the ratio is exactly the mean gap between arrivals — not a coincidence, and the reason the family is deployable.

    part 2 · practice
  3. 00.2500.5000.7501010203040age of an arrival, secondsweight it carries nowexponential, half-life 4.0 sbackward polynomial, α = 2, scale 4.0 sforward, β = 2, landmark 20 s backforward, β = 2, landmark 160 s backdotted: half weightweights at the moment of reading

    A decay measured from where it started

    An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.

    part 3 · streaming

All series