The Cost Tiers of a Single Allocation Request

A call to malloc is usually described as having a cost of a few tens of cycles. That figure is true only for the happiest path through a general-purpose allocator, and it hides the fact that the same call can instead take thousands of cycles, or can return immediately and leave the expensive part for later. Allocation cost is not a single number; it is a ladder of tiers, and the tier a request lands on is determined by allocator state the caller never sees.

Understanding the ladder matters because allocation sits in the inner loop of a great deal of code. A parser that allocates a node per token, an event loop that allocates a buffer per message, a serializer that builds a temporary string per field: in each case the useful work per allocation is small, so the tier the allocation lands on dominates the profile. Moving a workload from the slow tier to the fast tier is often worth more than any micro-optimisation inside the loop body.

The four tiers

The tiers, from cheapest to most expensive:

1. A pointer popped from a per-thread cache, with no atomic operation and no lock.
2. A pointer taken from a shared free list or size-class bin, requiring synchronisation with other threads.
3. A region carved out of an existing arena, which may require the arena to grow.
4. A new mapping from the kernel, plus a page fault when the memory is first touched.

Each tier can be an order of magnitude more expensive than the one above it. The progression is not linear: the gap between tier 1 and tier 4 spans roughly three orders of magnitude on current hardware, which is why an allocation count alone says little about allocation cost.

There is a fifth, separate cost that is easy to miss: the memory returned by the allocator is virtual. Its pages may not be backed by physical frames, they may not be in any cache, and they may not have an entry in the translation lookaside buffer. The first store to that memory pays for all three. That cost is attributed to whatever code touches the memory first, not to the allocator, and so it frequently appears in profiles as an unrelated function.

The fast path: a pointer out of a thread-local cache

A modern general-purpose allocator keeps a small cache of recently freed chunks per thread. glibc has done this since its 2.26 release, with a default of 64 size classes and up to 7 cached chunks per class per thread; both numbers are adjustable through the glibc.malloc.tcache_count and related tunables. jemalloc and tcmalloc have structurally similar per-thread caches, and mimalloc shards its free lists per thread as well.

A hit in this cache is a pop from a singly linked list whose head lives in thread-local storage. The cost is a load of the head pointer, a load of the next pointer stored in the freed chunk, and a store of the new head. On a warm cache that is on the order of ten to twenty cycles, and it involves no atomic instruction and no kernel involvement. The cached chunk is also almost certainly still in L1 or L2, because it was written by the same core shortly before.

The fast path has a structural limitation: it only serves the sizes that were recently freed on the same thread. A thread that frees a 96-byte block and then asks for a 4 KiB block gets no benefit. The cache also has a capacity, so a phase that frees many distinct sizes evicts its own contents. This is why allocator benchmarks that repeatedly allocate and free one size show numbers far below what a mixed workload achieves.

The shared tier: bins, locks, and reuse

When the thread cache misses, the request goes to the arena. The arena holds free chunks organised by size class, and serving a request means finding a chunk of at least the requested size, possibly splitting it, and removing it from whatever structure indexes it. Because several threads can share an arena, this step needs synchronisation: a lock, or in more recent designs a lock-free or mostly-lock-free path with atomic compare-and-swap.

The cost here is dominated by the synchronisation, not by the pointer manipulation. An uncontended lock acquisition is tens of cycles; a contended one can be hundreds or thousands, because the cache line holding the lock must be transferred between cores. Under high contention the line bounces between cores and each acquisition serialises the participating threads. This is the mechanism behind the classic result that a single global heap limits parallel speedup: the allocator, not the workload, becomes the bottleneck. The Hoard and jemalloc designs both exist largely to remove this serialisation from the common path.

The shared tier also determines whether a freed chunk is reused soon. A chunk that was freed by a different thread may be sitting in an arena whose free list the current thread does not consult first, and a chunk freed long ago may have been pushed deep into a bin. Reuse distance, not reuse existence, is what makes a free chunk useful, which is the subject of Allocation Churn and the Locality of Recycled Memory.

The kernel tier: mappings and untouched pages

If no free chunk of adequate size exists, the arena must grow. On Linux, growth happens in one of two ways. Extending the main heap with brk moves the program break, which grows a single contiguous region. Large requests, or requests from a secondary arena, use mmap with MAP_ANONYMOUS | MAP_PRIVATE to obtain a separate region.

glibc’s default threshold for choosing mmap over the heap is 128 KiB, and the threshold is adaptive: freeing a block that was itself mapped causes the threshold to rise, so a program that repeatedly allocates and frees large blocks eventually has them served from the heap instead. The mallopt interface exposes the threshold as M_MMAP_THRESHOLD, and the same value can be set through the glibc.malloc.mmap_threshold tunable.

