Compacting the Uncompactable: The Mesh Compacting Memory Allocator

Programs written in C/C++ can suffer from serious memory fragmentation, leading to low utilization of memory, degraded performance, and even application failure due to memory exhaustion. This problem extends to languages like Ruby and Python, where the standard interpreters for these languages are themselves C programs.

This talk introduces Mesh, a plug-in replacement for malloc that, for the first time, eliminates fragmentation in unmodified C/C++ applications through compaction. A key challenge is that, unlike in garbage-collected environments, the addresses of allocated objects in C and C++ are directly exposed to programmers, and applications may do things like stash addresses in integers or store flags in the low bits of aligned addresses. This hostile environment makes it impossible to safely relocate objects, as the runtime cannot precisely locate and update pointers.

Mesh combines novel randomized algorithms with widely-supported virtual memory operations to provably reduce fragmentation, breaking long-established worst-case bounds on memory efficiency with high probability. Mesh generally matches the runtime performance of state-of-the art memory allocators while reducing memory consumption and eliminating pathological cases; in particular, Mesh reduces the memory of consumption of Firefox by 16% and Redis by 39%. There are efforts underway to incorporate Mesh’s approach to eliminate fragmentation into existing allocators, like jemalloc. Mesh is publicly available at http://libmesh.org.

Joint work with Bobby Powers, David Tench, and Andrew McGregor (UMass Amherst).

[Slides]

Series:
Microsoft Research Talks
Date:
Speakers:
Emery Berger
Affiliation:
University of Massachusetts Amherst

Series: Microsoft Research Talks