The tuples a summary does not report

Asked how large it is, a Greenwald–Khanna summary answers truthfully about a moment nobody asked about.

At $\varepsilon = 0.01$ over twenty thousand values it reports seventy-seven tuples. Watch the same object through the same run and the largest it ever gets is a hundred and thirty-six. Neither number is wrong. The first is the size just after a compression, which is when anybody thinks to ask; the second is the size just before one, which is when the allocator finds out.

This site has run into the same shape twice before. In-place is a claim found that quicksort’s “sorts in place” is a statement about the array and not about the $\Theta(\log n)$ of recursion frames beside it, and the stack nobody counts put a number on those frames. Both were cases where a structure’s honest footprint is somewhere the structure does not look. This is a third, and it is the cleanest of them, because the gap is not an implementation detail — it is a stated parameter of the algorithm being spent in a currency the algorithm does not report.

Where the gap comes from #

Between two compressions the summary is a list that only grows. Every arrival splices in a tuple with $g = 1$; nothing is removed until the compression pass runs.

So over a period of $P$ updates the list gains $P$ tuples, most of which the next pass will merge away. The peak is the resident size plus that backlog:

$$\text{peak} \;\approx\; |S| + P$$

and with the prescribed schedule $P = \lfloor 1/2\varepsilon \rfloor$, and with the structure’s own bound $|S| \approx c/\varepsilon$ at a measured $c = 0.77$, the ratio is

$$\frac{|S| + P}{|S|} \;=\; 1 + \frac{1}{2c} \;\approx\; 1.65$$

free of $\varepsilon$ entirely. Measured across a twenty-five-fold range of tolerance it comes out 1.93, 1.92, 1.77, 1.78 and 1.70 — above the arithmetic, and above it for a reason the next section is about.

Why the measured ratio is above the arithmetic #

The identity $\text{peak} = |S| + P$ would hold if no tuple ever merged except during a compression pass. Tuples do merge between passes — not through the pass, but through the insert, which computes a new tuple’s $\Delta$ from the cap at its own rank and can give it a band wide enough that the following pass takes it immediately.

The measured departure is 14% at worst, which is small enough to draw and too large to call an identity. Reporting it as one would have been the tidier essay and it is a claim the measurement refuses; a limit is not a prediction is the general form of that discipline on this site, and this is a mild instance of it.

There is a second contribution and it is the one that makes the ratio drift downward as $\varepsilon$ tightens. At $\varepsilon = 0.05$ the resident list is fifteen tuples and the period is ten, so the backlog is two thirds of the object; at $\varepsilon = 0.002$ it is 397 and 250, so the backlog is a smaller fraction of a much larger list, and the peak’s own fluctuation — which is a fixed number of tuples rather than a fraction — matters less. The ratio therefore falls from 1.93 to 1.70 across the range and would keep falling slowly.

The peak is not a tail event #

A number like “the peak is 1.8 times the reported size” invites the reading that the peak is a rare excursion — something the structure touches occasionally under an unlucky arrival pattern, and which a deployment might reasonably provision below and absorb.

It is not. The list reaches its peak once per period, by construction, because the peak is the moment before a compression and a compression happens every $P$ updates. Over twenty thousand arrivals at $\varepsilon = 0.01$ that is four hundred visits to within a few tuples of the maximum. The occupancy profile is a sawtooth whose teeth all reach the same height, not a flat line with spikes.

That distinction has cost real deployments real money elsewhere on this site. Sized for a rate that does not hold still measures a window whose capacity was taken from its mean occupancy and which overflows at 46.7% of instants while 35.1% of the allocation stands empty — a case where the mean is the wrong statistic because the distribution is wide. Here the mean is the wrong statistic for the opposite reason: the distribution is not wide, it is bimodal-by-schedule, and the two modes are the reported number and the reported number plus a period.

Measuring it without breaking it #

Counting the peak is two lines and one of them is a trap this site has already fallen into.

The obvious implementation puts a peakTuples field on the summary and updates it in add. That is correct here. It stopped being correct in a different structure here, where a multi-pass algorithm’s enforcement reset the object at every pass boundary so that nothing undeclared crossed it — and wiped the peak counter along with everything else, so three different pass counts all reported the same number and it looked like a floor.

The rule that came out of it is worth restating because it applies to every measurement of this kind: the state an algorithm reads and the measurement nobody reads are different things, and only the first may be reset. A peak counter that participates in the structure’s own logic is not a peak counter; it is state, and it will be managed like state.