A system call is not free. Entering and leaving the kernel costs on the order of hundreds to a couple of thousand cycles even for a call that does almost nothing, because the return path must restore state and the branch predictors and caches have been disturbed. A mapping call does considerably more: it allocates a virtual memory area, may need to take a lock on the address space, and updates the process’s page tables lazily at fault time rather than immediately.

The important property of this tier is that it produces virtual address space, not physical memory. mmap with MAP_ANONYMOUS maps all pages of the new region to a single shared zero page, read only. No frame is allocated. The allocator hands back a pointer into a region that has never consumed a byte of RAM.

The deferred cost: the first write

The real cost of fresh memory is paid at first touch. A read of an untouched anonymous page is served from the shared zero page and costs one fault. A write triggers copy-on-write: the kernel allocates a physical frame, zeroes it, installs a page table entry, and resumes the faulting instruction. Zeroing is not optional for anonymous memory, because a process must never observe another process’s data.

That fault is far more expensive than the fault itself suggests. The kernel must zero 4 KiB, which is a handful of cache line writes and a few hundred cycles on its own, but the operation also evicts useful lines from the cache, and the new page table entry may require a page walk on the next access. A first-touch fault commonly costs a few thousand cycles, and on a large allocation the cost recurs once per 4 KiB page.

The consequence for measurement is that the cost is attributed to the wrong line of code. The allocator appears cheap and the initialisation loop appears expensive, even though the initialisation loop is doing nothing but storing zeroes into memory it was just given. The following sketch makes the split visible by counting minor faults around each phase.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/resource.h>

static long minor_faults(void)
{
    struct rusage ru;
    getrusage(RUSAGE_SELF, &ru);
    return ru.ru_minflt;
}

int main(void)
{
    const size_t n = 64u << 20;   /* 64 MiB, 16384 pages of 4 KiB */
    long before = minor_faults();

    char *p = malloc(n);          /* virtual only: no frames yet */
    long after_alloc = minor_faults();

    /* One store per page forces one copy-on-write fault per page. */
    for (size_t i = 0; i < n; i += 4096)
        p[i] = 1;

    long after_touch = minor_faults();
    printf("alloc: %ld  touch: %ld  pages: %zu\n",
           after_alloc - before, after_touch - after_alloc, n / 4096);

    free(p);
    return 0;
}

The alloc delta is near zero and the touch delta is approximately the page count. On a system that hands out transparent huge pages, the touch delta can be far smaller than the page count because a single fault can back 2 MiB at once, which is the mechanism discussed in First-Touch Costs in Demand-Paged Memory.

Why allocation count is a weak predictor

Two programs that call malloc the same number of times can differ in allocation cost by orders of magnitude, for reasons that have nothing to do with the call itself. A program that frees and reallocates the same sizes in a tight loop stays on tier 1 indefinitely. A program that allocates a monotonically increasing set of sizes walks up the tiers with every new size class, and one that allocates without freeing eventually forces the arena to grow and the kernel to provide frames.

The useful metric is therefore not the number of allocations but the distribution of tiers. A profile that shows time inside the allocator is showing time on tiers 2 and 3; a profile that shows time in initialisation code after allocation is showing tier 4. Separating those two before choosing a fix matters, because the fixes are different: tier 2 and 3 costs fall to pooling, size-class discipline, or per-thread arenas, while tier 4 costs fall to reusing memory that is already backed, or to allocating in larger units.

There is also a boundary case worth knowing. Very small allocations, below the minimum chunk size, are rounded up. glibc’s minimum chunk is 32 bytes on 64-bit systems, including the 8 bytes of metadata stored in the chunk itself, so a request for 1 byte consumes a 32-byte chunk. A structure of 40 bytes consumes 48. Padding to a 16-byte boundary is mandated by the ABI, which means the allocator’s size classes are not the only rounding in play. A layout change that moves a struct from 33 to 32 bytes can therefore move it into a smaller size class and change both its footprint and the tier it is served from, a point developed in Bytes Fetched per Field.

Reading the tiers in a profile

Allocator cost is visible in a sampling profile only when the sample lands inside the allocator, and tier 1 paths are short enough that sampling under-reports them. A more reliable signal is the fault counter, which is exact, cheap to read, and directly attributes first-touch cost. Pairing fault counts with allocation counts gives a two-dimensional picture: allocations that never fault are reuse, allocations that fault once per page are fresh memory.

Neither signal says anything about the locality of the returned memory, which is often the larger effect. A block served from a cache that is still warm and a block served from a fresh mapping have the same allocation cost and completely different traversal cost. That distinction is the subject of Working Set Size and the Miss-Rate Cliff, and it is the reason allocation tier alone does not predict application performance.

The tiers are also not stable over time. A program’s allocation pattern changes the allocator’s state: the mmap threshold adapts, arenas multiply under thread contention, and freed chunks accumulate in bins. An allocation that is cheap during warmup can become expensive during steady state, and the reverse happens when a long-lived free list finally starts being reused. Treating allocator cost as a constant, rather than as a function of history, is the most common modelling error in this area.