The effect of switching to TCMalloc on RocksDB memory use
blog.cloudflare.com
blog.cloudflare.com
It clear that some of these decisions still hang around today and that switching to a better allocator really can make a huge difference, especially given everything is multiple threads/cores today. But a lot of programmers never even look at memory usage or investigate alternatives. Even the JVM has a boatload of options on allocators for different usages; yet most Java programmers I know just go with the defaults.
Computers may be ridiculously fast and have enormous memory today and maybe you can live with the default; but it doesn't hurt to look, and might even save you money (pay less to AWS!) by reducing your need to allocate more or bigger servers.
Often these hardware improvements exacerbate problems with memory management. For years the runtime of the default JVM garbage collector would blow up past 48 GB of allocations. Which was probably fine for 99% of software out there, but the day your honking great server blew past that... was a bad day all round.
It pays to know your allocators and garbage collectors inside and out for modern cloud scale computing.
The 4.0 version of cassandra is finally doing the smart thing and spinning up separate threads dedicated to sets/shards of hash ranges held by a node. I'm not sure if they'll run different JVMs per thread as well to do further sharding of the GC generations as well or if they can effectively do that from one JVM, but that would make sense
It's a quick watch at 1.5x speed, the last third is an interview.
... and they get to punt to the OS too.
I'd certainly believe this isn't a "solved" problem.
There's something to be said about garbage collection as an actual strategy (!!). I know people think that garbage collection is slow, but... very smart people have put their minds on the memory problem.
A generational garbage collector is designed to tackle fragmentation head-on. Every "generation", the garbage collector recompacts all the data, "squeezing" your fragmentation out of the memory area.
Because some data is "longer lived" than other data, the compacted data is placed into a new generational-pool, where it is left alone for the next collection. IE: All data that survived a collection at time T will be left alone at collect time T+1. Maybe at time T+2 will it be re-checked... and those that survive the check at T+2 will be left alone until T+6.
--------------
This generational strategy minimizes the copying / moving of data around the fragmentation issue. Still though: moving / copying data is the singular catch-all solution to fragmentation.
(To my mind, "manual memory management" is when you get a big slab of memory from something, doesn't much matter what, and everything else is managed in your application code. If you're not doing that, you've got some sort of "automation" involved, and that automation can mismatch your program's memory needs every bit as much as a "GC" can.)
Indeed. And is Cheesecake a pie or a cake? You bake cheesecake in pie-crust, but it has cake in the name.
The memory-management "its both" scheme is reference-counting. In some contexts, its ref-counts are considered manual (C++ shared_ptr, Rust). In other contexts, its considered automated garbage collection (Python, Lisp).
In all cases: tons of atomic add/subtract + memory-barriers to strictly order reference counts between many threads... making it actually kind of bad for multithreaded code compared to other garbage collection schemes. (Each shared_ptr<> = blah() requires an atomic add and atomic-subtract. So you actually have escalating costs the more you use the shared_ptr). I think the circular-issue is kind of overblown: it certainly happens (doubly-linked lists, graphs, trees which store a "root pointer" or even an "iterator" somewhere inside of them) but people know how to use weak_ptr<> these days and avoid most issues. (Well... except for arbitrary graphs. No way to know where to put weak_ptr<> there. But most "graph heavy" algorithms use other representations: dense matrix or sparse matrix forms... and probably should avoid slow / low-performance general purpose memory allocators anyway)
-----------
Once you recognize the multithreaded-sync issues associated with shared_ptr<> / RefCount, you start building a thread that "centralizes" the ref-counts in a reader/writer queue to ensure that objects are deleted at the right time. Oh wait, that's called a garbage collector thread and you've suddenly moved to mark&sweep accidentally.
Once you get a garbage collector thread, its not too big of a leap to start thinking about multiple garbage-collector threads (scaling to higher garbage collection performance). I mean, yeah, I'm glossing over all sorts of high-performance multithreaded lock-free datastructures here, but lets pretend those implementation details are solved. Lol.
-----------
As usual: its not really the garbage collection or memory-management parts that are hard. Its the multithreaded high-performance (and provably correct!) portion that's really, really hard. Even for simple ideas like ref-counts or even "manual" malloc/free.
I tried to follow the rest of your comment but I was too disturbed by you thinking all cheesecake is baked in pie-crust.
There's literally a cheesecake on the "serving suggestion" image for the pie crust. I can't be the only one who makes cheesecakes on these...
One needs different allocation strategies for immutable (and strict/lazy) languages.
Compilers might be able to do some of that, but at least the standard libraries should be able to do the hints, and almost all dynamic allocations on day-to-day code uses dynamic structures in standard libraries like hashmaps and variable-length lists/vectors/arrays.
Basically everyone uses jemalloc or tcmalloc in production in the Ruby community nowadays. What frustrates me is the malloc community's sort of blase reaction along the lines of "there's no bug, this is expected behavior".
I would agree with you if it didn't seem like other allocators are solving this without any tradeoffs.
clearly there are circumstances where this is not an option, but for distributed systems that can handle the short-term loss of a given node it works very well. one important thing is to add is some randomized jitter to the periodic restarts to spread out when nodes are offline.
in practice this remedies a wide range of seldom-encountered problems. for instance, I have a program that pulls data from an http apis, and last week its connection to one of the remote servers became hung up somehow, resulting in no new data being pulled from that server. this problem had never happened before in 6 months since the program was deployed. rather than track down the very rare condition that was behind this I just added periodic "partial" restarts to the program, and now it will be able to recover from this if it ever happened again, and many other sorts of problems like slowing increasing memory fragmentation.
for a chat server or other server with client connections, obviously those would need to be maintained across the partial restart, but that seems like it would be pretty easy to do. while there is nothing dramatically different from my approach to what you did with actual, full periodic restarts, the partial restart approach does allow special handling for application-specific issues like that.
I'm a C novice and generally inexperienced with languages that require memory management. Nobody ever tells you this stuff!
Is this a very specific GNU concern, or do I have to keep this in mind in general on other systems when using their default allocators?
Obviously there are downsides to GC, but it's interesting to see how in this scenario malloc+free had the same "uses way more memory than strictly necessary" problem that people usually pin on garbage collectors.
We've spent endless hours trying to identify leaks before we finally tried a few alternative allocators. We switched to jemalloc and the positive effects where huge.
Its a bit weird that this is still an issue.
For example, build parse trees in explicit pools and deallocate the whole tree and associated allocations when done with it.
Language support for this is fairly poor or tricky in OO languages AFAIK; but I'm mostly familiar with C++ where destructors and lack of allocator scoping (until C++11, but optional) make this a pain. The language needs support for formally and transitively abandoning objects (or not caring, like C) to support efficient use of memory pools.
HN discussion from 2019: https://news.ycombinator.com/item?id=20249743
At work we've been able to use mimalloc to great effect, using it as a drop-in replacement for the standard msvc allocator showed 3x runtime (!) improvements on multi-minute workloads. In terms of memory use we also saw improvements, but less dramatic.
Of course these numbers mean nothing without context (and there was much more heap allocation going on than needed), but getting that kind of performance improvement for (comparatively) such little effort really changed my view on memory and optimization.
Not the most user-friendly library though, perhaps that is a result of its selling point: 0 code changes needed.
Besides tcmalloc, there are jmalloc, hoard, the more recent mimalloc, a bunch of commercial options, ...
Would have been interesting to see a comparison.
Edit: background is in this thread: https://news.ycombinator.com/item?id=26013230
For my bigger libraries glibc malloc and free has insane runtimes. Eg a final free could last over 1 minute. If you see this with a GC you would throw it out immediately. But apparently people don't measure and spread false rumors about GC's. Even a very poor and primitive GC as in emacs is not that slow as glibc malloc/free. A good one is miles faster. My GC has an upper limit of 10ms, not minutes.
I vaguely remember when working with the DOS memory allocator many years ago, you could choose between the first/next/best/worst fit strategies, and best fit would tend to produce the worst fragmentation (creating lots of tiny fragments); but as others have noted, it highly depends on the allocation pattern of the application.
Memory allocation is built to some purpose, and the programmer who uses it should be aware of its problems. There's probably a technical reason why the original glibc malloc does what it does (probably better optimized for low-thread counts)
Allocators like TCMalloc are not significantly worse in single threaded mode. The glibc allocator just isn’t very good.
I have personally fought with the glibc allocator and seen issues with it that don’t exist on other OSes.
If glibc malloc is so bad at something like this I find it hard to believe it would be great at anything important if jemalloc/tcmalloc are not.
More practically, anyone who was asked could reasonably respond “Why do you need to own the copyright? It’s already permissively licensed (in jemalloc’s case, with an LGPLv2.1-compatible license) - just use it!” FSF policy is the only obstacle, and they could make an exception if they wanted to.