§17.3–17.5Basic Strategies … Summary

No best answer exists — the request stream is the programmer’s whim, and any policy can be ambushed by the wrong workload. So the book does what engineers do: lay out the basic strategies, price them, and let the workload decide.

17.3 Basic Strategies

Best fit best fit Free-list strategy: search the whole list and return the SMALLEST chunk that satisfies the request — minimizes leftover waste but pays for the exhaustive search and tends to leave tiny slivers. defined in ch. 17 — open in glossary : search the whole list for candidates (chunks ≥ the request) and return the smallest — closest to what was asked, least waste per grant. Cost: an exhaustive search, and a trail of tiny slivers. Worst fit worst fit Free-list strategy: return the LARGEST chunk, hoping to keep leftovers usefully big — studies show it performs badly, with excess fragmentation and full-search overheads. defined in ch. 17 — open in glossary inverts it: take the largest chunk, hoping leftovers stay usefully big. Also a full search — and most studies show it simply performs badly. First fit first fit Free-list strategy: return the first chunk big enough — fast (no exhaustive search) but can pollute the list's start with small splinters; address-ordered lists ease coalescing. defined in ch. 17 — open in glossary grabs the first chunk big enough: no exhaustive search, but the front of the list silts up with splinters (address-based ordering helps, and eases coalescing too). Next fit next fit First fit plus a roving pointer: resume searching where the last search ended, spreading splinters through the list instead of piling them at the front. defined in ch. 17 — open in glossary adds a roving pointer that resumes where the last search ended — first-fit speed, splinters spread evenly.

17.4 Other Approaches

Segregated lists. If an application hammers one (or a few) sizes, give that size its own dedicated list segregated list Keeping a dedicated free list for a popular request size: near-zero fragmentation and O(1) alloc/free for that size, with the open question of how much memory to dedicate to it versus the general pool. defined in ch. 17 — open in glossary : no search, no splitting, near-zero fragmentation for that size — and a new headache (how much memory does the special pool get?). The definitive answer is Jeff Bonwick’s slab allocator slab allocator Bonwick's kernel allocator (Solaris): boot-time object caches — segregated lists for hot kernel objects (locks, inodes) — fed page-multiple slabs by a general allocator, with freed objects kept PRE-INITIALIZED to skip costly init/destroy cycles. defined in ch. 17 — open in glossary (built for the Solaris kernel): at boot, create object caches for hot kernel objects (locks, file-system inodes…); each cache is a segregated list of one size, and it trades memory with a general allocator dynamically — requesting page-multiple slabs when low, returning them when the objects’ reference counts all hit zero. One more trick: freed objects are kept in their initialized state, dodging the (measurably costly) init/destroy cycle on every reuse.

Buddy allocation. Since coalescing is what keeps a heap healthy, the binary buddy allocator buddy allocation Treat free memory as one 2^N space; recursively halve to the smallest sufficient power-of-two block (internal fragmentation is the tax). A freed block's buddy — its address differs by exactly one bit — is checked and merged, recursively, making coalescing trivial. defined in ch. 17 — open in glossary designs everything around making it trivial:

Other ideas. Plain lists don’t scale — advanced allocators reach for balanced binary trees, splay trees, or partially-ordered trees to cut search costs. And the multiprocessor era bred allocators built for concurrency: Hoard, and Evans’s jemalloc (still inside FreeBSD, Firefox, and Facebook’s stack). For the real world in one dive, read how glibc’s malloc works.

17.5 Summary

Rudimentary allocators live everywhere: linked into every C program, and inside the OS managing its own structures. The recipe is now yours: splitting and coalescing over an embedded free list, headers to remember sizes, a fit policy chosen with the workload in mind, and — when the workload cooperates — segregated pools or buddy trees to make the common case fast. Building one allocator that is fast, space- efficient, and scalable for arbitrary workloads remains an open challenge. The next chapter takes the other exit: make every unit the same size, and watch the whole problem dissolve.