Allocating memory consumes 4.3 percent of a fleet's processor cycles, which sounds like the number to attack — but this paper (Google, Cornell and MIT) argues that is the wrong target entirely, because between a fifth and two thirds of cycles are already lost waiting on memory, and the allocator decides where every object physically sits. Measuring Google's allocator across the production fleet reveals object lifetimes so varied that standard benchmarks cannot represent them, and four redesigns exploiting that yield 1.4 percent more throughput and 3.4 percent less memory across every machine.
The argument in one glance
-
Problem
Nobody owns the overhead that everybody pays
A warehouse-scale computer runs thousands of unrelated applications, so making any single one faster barely registers in the total. What does register is the work every application does regardless of purpose — serialising messages, making remote calls, compressing data, allocating memory. These shared costs are collectively substantial, and a gain in one of them lands on every workload simultaneously. Memory allocation is among the largest, which is why it is worth attacking, and why an improvement measured in single-digit percentages translates into a genuinely large number of servers.
-
What people did
Measure how much time the allocator takes and take less
The natural approach, and the one prior work follows, is to treat this as a cost-reduction problem. Profile how many cycles the fleet spends inside allocation and deallocation, then make those paths cheaper — better fast paths, fewer locks, less bookkeeping. Alongside that, measure candidate allocators against standard benchmark suites to see which is quickest. Both are reasonable, both have produced real improvements, and both treat the allocator as an overhead to be minimised.
-
Why it fell short
The ceiling on that is 4.3 percent, and the real cost is elsewhere
Measured across the fleet, allocation and deallocation account for 4.3 percent of processor cycles. Eliminating the allocator entirely could not beat that. Meanwhile prior measurements attribute between 20 and 64 percent of cycles to pipeline stalls in the back end, mostly cache misses — and the allocator is what decides where every object physically lives, and therefore how well the caches and address translation work. The benchmarks are a problem too, since their allocation behaviour turns out not to resemble production at all.
-
This paper's idea
Optimise what the allocator does to everything else
This paper (Google, Cornell and MIT — Zhou, Gogte, Vaish, Kennelly, Xia, Kanev, Moseley, Delimitrou and Ranganathan) reframes the goal as application productivity: more useful work from the same hardware, even if the allocator itself gets no faster. To find out how, they characterise the production allocator across the fleet — what sizes are allocated, how long objects live, where memory is wasted — and find diversity that no benchmark captures. Four redesigns follow, one per level of the allocator, yielding 1.4 percent more fleet throughput and 3.4 percent less memory.
Why this problem is worth solving
The allocator being studied has a specific shape, and the redesigns all follow
from where in that shape the costs sit.
Allocations of at most 256
kilobytes are rounded up to one of about eighty to ninety SIZE CLASSES and served
from a four-tier hierarchy. A PER-CPU CACHE at the front holds objects for the
threads running on one core, needing no locks because only one thread touches it
at a time. Behind it, a small TRANSFER CACHE lets objects move between cores,
which matters because one core often frees what another allocated. Behind that, a
CENTRAL FREE LIST manages SPANS — contiguous runs of memory carved into objects of
a single size class — in linked lists. At the back, a PAGEHEAP hands out memory in
hugepages, carving spans from them and eventually returning whole hugepages to the
operating system. Anything larger than the top size class skips the caches and goes
straight to the pageheap, which turns out to be 22 percent of all allocated
memory
Where memory is wasted is a structural consequence of that layering.
Fragmentation
comes in two forms. INTERNAL fragmentation is the slack between what an
application asked for and the size class it got, and finer size classes would
reduce it at the cost of more separate free lists and less reuse — an explicit
balance the allocator strikes. EXTERNAL fragmentation is memory the allocator is
holding but has not handed out. Fleet-wide, total fragmentation is 22.2 percent of
heap size, of which 18.8 points are external and 3.4 internal, and individual
applications range from 11.2 to 42.5 percent. The external part concentrates at the
back: the central free list holds 29 percent of it and the pageheap 51. The reason
is a release rule. A span can only go back when EVERY object on it is free, so a
single long-lived object pins an entire span, and the same logic one level up pins
a hugepage
What people did before, and where it broke
- Profile the cycles the fleet spends inside the allocator. Established work identifies allocation as a major component of shared datacentre overhead and proposes accelerating it.
- But that caps out at 4.3 percent of fleet cycles. Removing allocation entirely could not do better, while 20 to 64 percent of cycles are already lost to memory stalls the allocator influences.
- Compare allocators on standard benchmark suites. The usual way to evaluate a design before deploying it.
- But their allocation behaviour is nothing like production. Objects in those suites either live as long as the program or under a millisecond, with little in between, and the benchmarks barely allocate at all once in steady state.
- Size the allocator’s caches statically and tune the constants. Simple, predictable, and what the allocator did.
- But applications are pinned to a shifting subset of cores by the cluster scheduler while their thread counts move with load, so a fixed size is wrong most of the time and hyperthread counts have grown fourfold in five platform generations.
- Predict object lifetimes with a learned model to pack better. Prior work shows this improves placement.
- But inference costs runtime, which is the budget being defended. In a path this hot, a predictor that must run on every decision is hard to justify.
- The gap. Nobody had looked at what actually flows through a production allocator at fleet scale, so the designs were tuned against a workload nobody had measured.
How you improve something that only takes 4 percent
Reframing the objective, then letting fleet measurements dictate four redesigns
-
Profile the allocator and reduce its own cycle count
Measure how much time the fleet spends inside allocation and deallocation, then optimise those code paths. This is the established approach to shared datacentre overheads, and it is the framing this paper argues against rather than the one it adopts.
-
Change the objective to what the application achieves new
Measure success as work completed per unit of hardware rather than as time saved inside the library, using each application own throughput metric. That admits changes which make the allocator slower but the application faster, which is the direction most of the improvements turn out to run.
-
Characterise what actually flows through, across the fleet new
Sample a small fraction of production machines daily and collect allocator telemetry, then measure the distribution of object sizes, how long objects live, where cycles go inside the allocator, and where fragmented memory accumulates. Nobody had published this for a production allocator at this scale.
-
Size the front-end cache to what the application uses new
Applications are confined to a subset of cores by the cluster scheduler and their thread counts move with load, so uniform static caches are wrong nearly always. Give each per-core cache a capacity that follows its observed usage instead, so unused ones stop holding memory hostage.
-
Stop objects wandering between cache domains new
Much of the fleet now uses chiplet processors with several last-level cache domains, so a core in one domain freeing an object that a core in another later allocates forces a fetch from a distant cache. Give each domain its own transfer cache, and activate only as many as the application is scheduled across.
-
Pack by longevity, using something already known new
A span is only released when every object on it is free, so mixing long-lived and short-lived objects pins memory. Rather than predicting lifetimes with a model at runtime, use quantities the allocator already has — how many objects are still live on a span, and how many a span can hold — as free proxies.
The idea
The thing named after the cost is not where the cost is. The paper opens by disagreeing with the framing of its own field. Allocation is a well-known component of shared datacentre overhead, and the natural response is to make it cheaper, but the measurement bounds that ambition immediately: 4.3 percent of fleet cycles are spent inside allocation and deallocation, so perfect allocation is worth at most 4.3 percent. Against that, prior fleet measurements attribute 20 to 64 percent of cycles to back-end pipeline stalls, overwhelmingly cache misses — and the allocator is precisely the component that decides where every object physically sits, and therefore how well the caches and the address translation hardware do their jobs. So the objective is redefined as application productivity, work completed per unit of hardware, explicitly permitting changes that make the allocator slower if they make the application faster. The results bear this out: the largest single win comes from packing objects into hugepages by expected longevity, which shows up as 2.94 percent fewer address translation walk cycles and 8.1 percent fewer translation misses rather than as any reduction in allocator time. Refusing to optimise the quantity that shares a name with the problem, because measurement shows the leverage is in what that component does to everything else, is the same optimise-the-term-that-dominates correction covered elsewhere on this site where a system is deliberately made slower at the headline metric and wins on the one that matters.
The property the redesign depends on is invisible in every standard benchmark. The single most useful measurement in the paper is the distribution of object lifetimes, and its shape is what the last two redesigns exploit. In production, lifetimes are enormously varied and — crucially — vary within a size class: an object under 16 megabytes might live under a millisecond or over a week, and 46 percent of objects under a kilobyte are gone within a millisecond while 65 percent of objects over a gigabyte survive more than a day. That mixture is exactly the problem, because a span is only released when all its objects are free, so one long-lived object among many short-lived ones pins the whole span. The authors then run the same measurement over a standard benchmark suite and find nothing like it: objects there are either alive for the whole program or gone within a millisecond, with little in between, and the benchmarks barely allocate at all in steady state. Their conclusion is blunt — those benchmarks are unsuitable for evaluating memory allocators. Discovering that the characteristic a design must exploit does not appear in the workloads the field evaluates against is the same the-benchmarks-lack-the-phenomenon finding covered elsewhere on this site where a technique cannot be assessed on standard inputs because they do not exhibit the behaviour it addresses.
Use a number you already have instead of predicting one. Both back-end redesigns need to know how long memory will be held, and prior work answers that with a learned lifetime predictor — which the paper declines, on the grounds that inference costs runtime in the very path being defended. Instead each uses a proxy that costs nothing. For the central free list, the question is which span to allocate from, and the answer is whichever is least likely to be released soon, approximated by how many objects on it are already live: spans are bucketed by the logarithm of that count into eight lists, so nearly-full spans are lumped together while nearly-empty ones are distinguished finely, and allocations are served from the fullest bucket to pack densely. For the pageheap, the question is which allocations to place together, and the proxy is span capacity — how many objects a span holds, which is a static property of its size class, with a threshold of sixteen separating short-lived from long-lived. Neither requires a model, a training pipeline, or a single cycle of inference. Replacing a learned prediction with a cheap statistic that is already lying around and correlates well enough is the same the-simple-proxy-suffices move covered elsewhere on this site where an expensive estimator is displaced by a quantity the system was already tracking.
Following the fleet from measurement to rollout
What continuous profiling of a production allocator reveals, and what it changes
All figures from fleet-wide telemetry across Google production machines, sampled continuously and validated by A/B experiments.
Step 1 of 5
Establish the ceiling before choosing a target
Allocation and deallocation take 4.3 percent of fleet processor cycles, measured over two weeks. Inside that, the per-core cache accounts for 53 percent of allocator time, the central free list 12, and prefetching 16 — that last one deliberately, since the allocator prefetches the next object of a size class because prefetching the current one would arrive after the application had already touched it.
the top 50 binaries account for over half of allocator cycles and 65 percent of allocated memory, so there is no single application to optimise for prior work attributes 20 to 64 percent of fleet cycles to back-end stalls, which is the far larger pool the allocator can influence
Why it works
- Allocation is 4.3 percent of cycles while memory stalls are 20 to 64 → the allocator leverage is over where objects sit rather than over its own speed → so optimising for locality beats optimising for allocator time even when the allocator gets slower.
- Applications are confined to shifting subsets of cores with fluctuating thread counts → uniform static per-core caches are the wrong size nearly always → so sizing each by observed usage recovers memory and improves hit rates together.
- Chiplet processors give a machine several last-level cache domains → objects crossing domains through a shared transfer cache force distant fetches → so one transfer cache per domain keeps objects near the cores that use them.
- A span is released only when every object on it is free → serving allocations from the fullest spans concentrates live objects and empties the rest → recovering 1.41 percent of fleet memory with no change in application throughput.
- Span capacity is a static property that correlates with how long its objects live → grouping hugepage allocations by it needs no model and no inference → giving 8.1 percent fewer address translation misses at zero runtime cost.
What it costs (trade-offs and scope)
- The aggregate number is an estimate, not an experiment. The four designs rolled out over two years into a fleet whose workloads never stop changing, so the combined 1.4 and 3.4 percent are composed from relative improvements rather than measured end to end.
- Some changes trade memory for speed. The transfer cache redesign increases fragmentation slightly, justified by an outsized gain in application performance rather than by being free.
- The proxies are correlations, not truths. Span capacity stands in for lifetime and live count stands in for release probability, with thresholds of sixteen objects and eight buckets found empirically.
- Everything is one allocator in one fleet. The authors argue the layered structure is shared by other modern allocators so the insights transfer, but the measurements are from a single organisation’s workloads.
- Single-threaded workloads gain nothing. One benchmark is excluded from the study outright because it cannot benefit from optimisations aimed at multi-threaded applications.
The evaluation
Characterisation comes from continuous production profiling, which samples between 1 and 10 percent of fleet machines each day and collects allocator telemetry briefly and unobtrusively, plus allocation sampling that records a call stack once per 2 megabytes allocated. Each redesign is then evaluated by A/B experiment across the production fleet rather than on a testbed, with per-application throughput metrics as the success criterion and memory usage tracked alongside. Standard benchmarks appear only as a point of comparison, and mostly to argue that they are not representative.
| Property | Minimise allocator CPU time | Tune against benchmark suites | Redesign from fleet characterisation |
|---|---|---|---|
| What is being optimised | |||
| Object lifetime diversity assumed | |||
| How hardware variety is handled | |||
| Where lifetime knowledge comes from | |||
| How results are validated |
Check yourself
Check your understanding
1. Memory allocation is identified as a major shared overhead in warehouse-scale computing, yet the paper argues that making the allocator faster is the wrong goal. Predict the reasoning.
2. The paper concludes that standard benchmark suites are unsuitable for evaluating memory allocators. Predict what measurement leads to that.
3. Two of the redesigns need to know how long allocated memory will be held. Prior work predicts lifetimes with a learned model. Predict what this paper does instead and why.
4. The front-end per-core caches are redesigned to be sized dynamically rather than uniformly. Predict what makes uniform sizing wrong in this environment.
Sources
- Zhuangzhuang Zhou, Vaibhav Gogte, Nilay Vaish, Chris Kennelly, Patrick Xia, Svilen Kanev, Tipp Moseley, Christina Delimitrou and Parthasarathy Ranganathan. “Characterizing a Memory Allocator at Warehouse Scale.” ASPLOS 2024, Volume 3. Google, Cornell University and MIT. DOI 10.1145/3620666.3651350. The allocator studied is TCMalloc.
- Full text of the paper was used for this explainer, including the allocator architecture and profiling methodology in Section 2, the general characterization of allocation latency, cycle breakdown, fragmentation, object sizes and object lifetimes in Section 3, the per-tier characterization and four redesigns covering the per-CPU cache, transfer cache, central free list and pageheap in Section 4, and the discussion of datacenter tax framing and kernel cooperation in Section 5.
- The designs were open sourced.