tcmalloc/docs/sampling.md

How sampling in TCMalloc works.

Introduction

TCMalloc uses sampling to get representative data on memory usage and allocation.

Sampling

We chose to sample an allocation every N bytes where N is a random value using Sampler::PickNextSamplingPoint() with a mean set by the profile sample interval using MallocExtension::SetProfileSamplingInterval().

By default this is every 2MiB, and can be overridden in code. Note that this is an statistical expectation and it's not the case that every 2 MiB block of memory has exactly one sampled byte.

How We Sample Allocations

We'd like to sample each byte in memory with a uniform probability. The granularity there is too fine; for better fast-path performance, we can use a simple counter and sample an allocation if 1 or more bytes in it are sampled instead. This causes a slight statistical skew; the larger the allocation, the more likely it is that more than one byte of it should be sampled, which we correct for, as well as the fact that requested and allocated size may be different, in the weighting process. We defer a detailed treatment of the weighting process to the appendix.

Sampler::RecordAllocationSlow() determines when we should sample an allocation; if we should, it returns a weight that indicates how many bytes that the sampled allocation represents in expectation.

We do some additional processing around that allocation using SampleifyAllocation() to record the call stack, alignment, request size, and allocation size. Then we go through all the active samplers using ReportMalloc() and tell them about the allocation.

We also tell the span that we're sampling it. We can do this because we do sampling at tcmalloc page sizes, so each sample corresponds to a particular page in the pagemap.

For small allocations, the returned allocation uses an entire TCMalloc page (not shared with any other allocations) on a dedicated span. The returned allocation is placed on the sampled page heap, allowing us to use the pointer's tag bits to identify that the object was sampled and needs special handling on deallocation.

For the sampled page heap, the virtual addresses associated with the allocation are madvised with the MADV_NOHUGEPAGE flag. This, combined with the whole-page behavior above, means that every allocation gets its own native (OS) page(s) shared with no other allocations.

For large (>kMaxSize) allocations, the returned allocation will be on entire TCMalloc pages. These objects are requested directly from the non-sampled page heaps. These objects will be packed by Temeraire densely onto hugepages. While objects that are exact multiples of 2MB are given their own hugepages (the HugeCache), the access patterns of other objects may affect statistics for the profiled ones.

Statistic	Small	Large
RSS	Prior allocations may have	Huge page may make pages

: : used the page : resident even though unused :

| Stale | Accurate for > staleness time | Adjacent allocations on same |

  : allocs                        : huge page may skew           :

How We Free Sampled Objects

Each sampled allocation is either tagged or larger than kMaxSize. Using this, we can quickly test whether a particular allocation might be a sample. When we are done with the sampled span we release it using tcmalloc::Span::Unsample().

How Do We Handle Heap Profiling

To handle heap profiling we just need to traverse the list of sampled objects and compute the amount of heap they consume.