The same care applies to the scan counter used in the period that is not a promise. It accumulates tuples examined and is never read by add, compress or query, which is what makes it safe to leave alone across whatever the structure does to itself.

What a deployment is actually allocating #

The practical shape of this is worth being blunt about, because it is a sizing decision and sizing decisions are made from documentation.

A service keeping per-endpoint latency quantiles at $\varepsilon = 0.002$ over a thousand endpoints reads that a summary of that tolerance holds around four hundred tuples, multiplies, and provisions for four hundred thousand tuples’ worth of state. The structures will collectively want six hundred and seventy-four thousand. That is not a slow leak or a tail event — it is the steady state, reached within the first few hundred arrivals per endpoint and revisited every two hundred and fifty arrivals thereafter.

And it is worse in the case a deployment is most likely to be in, which is many small summaries rather than one large one. The backlog is a fixed $P$ tuples per summary regardless of how many arrivals that summary has seen, so a thousand summaries each holding a handful of tuples still carry a thousand periods of backlog between them. At $\varepsilon = 0.002$ that is 250,000 tuples of headroom against however little the summaries themselves hold.

There is a way out of that particular version of the problem and it is worth naming because it is free. A thousand summaries sharing one process do not all compress at the same instant unless somebody arranged for them to; their periods are independent and their sawtooths are out of phase, so the sum of a thousand peaks is not the peak of the sum. Provisioning for the sum of the peaks over-provisions by roughly the amount the phases decorrelate.

What that saving needs is exactly the assumption a deployment is least entitled to make, which is that the arrivals are spread across the summaries rather than arriving in bursts per key. A batch import that pushes ten thousand values into one endpoint’s summary and nothing into the others produces one summary at its peak and nine hundred and ninety-nine at rest — which is the good case. A fan-out that touches every endpoint on every request advances every since counter in lockstep, and the phases stay aligned for the life of the process.

So the correlated case is the one a scheduler creates, and it is created by the thing that looks most like good practice: uniform, regular, evenly distributed traffic. That is an unusual direction for a hazard to run and it is worth a sentence in a runbook.

The bits, rather than the tuples #

A tuple is three machine words on this site’s accounting — a value and two counters — so the headroom converts to bits by multiplication and nothing interesting happens. It is worth doing anyway, because it is what turns the ratio into a sentence somebody can act on.

At $\varepsilon = 0.002$ with 64-bit values and 32-bit counters, a tuple is 128 bits. The reported 397 tuples are 6.2 KB; the occupied 674 are 10.5 KB. A thousand of them is 6.1 MB reported and 10.3 MB occupied, and the difference is four megabytes that appear in no bound, no benchmark and no size estimate the structure will produce about itself.

The comparison worth making is against the thing this structure is a summary of. Twenty thousand 64-bit values are 160 KB. So the summary is a 26-fold saving on the reported figure and a 15-fold saving on the honest one — still an enormous win, and a materially different one. What a window costs in bits makes the same conversion for a different structure and for the same reason: a ratio between two state counts is an argument, and a number of bytes is a decision.

The number that is right depends on the question #

There are three sizes here and each is the right answer to something.

The resident count is what the structure will settle back to and is what a reader comparing two tolerances wants: it is the quantity with the clean $1/\varepsilon$ in it and the quantity every published bound is about.

The peak is what an allocator needs and is the only one of the three a deployment can safely be short of nothing else.

The total allocated over the run is a third quantity again, and on this structure it is uninteresting, because the list is a single array that grows and shrinks in place. On a structure that allocated per merge it would be the dominant number, which is exactly the distinction measuring what an algorithm keeps was built to make and the reason alloc() and frame() are counted separately in the first place.

The other structures have the same shape and do not all admit it #

The t-digest buffers arrivals and flushes them into its centroid list when the buffer fills, which is the same arrangement with a different name and a much larger constant: its default buffer is two hundred and fifty-six values against a centroid list that is often a hundred or so. Its reported size is the centroid count.

The biased variants are the interesting case, because their cap function makes the resident count depend on the distribution while the backlog does not. A high-biased summary on a heavy tail keeps far more tuples than an unbiased one, so its headroom ratio is smaller — the same fixed backlog against a bigger list. A deployment that measured the ratio on one bias and applied it to another would be wrong in the safe direction on the tail-biased one and the unsafe direction on the plain one.

What the decorrelation is worth, in tuples #

The observation that a thousand sawtooths out of phase do not peak together is worth a number rather than a gesture, because the number decides which of three allocations is right.

