Introducing 'mesh,' memory-saving plug-in to boost phone and computer performance

Berger and colleagues in the College of Information and Computer Science (CICS) expect Mesh to have a substantial impact on the computing world, from mobile applications to desktops to data centers, because no one has previously been able to compact memory in applications written in or running on top of widely-used languages like C, C++, or Objective C, the language used for iOS apps.

As the authors explain, programs written in C-like languages can suffer from serious memory fragmentation, where memory is broken up, much like a bad Tetris board, Berger says, so there are many empty gaps in between. "This is how memory gets wasted," he points out. "Imagine a Tetris board where you could stop and reorganize it at any time -- this would make the game a lot easier, because you could always squeeze out the empty space. But you can't do this in C, just as you can't do it in Tetris."

Mesh effectively squeezes out these gaps by taking advantage of a hardware feature called "virtual memory" that is supported by almost all modern computers. "The trick is to find chunks of memory that can be interleaved, sort of like when interlocking gears mesh," Berger explains. When Mesh finds these chunks, it can reclaim the memory from one of the chunks by combining the two chunks into just one. "This meshing process works because we only change things in 'physical' memory. From the perspective of the program, which can only see 'virtual' memory, nothing has changed. This is powerful because we can do this for any application automatically."

The team reports that the results to date have been extremely promising; for example, using Mesh automatically reduces the memory demands of the Firefox web browser by 16%. For Redis, a popular open source data structure server, Mesh reduces memory demands by almost 40%.

The CICS Mesh team includes professor Emery Berger, an expert in memory management who designed the algorithm that the Mac OS X memory manager is based on, professor Andrew McGregor, a specialist in algorithm design and analysis, and doctoral candidates Bobby Powers and David Tench. Powers is a fourth-year doctoral candidate who also is an infrastructure engineer at Stripe, and Tench is a fifth-year doctoral candidate specializing in randomized algorithms.

In a field where "catastrophic fragmentation" was long accepted as inevitable, their software is a major step forward, the authors point out. "This is something that everyone thought to be impossible," notes McGregor. "After Emery had his key insight, we were able to analyze it theoretically and design an efficient algorithm to implement the idea. Against almost 50 years of conventional wisdom, it's great that we now have a solution to this important problem that not only works in theory, but is practical."

Earlier this year, Berger presented technical details at the ACM SIGPLAN Programming Language Design and Implementation conference (PLDI '19) in Phoenix. In response to the paper, Microsoft programmer and distinguished engineer Miguel de Icaza tweeted that Mesh is a "truly inspiring work, with deep impact. A beautiful idea fully developed. What an amazing contribution to the industry."