Applications like web browsers or smartphone apps often use a lot of memory. To address this, a research group co-led by Emery Berger, a professor of computer science at the University of Massachusetts Amherst, has developed a system they call “Mesh” that can automatically reduce such memory demands. Berger presented this work at Cppcon, the C++ conference held in Aurora, Colorado.
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 explained, programs written in C-like languages can suffer from serious memory fragmentation, where memory is broken up, much like a bad Tetris board, so there are many empty gaps in between. “This is how memory gets wasted,” said Berger in a statement. “Imagine a Tetris board where you could stop and reorganize it at any time – this would make the game a lot easier, because you can 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 explained. 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 reported 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 percent. For Redis, a popular open source data structure server, Mesh reduces memory demands by almost 40 percent.
The CICS Mesh team included 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.
In a field where “catastrophic fragmentation” was long accepted as inevitable, their software is a major step forward, the authors pointed out. “This is something that everyone thought to be impossible,” noted 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 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.”