Tracemalloc tracks every allocation, which can be useful for debugging purposes, but imposes a high cost both in CPU (to collect the stacktrace for every allocation) and Memory (to store tracking metadata for every live object). In many cases, this overhead is unnecessary, and a statistical sample would be sufficient to explain both high memory consumption, as well as memory leaks.

This PR adds a poisson sampling mode to tracemalloc. In the common case, allocations are not sampled, which means the CPU cost of tracemalloc is just an increment and a comparison, while the additional memory cost would be 0. In cases where sampling does occur, the cost is the same as before.

Running pyperformance --fast gives the following performance results:

Runtime overhead vs baseline

Peak RSS overhead vs baseline

Absolute peak RSS delta vs baseline

Prior art

Go's heap profiler uses Horvitz-Thompson weighting for sampled allocations: an allocation of size S is sampled with probability p = 1 - exp(-S / rate), and the sample is credited with S / p. This
keeps per-allocation-site estimates unbiased even when allocation sizes are mixed.

TCMalloc uses a closely related scheme: sampled allocations are weighted based on the sampled allocation's own size and the sampling interval/overshoot, rather than simply crediting all bytes accumulated since
the previous sample to the allocation that crossed the threshold.

Thanks to @wincent for reviewing a previous draft of this code and proposing the use of Horvitz-Thompson weighting.

• Issue: Sampling mode for tracemalloc #150494