Dynamic memory allocation reserves and releases storage during execution in a region called the heap. It is a common source of work in latency-sensitive code, including work that changes unexpectedly with the application workload. section 7.4.1 section 7.4
A dynamic allocator obtains memory from the operating system for the process, then assigns smaller blocks to individual requests. In a simplified allocator, a linked list tracks free blocks. An allocation searches for a block large enough to use, possibly splitting it; releasing a block makes it available for a later request. Real allocators add layers and optimizations, but allocation still entails work rather than a fixed, deterministic cost. section 7.4.1
Figure 7.3 The dynamic memory allocator manages a section of memory we call the heap. In this example, the dynamic memory allocator maintains a list of free blocks in memory (freelist), which is a linked list of all the available blocks.
The free-list diagram makes the search, reuse, and possible splitting of heap blocks concrete. section 7.4.1
The way to request dynamic storage depends on the language: examples include `new`, C’s `malloc()`, and Rust’s `Box`. How much control a programmer has over lower-level allocation behavior also depends on the language and runtime; not every latency optimization available in a systems language transfers to a garbage-collected language. section 7.4.1 section 2.3
Measure before removing allocations
A Fibonacci benchmark compares a recursive implementation, a memoized version with a vector cache, and an iterative version. Reported times are about 157 ns, 44 ns, and 5 ns respectively. The gains have more than one cause: memoization changes the algorithmic complexity, while iteration also removes the dynamic allocation used by the cache. Benchmark the performance-sensitive path before attributing an improvement to allocation alone. section 7.7
