Beyond malloc efficiency to fleet efficiency: a hugepage-aware memory allocator

A.H. Hunter Chris Kennelly Paul Turner Darryl Gove Tipp Moseley
Jane Street Capital∗ Google Google Google Google
Parthasarathy Ranganathan
Google

Abstract in aggregate as the benefits can apply to entire classes of appli-

Memory allocation represents significant compute cost at cation. Over the past several years, our group has focused on
the warehouse scale and its optimization can yield consid- minimizing the cost of memory allocation decisions, to great
erable cost savings. One classical approach is to increase effect; realizing whole system gains by dramatically reducing
the efficiency of an allocator to minimize the cycles spent in the time spent in memory allocation. But it is not only the cost
the allocator code. However, memory allocation decisions of these components we can optimize. Significant benefit can
also impact overall application performance via data place- also be realized by improving the efficiency of application
ment, offering opportunities to improve fleetwide productivity code by changing the allocator. In this paper, we consider
by completing more units of application work using fewer how to optimize application performance by improving the
hardware resources. Here, we focus on hugepage coverage. hugepage coverage provided by memory allocators.
We present T EMERAIRE, a hugepage-aware enhancement Cache and Translation Lookaside Buffer (TLB) misses are
of TCM ALLOC to reduce CPU overheads in the applica- a dominant performance overhead on modern systems. In
tion’s code. We discuss the design and implementation of WSCs, the memory wall [44] is significant: 50% of cycles are
T EMERAIRE including strategies for hugepage-aware mem- stalled on memory in one analysis [23]. Our own workload
ory layouts to maximize hugepage coverage and to minimize profiling observed approximately 20% of cycles stalled on
fragmentation overheads. We present application studies for TLB misses.
8 applications, improving requests-per-second (RPS) by 7.7% Hugepages are a processor feature that can significantly
and reducing RAM usage 2.4%. We present the results of reduce the number, and thereby the cost, of TLB misses [26].
a 1% experiment at fleet scale as well as the longitudinal The increased size of a hugepage enables the same number of
rollout in Google’s warehouse scale computers. This yielded TLB entries to map a substantially larger range of memory.
6% fewer TLB miss stalls, and 26% reduction in memory On the systems under study, hugepages also allow the total
wasted due to fragmentation. We conclude with a discussion stall time for a miss+fill to be reduced as their page-table
of additional techniques for improving the allocator develop- representation requires one fewer level to traverse.
ment process and potential optimization strategies for future While an allocator cannot modify the amount of memory
memory allocators. that user code accesses, or even the pattern of accesses to
objects, it can cooperate with the operating system and con-
trol the placement of new allocations. By optimizing huge-
1 Introduction page coverage, an allocator may reduce TLB misses. Memory
placement decisions in languages such as C and C++ must
The datacenter tax [23, 41] within a warehouse-scale com- also deal with the consequence that their decisions are final:
puter (WSC) is the cumulative time spent on common service Objects cannot be moved once allocated [11]. Allocation
overheads, such as serialization, RPC communication, com- placement decisions can only be optimized at the point of
pression, copying, and memory allocation. WSC workload allocation. This approach ran counter to our prior work in
diversity [23] means that we typically cannot optimize sin- this space, as we can potentially increase the CPU cost of an
gle application(s) to strongly improve total system efficiency, allocation, increasing the datacenter tax, but make up for it
as costs are borne across many independent workloads. In by reducing processor stalls elsewhere. This improves appli-
contrast, focusing on the components of datacenter tax can cation metrics1 such as requests-per-second (RPS).
realize substantial performance and efficiency improvements
1 While
reducing stalls can improve IPC, IPC alone is a poor proxy [3] for
∗ Work performed while at Google. how much useful application work we can accomplish with a fixed amount
 Our contributions are as follows:
• The design of T EMERAIRE, a hugepage-aware enhance- allocate. . .
ment of TCM ALLOC to reduce CPU overheads in the used used used used
rest of the application’s code. We present strategies for free some. . .
hugepage-aware memory layouts to maximize hugepage used used
coverage and to minimize fragmentation overheads.
• An evaluation of T EMERAIRE in complex real-world ap- Figure 1: Allocation and deallocation patterns leading to frag-
plications and scale in WSCs. We measured a sample of mentation
8 applications running within our infrastructure observed
requests-per-second (RPS) increased by 7.7% and RAM
usage decreased by 2.4%. Applying these techniques
small to be used for requested allocations, by the allocator is
to all applications within Google’s WSCs yielded 6%
important in this process. For example consider the alloca-
fewer TLB miss stalls, and 26% reduction in memory
tions in Figure 1. After this series of allocations there are 2
wasted due to fragmentation.
units of free space. The choice is to either use small pages,
• Strategies for optimizing the development process of which result in lower fragmentation but less efficient use of
memory allocator improvements, using a combination TLB entries, or hugepages, which are TLB-efficient but have
of tracing, telemetry, and experimentation at warehouse- high fragmentation.
scale. A user-space allocator that is aware of the behavior pro-
duced by these policies can cooperate with their outcomes
by densely aligning the packing of allocations with hugepage
2 The challenges of coordinating Hugepages boundaries, favouring the use of allocated hugepages, and
(ideally) returning unused memory at the same alignment2 .
Virtual memory requires translating user space addresses to
A hugepage-aware allocator helps with managing memory
physical addresses via caches known as Translation Looka-
contiguity at the user level. The goal is to maximally pack
side Buffers (TLBs) [7]. TLBs have a limited number of
allocations onto nearly-full hugepages, and conversely, to min-
entries, and for many applications, the entire TLB only covers
imize the space used on empty (or emptier) hugepages, so that
a small fraction of the total memory footprint using the default
they can be returned to the OS as complete hugepages. This
page size. Modern processors increase this coverage by sup-
efficiently uses memory and interacts well with the kernel’s
porting hugepages in their TLBs. An entire aligned hugepage
transparent hugepage support. Additionally, more consistently
(2MiB is a typical size on x86) occupies just one TLB entry.
allocating and releasing hugepages forms a positive feedback
Hugepages reduce stalls by increasing the effective capacity
loop: reducing fragmentation at the kernel level and improv-
of the TLB and reducing TLB misses [5, 26].
ing the likelihood that future allocations will be backed by
Traditional allocators manage memory in page-sized
hugepages.
chunks. Transparent Huge Pages (THP) [4] provide an oppor-
tunity for the kernel to opportunistically cover consecutive
pages using hugepages in the page table. A memory allocator, 3 Overview of TCM ALLOC
superficially, need only allocate hugepage-aligned and -sized
memory blocks to take advantage of this support. TCM ALLOC is a memory allocator used in large-scale appli-
A memory allocator that releases memory back to the OS cations, commonly found in WSC settings. It shows robust
(necessary at the warehouse scale where we have long running performance [21]. Our design builds directly on the structure
workloads with dynamic duty cycles) has a much harder chal- of TCM ALLOC.
lenge. The return of non-hugepage aligned memory regions Figure 2 shows the organization of memory in TCM ALLOC.
requires that the kernel use smaller pages to represent what re- Objects are segregated by size. First, TCM ALLOC partitions
mains, defeating the kernel’s ability to provide hugepages and memory into spans, aligned to page size3 .
imposing a performance cost for the remaining used pages. TCM ALLOC’s structure is defined by its answer to the
Alternatively, an allocator may wait for an entire hugepage same two questions that drive any memory allocator.
to become free before returning it to the OS. This preserves
hugepage coverage, but can contribute significant amplifica- 1. How do we pick object sizes and organize metadata to
tion relative to true usage, leaving memory idle. DRAM is a 2 This is important as the memory backing a hugepage must be physically
significant cost the deployment of WSCs [27]. The manage- contiguous. By returning complete hugepages we can actually assist the
ment of external fragmentation, unused space in blocks too operating system in managing fragmentation.
3 Confusingly, TCM ALLOC ’s “page size” parameter is not necessarily the

of hardware. A busy-looping spinlock has extremely high IPC, but does little system page size. The default configuration is to use an 8 KiB TCM ALLOC
useful work under contention. “page”, which is two (small) virtual memory pages on x86.
 requested from OS The pageheap is also responsible for returning no-longer-
