How malloc Works: glibc, tcmalloc, jemalloc and Latency

The question

Module 1 said allocations have a fast path and slow paths. What exactly does malloc do, and where do the slow cases come from?

glibc malloc in outline

The default allocator on most Linux systems, glibc's malloc (derived from ptmalloc), works in layers. For a small request:

The thread cache (tcache). A small per-thread set of free lists, one per size class up to about 1 KB, holding a handful of recently freed chunks each. If there is a chunk of the right size, malloc pops it with no locking at all. This is the fast path, tens of nanoseconds or less.
The arena. If the tcache is empty, malloc goes to an arena: a heap with its own lock and its own bins of free chunks, sorted by size (fast bins for small sizes, small bins, large bins, an unsorted bin of recently freed chunks). glibc creates several arenas, up to a multiple of the number of cores, and assigns threads to them to reduce contention, but threads can still share one and contend for its lock.
The top of the heap. If no free chunk fits, the arena carves a new one from the top of its heap, extending the heap with a system call (brk or mmap) when it runs out.
Large requests above a threshold (128 KB by default, adjusted dynamically) bypass the arena and get their own mmap, which is a system call and fresh pages that fault on first touch, and are returned with munmap when freed.

free reverses this: small chunks go back to the tcache if it has room, otherwise to the arena's bins, where neighbouring free chunks are merged. When the top of the heap is free and large enough, glibc trims it, returning memory to the kernel.

Where the slow cases come from

Arena lock contention when several threads miss their tcaches at the same time.
Bin searches and merging on the arena path, whose cost depends on the heap's history.
System calls to grow the heap or map large blocks, followed by page faults on the new memory.
Trimming and unmapping on free, which can trigger TLB shootdowns in other threads (lesson 1), and means the next allocation faults again.
Cross-thread frees. A chunk freed by a thread other than the one that allocated it goes to the freeing thread's tcache or to the original arena under its lock. Producer-consumer designs where one thread allocates messages and another frees them defeat the per-thread caching and cause contention.
Fragmentation. Over a long day of mixed sizes, free memory ends up in pieces that do not fit new requests, the heap grows, and locality suffers.

Other allocators

Replacing the allocator is often a link-time change, which makes it a common first step:

tcmalloc (Google): per-thread or per-CPU caches with central free lists; very fast small allocations.
jemalloc: per-thread caches and multiple arenas with careful size classes; strong fragmentation behaviour; used widely in long-running servers.
mimalloc (Microsoft): per-thread free lists sharded by page, with deferred handling of cross-thread frees; very fast and compact.

All three make the fast path faster and the slow paths rarer than glibc's. None removes the slow paths, because they all eventually need memory from the kernel and they all have to handle frees from other threads.

What that means for design

The lesson of this module is not to tune malloc but to keep it off the hot path entirely: preallocate at start-up, use pools and arenas owned by one thread (Module 3), keep messages in rings rather than allocating and freeing them per message, and return objects to the thread that owns them. Use a modern allocator for everything else in the process, and configure it not to return memory to the kernel during the trading day.

Checking

malloc_stats() or mallinfo2() in glibc, or the statistics interfaces of jemalloc and tcmalloc, show heap size, fragmentation and arena use. An allocation hook in tests, counting calls after warm-up, proves that the hot path does not allocate.

Check yourself

Question 1 of 3

What serves most small allocations in glibc without taking a lock?

Question 2 of 3

What happens by default when you malloc 1 MB in glibc?

Question 3 of 3

Why can a design where thread A allocates messages and thread B frees them hurt allocator performance?

In the interview

Say your own answer out loud first, then open the one we would give.

How does glibc malloc work?

Small requests are served first from a per-thread cache of freed chunks with no locking; misses go to an arena, a heap with its own lock and size-sorted bins; if nothing fits, the arena extends its heap with a system call. Large requests above about 128 KB get their own mmap. free returns chunks to the thread cache or the arena, merging neighbours and occasionally trimming memory back to the kernel.

Why is malloc a latency risk if its average is fast?

Its slow paths: arena lock contention, bin searches, system calls to grow the heap followed by page faults, unmapping that triggers TLB shootdowns, and cross-thread frees. They are rare, which is exactly what makes them tail latency.

Would switching to jemalloc or tcmalloc solve allocation latency?

It would improve it: faster thread caches, better handling of cross-thread frees and less fragmentation. But every allocator eventually needs the kernel, so the real fix for the hot path is not to allocate there, using preallocated pools and rings, and to use the better allocator for the rest of the process.

How malloc works, and why it matters on the hot path