← Labssystems-01Systems and syscalls●●○○

malloc is not slow, it is UNPREDICTABLE

systems/01_malloc_variance.cneeds: tools/bench.h, tools/pin.sh, strace2 steps

0/2 steps

what this lab teaches

The argument against allocation on a latency-critical path is not the median cost of malloc (tens of ns) but its tail and its dependence on allocator state you do not control: size classes, the mmap threshold, trimming, first-touch page faults. Each iteration allocates, touches one byte, frees, and is timed individually (serialized TSC), 200k times: 32 B tcache fast path 4 KiB above tcache, small-bin path 1 MiB (default) what glibc does out of the box 1 MiB (forced mmap) the threshold pinned so every block is mmap/munmap 1 MiB (heap) threshold raised and trimming disabled pool 64 B a free list over pre-faulted memory (what you ship)

evidence to leave with

36 / 52 / 41 ns medians; forced mmap 4.2 us p50 (200k mmap+munmap); pool 16 ns

first, get the code

run this

$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs

then build it

run this

$ cd systems && ./build.sh

walk it, one step at a time

run this

$ ../tools/pin.sh -q ./bin/01_malloc_variance

what it printed on the machine that wrote this lab

label                       min      p50      p90      p99    p99.9      max       mean   (ns per alloc+touch+free)
malloc 32 B                  28       36       43       49       51    13215       36.7
malloc 4 KiB                 43       52       56       60       64     8088       52.2
malloc 1 MiB (default)       38       41       42       43       44     5458       41.0
malloc 1 MiB (forced mmap)     4068     4184     4413    10345    14810   205867     4578.7
malloc 1 MiB (heap, no trim)       38       41       42       44       48     7255       41.2
pool 64 B                    14       16       18       18       18     3971       16.4

run this

$ strace -c ./bin/01_malloc_variance large-mmap 2>&1 | grep -E "mmap|munmap"

what it printed on the machine that wrote this lab

 59.59    1.420996           7    200003           munmap
 40.38    0.962921           4    200010           mmap
Two syscalls per allocation, plus a page fault on the touch (fresh
mmap memory is unmapped until first write) and the kernel zeroing the
page. p50 4.2 us, p99 10 us, max 206 us: that is the "malloc is slow"
people remember, and it is the mmap path, not malloc.

how to read it

- 32 B: p50 36 ns, p99.9 51 ns, but max 13 us. The median is a tcache hit (a per-thread free list: pop, push). The max is one iteration that hit something else: a page fault, a timer interrupt, a migration. Even the fast path has a tail you cannot budget for. - 4 KiB: 52 ns. Above the tcache limit (1032 bytes by default), so the request goes through the arena's bins with a lock (uncontended here). - 1 MiB (default): 41 ns and a 5 us max. Surprise: glibc's mmap threshold is DYNAMIC. The first 1 MiB block is mmapped (that is the max), and when it is freed glibc raises the threshold so later blocks of that size come from the heap. Your program's allocation history changes the cost of the next allocation. Nothing about that is under your control unless you pin it with mallopt. - forced mmap: mallopt(M_MMAP_THRESHOLD, 512 KiB) disables the dynamic behaviour: every 1 MiB block is mmap + fault + munmap: 100x slower. - heap, no trim: raising M_MMAP_THRESHOLD and M_TRIM_THRESHOLD keeps the blocks on the heap and stops free() from returning memory to the OS (a madvise/brk you would otherwise pay later). 41 ns, tight tail. - pool: 16 ns, p99.9 18 ns, and even its max (4 us) is an interrupt, not the allocator. Pre-allocated, pre-faulted, one pointer swap each way. This is the shape of every allocator in a trading system. WHAT MAKES ALLOCATION UNPREDICTABLE (the list to recite): size-class boundaries (tcache 1032 B, mmap threshold 128 KiB default and dynamic up to 32 MiB), first-touch page faults, arena locks between threads, trimming (free returning memory via brk/madvise), fragmentation over a long run, and the allocator's own metadata cache misses.

the rules

