"Compacting the Uncompactable" by Bobby Powers

Bobby Powers introduces Mesh, a drop-in malloc replacement that eliminates memory fragmentation in C and C++ programs through compaction.

Programs written in C/C++, can suffer from serious memory fragmentation, leading to low utilization of memory, degraded performance, and 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. Bobby Powers University of Massachusetts Amherst @lilbobbypowers Bobby is a PhD candidate in the PLASMA Lab at UMass Amherst, and a software engineer at Stripe. His interests span systems and programming languages, with a focus on making existing software more efficient, more secure, and usable in new contexts.