Memory allocator simulator

The heap is drawn as eight rows of 8 KiB. Dark segments are the bytes a program asked for, light segments the extra each allocator took (headers and rounding), and blank space is free. Pick an allocator and a program, then run it, or call malloc and free yourself.

• Run Free every other block with first fit: half the heap ends up free, yet a 2 KB request fails because no single hole is big enough.
• Run the same program with Buddy: every 300-byte request takes 512 bytes, and the heap is full before the program has allocated everything.
• Run Random churn with next fit and then best fit, and compare the external fragmentation and the number of blocks examined per request.

A memory allocator manages a program's heap: it hands out blocks of memory on request and takes them back when the program frees them. It cannot move a block once handed out, because the program holds pointers into it, and it cannot know what will be requested or freed next. Every design is a trade-off between time spent finding a block, memory wasted by rounding, and memory wasted in holes between live blocks.

The allocators on this page follow the common designs: free lists searched by first, next or best fit with immediate coalescing, the binary buddy system, and segregated size classes.

A free-list allocator keeps the free blocks and searches them for one big enough. First fit takes the first in address order. Next fit continues from where the previous search stopped, which is faster but spreads objects over the whole heap. Best fit takes the smallest block that is big enough, leaving the largest blocks intact. The chosen block is split if the leftover can hold a minimal block, and on free the block is merged with free neighbours, which a header and footer on each block (boundary tags) make an O(1) check. Each block here costs an 8-byte header and is rounded to 16 bytes, at least 32, as in glibc.

Internal fragmentation is memory inside allocated blocks that the program did not ask for: headers, alignment and rounding to a size the allocator can manage. External fragmentation is free memory broken into pieces too small to use. In the first program, the free-list allocators had 30,544 bytes free when a 2 KB request failed, in holes of at most 1,744 bytes, a heap that is about half empty and still full.

Donald Knuth observed that a heap in a steady state carries a predictable number of holes. If each allocation splits a free block with probability p, the number of free blocks settles at about p/2 times the number of allocated blocks, the "fifty-percent rule". The simulator reproduces it for random requests of 16 to 416 bytes:

Kenneth Knowlton's buddy system of 1965 manages blocks whose sizes are powers of two, each aligned to its size. A request takes the smallest power of two that fits; a larger block is split in half repeatedly to make one, and each split produces two buddies. A freed block merges with its buddy if the buddy is free, and the buddy's address is the block's address with one bit flipped, so finding it costs nothing. Merging is complete: once everything is freed, the heap is one block again.

The cost is internal fragmentation. A 300-byte object plus header needs 308 bytes and gets 512, so in the first program the buddy allocator held only 128 of the 180 objects and wasted 13.3 KiB in rounding. The Linux kernel uses a buddy allocator for physical pages, where requests are already multiples of the page size.

Segregated allocators round each small request up to one of a few size classes and keep separate pages for each class; here 14 classes from 16 to 512 bytes in 2 KiB pages. Objects of one class are packed without headers, finding a slot is quick, and freeing one leaves a hole exactly one object wide, which the next request of that class fills. Jeff Bonwick's slab allocator for the SunOS kernel (1994) added caching of constructed objects; jemalloc, tcmalloc and mimalloc all use size classes for small objects, with per-thread caches on top.

The weakness is memory stranded in partly used pages: a page of 320-byte slots with one live object cannot serve a 64-byte request. In the first program, freeing every other object left every page half full, so no page could be returned and the 2 KB requests failed.

Production allocators combine these ideas. glibc's malloc keeps bins of free chunks by size, with fast per-thread caches (tcache) for small requests and mmap for very large ones. jemalloc and tcmalloc use size classes for small objects, page runs for larger ones and per-thread or per-CPU caches to avoid locks. Programs that allocate many objects of one type often add their own pools or arenas, which free everything at once. Garbage-collected runtimes can go further and compact the heap, moving objects to close the holes, something malloc can never do.

Kenneth Knowlton described the buddy system in "A fast storage allocator" in 1965. Donald Knuth's The Art of Computer Programming, volume 1 (1968), analyzed first fit, best fit, boundary tags and the buddy system, and stated the fifty-percent rule. Jeff Bonwick presented the slab allocator at USENIX in 1994, and Paul Wilson and colleagues' 1995 survey "Dynamic storage allocation: a survey and critical review" re-evaluated the classic policies on real program behavior. Doug Lea's dlmalloc, the basis of glibc's malloc, dates from 1987; jemalloc appeared in FreeBSD in 2005 and tcmalloc at Google around the same time.