H1. No malloc/free on the hot path. Pools, arenas, free lists, ring buffers, sized at startup, pre-faulted (MAP_POPULATE / touch) and mlocked. H2. If you must use malloc, pin its behaviour: mallopt(M_MMAP_THRESHOLD), mallopt(M_TRIM_THRESHOLD, huge), mallopt(M_TOP_PAD), and verify with strace -c that steady state makes no mmap/munmap/brk calls. H3. Measure allocation cost as a DISTRIBUTION per size class in your process, after warm-up; the median tells you almost nothing.

take it further

1. Run `small` under `ltrace -c -e malloc+free`: ltrace adds ~100 us per call (it stops the process at each PLT entry). Tools change what they measure; use ltrace for counts, never for timing. 2. Allocate from two threads at once (each its own sizes): the first contended malloc creates a second arena (mmap of 64 MB): find it in the histogram. 3. Add `mlockall(MCL_CURRENT | MCL_FUTURE)` at startup and rerun `large-mmap`: faults disappear, mmap/munmap remain. ============================================================

read the source · systems/01_malloc_variance.c

#include "../tools/bench.h"
#include <malloc.h>
#define ITERS 200000
/* A fixed-size pool: a free list threaded through pre-allocated, pre-faulted blocks. */
typedef struct Node { struct Node *next; } Node;
static Node *pool_free; static char *pool_mem;
static void pool_init(size_t block, size_t count) {
    pool_mem = malloc(block * count); memset(pool_mem, 0, block * count);          /* pre-fault */
    for (size_t i = 0; i < count; i++) { Node *n = (Node *)(pool_mem + i * block); n->next = pool_free; pool_free = n; }
}
static inline void *pool_alloc(void) { Node *n = pool_free; pool_free = n->next; return n; }
static inline void pool_free_(void *p) { Node *n = (Node *)p; n->next = pool_free; pool_free = n; }

static void measure(const char *label, size_t bytes, int use_pool, uint64_t *samples, double hz) {
    for (int i = 0; i < ITERS; i++) {
        uint64_t t0 = bench_tsc_begin();
        void *p = use_pool ? pool_alloc() : malloc(bytes);
        ((volatile char *)p)[0] = 1;                                  /* touch: a fresh page must be faulted in */
        if (use_pool) pool_free_(p); else free(p);
        uint64_t t1 = bench_tsc_end();
        samples[i] = (uint64_t)((double)(t1 - t0) * 1e9 / hz);
    }
    bench_stats st = bench_compute(samples, ITERS);
    bench_print(label, &st);
}
int main(int argc, char **argv) {
    const char *mode = argc > 1 ? argv[1] : "all";
    uint64_t *s = malloc(ITERS * sizeof *s); memset(s, 0xFF, ITERS * sizeof *s);
    double hz = bench_tsc_hz();
    pool_init(64, 1024);
    bench_print_header("ns per alloc+touch+free");
    if (!strcmp(mode, "all") || !strcmp(mode, "small"))  measure("malloc 32 B", 32, 0, s, hz);
    if (!strcmp(mode, "all") || !strcmp(mode, "medium")) measure("malloc 4 KiB", 4096, 0, s, hz);
    if (!strcmp(mode, "all") || !strcmp(mode, "large"))  measure("malloc 1 MiB (default)", 1 << 20, 0, s, hz);
    if (!strcmp(mode, "all") || !strcmp(mode, "large-mmap")) {
        mallopt(M_MMAP_THRESHOLD, 512 << 10);                                         /* FIX the threshold: every 1 MiB block is mmap/munmap */
        measure("malloc 1 MiB (forced mmap)", 1 << 20, 0, s, hz);
    }
    if (!strcmp(mode, "all") || !strcmp(mode, "large-heap")) {
        mallopt(M_MMAP_THRESHOLD, 64 << 20); mallopt(M_TRIM_THRESHOLD, 128 << 20);   /* keep 1 MiB blocks on the heap, never trim */
        measure("malloc 1 MiB (heap, no trim)", 1 << 20, 0, s, hz);
    }
    if (!strcmp(mode, "all") || !strcmp(mode, "pool"))   measure("pool 64 B", 64, 1, s, hz);
    return 0;
}

◇

Finish the lab: write the evidence note

A lab is done when you can say what it showed on your machine — not when you have read it.