2 MiB needed memory to the OS when possible. Rather than do-
ing this on the free() path, a dedicated release-memory
method is invoked periodically, aiming to maintain a con-
figurable, steady rate of release in MB/s. This is a heuristic.
TCM ALLOC wants to simultaneously use the least memory
25 KiB possible in steady-state, avoiding expensive system alloca-
tions that could be elided by using previously provisioned
memory. We discuss handling this peak-to-trough allocation
pattern in more detail in Section 4.3.
Ideally, TCM ALLOC would return all memory that user
code will not need soon. Memory demand varies unpre-
200 KiB dictably, making it challenging to return memory that will
go unused while simultaneously retaining memory to avoid
Figure 2: Organization of memory in TCM ALLOC. System- syscalls and page faults.. Better decisions about memory re-
mapped memory is broken into (multi-)page spans, which are turn policies have high value and are discussed in section 7.
sub-divided into objects of an assigned, fixed sizeclass, here TCM ALLOC will first attempt to serve allocations from a
25 KiB. “local” cache, like most modern allocators [9,12,20,39]. Orig-
inally these were the eponymous per-Thread Caches, storing
a list of free objects for each sizeclass. To reduce stranded
memory and improve re-use for highly threaded applications,
minimize space overhead and fragmentation? TCM ALLOC now uses a per-hyperthread local cache. When
2. How do we scalably support concurrent allocations? the local cache has no objects of the appropriate sizeclass to
serve a request (or has too many after an attempt to free()),
Sufficiently large allocations are fulfilled with a span con- requests route to a single central cache for that sizeclass. This
taining only the allocated object. Other spans contain multiple has two components–a small fast, mutex-protected transfer
smaller objects of the same size (a sizeclass). The “small” ob- cache (containing flat arrays of objects from that sizeclass)
ject size boundary is 256 KiB. Within this “small” threshold, and a large, mutex-protected central freelist, containing every
allocation requests are rounded up to one of 100 sizeclasses. span assigned to that sizeclass; objects can be fetched from,
TCM ALLOC stores objects in a series of caches, illustrated in or returned to these spans. When all objects from a span have
been returned to a span held in the central freelist, that span
mmap is returned to the pageheap.
(large) malloc()
OS pageheap In our WSC, most allocations are small (50% of allocated
(large) free() space is objects ≤ 8192 bytes), as depicted in Figure 4. These
release s
s p are then aggregated into spans. The pageheap primarily al-
8 bytes span . . . ans 256KiB locates 1- or 2-page spans, as depicted in Figure 5. 80% of
central central central spans are smaller than a hugepage.
... The design of “stacked” caches make the system usefully
transfer transfer transfer modular, and there are several concomitant advantages:

• Clean abstractions are easier to understand and test.

CPU 0 cache CPU. . . CPU 9 cache
• It’s reasonably direct to replace any one level of the
cache with a totally new implementation.
• When desired, cache implementations can be selected at
malloc() free() runtime, with benefits to operational rollout and experi-
mentation.
Figure 3: The organization of caches in TCM ALLOC; we see
memory allocated from the OS to the pageheap, distributed TCM ALLOC’s pageheap has a simple interface for manag-
up into spans given to the central caches, to local caches. This ing memory.
paper focuses on a new implementation for the pageheap.
• New(N) allocates a span of N pages
• Delete(S) returns a New’d span (S) to the allocator.
Figure 3. Spans are allocated from a simple pageheap, which • Release(N) gives >= N unused pages cached by the
keeps track of all unused pages and does best-fit allocation. page heap back to the OS
 1.0 1.0

0.8 0.8

0.6 0.6
Proportion

Proportion
0.4 0.4

0.2 0.2

0.0 0.0
102 104 106 108 1010 104 105 106 107 108 109 1010
Allocated Size (bytes) Span Size (bytes)

Figure 4: CDF of allocation sizes from WSC applications, Figure 5: CDF of TCM ALLOC span sizes from WSC appli-
weighted by bytes. cations, weighted by bytes.

4 T EMERAIRE’s approach 2. Completely draining hugepages implies packing

memory at hugepage granularity. Returning huge-
T EMERAIRE, this paper’s contribution to TCM ALLOC, re- pages that aren’t nearly-empty to the OS is costly (see
places the pageheap with a design that attempts to maximally section 2). Generating empty/nearly-empty hugepages
fill (and empty) hugepages. The source code is on Github implies densely packing the other hugepages in our bi-
(see Section 9). We developed heuristics that pack allocations nary. Our design must enable densely packing alloca-
densely onto highly-used hugepages and simultaneously form tions into as few, saturated, bins as possible.
entirely unused hugepages for return to the OS. While we aim to use exclusively hugepage-sized bins,
We refer to several definitions. Slack is the gap between an malloc must support allocation sizes larger than a sin-
allocation’s requested size and the next whole hugepage. Vir- gle hugepage. These can be allocated normally, but we
tual address space allocated from the OS is unbacked without place smaller allocations into the slack of the allocation
reserving physical memory. On use, it is backed, mapped by to achieve high allocation density. Only when small al-
the OS with physical memory. We may release memory to locations are dominated by slack do we need to place
the OS once again making it unbacked. We primarily pack large allocations end on end in regions.
within hugepage boundaries, but use regions of hugepages for
3. Draining hugepages gives us new release decision
packing allocations across hugepage boundaries.
points. When a hugepage becomes completely empty,
From our telemetry of malloc usage and TCM ALLOC we can choose whether to retain it for future memory
internals, and knowledge of the kernel implementation, we allocations or return it to the OS. Retaining it until re-
developed several key principles that motivate T EMERAIRE’s leased by TCM ALLOC’s background thread carries a
choices. higher memory cost. Returning it reduces memory us-
age, but comes at a cost of system calls and page faults
1. Total memory demand varies unpredictably with if reused. Adaptively making this decision allows us to
time, but not every allocation is released. We have return memory to the OS faster than the background
no control over the calling code, and it may rapidly (and thread while simultaneously avoiding extra system calls.
repeatedly) modulate its usage; we must be hardened to
this. But many allocations on the pageheap are immortal 4. Mistakes are costly, but work is not. Very few alloca-
(and it is difficult to predict which they are [30]); any tions directly touch the pageheap, but all allocations are
particular allocation might disappear instantly or live backed via the pageheap. We must only pay the cost of al-
forever, and we must deal well with both cases. location once; if we make a bad placement and fragment
 a hugepage, we pay either that space or the time-cost Span New(N) {
of breaking up a hugepage for a long time. It is worth // Slack is too small to matter
slowing down the allocator, if doing so lets it make better if (N >= 1 GiB) return [Link](N);
decisions. // Help bin-pack a single hugepage
if (N <= 1 MiB) return [Link](N);
Our allocator implements its interface by delegating to
several subcomponents, mapped in Figure 6. Each component if (N < 2 MiB) {
is built with the above principles in mind, and each specializes // If we can reuse empty space, do so
its approximation for the type of allocation it handles best. As Span s = [Link](N);
per principle #4, we emphasize smart placement over speed4 . if (s != NULL) return s;
While the particular implementation of T EMERAIRE is }
tied to TCM ALLOC internals, most modern allocators share
similar large backing allocations of page (or higher) granu- // If we have a region, use it
larity, like TCM ALLOC’s spans: compare jemalloc’s “ex- Span s = [Link](N);
tents” [20], Hoard’s “superblocks” [9], and mimalloc’s if (s != NULL) return s;
“pages” [29]. Hoard’s 8KB superblocks are directly allo-
cated with ‘mmap‘, preventing hugepage contiguity. Those // We need a new hugepage.
superblocks could instead be densely packed onto hugepages. s = [Link](N);
mimalloc places its 64KiB+ “pages” within “segments,” but [Link](s);
these are maintained per-thread which hampers dense pack-
ing across the segments of the process. Eagerly returning return s;
pages to the OS minimizes the RAM cost here, but breaks }
up hugepages. These allocators could also benefit from a
T EMERAIRE-like hugepage aware allocator5 .
Figure 7: Allocation flow for subcomponents. Hugepage size
is 2 MiB.
HugeAllocator

unbacked hugepages
Behind all components is the HugeAllocator, which deals
HugeCache with virtual memory and the OS. It provides other compo-
backed hugepages nents with unbacked memory that they can back and pass on.
We also maintain a cache of backed, fully-empty hugepages,
called the HugeCache.
HugeFiller HugeRegion We keep a list of partially filled single hugepages (the
HugeFiller) that can be densely filled by subsequent small
sometimes
allocations. Where binpacking the allocations along hugepage
small requests large requests medium requests boundaries would be inefficient, we implement a specialized
(< 1 MiB) (≥ 1 GiB) (1 MiB - 1 GiB) allocator (the HugeRegion).
T EMERAIRE directs allocation decisions to its subcompo-
nents based on request size with the algorithm in Figure 7.
Figure 6: T EMERAIRE’s components. Arrows represent the Each subcomponent is optimized for different allocation sizes.
flow of requests to interior components. Allocations for an exact multiple of hugepage size, or those
sufficiently large that slack is immaterial, we forward directly
to the HugeCache.
Intermediate sized allocations (between 1MiB and 1GiB)
4.1 The overall algorithm are typically also allocated from the HugeCache, with a final
We will briefly sketch the overall approach and each com- step of donation for slack. For example, a 4.5 MiB allocation
ponent’s role, then describe each component in detail. Our from the HugeCache produces 1.5 MiB of slack, an unaccept-
goal is to minimize generated slack, and if we do generate ably high overhead ratio. T EMERAIRE donates that slack to
slack, to reuse it for other allocations (as with any page-level the HugeFiller by pretending that the last hugepage of the
fragmentation.) request has a single “leading” allocation on it (Figure 8).
4 As each operation holds an often-contended mutex, we do maintain
When such a large span is deallocated, the allocator also
reasonable efficiency: most operations are O(1), with care taken to optimize
marks the fictitious leading allocation as free. If the slack is un-
constant factors. used, it is returned to the tail hugepage along with the rest. Oth-
5 Indeed, jemalloc is doing so, based on T EMERAIRE . erwise the tail hugepage is left behind in the HugeFiller and
 while (true) {
allocation slack Delete(New(512KB))
}