Each allocation gets additional metadata associated with it when it is exposed in the heap profile. In the preparation for writing the heap profile, MergeProfileSamplesAndMaybeGetResidencyInfo() probes the operating system for whether or not the underlying memory pages in the sampled allocation are swapped or not resident at all (this can happen if they've never been written to). We use /proc/pid/pagemap to obtain this information for each underlying OS page.

The OS is more aggressive at swapping out pages for sampled allocations than the statistics might otherwise indicate. Sampled allocations do not share memory pages (either huge or otherwise) with any other allocations, so a sampled rarely-accessed allocation becomes eligible for reclaim more readily than an allocation that has not been sampled (which might share pages with other allocations that are heavily accessed). This design is a fortunate consequence of other aspects of sampling; we want to identify specific allocations as being more readily swapped independent of our memory allocation behavior.

More information is available via pageflags, but these require root to access /proc/kpageflags. To make this information available to tcmalloc, proposed kernel changes would need to be merged.

How Do We Handle Allocation Profiling

Allocation profiling reports a list of sampled allocations during a length of time. We start an allocation profile using MallocExtension::StartAllocationProfiling(), then wait until time has elapsed, then call Stop on the token. and report the profile.

While the allocation sampler is active it is added to the list of samplers for allocations and removed from the list when it is claimed.

How Do We Handle Lifetime Profiling

Lifetime profiling reports two types of measurements: observed lifetime and partially observed lifetime. Having observed lifetime means that the object was deallocated during a profiling session, and having partially observed lifetime means that the object was still alive when the session stopped (i.e., its lifetime was right censored). The profiler reports the two types of measurements for allocation sampled either before or after the current profiling session started. Profiling is initiated by calling MallocExtension::StartLifetimeProfiling(). Profiling continues until Stop is invoked on the token.

The mechanism extended the initial version of the lifetime profiler to include objects sampled before the current session started, as well as adding measurements to handle right censorship. A description of the initial version of the sampling based lifetime profiler can be found in Section 4 of "Learning-based Memory Allocation for C++ Server Workloads, ASPLOS 2020".

Appendix

Detailed treatment of weighting

Sampling via a distance counter; simplification for sampled allocations.

We have one parameter, sampling period, that we denote with T throughout.

Ideally we'd like to sample each byte of allocated memory with a constant probability p = 1/T. The distance between each successive pair of sampled bytes is a geometric distribution on \mathbb N; the actual code takes the equivalent ceiling of an exponentially-distributed variable with parameter $$\lambda = 1/T$$. Whenever we make an allocation, we decrement the requested size plus one byte (we concentrate more on this in the next section; we can treat this as a decrement of the allocated size for now) from a counter initialized to one realization of this random variable.

If all allocations were one byte wide, this would work perfectly. Each sampled byte would represent T bytes in the total, and each byte of memory would be uniformly likely to be sampled. Unfortunately, allocations are typically more than one byte wide, so we will need to compensate.

Take an allocation that has been chosen to be sampled (of size k). The byte marked * is the byte that decreases the counter to zero; the counter starts at f before this allocation.

+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | * |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
  \_______________________/   \_______________/
              f                     k - f

The sampling weight W (n.b. not allocation count estimate, which is reported as weight in MallocHook::SampledAlloc) of this allocation is the number of bytes represented by this sample. The byte marked * contributes T bytes, as that is the average sampling rate; the bytes before the sampled byte were specifically not sampled and don't contribute to the sampling weight.

The k-f bytes after * have some probability of being sampled. Specifically, each byte continues to have a 1/T probability of being sampled, which means that a remaining X bytes would be sampled if we had continued our technique, where

X \sim \mathrm{Pois}\left(\frac{k-f}{T}\right),

which follows by applying the definition of the Poisson distribution. So each sampled allocation has a weight of

W = T + TX.

Instead of realizing an instantiation of X, which is computationally cumbersome, we simplify in this case by taking X to be its expectation:

W = T + T\hat X = T + T \left(\frac{k - f}{T}\right) = T + k - f.

Now let's consider our estimate on the total memory usage

M = \sum_i W_i

where the sum ranges over all sampled allocations. In either the world where we did not make the simplifying assumption or in the limit where all allocations are one byte, there is no k-f part to worry about; the variance is just that of the underlying Poisson process, which is

\sigma^2 = \lambda = TM.

In the other direction with one gigantic allocation k = M \gg T, the variance is just on a single realization of our geometric random variable representing the distance between sampled allocations, which is

\sigma^2 = \frac{1-p}{p^2} = \frac{1 - \frac1T}{\frac{1}{T^2}} = T^2 - T.

Thus, depending on allocation pattern, the variance for our estimate on M varies between T^2 - T and TM.

Requested memory size versus actual allocation size.

To keep the fast path fast, all of the above logic works on requested size plus one byte, not actual allocation sizes. For larger allocations (as of the time of writing, greater than 262144 bytes), these two values differ by a byte; for smaller allocations, allocations are bucketed into a set of discrete size classes for optimal cache performance.

For the smallest allocation, zero bytes, we run into an issue: we actually do allocate memory (we round it up to the smallest class size), so we need to ensure that there is some chance of sampling even zero byte allocations. We increment all requested sizes by one in order to deal with this and we come up with the final term of "requested plus one."

When we choose an allocation to be sampled, we report an allocation estimate, which is called weight in MallocHook::SampledAlloc; this variable means "how many allocations this sample represents." We take the sampling weight W from the previous section and divide by the actual requested size plus one (not the allocated size). Thus the estimate on the number of bytes a sampled allocation represents is

\frac{a}{r+1} W

where r is the requested size, a is the actual allocated size, and W is the allocation weight from the previous section.

For an intuitive sense of how this works, suppose we only have 1-byte requested allocations (which are currently rounded up to 8-byte actual allocations). Each allocation decrements the distance counter from the previous section by 2 bytes (r+1) instead of the true value of 8 bytes. When an allocation is chosen to be sampled, we multiply by the same unskewing ratio (4, which is the allocated size, 8, over the requested size plus one, 2).

Essentially, what we are doing here is actually sampling slightly less than the requested sampling rate, at a variable rate depending on the requested-to-allocated ratio. This will increase the variance on allocations geometrically far from the next size class, but does not change the underlying expectation of the distribution; the memorylessness nature of the distribution means that no allocation pattern can result in over- or under- reporting of allocations that differ significantly in requested-to-allocated.

In the extreme case (all allocations are much smaller than the smallest size class), this approach becomes identical to a "per-allocation" sampling strategy. A per-allocation sampling strategy results in a higher variance for larger allocations; here, we note that our actual distribution of size classes covers any larger allocations and the variance term can only increase by a small amount.