Allocator

An allocator is a subsystem responsible for managing chunks of memory from a larger pool, satisfying requests for variable-sized blocks and reclaiming freed memory for reuse. It sits at the boundary between the raw memory provided by the operating system and the structured objects demanded by applications, and its design is one of the most consequential low-level decisions in systems engineering.

The fundamental problem an allocator solves is fragmentation: as blocks of varying sizes are allocated and freed, the remaining free memory becomes divided into non-contiguous pieces. A request for a large block may fail even though the total free memory is sufficient, because no single contiguous region is large enough. Different allocation strategies trade off fragmentation, speed, and concurrency in characteristically different ways.

Allocation Strategies

The simplest strategy is the buddy system, which allocates memory in power-of-two-sized blocks. When a block of size 2^k is requested, the allocator finds the smallest available block of size 2^m ≥ 2^k, splits it recursively if necessary, and returns the appropriately sized piece. Upon deallocation, adjacent buddies are coalesced. The buddy system guarantees logarithmic allocation time and bounded external fragmentation, at the cost of internal fragmentation: a request for 2^k + 1 bytes consumes a block of size 2^{k+1}.

More flexible are free-list allocators, which maintain lists of free blocks segregated by size. Strategies like first-fit, best-fit, and worst-fit scan these lists to find suitable blocks. First-fit is fastest but produces the most fragmentation; best-fit minimizes waste but is slower; worst-fit, counterintuitively, can outperform both in certain workloads by leaving larger fragments available.

Modern high-performance allocators have moved beyond these classical strategies. jemalloc, developed by Jason Evans for FreeBSD, organizes memory into arenas and size classes, reducing lock contention in multi-threaded programs. tcmalloc, Google's thread-caching allocator, maintains per-thread caches of small objects and a central heap for large objects, minimizing the cost of synchronization. The Linux kernel's slab allocator pre-allocates fixed-size objects for kernel data structures, eliminating the overhead of general-purpose allocation for the most frequently used structures.

The Systems View

The allocator is not merely a utility. It is a hidden architect of program performance. A poor allocator can degrade throughput by orders of magnitude through false sharing (where threads on different cores contend for cache lines), cache pollution, and lock contention. A good allocator can make the difference between a system that scales linearly with core count and one that collapses under load.

The choice of allocator is therefore a systems decision, not merely an implementation detail. Database engines and distributed systems rely on specialized allocation strategies to manage large in-memory datasets without triggering garbage collection pauses. Real-time systems use deterministic allocators with fixed-size pools to guarantee worst-case allocation times. The allocator embodies the same trade-off that appears at every level of systems design: generality versus performance, safety versus speed, simplicity versus scalability.

The allocator is the unacknowledged legislator of program performance. Programmers think they are writing algorithms; in fact, they are writing memory access patterns, and the allocator translates those patterns into physical reality. A fast algorithm with a poor allocator is slower than a slow algorithm with a good one. The heap is the stage; the allocator is the director.