188
Internal and External Fragmentation
Internal fragmentation refers to space that is overprovisioned inside allocated blocks.
An allocator always returns memory in fixed-sized chunks or buckets. The allocator must
determine what size each bucket is and how many different sized buckets it provides.
If the size of the memory allocation request does not exactly match a predefined bucket
size, the allocator will return a larger memory bucket. For example, if the application
requests a memory allocation of 200KiB, but the allocator has bucket sizes of 128KiB
and 256KiB, the request is allocated from an available 256KiB bucket. The allocator must
usually return a memory chunk with a size divisible by 16 due to its internal alignment
requirements.
External fragmentation occurs when free memory is scattered in small blocks.
For example, imagine using up the entire memory with 4KiB allocations. If we then
free every other allocation, we have half of the memory available; however, we cannot
allocate more than 4KiB at once because that is the maximum size of any contiguous free
space. Figure 11-1 illustrates this fragmentation, where the red cells represent allocated
space and the white cells represent free space.
When storing a sequence of elements in persistent memory, several possible data
structures can be used:
• Linked list: Each node is allocated from persistent memory.
• Dynamic array (vector): A data structure that pre-allocates memory
in bigger chunks. If there is no free space for new elements, it
allocates a new array with bigger capacity and moves all elements
from the old array to the new one.
• Segment vector: A list of fixed-size arrays. If there is no free space left
in any segment, a new one is allocated.
Figure 11-1. External fragmentation
Chapter 11 Designing Data struCtures for persistent MeMory
Internal and External Fragmentation
Internal fragmentation refers to space that is overprovisioned inside allocated blocks.
An allocator always returns memory in fixed-sized chunks or buckets. The allocator must
determine what size each bucket is and how many different sized buckets it provides.
If the size of the memory allocation request does not exactly match a predefined bucket
size, the allocator will return a larger memory bucket. For example, if the application
requests a memory allocation of 200KiB, but the allocator has bucket sizes of 128KiB
and 256KiB, the request is allocated from an available 256KiB bucket. The allocator must
usually return a memory chunk with a size divisible by 16 due to its internal alignment
requirements.
External fragmentation occurs when free memory is scattered in small blocks.
For example, imagine using up the entire memory with 4KiB allocations. If we then
free every other allocation, we have half of the memory available; however, we cannot
allocate more than 4KiB at once because that is the maximum size of any contiguous free
space. Figure 11-1 illustrates this fragmentation, where the red cells represent allocated
space and the white cells represent free space.
When storing a sequence of elements in persistent memory, several possible data
structures can be used:
• Linked list: Each node is allocated from persistent memory.
• Dynamic array (vector): A data structure that pre-allocates memory
in bigger chunks. If there is no free space for new elements, it
allocates a new array with bigger capacity and moves all elements
from the old array to the new one.
• Segment vector: A list of fixed-size arrays. If there is no free space left
in any segment, a new one is allocated.
Figure 11-1. External fragmentation
Chapter 11 Designing Data struCtures for persistent MeMory