Understanding Mesh Allocator
2024-Jan-24
I recently read about the Mesh memory allocator and was fascinated by its ability to perform compaction without changing the addresses of allocated objects.
In this post, I will briefly summarize how Mesh allocator works. For more details about its algorithms and implementation, refer to the paper (PDF) by Bobby Powers et al. or watch this talk.
1 Fragmentation
Applications written in manually memory managed languages might fail to allocate memory, even when the required amount of space is available in memory. This problem is known as memory fragmentation and can be solved by compaction, where all allocated objects are moved together to make a contiguous block of free space available.
Garbage collected languages can solve this by stopping program execution to compact allocated objects and update all pointers to point to the relocated objects. But, languages which expose raw pointers to the programmer don’t have this luxury as it is impossible to trace and update all the pointers.
Therefore, to reduce memory fragmentation for applications written in manually memory managed languages, compaction should occur without changing the pointers’ values and this is exactly where Mesh shines.
2 Compaction Without Relocation
The Mesh allocator performs compaction without relocation by taking advantage of the fact that pointers are virtual memory addresses pointing to objects on physical memory. This allows the allocator to move objects in the physical memory and update the virtual to physical memory mapping without changing the virtual memory address of allocated objects.
There are three core concepts behind the Mesh allocator:
2.1 Meshing
Meshing is the phase where objects are relocated in physical memory. It randomly selects physical memory pages with objects allocated at non-overlapping offsets and merges (meshes) them together by copying all objects from one page to another. The copied objects retain their original offsets. Then, the page from which content was moved is given back to the operating system; effectively reducing memory consumption.
This does not affect performance as meshing is performed concurrently without stopping program execution.
2.2 Updating Virtual to Physical Address Mapping
After meshing, the process’s page table is updated to remap the virtual memory addresses of moved objects to the new physical addresses. However, the program is unaware of this change because the virtual memory addresses (pointers) remain the same since the offsets of objects have not changed.
2.3 Randomized Allocation
Memory allocation is randomly spread throughout a page to facilitate meshing by increasing the chances of pages having objects allocated at non-overlapping offsets. This doesn’t seem to affect cache performance as allocations returned from popular memory allocators are not contiguous either.
3 Conclusion
This memory allocator has proven to significantly reduce the memory consumption of Firefox and Redis with only a small increase in performance overhead.
I’m amazed at how simple and easy-to-understand techniques can significantly reduce fragmentation while maintaining performance, without requiring any changes to the codebase.