Each summary’s occupancy is $|S| + u$ where $u$ walks from 0 to $P$ and resets. Over $N$ independent summaries with independent phases, the aggregate is $N|S|$ plus a sum of $N$ draws that are near enough uniform on $[0, P]$ — so its mean is $N(|S| + P/2)$ and its standard deviation is $\sqrt{N}\,P/\sqrt{12}$. The mean grows with $N$ and the fluctuation with $\sqrt{N}$, so the aggregate concentrates, and a large deployment’s total occupancy is not a distribution to provision the tail of. It is nearly a constant.

At a thousand summaries with $\varepsilon = 0.002$, where $|S| = 397$ and $P = 250$: the reported figure is 397,000 tuples; the sum of the individual peaks is 647,000; and the aggregate’s mean is 522,000 with a standard deviation of 2,280. Three standard deviations is 6,800 — one and three tenths per cent of the total.

So the right allocation is 529,000, and both of the numbers a reader is likely to arrive at are wrong by about a quarter in opposite directions. Taking the structure’s own answer under-provisions by 33%. Multiplying the peak by the count over-provisions by 22%, which on this arithmetic is 118,000 tuples of memory bought to cover a coincidence that the arithmetic says will not happen.

The concentration arrives fast, which is the part worth knowing before deciding whether to reason about it at all. At ten summaries the three-sigma excess over the mean is 11% of the total; at a hundred it is 3.4%; at a thousand it is 1.3%. Below about ten summaries, provision the peak; above about a hundred, provision the mean. There is no wide middle band where the answer is delicate.

All of which holds only while the phases stay independent, and the essay’s warning above is exactly the term that would break it. Summaries advanced in lockstep — a fan-out touching every key on every request — have one phase between them, so the aggregate is a single sawtooth of amplitude $NP$ and its peak really is 647,000. The whole saving is the $NP/2$ that decorrelation removes, which at these parameters is 125,000 tuples, or a fifth of the allocation, decided entirely by whether the traffic pattern happens to advance the counters together.

That is an unusually clean instance of a distinction this site keeps making: expected is not average is normally a warning that a mean hides a spread, and here it is the opposite — the spread is genuinely negligible and the mean is the honest number, provided an independence assumption that the deployment, rather than the structure, is responsible for. The right thing to write in a runbook is not a figure but a conditional, and on average is not a number is the standing form of the complaint about writing the figure alone.

Both halves of the accounting are worth reading at the tolerance the rest of this page uses, so the two plates are drawn once more at ε = 0.01 rather than swept.

All of it holds at twice the stream, which is the only check available that the ratio is a property of the schedule rather than of twenty thousand arrivals.

What this does not say #

It does not say the structure is larger than its bound. $|S| + P$ is $c/\varepsilon + 1/2\varepsilon$, which is $\Theta(1/\varepsilon)$, the same class the bound states. Nothing here is a violation of anything and nobody has been misled about a complexity.

It says the constant is 1.7 to 1.9 times what the structure reports, and that the constant is the content — which is this site’s standing position and the reason how close anything gets to the floor is a separate essay from the floor itself. An asymptotic class is not an allocation. Somebody has to write a number into a configuration file, and the number the structure hands them is the wrong one by a factor that no amount of reasoning about $\Theta$ will recover.

It also does not say the schedule is wrong. The period that is not a promise works out what the prescribed period buys — a housekeeping bill that stops depending on the tolerance, flat to 3% across a twenty-five-fold range — and it is a good trade. The complaint is not that the structure spends peak space to buy flat work. It is that it spends it silently, and then reports the half of the state that the spending did not touch.

One more reading is available and it is the one that makes the essay’s title exact. Ask the structure for tuples and it answers a question about itself. Ask it how much memory it needs and it has no method for that at all — the field does not exist, on this implementation or on the ones it is modelled from. The number is not misreported; it is absent, and the nearest available number is taken for it. That is the shape of most of the resource-accounting failures on this site, and it is why measuring what an algorithm keeps counts allocations rather than trusting descriptions.

The honest limit is that all of this was measured on one implementation with one insert rule. A summary that compressed only the tuples inserted since the last pass would have a different resident count and the same backlog; one that compressed on a byte budget rather than an update count would have a backlog that varied with the values. The arithmetic in this essay is $|S| + P$ and it needs a $P$ that is a number of updates. Where the schedule is not counted in updates, the shape of the argument survives and the number in it does not.