27 ms·
Linus Torvalds on Garbage Collection (2002)
- wladimir 16y ago[2002] Though his argument about cache does still hold.
- MatthewPhillips 16y agoI think his opinion might not have changed. In his latest "C++ sucks" rant in that "why is git written in C" thread he points out not having GC as being one of the detriments of C++.
- awj 16y agoFor the complexity it adds not having GC is a detriment of C++. The language makes reasoning about allocation, object ownership, etc, much harder. It does this in the course of providing features intended to help you structure and manage larger pieces of code, and thus accidentally works to defeat that purpose. I don't think Linus ever intended to declare GC as evil or wrong. He was calling it out as a very poor choice that people persist in making for certain domains.
- deleted 16y ago[deleted]
- stonemetal 16y agoI could see it holding for say Java or C#, but for a single assignment languages like SML or Haskell I don't think it would hold. It seems like changing single assignment to mutation would be one of the first memory related optimizations you would make. While it is easiest to think of that as A1 = A0 + B is a mutation of A, there is nothing that says it should be so limited.
- masklinn 16y ago> for a single assignment languages like SML or Haskell I don't think it would hold. It would not have to hold, but I have not heard of any such scheme being implemented.
- sausagefeet 16y agoWhat about for something like SISAL?
- koenigdavidmj 16y agoAnd sure enough, graph colouring register allocators work just as well for allocating chunks of memory as they do for allocating registers.
- AndrewDucker 16y agoI think it holds for work that's happening close to the metal. If you're working at the level where you're trying to fit all your data in the cache, then GC will get in the way of that. For applications operating at a higher level, or where any calculation that's going on is taking up a trivial amount of CPU time compared to (say) waiting for the user, then the overhead of reference counting (and the mistakes that are associated with that) is probably not worth it.
- wladimir 16y agoSure. He was talking about the OS level. In UI scripts or something else running on multiple levels of abstraction, preventing memory leaks and allowing developers to quickly prototype is much more important. Cache performance does not even come into it. It would be crazy to advocate manually managing memory there.
- rayiner 16y agoAre you sure?
- Vlasta 16y agoI like him mentioning the programmer's mindset associated with GC being a big danger. Some people consider GC a magic bullet and refuse to think about what's happening under the hood. I do not consider that a good habit.
- sausagefeet 16y agoSome people consider it free too which is very painful. Like pretending networks don't have latency.
- marshray 16y agoIt seems to be far easier (i.e., possible) to go from a manual-memory-management style of development to an automatic one than the other way around. I've known plenty of Java-CS-degree programmers who just never could get the hang of writing C/C++ code without leaking stuff (and not just memory).
- alextingle 16y agoThis is a key point that I think lots of GC proponents gloss over. Memory is not the only resource that needs to be managed. Open file handles, sockets, user sessions, whatever... they all need to be managed in much the same way as memory.
- jasongullickson 16y agoWhat he's advocating sounds a lot like how things work in the iOS world, in my experience.
- adolph 16y agoA GC system with explicitly visible reference counts (and immediate freeing) with language support to make it easier to get the refcounts right (things like automatically incrementing the refcounts when passing the object off to others) wouldn't necessarily be painful to use, and would clearly offer all the advantages of just doing it all by hand. I was wondering how that was different from Cocoa on Objective-C. See: http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/mmPractical.html%23//apple_ref/doc/uid/TP40004447-SW1 http://developer.apple.com/library/mac/#documentation/Cocoa/...
- pdhborges 16y agoThe runtime system might not free the memory immediately.
- pohl 16y agoCould you expand on this thought? I assumed that free() was invoked in the dealloc method, which was explicitly called if the release method reached a zero ref count.
- sil3ntmac 16y agoThat's correct, unless the object is autoreleased, in which case the system will get around to deallocating it after the current run loop iterates (provided you're using the default autorelease pool).
- DougBTX 16y agoWorth noting that an autoreleased object which you haven't retained will have a ref count of 1, so they are not an exception to the "freed when the ref count is zero" idea.
- manveru 16y agoMight be worth mentioning Tcl in this context, as it uses reference counting for the GC [1]. It also doesn't allow circular data structures, which are quit hard to implement if all you have are strings anyway. [1]: http://wiki.tcl.tk/3096 http://wiki.tcl.tk/3096
- zerohp 16y agoPerl also uses reference counting, and cyclical data structures cause memory leaks unless you explicitly decrease the reference count with the weaken function from Scalar::Util.
- IgorPartola 16y agoAnd Python. AFAIK, there are no plans to fix it at this point. Also Python is notorious for allocating lots of small objects.
- LeonidasXIV 16y agoThough it does throw away unused cyclic dependencies, so you don't have to do the same trickery as in Perl.
- stonemetal 16y agoPython has a mark and sweep garbage collector(since 2.0) to catch that which reference counting misses. You can disable it if you know you don't make any cyclical objects.
- pnathan 16y agoI've done minor amounts of text analysis in Python. It is a memory pig. I was shocked. Anything remotely like a non-trivial dataset should not be run in pure Python, based on my experience.
- sklivvz1971 16y agoIt's 2011, FFS. This kind of mindset is really self defeating in the long term. Sure, hand optimizing is better. Having a gazillion lines of shit legacy code and technical debt to fix because you hand optimized for the 90's, it's not so great. I'll keep my GC and sip a Mohito on the beach, while Linus keeps on fixing Linux's "optimizations" ten years from now.
- hasenj 16y agoIt's already been ten years since he wrote that.
- gaius 16y agoYeah - mods can we edit a date into the title please?
- parfe 16y agoThe email was written a decade ago.
- shin_lao 16y agoThe alternative to a GC is not "hand optimizing". There are several patterns such as reference counted memory and RAII that are far from complex to use. If you've written any data intensive application you know that a GC doesn't solve memory issue. It's just a different strategy.
- sklivvz1971 16y agoIt's a strategy _I_don't_need_to_concern_with_ :-)
- mmcconnell1618 16y agoI'm quite sure the machine code generated by my compiler isn't nearly as good as it could be if I hand coded it but the efficiency of not writing in machine code far outweighs any potential performance gains.
- Rusky 16y agoYou have a good point that applies in a lot of places, but here you're aiming it at a straw man. Linus advocates reference counting and even suggests building it into the language would be a good idea. That's hardly hand coding anything- it's just a different strategy for GC (which is actually done). It is getting harder and harder to beat compilers with hand-coded assembly without an enormous amount of effort, though.
- mckoss 16y agoDidn't Linus forget newnode->count = 1;
- ciupicri 16y agoMaybe it's done by the copy_alloc function.
- jfr 16y ago> A GC system with explicitly visible reference counts (and immediate freeing) with language support to make it easier to get the refcounts right [...] To be a little pedantic on the subject, such a system (reference counting and immediate freeing) is a form of automatic memory management, but it is not GC in any way. Garbage collection implies that the system leaves garbage around, which needs to be collected in some way or another. The usual approach to refcounting releases resources as soon as they are no longer required (either by free()ing immediately or by sending it to a pool of unused resources), thus doesn't leave garbage around, and doesn't need a collector thread or mechanism to. There are partial-GC implementations of refcounting, either because items are not free()d when they reach zero references, or to automatically detect reference loops which are not handled directly. I agree with Torvalds on this matter. GC as it is promoted today is a giant step that gives programmers one benefit, solving one problem, while introducing a immeasurable pile of complexity to the system creating another pile of problems that are still not fixed today. And to fix some of these problems (like speed) you have to introduce more complexity. This is my problem with GC. I like simplicity. Simplicity tends to perform well, and being simple also means it has little space for problems. Refcounting is simple and elegant, you just have to take care of reference loops, which also has another simple solution, that is weak references. I can teach a class of CS students everything they need to know to design a refcounting resource management system in one lesson. GC is the opposite: it is big, complex, and a problem that the more you try to fix it, the more complex it becomes. The original idea is simple, but nobody uses the original idea because it performs so badly. To teach the same class how to design a GC system that performs as well as we expect today, an entire semester may not be enough.
- stcredzero 16y agoI agree with Torvalds on this matter. In a way, I do as well. GC as it is promoted today is a giant step that gives programmers one benefit, solving one problem, while introducing a immeasurable pile of complexity to the system creating another pile of problems that are still not fixed today. And to fix some of these problems (like speed) you have to introduce more complexity. There are plenty of contexts where speed is a non-issue. In those cases, GC has been a huge win. The conceptual simplicity is the important part. The cost of the resources that would be saved with explicit and optimized memory management would be far outweighed by the resources required to implement such things. The original idea is simple, but nobody uses the original idea because it performs so badly. This is simply not true. In the context of IO-bound enterprise systems, I've seen generational GC perform admirably, almost magically. As a lark, I've put infinite loops into such apps that do nothing but allocate new objects, and unless you are doing an exceptionally intense operation, you couldn't tell the difference. Properly tuned generational GC can be a truly fantastic seeming thing! However, I will agree that the concerns Linus highlights are real, and that refcounting systems, like the one in iOS are by far better choices in many contexts. EDIT: The above system I victimized, I only victimized in the TEST environment, but it was populated with something like 2-week old production data. The application in question is a traditional client/server desktop app used by a major energy company and had 800 active users at the time, handling millions in transactions every minute. IDEA: If someone had an augmented ref-counting system with a runtime containing an optional cycle-detector and something like LINT but for the runtime reference graph, one would get most of the benefits of GC with the efficiency of the ref-counting system. I half expect someone to tell me that this already exists for Python.
- teh 16y agoSlightly related: He mentions that when the containing structure of a sub structure goes away you can free all the resources. The guys behind Samba 4 developed talloc [1] which is build around that idea. [1] http://talloc.samba.org/talloc/doc/html/index.html http://talloc.samba.org/talloc/doc/html/index.html
- neilc 16y agoArena or pool memory allocation is a very old idea, and has been implemented by many different systems (e.g., Apache/APR, PostgreSQL, lcc).
- mfukar 16y agoHacker News, another place where 10-year-old emails are submitted as news.
- loup-vaillant 16y agoSo. Programs that use Garbage Collection tend to be slow. Cause: Hardware don't like it. Solution: fix the hardware? Seriously, I'm afraid we're stuck in a local optimum here. It is as if machines are optimized for the two dominant C/C++ compilers out there, and we have then to optimize our program against that, closing the loop. Shouldn't compilers and hardware be designed hand in hand?
- tlholaday 16y agoIntel makes both processors and compilers.
- marshray 16y agoYes, but their compiler doesn't have much market share, certainly not enough that it can drive the chip design. They do, of course, make a lot of popular chips, but even there they can't dictate the architecture single-handedly. The vast majority of software seems to be built with something other than Intel compilers and compiled for generic 32-bit x86/i386/ia32 and/or x64/x86_64/amd64 platforms. (whatever you want to call 'em)
- rgoddard 16y agoThe design of the memory hierarchy is dictated by the fact that in general the faster your memory is, the more it costs. As a way to balance this you have a hierarchy of memory, with the fastest closest to the cpu and also in the smallest quantity. So the compilers are optimized for the hardware, not the other way around.
- ciupicri 16y agoThere were a couple of machines optimized for LISP some years ago, but guess what? They were beaten by ordinary machines.
- jimwise 16y agoSure -- but they were beaten by ordinary machines because the combination of better ordinary machines and better techniques for running lisp on ordinary machines improved to the point where lisp machines weren't better at running lisp. A lot of this is that a few small low-budget research groups were building lisp machines at a time when the big players suddenly started pouring all their efforts into developing commodity single-user graphical workstations. But it's also true that developments in GC technology -- developments which Torvalds seems unaware of in this 2002 post, even though they were 15-20 years old by then -- made GC really fast even on hardware not designed with GC in mind.
- LarrySDonald 16y agoSo.. Essentially man the F up and live without GC in the parts that are going too slow instead of saying "Oh it's cool, just wait ten years and hardware will be fast enough to run this anyway". Use GC for stuff that needs to be simple and is fast enough anyway, don't bog down code that's too slow with it.
- ekidd 16y agoShortly before Linus wrote this article in 2002, I wrote an XML-RPC library in C that used reference counting. By the time I was done, I'd written 7,000+ lines of extremely paranoid C code, and probably eliminated all the memory leaks. The project cost my client ~$5K. The standard Python xmlrpc library was less than 800 lines of code, and it was probably written in a day or two. Was my library about 50 times faster? Sure, I could parse 1,500+ XML-RPC requests/second. Did anybody actually benfit from this speed? Probably not. But the real problem is even bigger: Virtually every reference-counting codebase I've ever seen was full of bugs and memory leaks, especially in the error-handling code. I don't think more than 5% of programmers are disciplined enough to get it right. If I'm paying for the code, I'll prefer GC almost every time. I value correctness and low costs, and only worry about performance when there's a clear business need.
- ekiru 16y agoLinus suggested in the OP that automated reference counting (where the language implementation handles reference counting for the programmer) is preferable to GC. Python uses such reference counting (although it also has a GC fallback to ensure cyclic structures are collected).
- cdavid 16y agoAnd it is one of the reason why python is slow and difficult to scale on multiple cores (the main difficulty by far of removing the GIL is reference counting).
- kragen 16y agoScaling Python on multiple cores is easy: you just run multiple Python processes, each with its own per-core GIL. You are correct, though, that ref-counting overhead is one of the main reasons Python is slow.
- cdavid 16y agoYou are playing with words here: of course you can run multiple python instances to scale your application on multiple-cores, that's a trivial statement. But I was talking about python the interpreter (more exactly cpython). There are legitimate cases where multi-threading is the natural, elegant solution, and cpython, mostly because of reference counting, prevents that.
- joshhart 16y agoHere are a couple of reasons why I think it's not so clear cut: 1. If garbage collection was that damaging to the cache, Haskell wouldn't be nearly as fast as C. 2. Copy-on-write data structures are nice because the immutability allows for concurrent access without locking. Granted, this was from 2002 and Linus may no longer feel so strongly about the topic.
- jedbrown 16y agoShow me a memory-intensive kernel in which Haskell runs close to the performance model. Sparse and dense matrix kernels would be a good place to start. Our C code for sparse matrix-vector products and sparse triangular solves gets better than 90% of STREAM bandwidth (based on an assumption of optimal cache reuse, STREAM is about 85% of hardware peak). Dense matrix kernels should get better than 90% of FPU peak. Unlike sparse kernels, dense kernels are no longer bandwidth limited, but cache reuse in both L1 and L2, as well as friendly TLB behavior is important to good performance. It would be interesting to see any Haskell implementations that are competitive. I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad.
- joshhart 16y agoLet's be fair here. Numerical processing is not representative of most applications, but I concede the point. It's an interesting question though. I'm a Haskell beginner, but I'm pretty experienced with Scala. Let me try to see how using sliding compares with a tight Java loop on statically allocated data for convolutions/filters.
- marshray 16y agoI suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad. Of course not every problem is going to fit well into an imperative model either. E.g. a problem with a large variety of pointer-y data structures and interit-y objects, like say, a compiler.
- dons 16y ago
- barrkel 16y agoReference counting is GC; a poor form if it's the only thing you rely on, but it is automatic memory management all the same. Generational GC will frequently use the (L2/L3) cache size itself as its smallest generation, meaning it shouldn't suffer from the pathologies talked about by Linus here. What GC really gives you, though, is the freedom to write code in a functional and referentially transparent way. Writing functions that return potentially shared, or potentially newly allocated, blobs of memory is painful in a manual memory management environment, because every function call becomes a resource management problem. You can't even freely chain multiple invocations (y = f(g(h(x)))) because, what if there's a problem with g? How do you then free the return value of h? How to you cheaply and easily memoize a function without GC, where the function returns a value that must be allocated on the heap, but might be shared? Writing code that leans towards expressions rather than statements, functions rather than procedures, immutability rather than mutability, referentially transparent rather than side-effecting and stateful, gives you big advantages. You can compose your code more easily and freely. You can express the intent of the code more directly, letting you optimize at the algorithm level, while the ease of memoization lets you trade space for speed without significantly impacting the rest of your program. Doing this without GC is very awkward. GC, used wisely, is the key to maintainable programs that run quickly. You can write maintainable yet less efficient programs, or highly efficient yet less maintainable programs, easily enough in its absence; but its presence frees up a third way.
- cageface 16y agoThis is the essential point. GC may not be appropriate in all contexts, but, when it is, it tremendously improves the expressiveness of the language.
- illumen 16y agoGC code runs differently depending on the code running around it. It causes the code to be non deterministic, and introduces a side effect. I've written code in a reference counted language(python) which processes about a gigabyte of data per second from the network, with hard real time requirements - all on one machine with multiple cpus/cores. The code is fully unit tested, doc tested, and functionally tested. It's also short, runs on multiple platforms and has been maintained by other people than myself. My personal experience is that you can write highly efficient maintainable code with reference counting. Reference counting manages memory automatically for you, but it also lets to manage memory manually when needed too. For many situations, it's the best of both worlds.
- albertzeyer 16y agoWhen I read this, I immediately thought about std/boost::shared_ptr. This is a bit ironic since Linus hates C++ so much. shared_ptr is a really nice thing in C++. (For those who don't know: It is a ref-counting pointer with automatic freeing.) And its behavior is very deterministic. In many cases in complex C++ applications, you want to use that.
- alextingle 16y agoOr as we like to call it, std::shared_ptr
- famousactress 16y agoWe should really encourage eachother to put the date in the title when submitting old articles to HN. It's a total brainf*k to read through the entire article, and not realize the context it was in.. or to just glance at the title and assume the topic is a current one. Just saying. [Edit] Not that I have a problem with older posts, btw.. I actually really like them most of the time. But the date would give everyone a better opportunity to evaluate whether they want to read the article, and would be reading it with reasonable context.
- oinksoft 16y agoDate: Fri, 9 Aug 2002 20:28:16 -0700
- famousactress 16y agoSorry if I wasn't clear. Of course I can click through and check the date. I'm just suggesting that since HN is generally a news site that the general expectation is that the articles posted will be current, and I think it'd be handy if we tried to call out dates in the title when posting old stuff. My original comment's relatively well upvoted now also, so I don't think I'm alone.
- lambda 16y agoIs it just me, or does the title say (2002) to give you context?
- famousactress 16y agoThat was added later (presumably in response to this comment).
- earino 16y agoGuy who writes kernel code cares about performance, film at 11.
- iskander 16y agoI'm very suspicious of anyone (even Linus) claiming that gcc is slow because of its memory management. The codebase is crufty and convoluted--- it's probably slow for a thousand different reasons. If you refactored into a clean design and rewrote the beast in OCaml (or any other language with a snappy generational collector), you'd probably get a large performance boost.
- astrange 16y agoI think your argument consists of "gcc is slow because I don't understand the code layout". One of the problems affecting the C frontend and backend is poor cache locality due to pointer chasing in their data structures, and they currently do switch between GC memory and manually allocated zones (obstacks) to improve this.
- KirinDave 16y agoThat was 2002. Here is the state of the art in 2008: http://cs.anu.edu.au/techreports/2007/TR-CS-07-04.pdf http://cs.anu.edu.au/techreports/2007/TR-CS-07-04.pdf Unsurprisngly, things have changed. Many of Linus's complaints were valid, and we've learned how to address them.
- joeyespo 16y agoI think this is another case of everybody thinks about garbage collection the wrong way: http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047586.aspx http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047... From the article: "Garbage collection is simulating a computer with an infinite amount of memory. The rest is mechanism." Whether or not it's reference counting or generational, the goal is still to simulate infinite memory. That way, you can focus on the high-level problems instead of the technical memory-related details. So it's not necessarily a bad mindset to have.
- __david__ 16y agoI like the way the D language approached this. It's garbage collected but it also has a "delete" function/operator. That way you can use garbage collection if you'd like, or you can manually free memory when you think it's worth it. That seems like a reasonable compromise and I'm surprised that more languages don't do it.
- deleted 16y ago[deleted]
- ww520 16y agoThis is like arguing assembly is better than high level languages because it's faster with explicit control. The thing is 99% of the time it doesn't matter. In most cases, GC-based programs have good enough performance to get the job done. For the 1% case, sure use the C/C++/Assembly to have the explicit control and performance. Doing things in non-GC systems because of potential caching problem sounds like a case of premature optimization.
- astrange 16y agoI really like it when people reply "usually this doesn't matter" to a discussion in a project where it _does_ matter.
- ww520 16y agoI got the impression that Linus was discussing GC in general usage in the long post, not specific to the GCC compiler. He even brought up the copy_on_write example, which was a kernel or file system usage. If the goal is to speed up GCC, there are a long list of things to do before you have to worry about L1/L2 cache miss. Header file processing (or re-processing) is one of the biggest time sinks during compilation.
- astrange 16y agocpp avoids reprocessing: http://gcc.gnu.org/onlinedocs/cpp/Once_002dOnly-Headers.html http://gcc.gnu.org/onlinedocs/cpp/Once_002dOnly-Headers.html Processing header files in the first place is certainly a problem affecting C, but I believe optimizations take more time. Parsing is a much larger problem for C++.
- ww520 16y agoI meant reprocessing the same set of header files for every single cpp file including them. Precompiled headers suppose to speed it up. But they still need to be read in and re-created in memory for each cpp file. Why not just compile all the cpp files in one process rather than spawning off a compiler process for every file? That can ensure reusing all the header files processed and are still in memory. My point is: run the profiler, see what are the bottlenecks, and pick those areas for optimization. Rather than speculating that L1/L2 cache misses are causing the major delay. If they ran the profiler and L1/L2 cache misses are really the problem, then I have nothing else to say.
- kerkeslager 16y ago> In contrast, in a GC system where you do _not_ have access to the explicit refcounting, you tend to always copy the node, just because you don't know if the original node might be shared through another tree or not. Even if sharing ends up not being the most common case. So you do a lot of extra work, and you end up with even more cache pressure. It's possible that things were different in 2002, but I don't really think this is the case now. In general, I make the node immutable and never copy it (copying an immutable object makes no sense). In a well-designed code base, mutations happen within the function where the data is created (read: on the stack, where cache locality is a given). Immutability also addresses Linus' concerns with thread-safety. And that's not accounting for concerns which Linus DOESN'T mention, such as increased development speed and correct program behavior. I'm not the only one saying this. Josh Bloch, for example, recommends immutability and cites cache reasons (http://www.ibm.com/developerworks/java/library/j-jtp02183/index.html http://www.ibm.com/developerworks/java/library/j-jtp02183/in...). And many languages (Haskell, Clojure) are designed heavily around avoiding mutation and sharing nodes within data structures. This talk of copying nodes to avoid your objects changing out from under you sounds a lot like what I call "writing C in Java". Linus is looking at this from the perspective of, "If they took away explicit memory management from C, this is how I would do it." But OF COURSE if you just bolt a feature like GC into a language that didn't have it before, it won't work well. Effective cache usage in a GCed system requires other language constructs (like immutability). Now, after all that, I won't make the claim that immutability in a GCed language like Java or C# is faster or even as fast as C with explicit memory management: it would take a lot of profiling code and comparing its functionality to make that claim with any kind of certainty. But it doesn't seem like Linus has done that profiling and comparison either.
- VladRussian 16y ago"All the papers I've seen on it are total jokes." Couldn't agree more. We were actually laughing in the office when an office mate brought up such a paper many years ago. "I really think it's the mindset that is the biggest problem." Linus is a superhero 20+ years working on the supertask of changing people's mindset.
- mv1 16y agoI find it sad that, to this day, one has to spend so much time worrying about memory management to get decent performance. I've yet to work on a performance oriented project where I didn't need to write at least a couple custom allocators to reduce memory management overhead. GC systems are no better in this regard. I was told of an interesting hack in a Java program that implemented a large cache of objects by serializing them into a large memory block so that the GC saw it as one big object and didn't traverse it. This resulting in dramatically reduced GC pause times (10x+). When needed, objects were deserialized from the array. Disgusting, but effective.