https://veera.app/mesh_allocator.html

Github Home About Email

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.

Last updated on 2024-Jan-24 Wed 23:08.