Figure 9: Program which repeatedly drains a single hugepage.

"free"

4.2 HugeAllocator
Figure 8: The slack from a large allocation spanning 3 huge- HugeAllocator tracks mapped virtual memory. All OS map-
pages is “donated” to the HugeFiller. The larger allocation’s pings are made here. It stores hugepage-aligned unbacked
tail is treated as a fictitious allocation. ranges (i.e. those with no associated physical memory.) Vir-
tual memory is nearly free, so we aim for simplicity and rea-
sonable speed. Our implementation tracks unused ranges with
only the first N − 1 hugepages are returned to the HugeCache. a treap [40]. We augment subtrees with their largest contained
range, which lets us quickly select an approximate best-fit.
For certain allocation patterns, intermediate-size alloca-
tions produce more slack than we can fill with smaller al-
locations in strict 2MiB bins. For example, many 1.1MiB 4.3 HugeCache
allocations will produce 0.9MiB of slack per hugepage (see
The HugeCache tracks backed ranges of memory at full huge-
Figure 12). When we detect this pattern, the HugeRegion
page granularity. A consequence of the HugeFiller filling
allocator places allocations across hugepage boundaries to
and draining whole hugepages is that we need to decide when
minimize this overhead.
to return empty hugepages to the OS. We will regret returning
Small requests (<= 1MiB) are always served from the memory we will need again, and equally regret not returning
HugeFiller. For allocations between 1MiB and a hugepage, memory that will languish in the cache. Returning memory
we evaluate several options: eagerly means we make syscalls to return the memory and
take page faults to reuse it. Releasing memory only at the rate
1. We try the HugeFiller: if we have available space there requested by TCM ALLOC’s periodic release thread means
we use it and are happy to fill a mostly-empty page. memory is held unused.
Consider the artificial program in Figure 9 with no addi-
2. If the HugeFiller can’t serve these requests, we next tional heap allocations. On each iteration of the loop, ‘New‘
consider HugeRegion; if we have regions allocated requires a new hugepage and places it with the HugeFiller.
which can serve the request, we do so. If no region exists ‘Delete‘ removes the allocation and the hugepage is now com-
(or they’re all too full) we consider allocating one, but pletely free. Returning eagerly would require a syscall every
only, as discussed below, if we’ve measured high ratios iteration for this simple, but pathological program.
of slack to small allocations. We track periodicity in the demand over a 2-second slid-
ing window and calculate the minimum and maximum seen
3. Otherwise, we allocate a full hugepage from the (demandmin , demandmax ). Whenever memory is returned to
HugeCache. This generates slack, but we anticipate that the HugeCache, we return hugepages to the OS if the cache
it will be filled by future allocations. would be larger than demandmax − demandmin . We also tried
other algorithms, but this one is simple and suffices to capture
We make a design choice in T EMERAIRE to care about the empirical dynamics we’ve seen. The cache is allowed
external fragmentation up to the level of a hugepage, but to grow as long as our windowed demand has seen a need
essentially not at all past it (but see Section 4.5 for an excep- for the new size. In oscillating usage, this will (incorrectly)
tion.) For example, a system with a single 1 GiB free range free memory once, then (correctly) keep it from then on. Fig-
and one with 512 discontiguous free hugepages is handled ure 10 shows our cache size for a Tensorflow workload which
equally well by T EMERAIRE. In either case, the allocator rapidly oscillates usage by a large fraction; we track the actu-
will (typically) return all of the unused space to the OS; a ally needed memory tightly.
fresh allocation of 1 GiB will require faulting in memory in
either case. In the fragmented scenario, we will need to do
4.4 HugeFiller
so on fresh virtual memory. Waste of virtual address range
unoccupied by live allocations and not consuming physical The HugeFiller satisfies smaller allocations that each fit
memory is not a concern, since with 64-bit address spaces, within a single hugepage. This satisfies the majority of allo-
virtual memory is practically free. cations (78% of the pageheap is backed by the HugeFiller
 500 • the longest free range (L), the number of contiguous
total usage pages not already allocated,
400 • the total number of allocations (A),
memory (MiB)

• the total number of used pages (U).

300 demand
These three statistics determine a priority order of huge-
200 pages to place allocations. We choose the hugepage with the
lowest sufficient L and the highest A. For an allocation of K
pages, we first consider only hugepages whose longest free
100 range is sufficient (L ≥ K). This determines whether a huge-
page is a possible allocation target. Among hugepages with
0 the minimum L ≥ K, we prioritize by fullness. Substantial
experimentation led us to choose A, rather than U.
time This choice is motivated by a radioactive decay-type al-
location model [16] where each allocation, of any size, is
equally likely to become free (with some probability p). In
Figure 10: Tensorflow’s demand on the HugeCache over time, this model a hugepage with 5 allocations has a probability
plotted with the cache limit (+demand). Notice that we tightly of becoming free of p5 << p; so we should very strongly
track their saw-toothed demand the first time it drops. After avoid allocating from hugepages with very few allocations.
that, we recognize the pattern and keep the peak demand in In particular, this model predicts A is a much better model of
cache. "emptiness" than U: one allocation of size M is more likely
to be deallocated than M allocations of size 1.
The decay model isn’t perfectly true in real applications, but
on average across the fleet) and is the most important–and
it is an effective approximation, and experimentation backs up
most optimized–component of our system. Within a given
its primary claim: prioritizing by A empties substantially more
hugepage, we use a simple (and fast) best-fit algorithm to
pages than prioritizing by U. (In practice, using U produces
place an allocation; the challenging part is deciding which
acceptable results, but meaningfully worse ones.)
hugepage to place an allocation on.
In some more detail, A is used to compute a chunk index C,
This component solves our binpacking problem: our goal given by min(0,Cmax − log2 (A)). We compute our chunk in-
is to segment hugepages into some that are kept maximally dex so that our fullest pages have C = 0 and the emptiest have
full, and others that are empty or nearly so. The emptiest C = Cmax −1. In practice, we have found that Cmax = 8 chunks
hugepages can be reclaimed (possibly breaking up a huge- are sufficient to avoid allocation from almost-empty pages.
page as needed) while minimizing the impact on hugepage Distinguishing hugepages with large counts is less important:
coverage as the densely-filled pages cover most used memory For example, we predict a hugepage with 200 allocations and
with hugepages. But it is challenging to empty out hugepages, one with 150 as both very unlikely to completely drain. This
since we cannot rely on any particular allocation disappearing. scheme prioritizes distinguishing gradations among pages
A secondary goal is to minimize fragmentation within each that might become empty.
hugepage, to make new requests more likely to be served. We store hugepages in an array of lists, where each huge-
If the system needs a new K-page span and no free ranges page is stored on the list at index I = Cmax ∗ L + C. Since
of ≥ K pages are available, we require a hugepage from a K-page allocation is satisfiable from any hugepage with
the HugeCache. This creates slack of (2MiB − K ∗ pagesize), L >= K, the hugepages which can satisfy an allocation are ex-
wasting space. actly those in lists with I >= Cmax ∗ K. We pick an (arbitrary)
These give us two goals to prioritize. Since we want to hugepage from the least such nonempty list, accelerating that
maximize the probability of hugepages becoming totally free, to constant time with a bitmap of nonempty lists.
nearly-empty hugepages are precious. Since we need to mini- Our strategy differs from best fit. Consider a hugepage X
mize fragmentation, hugepages with long free ranges are also with a 3 page gap and a 10 page gap and another hugepage
precious. Both priorities are satisfied by preserving hugepages Y with a 5 page gap. Best fit would prefer X. Our strategy
with the longest free range, as longer free ranges must have prefers Y . This strategy works since we are looking to allocate
fewer in-use blocks. We organize our hugepages into ranked on the most fragmented page, since fragmented pages are less
lists correspondingly, leveraging per-hugepage statistics. likely to become entirely free. If we need, say, 3 pages, then
Inside each hugepage, we track a bitmap of used pages; pages which contain at most a gap of 3 available pages are
to fill a request from some hugepage we do a best-fit search more likely to be fragmented and therefore good candidates
from that bitmap. We also track several statistics: for allocation. Under the radioactive-decay model, allocations
 500 // Delete large allocation
