325
This works by using a free list for many different sizes, shown in Figure 16-6,
until some predefined threshold, after which it is sensible to allocate directly from
the operating system. Those free lists are typically called bins or buckets and can be
implemented in various ways, such as a simple linked list or contiguous buffer with
boundary tags. Each incoming memory allocation request is rounded up to match
one of the free lists, so there must be enough of them to minimize the amount of
overprovisioned space for each allocation. This algorithm approximates a best-fit
allocation policy that selects the memory block with the least amount of excess space for
the request from the ones available.
Using this technique allows memory allocators to have average-case O(1) complexity
while retaining the memory efficiency of best fit. Another benefit is that rounding up of
memory blocks and subsequent segregation forces some regularity to allocation patterns
that otherwise might not exhibit any.
Some allocators also sort the available memory blocks by address and, if possible,
allocate the one that is spatially collocated with previously selected blocks. This
improves space efficiency by increasing the likelihood of reusing the same physical
memory page. It also preserves temporal locality of allocated memory objects, which can
minimize cache and translation lookaside buffer (TLB) misses.
One important advancement in memory allocators is scalability in multithreaded
applications. Most modern memory allocators implement some form of thread caching,
where the vast majority of allocation requests are satisfied directly from memory that
is exclusively assigned to a given thread. Only when memory assigned to a thread is
entirely exhausted, or if the request is very large, the allocation will contend with other
threads for operating system resources.
This allows for allocator implementations that have no locks of any kind, not even
atomics, on the fast path. This can have a potentially significant impact on performance,
even in the single-threaded case. This technique also prevents allocator-induced false
sharing between threads, since a thread will always allocate from its own region of
Figure 16-6. Example of free lists in a memory allocator
Chapter 16 pMDK Internals: IMportant algorIthMs anD Data struCtures
This works by using a free list for many different sizes, shown in Figure 16-6,
until some predefined threshold, after which it is sensible to allocate directly from
the operating system. Those free lists are typically called bins or buckets and can be
implemented in various ways, such as a simple linked list or contiguous buffer with
boundary tags. Each incoming memory allocation request is rounded up to match
one of the free lists, so there must be enough of them to minimize the amount of
overprovisioned space for each allocation. This algorithm approximates a best-fit
allocation policy that selects the memory block with the least amount of excess space for
the request from the ones available.
Using this technique allows memory allocators to have average-case O(1) complexity
while retaining the memory efficiency of best fit. Another benefit is that rounding up of
memory blocks and subsequent segregation forces some regularity to allocation patterns
that otherwise might not exhibit any.
Some allocators also sort the available memory blocks by address and, if possible,
allocate the one that is spatially collocated with previously selected blocks. This
improves space efficiency by increasing the likelihood of reusing the same physical
memory page. It also preserves temporal locality of allocated memory objects, which can
minimize cache and translation lookaside buffer (TLB) misses.
One important advancement in memory allocators is scalability in multithreaded
applications. Most modern memory allocators implement some form of thread caching,
where the vast majority of allocation requests are satisfied directly from memory that
is exclusively assigned to a given thread. Only when memory assigned to a thread is
entirely exhausted, or if the request is very large, the allocation will contend with other
threads for operating system resources.
This allows for allocator implementations that have no locks of any kind, not even
atomics, on the fast path. This can have a potentially significant impact on performance,
even in the single-threaded case. This technique also prevents allocator-induced false
sharing between threads, since a thread will always allocate from its own region of
Figure 16-6. Example of free lists in a memory allocator
Chapter 16 pMDK Internals: IMportant algorIthMs anD Data struCtures