Bobby Powers, David Tench, Emery D. Berger, Andrew McGregor
2019 · arXiv
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 paper introduces Mesh, a plug-in replacement for malloc that, for the first time, eliminates fragmentation in unmodified C/C++ applications. Mesh combines novel randomized algorithms with widely-supported virtual memory operations to provably reduce fragmentation, breaking the classical Robson bounds with high probability. Mesh generally matches the runtime performance of state-of-the-art memory allocators while reducing memory consumption; in particular, it reduces the memory of consumption of Firefox by 16% and Redis by 39%.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
5 selected excerpts · 5 total mentions
There’s a great paper from the group of Emery Berger, where they merge memory pages that become sparse. A kind of garbage collection for C and C++ languages. There’s also a good presentation about it on youtube. https://arxiv.org/abs/1902.04738 The presentation: https://youtu.be/c1UBJbfR-H0
In the basic generational references approach that was a drawback, and the reason it couldn't release memory back to the OS. We planned to use something like MESH [0] to reduce the fragmentation. We created two newer approaches since then, which let any memory be reused for any purpose: * Random generational references, where it's fine if generations overlap with other data. * Side-table generations, which is slower but we keep the generations in a side-table. It's can be seen in old 0.1 versions as the "resilient-v2" mode, and I plan on resurrecting it for unrelated reasons. The former will be the default, and the latter we'll be adding back in as an option. Hope that helps! [0] https://arxiv.org/pdf/1902.04738.pdf
Actually...https://arxiv.org/pdf/1902.04738.pdf On a more serious note, most c programs I see don't do very much of that, preferring to allocate fixed-size buffers on the stack. Additionally, most GC'd languages that aren't java have crappy GCs, and those GC'd languages that are java lack value types. This harms spatial locality quite a bit, and compaction can't fully compensate for that. They are working on adding value types to the jvm, though; it will be very interesting to see how performance changes. (I expect not very much in practice—those projects for which performance was important were already using whatever tricks they needed to—but perhaps it will improve the ergonomics of performant java.)
Looks like he reinvented shuffle vectors on his own. I think a lot of people have over the years, but crazy enough nobody bothered to publish it until February this year! Maybe it felt too intuitive? [0] https://observablehq.com/@jobleonard/shuffle-vectors [1] https://arxiv.org/abs/1902.04738
Fragmentation is solvable. Mesh can compact C programs using malloc/free without any source changes. https://arxiv.org/abs/1902.04738
More from the same topics.
Anders Sandberg, Eric Drexler, Toby Ord
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
Scott Aaronson
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.