Wait, What?
Getting memory is not just “find some free bytes.” An allocator must find usable space quickly, preserve alignment, limit fragmentation, scale across threads and still be able to reuse what gets returned.
At beginner level, memory allocation can be drawn as occupied and empty blocks. At professional level, allocators use size classes, per-thread or per-CPU caches, page heaps, slabs, buddy systems, metadata, NUMA policies and carefully engineered fast paths. The central problem never disappears: convert a changing pattern of requests into a reusable physical layout without spending too much time or wasting too much space.
Quick Answer
Learn memory-allocation algorithms through the route contiguous blocks → free-space representation → first fit/best fit → splitting → coalescing → internal versus external fragmentation → segregated free lists → size classes → buddy allocation → slabs → thread/CPU-local caches → spans/pages → large-object paths → NUMA and locality → contention → profiling → professional allocator selection. A beginner should be able to hand-simulate allocation and free on a small heap. A professional should be able to explain where fragmentation comes from, which fast path serves a request, when global coordination occurs and how allocator policy interacts with workload size distribution and concurrency.
1. Begin With a Tiny Heap
Draw 64 units of memory as one free interval. Allocate blocks of 8, 12 and 6 units. Free the middle block. Now ask where a new 10-unit request should go. This tiny exercise reveals almost every core allocator question: placement, splitting, metadata, fragmentation and future reuse.
2. A Free List Is the Simplest Explicit Model
A free list stores available blocks. To allocate, search for a sufficiently large block; to free, return a block to the structure. The algorithmic challenge is that the list changes after every split, allocation and coalescing operation.
3. First Fit Stops at the First Sufficient Block
First fit scans free blocks and selects the first one large enough. It is simple and often fast, but its long-term fragmentation pattern depends on request order and list organisation.
4. Best Fit Searches for the Smallest Sufficient Block
Best fit tries to leave the smallest remainder. That sounds space-efficient, but it can create many tiny unusable fragments and requires more searching unless free blocks are indexed cleverly.
5. Placement Policy and Search Cost Are Coupled
An allocator cannot discuss “best placement” without discussing how quickly it can find that placement. Data structures for free space—lists, trees, bitmaps and size-class bins—exist partly to reduce search overhead.
6. Splitting Prevents Large Blocks From Being Wasted
If a 32-unit free block serves an 8-unit request, the allocator can split it into an allocated 8-unit block and a remaining 24-unit free block. The split improves utilisation but increases metadata and the number of fragments the allocator must manage.
7. Coalescing Rebuilds Larger Free Regions
If adjacent free blocks are merged after deallocation, future large requests have a better chance of succeeding. Boundary tags, ordered free structures or page-level metadata can help determine whether neighbours are free.
8. External Fragmentation Means Free Memory Exists in the Wrong Shape
A heap can contain enough total free memory for a request but no single sufficiently large contiguous block. That is external fragmentation.
9. Internal Fragmentation Means the Allocated Block Is Larger Than the Request
If a 33-byte request is served from a 40-byte size class, the unused 7 bytes are internal fragmentation. Allocators deliberately accept some internal waste to make lookup and reuse faster.
10. Alignment Adds Another Rounding Constraint
Objects often require addresses aligned to particular boundaries. Alignment can increase the size of an allocation or create padding around it. A professional allocator must preserve alignment while keeping metadata compact.
11. Segregated Free Lists Group Similar Sizes
Instead of searching every free block, maintain separate bins for ranges such as 16, 32, 64 and 128 bytes. A request can jump directly to a likely size class, dramatically reducing search time.
12. Size Classes Turn a Continuous Problem Into a Discrete One
Requests of many exact sizes are rounded into a smaller set of classes. The class spacing determines the trade-off between metadata/search simplicity and internal fragmentation.
Google’s TCMalloc design documents this explicitly: small requests map to size classes and are served through fast front-end caches, while larger requests follow different paths. See TCMalloc Design.
13. The Fast Path Is Usually Not the Whole Allocator
A modern allocator often serves common small allocations from a local cache with only a few operations. When that cache empties, it refills from a central structure; when the central structure empties, the allocator requests larger spans or pages from a back end.
14. Thread-Local and CPU-Local Caches Reduce Contention
If every allocation acquires one global lock, many-core programs serialize around the allocator. Local caches let most allocations and frees complete without touching shared state.
TCMalloc supports modern per-CPU caches; mimalloc uses page-local sharded free lists to improve locality and reduce contention. See mimalloc: Free List Sharding in Action.
15. Local Caches Can Increase Memory Footprint
Memory sitting unused in one thread’s or CPU’s cache may be unavailable to another until it is returned to central structures. Fast local allocation therefore trades coordination cost against temporary memory retention.
16. The Buddy Allocator Uses Powers of Two
A buddy allocator manages free blocks in sizes that are powers of two. If the smallest available block is too large, split it into two equal buddies. When both buddies become free, merge them back into the next larger order.
Linux uses this family for page allocation. Its physical-memory documentation describes free areas by order, recursive splitting and merging with a buddy: Linux Physical Memory.
17. Buddy Allocation Makes Coalescing Cheap
Because each block has a mathematically determined buddy, the allocator can efficiently determine which adjacent block could be merged. The price is power-of-two rounding and therefore potential internal fragmentation for awkward request sizes.
18. Page Allocation and Object Allocation Are Different Layers
An operating system may allocate physical pages with a buddy allocator, while a userspace allocator subdivides larger page spans into application objects. One allocator can therefore sit on top of another.
This layered view prevents a common confusion: the algorithm serving a 48-byte object request is not necessarily the same algorithm acquiring physical pages from the kernel.
19. Slab Allocation Reuses Pre-Organised Object Storage
Slab-style allocators manage caches of objects or fixed-size slots backed by pages. Reusing slots avoids repeated general-purpose searching and can preserve useful object-layout properties.
Linux SLUB documentation exposes the relationship among slab order, objects per slab, contention and NUMA placement: Linux SLUB Guide.
20. Large Objects Need a Different Path
A request larger than ordinary size classes may be served directly from page- or span-level structures. Treating a 20 MB allocation like a 32-byte object would create enormous binning and copying problems.
21. Deallocation Can Be More Complex Than Allocation
When a block is freed, the allocator must determine its size class or span, update local or central free structures, perhaps coalesce pages and possibly return memory to the operating system. Cross-thread frees can add synchronization or deferred-transfer machinery.
22. Cross-Thread Freeing Creates Ownership Questions
Thread A can allocate an object and thread B can free it. If free lists are thread-local, the allocator must transfer ownership safely without turning every deallocation into a global synchronization event.
mimalloc’s sharded free-list design is a good professional example of handling local and cross-thread frees separately.
23. Cache Locality Is Part of Allocation Performance
Two allocators with similar operation counts can behave differently if one reuses nearby memory and the other scatters objects across pages or NUMA nodes. Allocation strategy changes later cache and TLB behaviour.
The existing How to Learn Cache-Efficient Algorithms article owns general memory-hierarchy reasoning. Allocation turns locality into a layout decision that persists after the allocator returns.
24. NUMA Makes “Free Memory” Location-Sensitive
On multi-socket machines, memory attached to one NUMA node may be slower for a CPU on another node. An allocator may therefore balance locality against global utilisation.
Linux exposes allocator and slab policies that account for NUMA placement, illustrating that physical location becomes part of the cost model.
25. Returning Memory to the OS Is a Separate Policy
A block can be free from the application’s perspective while still retained inside allocator caches or page heaps. Releasing it to the operating system may reduce resident memory but make future allocation more expensive.
26. Fragmentation Must Be Measured Under the Real Workload
A synthetic benchmark with one repeated size may make every allocator look excellent. Real programs allocate mixtures of sizes and lifetimes across threads. Fragmentation is therefore a workload property interacting with allocator policy.
27. Garbage Collection and Allocation Are Adjacent but Different Jobs
An allocator finds storage for objects and recycles returned blocks. A garbage collector determines which managed objects can be considered dead. A runtime may use both.
The existing How to Learn Garbage-Collection Algorithms article owns reachability and automatic reclamation. This article owns allocation and free-space organisation.
28. Concurrency Changes the Allocator’s Correctness Surface
Free-list metadata, central caches and page structures can be corrupted if concurrent updates race. Production allocators use locks, atomics, ownership rules and carefully designed local structures to preserve invariants.
The existing How to Learn Concurrent Algorithms article owns generic concurrency correctness. Allocators provide one demanding systems application.
29. Profiling Turns Allocation From Guesswork Into Evidence
Professionals inspect allocation counts, size distributions, retained memory, page-heap state, fragmentation, cache misses and hot call sites. Linux now documents low-overhead memory-allocation profiling intended for production accounting: Memory Allocation Profiling.
30. Allocator Benchmarks Need More Than Operations per Second
Throughput can improve while resident memory rises. Tail latency can worsen under contention even when average allocation time looks good. A fair comparison therefore considers speed, footprint, fragmentation, scalability and the actual object-lifetime distribution.
31. Common Learning Failure States
- Thinking total free bytes guarantee a large contiguous allocation.
- Confusing internal and external fragmentation.
- Assuming best fit always wastes less memory.
- Ignoring alignment and metadata overhead.
- Thinking size classes are exact request sizes.
- Confusing page allocation with small-object allocation.
- Assuming thread-local caches reduce both contention and memory footprint.
- Ignoring cross-thread frees.
- Comparing allocators on one repeated allocation size.
- Optimising average allocation time while ignoring resident memory and tail latency.
32. A Beginner-to-Professional Learning Ladder
- Level 1: allocate and free blocks on a drawn heap.
- Level 2: compare first fit and best fit on the same request sequence.
- Level 3: perform splitting and coalescing correctly.
- Level 4: classify internal versus external fragmentation.
- Level 5: implement simple segregated free lists and size classes.
- Level 6: simulate buddy splitting and merging by order.
- Level 7: explain slab/page layering and large-object paths.
- Level 8: reason about thread-local caches, central free lists and cross-thread frees.
- Level 9: analyse locality, NUMA and memory-return policies.
- Level 10: diagnose allocator behaviour using allocation profiles, footprint, fragmentation, contention and latency distributions together.
33. Teach Allocation With Blocks Before Code
Use a strip of paper divided into units. Let learners physically place and remove allocation cards. Ask them to predict which free region first fit, best fit and buddy allocation will choose before running any program.
This prediction-first route aligns with PRIMM’s Predict–Run–Investigate–Modify–Make sequence: Using PRIMM to teach programming.
34. Fade Worked Heap States Into Independent Diagnosis
Begin with every block labelled by size, owner, alignment and free-list class. Remove some labels in later examples. Finally provide only an allocation trace and ask the learner to reconstruct likely fragmentation and free-space state.
Faded worked examples with metacognitive scaffolding have shown benefits in programming problem solving: Shin et al. (2023).
35. Immediate, Delayed and Transfer Checks
- Immediate: trace first fit, best fit and buddy allocation on a tiny heap.
- Counterexample: construct enough free total memory but no sufficiently large contiguous block.
- Explain: distinguish size classes, slabs and page-level allocation.
- Delayed: reconstruct why local caches reduce contention but can retain memory.
- Transfer: choose allocator priorities for an embedded system, many-core server and latency-sensitive service.
- Professional: explain a memory-footprint regression using size distribution, fragmentation, local caches, page retention and concurrency evidence together.
36. AI Assistance Boundary
AI can generate allocation traces, visualise free-list states, explain allocator documentation and propose fragmentation counterexamples. The learner should still be able to trace the allocator invariant, distinguish fragmentation types, identify the fast and slow paths and verify platform-specific claims against authoritative runtime or kernel documentation.
Professional Direction
Advanced study includes boundary tags, segregated fits, TLSF, dlmalloc-style bins, jemalloc arenas, TCMalloc per-CPU caches, mimalloc sharding, slab/SLUB internals, page heaps, huge pages, NUMA-aware placement, remote frees, memory tagging, guard pages, hardened allocators, lock-free free lists, object pools, region/arena allocation, bump allocators, fragmentation modelling and allocator-aware runtime design.
Algorithm-learning rule: when allocation looks constant-time, ask which cache or size class served the request, what happens when that fast path empties, where freed memory waits, how blocks are coalesced or returned, and whether speed was purchased with fragmentation, footprint or contention elsewhere in the system.
eduKate Sengkang 