Delete(L);
}
400
Each iteration only allocates 1 (net) page, but if we always
memory (MiB)

use the slack from L to satisfy S, we will end up placing

300
each S on its own hugepage. In practice, simply refusing to
use donated pages if others are available prevents this, while
200 effectively using slack where it’s needed.
Demand
LFR-priority 4.5 HugeRegion
100
Best-fit
Fullness-priority HugeCache (and HugeAllocator behind it) suffices for large
0 allocations, where rounding to a full hugepage is a small
time cost. HugeFiller works well for small allocations that can
be packed into single hugepages. HugeRegion helps those
between.
Figure 11: HugeFiller with various bin-packing strate- Consider a request for 1.1 MiB of memory. We serve it
gies. Best fit is outperformed by prioritizing either fullness or from the HugeFiller, leaving 0.9 MiB of unused memory
longest free range (LFR); LFR dominates fullness. from the 2MiB hugepage: the slack space. The HugeFiller
assumes that slack will be filled by future small (<1MiB)
near large gaps are as likely as any other to become free, allocations, and typically it is: our observed byte ratio of fleet-
which can cause those gaps to substantially grow; they can wide small allocations to slack is 15:1. In the limit we can
then be used for large allocations. We treat that 10-page gap imagine a binary that requests literally nothing but 1.1 MiB
as precious and avoid allocating near it unless nothing else spans in Figure 12.
works, which allows it to grow. The HugeRegion deals with this problem, which is to
Figure 11 demonstrates this in a simple case. We plot the some extent caused by our own choices. We focus heavily
demand on the HugeFiller from a synthetic trace (see Sec- on packing allocations into hugepage-sized bins with the
tion 6.1). We also show the total used memory from three HugeFiller, and our desire to do that with donated slack
approaches: HugeFiller’s actual search, a search that priori- is catastrophic with some allocation patterns. Most normal
tizes fullness over fragmentation (A over L), and a global best binaries are of course fine without it, but a general purpose
fit. Note that the trace includes a substantial one-time drop, memory allocator needs to handle diverse workloads, even
to go with random fluctuations in usage. Our LFR-priority those dominated by slack-heavy allocations. Clearly, we must
algorithm beats both other approaches. In particular, we see be able to allocate these lying across hugepage boundaries.
that after the usage drop, best-fit barely recovers any total HugeRegion neatly eliminates this pathological case.
memory, and finishes with close to 100% overhead, whereas A HugeRegion is a large fixed-size allocation (currently 1
both other algorithms closely match the actual demand. GiB) tracked at small-page granularity with the same kind
Surprisingly, this simple strategy substantially outperforms of bitmaps used by individual hugepages in the HugeFiller.
a global best fit algorithm–placing a request in the single gap As with those single hugepage ranges, we best-fit any request
in any hugepage that is closest to its size. Best-fit would be across all pages in the region. We keep a list of these re-
prohibitively expensive—we cannot search 10-100K huge- gions, ordered by longest free range, for the same reason as
pages for every request, but it’s quite counter-intuitive that it HugeFiller. Allocating from these larger bins immediately
also produces higher fragmentation. Best-fit being far from allows large savings in wasted space: rather than losing 0.9
optimal for general fragmentation problems is not a new re- MiB/hugepage in our pessimal load, we lose 0.9 MiB per
sult [36], but it’s interesting to see how poor it can be here.
A last important detail is that donated hugepages are less
desirable allocation targets than any non-donated hugepage. a s
Consider the pathological program looping:

while (true) { Figure 12: Slack (“s”) can accumulate when many allocations
// Reserve 51 hugepages + donate tail of last (“a”) are placed on single hugepages. No single slack region
L = New(100 MiB + 1 page); is large enough to accommodate a subsequent allocation of
// Make a small allocation size “a.”
S = New(1);
HugeRegion, only about 0.1%. (This motivates the large size ing both CPU and memory savings. We present evaluations
of each region.) of T EMERAIRE on several key services, measuring 10% of
Most programs don’t need regions at all. We do not allocate cycles and 15% of RAM usage in our WSC. In section 6.4
any region until we’ve accumulated large quantities of slack we discuss workload diversity; in this evaluation we examine
that are larger than the total of the program’s small allocations. data across all workloads using our experimental framework
Fleetwide, only 8.8% of programs trigger usage of regions, and fleetwide-profiler telemetry. We’ve argued for prioritizing
but the feature is still important: 53.2% of allocations in those workload efficiency over the attributable cost of malloc; we
binaries are served from regions. One such workload is a therefore examine IPC metrics (as a proxy for user through-
key-value store that loads long-lived data in large chunks put) and where possible, we obtained application-level perfor-
into memory and makes a small number of short-lived small mance metrics to gauge workload productivity (e.g., requests-
allocations for serving requests. Without regions, the request- per-second per core) on our servers. We present longitudinal
related allocations are unable to fill the slack generated by the data from the rollout of T EMERAIRE to all TCM ALLOC users
larger allocations. This technique prevents this slack-heavy in our fleet.
uncommon allocation pattern from bloating memory use. Overall, T EMERAIRE proved a significant win for CPU and
memory.
4.6 Memory Release
As discussed above, Release(N) is invoked periodically by
5.1 Application Case Studies
support threads at a steady trickle. We worked with performance-sensitive applications to enable
To implement our interface’s Release(N) methods, T EMERAIRE in their production systems, and measure the
T EMERAIRE typically just frees hugepage ranges from effect. We summarize the results in Table 1. Where possible,
HugeCache and possibly shrinks its limit as described above. we measured each application’s user-level performance met-
Releasing more than the hinted N pages is not a problem; the rics (throughput-per-CPU and latency). These applications
support threads use the actual released amount as feedback, use roughly 10% of cycles and 15% of RAM in our WSC.
and adjust future calls to target the correct overall rate. Four of these applications (search1; search2; search3;
If the HugeCache cannot release N pages of memory, the and loadbalancer) had previously turned off the periodic
HugeFiller will subrelease just the free (small) pages on the memory release feature of TCM ALLOC. This allowed them
emptiest hugepage. to have good hugepage coverage, even with the legacy page-
Returning small pages from partially filled hugepages heap’s hugepage-oblivious implementation, at the expense of
(“subreleasing” them) is the last resort for reducing memory memory. We did not change that setting with T EMERAIRE.
footprints as the process is largely irreversible6 . By returning These applications maintained their high levels of CPU per-
some but not all small pages on a hugepage, we cause the OS formance while reducing their total memory footprint.
to replace the single page table entry spanning the hugepage With the exception of Redis, all of these applications are
with small entries for the remaining pages. This one-way op- multithreaded. With the exception of search3, these work-
eration, through increased TLB misses, slows down accesses loads run on a single NUMA domain with local data.
to the remaining memory. The Linux kernel will use small
pagetable entries for the still-used pages, even if we re-use • Tensorflow [1] is a commonly used machine learning ap-
the released address space later. We make these return deci- plication. It had previously used a high periodic release
sions in the HugeFiller, where we manage partially filled rate to minimize memory pressure, albeit at the expense
hugepages. of hugepages and page faults.
The HugeFiller treats the subreleased hugepages sepa-
rately: we do not allocate from them unless no other hugepage • search1, search2, ads1, ads2, ads4, ads5 receive
is usable. Allocations placed on this memory will not benefit RPCs and make subsequent RPCs of their own other
from hugepages, so this helps performance and allows these services.
partially released hugepages to become completely empty.
• search3, ads3, ads6 are leaf RPC servers, performing
read-mostly retrieval tasks.
5 Evaluation of T EMERAIRE
• Spanner [17] is a node in a distributed database. It also
We evaluated T EMERAIRE on Google’s WSC workloads. includes an in-memory cache of data read from disk
The evaluation was concerned with several metrics, includ- which adapts to the memory provisioned for the process
6 While the THP machinery may reassemble hugepages, it is non- and unused elsewhere by the program.
deterministic and dependent on system utilization. There is a negative feed-
back loop here where high-utilization scenarios actually compete with and • loadbalancer receives updates over RPC and periodi-
impede THP progress that might benefit them the most. cally publishes summary statistics.
 Mean RSS RAM IPC dTLB Load Walk (%) malloc (% of cycles) Page Fault (% of cycles)
Application Throughput
Latency (GiB) change Before After Before After Before After Before After
Tensorflow [1] +26%
search1 [6, 18]† 8.4 -8.7% 1.33 ± 0.04 1.43 ± 0.02 9.5 ± 0.6 9.0 ± 0.6 5.9 ± 0.09 5.9 ± 0.12 0.005 ± 0.003 0.131 ± 0.071
search2† 3.7 -20% 1.28 ± 0.01 1.29 ± 0.01 10.3 ± 0.2 10.2 ± 0.1 4.37 ± 0.05 4.38 ± 0.02 0.003 ± 0.003 0.032 ± 0.002
search3 † 234 -7% 1.64 ± 0.02 1.67 ± 0.02 8.9 ± 0.1 8.9 ± 0.3 3.2 ± 0.02 3.3 ± 0.04 0.001 ± 0.000 0.005 ± 0.001
ads1 +2.5% -14% 4.8 -6.9% 0.77 ± 0.02 0.84 ± 0.01 38.1 ± 1.3 15.9 ± 0.3 2.3 ± 0.04 2.7 ± 0.05 0.012 ± 0.003 0.011 ± 0.002
ads2 +3.4% -1.7% 5.6 -6.5% 1.12 ± 0.01 1.22 ± 0.01 27.4 ± 0.4 10.3 ± 0.2 2.7 ± 0.03 3.5 ± 0.08 0.022 ± 0.001 0.047 ± 0.001
ads3 +0.5% -0.2% 50.6 -0.8% 1.36 ± 0.01 1.43 ± 0.01 27.1 ± 0.5 11.6 ± 0.2 2.9 ± 0.04 3.2 ± 0.03 0.067 ± 0.002 0.03 ± 0.003
ads4 +6.6% -1.1% 2.5 -1.7% 0.87 ± 0.01 0.93 ± 0.01 28.5 ± 0.9 11.1 ± 0.3 4.2 ± 0.05 4.9 ± 0.04 0.022 ± 0.001 0.008 ± 0.001
ads5 +1.8% -0.7% 10.0 -1.1% 1.16 ± 0.02 1.16 ± 0.02 21.9 ± 1.2 16.7 ± 2.4 3.6 ± 0.08 3.8 ± 0.15 0.018 ± 0.002 0.033 ± 0.007
ads6 +15% -10% 53.5 -2.3% 1.40 ± 0.02 1.59 ± 0.03 33.6 ± 2.4 17.8 ± 0.4 13.5 ± 0.48 9.9 ± 0.07 0.037 ± 0.012 0.048 ± 0.067
Spanner [17] +6.3% 7.0 1.55 ± 0.30 1.70 ± 0.14 31.0 ± 4.3 15.7 ± 1.8 3.1 ± 0.88 3.0 ± 0.24 0.025 ± 0.08 0.024 ± 0.01
loadbalancer† 1.4 -40% 1.38 ± 0.12 1.39 ± 0.28 19.6 ± 1.2 9.5 ± 4.5 11.5 ± 0.60 10.7 ± 0.46 0.094 ± 0.06 0.057 ± 0.062
Average (all WSC apps) +5.2% -7.9% 1.26 1.33 23.3 12.4 5.2 5.0 0.058 0.112
Redis† +0.75%
Redis +0.44%

Table 1: Application experiments from enabling T EMERAIRE. Throughput is normalized for CPU. †: Applications’ periodic
memory release turned off. dTLB load walk (%) is the fraction of cycles spent page walking, not accessing the L2 TLB. malloc
(% of cycles) is the relative amount of time in allocation and deallocation functions. 90%th confidence intervals reported.

• Redis is a popular, open-source key-value store. We 80

evaluated the performance of Redis 6.0.9 [42] with
T EMERAIRE, using TCM ALLOC’s legacy page heap as 67.3

% hugepage coverage
a baseline. These experiments were run on servers with 60
Intel Skylake Xeon processors. Redis and TCM ALLOC
were compiled with LLVM built from Git commit
‘cd442157cf‘ using ‘-O3‘. In each configuration, we ran 44.3
40
2000 trials of ‘redis-benchmark‘, with each trial making
1000000 requests to push 5 elements and read those 5
elements. 23
20
For the 8 applications with periodic release, we observed a
11.8
mean CPU improvement of 7.7% and a mean RAM reduction
of 2.4%. Two of these workloads did not see memory reduc- 0
tions. T EMERAIRE’s HugeCache design handles Tensorflow’s periodic release on periodic release off
allocation pattern well, but cannot affect its bursty demand.
Spanner maximizes its caches up to a certain memory limit, control T EMERAIRE
so reducing TCM ALLOC’s overhead meant more application
data could be cached within the same footprint.
Figure 13: Percentage of heap memory backed by hugepages
during fleet experiment and 90%th confidence interval. (Error
5.2 Fleet experiment bars in "release on" condition are too small to cleanly render.)
We randomly selected 1% of the machines distributed through-
out our WSCs as an experiment group and a separate 1% as
a control group (see section 6.4). We enabled T EMERAIRE
on all applications running on the experiment machines. The We observed a strong improvement even in the case that pe-
applications running on control machines continued to use riodic release was disabled. Since these binaries do not break
the stock pageheap in TCM ALLOC. up hugepages in either configuration, the benefit is derived
Our fleetwide profiler lets us correlate performance metrics from increased system-wide availability of hugepages (due
against the groupings above. We collected data on memory to reduced fragmentation in other applications). T EMERAIRE
usage, hugepage coverage, overall IPC, and TLB misses. At improves this situation in two ways: since we aggressively re-
the time of the experiment, application-level performance lease empty hugepages (where the traditional pageheap does
metrics (throughput-per-CPU, latency) were not collected. In not), we consume fewer hugepages that we do not need, allow-
our analysis, we distinguish between applications that period- ing other applications to more successfully request them, and
ically release memory to the OS and those that turn off this other co-located applications are no longer breaking up huge-
feature to preserve hugepages with TCM ALLOC’s prior non- pages at the same rate. Even if we map large aligned regions
hugepage-aware pageheap. Figure 13 shows that T EMERAIRE of memory and do not interfere with transparent hugepages,
improved hugepage coverage, increasing the percentage of the kernel cannot always back these with hugepages [26, 33].
heap memory backed by hugepages from 11.8% to 23% for Fragmentation in physical memory can limit the number of
applications periodically releasing memory and from 44.3% available hugepages on the system.
to 67.3% for applications not periodically releasing memory. We next examine the effect this hugepage coverage had
 Periodic Walk Cycles (%) MPKI
Release Control Exp. Control Exp.
On 12.5 11.9 (-4.5%) 1.20 1.14 (-5.4%) -1.3%

%age of TLB miss cycles

Off 14.1 13.4 (-5%) 1.36 1.29 (-5.1%) 20
Table 2: dTLB load miss page walk cycles as percentage of
application usage and dTLB misses per thousand instructions
(MPKI) without T EMERAIRE (Control) T EMERAIRE enabled 15
(Exp.)

10
on TLB misses. Again, we break down between apps that
enable and disable periodic memory release. We measure the
percentage of total cycles spent in a dTLB load stall7 . 5
We see reductions of 4.5-5% of page walk miss cycles
(Table 2). We see in the experiment data that apps not re- 10 20 30 40 50 60
leasing memory (which have better hugepage coverage) have time (days)
higher dTLB stall costs, which is slightly surprising. Our dis-
load (old) store (old)
cussions with teams managing these applications is that they
turn off memory release because they need to guarantee per- load (T EMERAIRE) store (T EMERAIRE)
formance: on average, they have more challenging memory
access patterns and consequently greater concerns about mi- Figure 14: Stacked line graph showing effect of T EMERAIRE
croarchitectural variance. By disabling this release under the rollout on TLB miss cycles. We see an overall downward
prior implementation, they observed better application perfor- trend from 21.6% to 20.3% as T EMERAIRE became a larger
mance and fewer TLB stalls. With T EMERAIRE, we see our fraction of observed usage in our WSC.
improved hugepage coverage leads to materially lower dTLB
costs for both classes of applications.
For our last CPU consideration, we measured the over-
to 20.3% (6% reduction) and a reduction in pageheap over-
all impact on IPC8 . Fleetwide overall IPC in the control
head from 14.3% to 10.6% (26% reduction). Figure 14 shows
group was 0.796647919 ± 4e−9; in the experiment group,
the effect on TLB misses over time: at each point we show
0.806301729 ± 5e−9 instructions-per-cycle. This 1.2% im-
the total percentage of cycles attributable to TLB stalls (load
provement is small in relative terms but is a large absolute
and store), broken down by pageheap implementation. As
savings (especially when considered in the context of the
T EMERAIRE rolled out fleetwide, it caused a noticeable down-
higher individual application benefits discussed earlier).
ward trend.
For memory usage, we looked at pageheap overhead: the Figure 15 shows a similar plot of pageheap overhead. We
ratio of backed memory in the pageheap to the total heap see another significant improvement. Hugepage optimization
memory in use by the application. The experiment group has a natural tradeoff between space and time here; saving the
decreased this from 15.0% to 11.2%, again, a significant im- maximum memory possible requires breaking up hugepages,
provement. The production experiments comprise thousands which will cost CPU cycles. But T EMERAIRE outperforms
of applications running continuously on many thousands of the previous design in both space and time. We highlight
machines, conferring high confidence in a fleetwide benefit. several conclusions from our data:
Application productivity outpaced IPC. As noted above
5.3 Full rollout trajectories and by Alameldeen et al. [3], simple hardware metrics don’t
always accurately reflect application-level benefits. By all
With data gained from individual applications and the indication, T EMERAIRE improved application metrics (RPS,
1% experiment, we changed the default9 behavior to use latencies, etc.) by more than IPC.
T EMERAIRE. This rolled out to 100% of our workloads grad- Gains were not driven by reduction in the cost of malloc.
ually [10, 38]. Gains came from accelerating user code, which was some-
Over this deployment, we observed a reduction in cycles times drastic–in both directions. One application (ads2) saw
stalled on TLB misses (L2 TLB and page walks) from 21.6% an increase of malloc cycles from 2.7% to 3.5%, an apparent
regression, but they reaped improvements of 3.42% RPS, 1.7%
7 More precisely cycles spent page walking, not accessing the L2 TLB.
8 Our source of IPC data is not segmented by periodic background memory
latency, and 6.5% peak memory usage.
release status.
There is still considerable headroom, and small percent-
9 This doesn’t imply, quite, that every binary uses it. We allow opt outs ages matter. Even though T EMERAIRE has been successful,
for various operational needs. hugepage coverage is still only 67% when using T EMERAIRE
 6.1 “Empirical” distribution sampling
15
Our production fleet implements a fleet wide profiler [35].
%age memory overhead

-3.7% Among the data collected by this profiler are fleet-wide sam-
ples of malloc tagged with request size and other useful prop-
10 erties. We collect a sample of currently-live data in our heap
and calls to malloc. From these samples we can infer the
empirical distribution of size both for live objects and mal-
loc calls. Our empirical driver generates calls to malloc and
5 free as a Poisson process10 that replicates these distributions,
while also targeting an arbitrary (average) heap size. That
target size can be changed over simulated time, reproducing
factors such as diurnal cycles, transient usage, or high startup
costs. We have made this driver and its inputs available on
20 40 60 80 Github (see Section 9).
time (days) Despite the name “empirical driver,” this remains a highly
unrealistic workload: every allocation (of a given size) is
old T EMERAIRE
equally likely to be freed at any timestep, and there is no cor-
relation between the sizes of consecutive allocation. Neither
Figure 15: Stacked line graph showing effect of T EMERAIRE does it reproduce per-thread or per-CPU dynamics. Never-
rollout on pageheap overhead. Total memory overhead goes theless, the empirical driver is a fast, efficient way to place
from 14.3% to 10.6%, as T EMERAIRE became a larger frac- malloc under an extremely challenging load that successfully
tion of observed usage in our WSC by growing from a handful replicates many macro characteristics of real work.
of applications (section 5.1) to nearly all applications.

6.2 Heap tracing

Tracing every call to malloc without the instrumentation
without subrelease due to physical memory contiguity limita- overhead perturbing the workload itself is extremely difficult,
tions. Increasing to 100% would significantly improve appli- even infeasible over long timescales. Typical applications
cation performance. can make millions of calls to malloc per second. Even if
tracing was accomplished non-disruptively, replaying these
traces back accurately into a memory allocator in real time or
faster is similarly intractable: it’s difficult to force the right
6 Strategies used in building T EMERAIRE combinations of threads to allocate, access, and free the right
buffers on the right CPU at the right (relative) time.
Fortunately, tracing the pageheap is considerably easier. It
It is difficult to predict the best approach for a complex sys- is a single-threaded allocator, only invoked by a small fraction
tem a priori. Iteratively designing and improving a system of requests. Playback is also simple–our abstractions allow
is a commonly used technique. Military pilots coined the directly instantiating and manipulating our pageheap repre-
term “OODA (Observe, Orient, Decide, Act) loop” [13] to sentation, rather than going through malloc() itself. Traces
measure a particular sense of reaction time: seeing incom- taken from both real binaries and, surprisingly, the empirical
ing data, analyzing it, making choices, and acting on those driver itself, played a major role in developing T EMERAIRE.
choices (producing new data and continuing the loop). Shorter T EMERAIRE’s components serve a request for K pages
OODA loops are a tremendous tactical advantage to pilots with memory at address [p, p + K), but never read or write
and accelerate our productivity as well. Optimizing our own that memory range. We built this for unit testing–allowing
OODA loop–how quickly we could develop insight into a the test of corner cases such as 64 GiB of allocations without
design choice, evaluate its effectiveness, and iterate towards actually needing 64 GiB of memory–but this is also crucial
better choices–was a crucial step in building T EMERAIRE. to accelerating simulations. What might take hours with the
While our final evaluation was driven by execution on empirical driver can be played back in minutes.
our production servers, this was both too disruptive and too
10 Little’s law tells us that the average number of live objects L is equal to
risky to test intermediate ideas; however, malloc microbench-
the product of the arrival rate λ and average lifetime W . To replicate a given
marks are also not particularly interesting at the page level.
distribution of live/allocation object sizes where pa of live objects have size
To address these challenges, we generated traces to drive the a, we set Wa = c·p a
λa . (c is a scaling parameter that determines the total heap
development of TCM ALLOC in two ways. size.)
6.3 Telemetry i + 1 when malloc is returning object i from its freelists. Ef-
fective prefetches need to be timely [28]. Too early and data
Beyond producing numbers motivating and evaluating our
can be evicted from the cache before use. Too late and the pro-
work, our fleetwide profiler is itself a powerful tool for de-
gram waits. In this case, prefetching object i when returning
signing allocators. It reveals patterns of allocation we can use
it, turns out to be too late: User code will write to the object
to derive heuristics, it allows validation of hypotheses about
within a few cycles, far sooner than the prefetch’s access to
typical (or even possible) behavior, it helps identify which pat-
main memory can complete. Prefetching object i + 1 gives
terns we can safely ignore as unimportant and which we must
time for the object to be loaded into the cache by the time
optimize. Besides being used in obvious ways–such as tuning
the next allocation occurs. Independent of the experiments
cache sizes to fit typical use or determining thresholds for
to develop T EMERAIRE, we added this next object prefetch
“small” allocations based on the CDF of allocations–querying
for TCM ALLOC usage in our WSC despite the contrarian
the profiler was our first step whenever we were unsure of
evidence that it appears to slowdown microbenchmarks and
useful facts. We gained confidence that our approach to filling
increases apparent malloc cost. We were able to still identify
slack (see section 4.5) worked on diverse workloads by query-
this benefit thanks to the introspective techniques described
ing the profiler for ratios of page allocation sizes. Providing
here, allowing us to prove that application performance was
large scale telemetry that can be consumed by data analysis
improved at scale in our WSC; both unlocking important per-
tools makes it easy to test and eliminate hypotheses. Such
formance gains and proving the generality of these macro
"tiny experiments" [8] lead to better designs.
approaches.
This reflects a cultivated mindset in identifying new teleme-
try. Our first question for any new project is “What metrics
should we add to our fleetwide profiler?” We continually 7 Future Work
expose more of the allocator’s internal state and derived statis-
tics, such as cache hit rates. While we can form some hypothe- Peak vs. average. A job quickly oscillating between peak
ses using traditional loadtests, this technique helps validate and trough demand cannot be usefully binpacked against its
their generality. average. Even if the allocator could instantaneously return
unused memory, job schedulers could not make use of it be-
fore it was required again. Thus transient overhead is not a
6.4 Experiment framework practical opportunity [43]. This guides us to measure how
We have also developed an experiment framework allowing us overhead changes over time, which can motivate slower re-
to A/B test implementations or tuning choices across our fleet lease rates [31] or application of compaction techniques (such
at scale. We can enable or disable experiment groups across as Mesh [34]).
a small percentage of all our machines, without requiring Intermediate caches / exposed free spans. TCM ALLOC’s
product teams running services on those machines to take any design of stacked caches makes for direct optimization and is
action. A/B testing is not a new approach, but enabling it at highly scalable, but hides useful cross-layer information. A
the scale of our WSC is a powerful development tool. good example comes from Bigtable at Google [14]. Cached
As discussed above, our A/B experiment for T EMERAIRE ranges are 8 KiB malloc’d segments (i.e. one TCM ALLOC
demonstrated improved hugepage coverage, even for jobs page) to avoid fragmentation. Meaning, most freed buffers
that never released memory. This is an example of an effect– won’t make it past the local cache or central freelist; only
against neighboring, collocated services–that might go unno- when a full span’s worth is simultaneously freed (and some-
ticed during the test of an individual service. how pushed out of TCM ALLOC’s local cache) do these freed
We’ve observed two noteworthy advantages to A/B experi- buffers get returned to the pageheap. If every alloc/free of
mentation: these chunks were visible to the pageheap, we’d be able to re-
duce fragmentation–we’d have a much more precise estimate
• Reduced cost and uncertainty associated with major be-
of available space within each hugepage. Of course, if every
havioral changes. Small 1% experiments can uncover
malloc(8192)/free went to the pageheap, we would also
latent problems well before we roll new defaults, at far
eliminate all scalability! There must be a middle ground. Can
less cost [10, Appendix B].
we expose the contents of frontline caches to the pageheap
• Reduced likelihood of overfitting to easily tested work-
and reduce fragmentation?
loads. Tuning for production-realistic loadtests, while
Upfront costs / amortization / prediction. The fact we can-
great for the applications they represent, can result in
not anticipate what Delete() calls will come in the future
non-ideal results for other workloads. Instead, we can be
is the hardest part of building a hugepage-friendly algorithm.
confident our optimization is good on average for every-
We try to generate empty hugepages through heuristics and
one, and detect (and fix) applications that see problems.
hope: we aim to have mostly-empty things stay that way and
Experiments allow us to evaluate changes on diverse work- hope that the final allocations will quickly get freed. But some
loads. Kanev, et. al. [24] proposed prefetching the next object allocations are likely immortal–common data structures that
are used throughout the program’s run, or frequently used proposed managing memory contiguity as a resource at the
pages that will bounce in and out of local caches. kernel level. Panwar et. al. [32] observed memory bloat from
We can improve allocation decisions when we know– using the Linux’s transparent hugepage implementation, due
immortal or not–they will be hot and see frequent access. to insufficient userspace level packing.
Ensuring these allocations are placed onto hugepages pro- Optimization of TLB usage in general has been discussed
vides larger marginal performance benefit. TLB misses occur extensively; Basu [7] suggested resurrecting segments to
on access, so it may be preferable to save memory rather than avoid it entirely, addressing TLB usage at the architectural
improve access latency to colder allocations. level. CoLT [33] proposed variable-size hugepages to mini-
Far memory cooperation “Far memory” [27] allows us to mize the impact of fragmentation. Illuminator [5] improves
move data to slower, but less expensive memory, reducing page decisions in the kernel to reduce physical memory frag-
DRAM costs. Clustering rarely accessed allocations can make mentation. Ingens [26] attempts to fairly distribute a lim-
far memory more effective. More overhead can be afforded on ited supply of kernel-level hugepages and HawkEye [32]
those decisions since they can’t happen very often. Avenues manages kernel allocation of hugepages to control memory
like machine learning [30] or profile directed optimization [15, bloat. Kernel-based solutions can be defeated by hugepage-
37] show promise for identifying these allocations. oblivious user allocators that return partial hugepages to the
Userspace-Kernel Cooperation T EMERAIRE places mem- OS and fail to densely pack allocations onto hugepages.
ory in a layout designed to be compatible with kernel huge- At the malloc level, SuperMalloc [25] considers huge-
page policy (Section 2), but this is only an implicit cooper- pages, but only for very large allocations. MallocPool [22]
ation. Kernel APIs which prioritize the allocation of huge- uses similar variable-sized TLBs as CoLT [33] but does not
pages within an address space or across processes would en- attempt to used fixed-size hugepages. LLAMA [30] studies
able proactive management of which regions were hugepage- a possible solution using lifetime predictions, but solutions
backed, versus the current best-effort reactive implementation. with practical costs remain open problems.
In developing T EMERAIRE, we considered but did not de-
ploy an interface to request a memory region be immediately
repopulated with hugepages. T EMERAIRE primarily tries to 9 Conclusion
avoid breaking up hugepages altogether as the existing THP
machinery is slow to reassemble them (Section 4.6). Being In warehouse scale computers, TLB lookup penalties are one
able to initiate on-demand repopulation would allow an ap- of the most significant compute costs facing large applica-
plication to resume placing allocations in that address space tions. T EMERAIRE optimizes the whole WSC by changing
range without a performance gap. the memory allocator to make hugepage-conscious place-
A common problem today is that the first applications to ment decisions while minimizing fragmentation. Application
execute on a machine are able to claim the majority of huge- case studies of key workloads from Google’s WSCs show
pages, even if higher priority applications are subsequently RPS/CPU increased by 7.7% and RAM usage decreased by
assigned. We ultimately imagine that such a management 2.4%. Experiments at fleet scale and longitudinal data during
system might execute as an independent user daemon, coop- the rollout at Google showed a 6% reduction in cycles spent
erating with individual applications. Kernel APIs could allow in TLB misses, and 26% reduction in memory wasted due to
hugepages to be more intelligently allocated against a more fragmentation. Since the memory system is the biggest bot-
detailed gradient of priority, benefit, and value. tleneck in WSC applications, there are further opportunities
to accelerate application performance by improving how the
allocator organizes memory and interacts with the OS.
8 Related work
Some work has optimized malloc for cache efficiency of Acknowledgments
user-level applications. To minimize L1 conflicts, Dice [19]
proposed jittering allocation sizes. Similarly, a cache-index- Our thanks to our shepherd Tom Anderson for his help improv-
aware allocator [2] reduces conflict misses by changing rela- ing this paper. We also thank Atul Adya, Sanjay Ghemawat,
tive placement of objects inside pages. mimalloc [29] tries to Urs Hölzle, Arvind Krishnamurthy, Martin Maas, Petros Ma-
give users objects from the same page, increasing the locality. niatis, Phil Miller, Danner Stodolsky, and Titus Winters, as
Addressing this at the kernel level alone would face the well as the OSDI reviewers, for their feedback.
same fragmentation challenges and be more difficult to handle
because we have less control over application memory usage. Availability
The kernel can back the memory region with a hugepage,
but if the application does not densely allocate from that The code repository at [Link]
hugepage, memory is wasted by fragmentation. Prior work includes T EMERAIRE. It also includes the empirical driver
has examined the kernel side of this problem: Kwon et. al. [26] (6.1) and its input parameters (CDF of allocation sizes).
References International Conference on Measurement and Mod-
eling of Computer Systems, SIGMETRICS ’04/Perfor-
[1] Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng mance ’04, page 25–36, New York, NY, USA, 2004.
Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, San- Association for Computing Machinery.
jay Ghemawat, Geoffrey Irving, Michael Isard, Man-
junath Kudlur, Josh Levenberg, Rajat Monga, Sherry [12] Jeff Bonwick and Jonathan Adams. Magazines and
Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vmem: Extending the Slab Allocator to Many CPUs
Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Arbitrary Resources. In Proceedings of the Gen-
and Xiaoqiang Zheng. Tensorflow: A system for large- eral Track: 2001 USENIX Annual Technical Conference,
scale machine learning. In 12th USENIX Symposium on page 15–33, USA, 2001. USENIX Association.
Operating Systems Design and Implementation (OSDI
16), pages 265–283, 2016. [13] John R. Boyd. Patterns of Conflict. 1981.

[2] Yehuda Afek, Dave Dice, and Adam Morrison. Cache [14] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C.
Index-Aware Memory Allocation. SIGPLAN Not., Hsieh, Deborah A. Wallach, Mike Burrows, Tushar
46(11):55–64, June 2011. Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable:
A Distributed Storage System for Structured Data. In
[3] A. R. Alameldeen and D. A. Wood. IPC Considered 7th USENIX Symposium on Operating Systems Design
Harmful for Multiprocessor Workloads. IEEE Micro, and Implementation (OSDI), pages 205–218, 2006.
26(4):8–17, 2006.
[15] Dehao Chen, David Xinliang Li, and Tipp Moseley. Aut-
[4] Andrea Arcangeli. Transparent hugepage support. 2010. ofdo: Automatic Feedback-Directed Optimization for
Warehouse-Scale Applications. In CGO 2016 Proceed-
[5] Aravinda Prasad Ashish Panwar and K. Gopinath. Mak- ings of the 2016 International Symposium on Code Gen-
ing Huge Pages Actually Useful. In Proceedings of the eration and Optimization, pages 12–23, New York, NY,
Twenty-Third International Conference on Architectural USA, 2016.
Support for Programming Languages and Operating
Systems (ASPLOS ’18), 2018. [16] William D. Clinger and Lars T. Hansen. Generational
Garbage Collection and the Radioactive Decay Model.
[6] Luiz Andre Barroso, Jeffrey Dean, and Urs Hölzle. Web
SIGPLAN Not., 32(5):97–108, May 1997.
search for a planet: The google cluster architecture.
IEEE Micro, 23:22–28, 2003. [17] James C. Corbett, Jeffrey Dean, Michael Epstein,
Andrew Fikes, Christopher Frost, JJ Furman, Sanjay
[7] Arkaprava Basu, Jayneel Gandhi, Jichuan Chang,
Ghemawat, Andrey Gubarev, Christopher Heiser, Pe-
Mark D. Hill, and Michael M. Swift. Efficient Virtual
ter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eu-
Memory for Big Memory Servers. In Proceedings of
gene Kogan, Hongyi Li, Alexander Lloyd, Sergey Mel-
the 40th Annual International Symposium on Computer
nik, David Mwaura, David Nagle, Sean Quinlan, Rajesh
Architecture, ISCA ’13, page 237–248, New York, NY,
Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak,
USA, 2013. Association for Computing Machinery.
Christopher Taylor, Ruth Wang, and Dale Woodford.
[8] Jon Bentley. Tiny Experiments for Algorithms and Life. Spanner: Google’s Globally-Distributed Database. In
In Experimental Algorithms, pages 182–182, Berlin, Hei- 10th USENIX Symposium on Operating Systems Design
delberg, 2006. Springer Berlin Heidelberg. and Implementation (OSDI 12), Hollywood, CA, 2012.

[9] Emery D. Berger, Kathryn S. McKinley, Robert D. Blu- [18] Jeffrey Dean. Challenges in building large-scale infor-
mofe, and Paul R. Wilson. Hoard: A Scalable Memory mation retrieval systems: invited talk. In WSDM ’09:
Allocator for Multithreaded Applications. SIGPLAN Proceedings of the Second ACM International Confer-
Not., 35(11):117–128, November 2000. ence on Web Search and Data Mining, pages 1–1, New
York, NY, USA, 2009.
[10] Jennifer Petoff Betsy Beyer, Chris Jones and
Niall Richard Murphy. Site Reliability Engineering: [19] Dave Dice, Tim Harris, Alex Kogan, and Yossi Lev. The
How Google Runs Production Systems. O’Reilly Media, Influence of Malloc Placement on TSX Hardware Trans-
Inc, 2016. actional Memory. CoRR, abs/1504.04640, 2015.

[11] Stephen M. Blackburn, Perry Cheng, and Kathryn S. [20] Jason Evans. A scalable concurrent malloc (3) imple-
McKinley. Myths and Realities: The Performance Im- mentation for FreeBSD. In Proceedings of the BSDCan
pact of Garbage Collection. In Proceedings of the Joint Conference, 2006.
[21] T. B. Ferreira, R. Matias, A. Macedo, and L. B. Araujo. [30] Martin Maas, David G. Andersen, Michael Isard, Mo-
An Experimental Study on Memory Allocators in Mul- hammad Mahdi Javanmard, Kathryn S. McKinley, and
ticore and Multithreaded Applications. In 2011 12th Colin Raffel. Learning-based Memory Allocation for
International Conference on Parallel and Distributed C++ Server Workloads. In 25th ACM International
Computing, Applications and Technologies, pages 92– Conference on Architectural Support for Programming
98, 2011. Languages and Operating Systems (ASPLOS), 2020.

[22] M. Jägemar. Mallocpool: Improving Memory Perfor- [31] Martin Maas, Chris Kennelly, Khanh Nguyen, Darryl
mance Through Contiguously TLB Mapped Memory. In Gove, Kathryn S. McKinley, and Paul Turner. Adaptive
2018 IEEE 23rd International Conference on Emerging huge-page subrelease for non-moving memory alloca-
Technologies and Factory Automation (ETFA), volume 1, tors in warehouse-scale computers. In Proceedings
pages 1127–1130, 2018. of the 2021 ACM SIGPLAN International Symposium
on Memory Management, ISMM 2021, New York, NY,
[23] Svilen Kanev, Juan Darago, Kim Hazelwood, USA, 2021. Association for Computing Machinery.
Parthasarathy Ranganathan, Tipp Moseley, Gu-Yeon
[32] Ashish Panwar, Sorav Bansal, and K. Gopinath. Hawk-
Wei, and David Brooks. Profiling a warehouse-scale
Eye: Efficient Fine-Grained OS Support for Huge Pages.
computer. In ISCA ’15 Proceedings of the 42nd Annual
In Proceedings of the Twenty-Fourth International Con-
International Symposium on Computer Architecture,
ference on Architectural Support for Programming Lan-
pages 158–169, 2014.
guages and Operating Systems, ASPLOS ’19, page
347–360, New York, NY, USA, 2019. Association for
[24] Svilen Kanev, Sam Likun Xi, Gu-Yeon Wei, and David
Computing Machinery.
Brooks. Mallacc: Accelerating Memory Allocation.
SIGARCH Comput. Archit. News, 45(1):33–45, April [33] Binh Pham, Viswanathan Vaidyanathan, Aamer Jaleel,
2017. and Abhishek Bhattacharjee. CoLT: Coalesced Large-
Reach TLBs. In Proceedings of the 2012 45th Annual
[25] Bradley C. Kuszmaul. Supermalloc: A Super Fast Mul- IEEE/ACM International Symposium on Microarchi-
tithreaded Malloc for 64-Bit Machines. SIGPLAN Not., tecture, MICRO-45, page 258–269, USA, 2012. IEEE
50(11):41–55, June 2015. Computer Society.
[26] Youngjin Kwon, Hangchen Yu, Simon Peter, Christo- [34] Bobby Powers, David Tench, Emery D. Berger, and An-
pher J. Rossbach, and Emmett Witchel. Coordinated drew McGregor. Mesh: Compacting Memory Manage-
and Efficient Huge Page Management with Ingens. In ment for C/C++ Applications. In Proceedings of the
Proceedings of the 12th USENIX Conference on Operat- 40th ACM SIGPLAN Conference on Programming Lan-
ing Systems Design and Implementation, OSDI’16, page guage Design and Implementation, PLDI 2019, page
705–721, USA, 2016. USENIX Association. 333–346, New York, NY, USA, 2019. Association for
Computing Machinery.
[27] Andres Lagar-Cavilla, Junwhan Ahn, Suleiman Souhlal,
Neha Agarwal, Radoslaw Burny, Shakeel Butt, Jichuan [35] Gang Ren, Eric Tune, Tipp Moseley, Yixin Shi, Silvius
Chang, Ashwin Chaugule, Nan Deng, Junaid Shahid, Rus, and Robert Hundt. Google-Wide Profiling: A Con-
Greg Thelen, Kamil Adam Yurtsever, Yu Zhao, and tinuous Profiling Infrastructure for Data Centers. IEEE
Parthasarathy Ranganathan. Software-Defined Far Mem- Micro, pages 65–79, 2010.
ory in Warehouse-Scale Computers. In Proceedings of
[36] John Robson. Worst Case Fragmentation of First Fit
the Twenty-Fourth International Conference on Archi-
and Best Fit Storage Allocation Strategies. Comput. J.,
tectural Support for Programming Languages and Oper-
20:242–244, 08 1977.
ating Systems, ASPLOS ’19, page 317–330, New York,
NY, USA, 2019. Association for Computing Machinery. [37] Joe Savage and Timothy M. Jones. HALO: Post-Link
Heap-Layout Optimisation. In Proceedings of the 18th
[28] Jaekyu Lee, Hyesoon Kim, and Richard Vuduc. When ACM/IEEE International Symposium on Code Genera-
Prefetching Works, When It Doesn’t, and Why. ACM tion and Optimization, CGO 2020, page 94–106, New
Transactions on Architecture and Code Optimization - York, NY, USA, 2020. Association for Computing Ma-
TACO, 9:1–29, 03 2012. chinery.

[29] Daan Leijen, Ben Zorn, and Leonardo de Moura. Mi- [38] T. Savor, M. Douglas, M. Gentili, L. Williams, K. Beck,
malloc: Free List Sharding in Action. Technical Report and M. Stumm. Continuous Deployment at Facebook
MSR-TR-2019-18, Microsoft, June 2019. and OANDA. In 2016 IEEE/ACM 38th International
 Conference on Software Engineering Companion (ICSE-
C), pages 21–30, 2016.
[39] Scott Schneider, Christos D. Antonopoulos, and Dim-
itrios S. Nikolopoulos. Scalable Locality-Conscious
Multithreaded Memory Allocation. In Proceedings of
the 5th International Symposium on Memory Manage-
ment, ISMM ’06, page 84–94, New York, NY, USA,
2006. Association for Computing Machinery.
[40] Raimund Seidel and Cecilia R Aragon. Randomized
search trees. Algorithmica, 16(4-5):464–497, 1996.

[41] Akshitha Sriraman and Abhishek Dhanotia. Accelerom-

eter: Understanding Acceleration Opportunities for Data
Center Overheads at Hyperscale. In Proceedings of the
Twenty-Fifth International Conference on Architectural
Support for Programming Languages and Operating
Systems, ASPLOS ’20, page 733–750, New York, NY,
USA, 2020. Association for Computing Machinery.
[42] Redis Team. Redis 6.0.9 and 5.0.10 are out.
[43] Abhishek Verma, Luis Pedrosa, Madhukar R. Korupolu,
David Oppenheimer, Eric Tune, and John Wilkes. Large-
scale cluster management at Google with Borg. In Pro-
ceedings of the European Conference on Computer Sys-
tems (EuroSys), Bordeaux, France, 2015.
[44] Wm. A. Wulf and Sally A. McKee. Hitting the Memory
Wall: Implications of the Obvious. SIGARCH Comput.
Archit. News, 23(1):20–24, March 1995.