Linus Torvalds on Garbage Collection (2002)

http://gcc.gnu.org/ml/gcc/2002-08/msg00552.html

by AndrewDucker • 15 years ago

279 204 15 years ago

gcc.gnu.org

wladimir2• 15 years ago

[2002]

Though his argument about cache does still hold.

MatthewPhillips• 15 years ago

I 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• 15 years ago

For 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.

stonemetal3• 15 years ago

I 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• 15 years 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.

koenigdavidmj• 15 years ago

And sure enough, graph colouring register allocators work just as well for allocating chunks of memory as they do for allocating registers.

AndrewDucker• 15 years ago

I 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.

wladimir2• 15 years ago

Sure. 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.

rayiner11• 15 years ago

Are you sure?

jasongullickson• 15 years ago

What he's advocating sounds a lot like how things work in the iOS world, in my experience.

adolph• 15 years ago

A 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/...

pdhborges2• 15 years ago

The runtime system might not free the memory immediately.

bcl• 15 years ago

In ObjC the retain/release memory management system uses reference counters. When the count hits zero the object is deallocated so that does sound like what Linus is talking about.

Objective C also has the 'new' garbage collection system and there is autorelease which uses a memory pool and releases at some later point.

lobster_johnson3• 15 years ago

Objective-C also has the autorelease pool, which allows for a bit more flexibility in that you don't need to pay as much attention to the refcount.

You can also optimize allocations using zones, which are like mini-heaps that collect a bunch of objects and allow you to release all of them with a single deallocation -- very handy if you have a ton of small objects (like a DAG) where you know for a fact that when the root is deallocated, all the nodes should be freed as well.

BenoitEssiambre• 15 years ago

And thus the insanely smooth user experience on iOS. As an Android developer, this is _the one thing_ I feel makes it difficult to have a polished user experience on Android compared to iOS.

If you think long and hard about each place you call 'new' in java Android apps, it is possible to get a smooth interface. However, the language doesn't encourage it by default like on iOS and you have to put time into it you usually don't have.

For users, milliseconds of jitters and blockiness everywhere is a huge turn off. It feels like the device is struggling to handle simple tasks and it destroys the belief in the UI metaphor of physical objects that have inertia and flow, stretch and bounce when you touch and flick them.

IMO, because it makes such a huge difference to users, UI programming should always happen in a high performance language and environment. One way to attain this performance is to eschew garbage collection. This is also a problem in web browsers where the UI is often written in javascript.

At the very least those who make programing environments, languages or GCs used for building user interfaces should optimize how their environments promote good use of local hardware cache and acceleration. There is a reason why UI rendering often relies on video hardware that is not totally unlike a desktop high performance computer.

kenjackson• 15 years ago

And thus the insanely smooth user experience on iOS. As an Android developer, this is _the one thing_ I feel makes it difficult to have a polished user experience on Android compared to iOS.

Yet for WP7 its also silky smooth. The main issue on WP7 for user apps isn't GC at all, but rather the network (creating long lists of images that you're getting from a web service). Once people learned some techniques for dealing with that on the device the experience for 3rd party apps was just as silky as iOS apps -- yet a full generational GC.

The GC is an excuse (unless its not well written), not the reason.

cpeterso• 15 years ago

And that Android's GUI did not use GPU hardware acceleration until Honeycomb. The iOS GUI uses hardware acceleration extensively (which is admittedly probably easier when you control the iOS devices' hardware design).

https://code.google.com/p/android/issues/detail?id=6914

manveru• 15 years ago

Might 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

zerohp• 15 years ago

Perl 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• 15 years ago

And Python. AFAIK, there are no plans to fix it at this point. Also Python is notorious for allocating lots of small objects.

Vlasta• 15 years ago

I 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.

sausagefeet2• 15 years ago

Some people consider it free too which is very painful. Like pretending networks don't have latency.

marshray10• 15 years ago

It 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).

alextingle2• 15 years ago

This 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.

sklivvz19712• 15 years ago

It'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• 15 years ago

It's already been ten years since he wrote that.

gaius• 15 years ago

Yeah - mods can we edit a date into the title please?

parfe• 15 years ago

The email was written a decade ago.

shin_lao• 15 years ago

The 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.

sklivvz19712• 15 years ago

It's a strategy _I_don't_need_to_concern_with_ :-)

mmcconnell1618• 15 years ago

I'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• 15 years ago

You 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• 15 years ago

Didn't Linus forget

    newnode->count = 1;

ciupicri2• 15 years ago

Maybe it's done by the copy_alloc function.

jfr• 15 years 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.

stcredzero2• 15 years ago

I 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.

kragen11• 15 years ago

> 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

While I agree that generational GC can perform spectacularly well, what you're describing is close to the case it's optimized for, not close to its worst case. The worst case is that you allocate lots and lots of small objects and then write a pointer to all of them into a tenured garbage object.

> I half expect someone to tell me that this already exists for Python.

Yes, that's how Python works, except that I don't know what you mean by "something like LINT but for the runtime reference graph."

abstractfactory• 15 years ago

In 2004 Bacon et al. showed that tracing GC and ref-counting GC are special cases of a more general framework, and that it is possible to combine them to get the benefits of both. See "A Unified Theory of Garbage Collection" here:

http://www.research.ibm.com/people/d/dfb/publications.html

Scholar cluster:

http://scholar.google.com/scholar?q=bacon+unified+theory+gar...

Incidentally, it is not even remotely true that reference counting is more efficient than tracing GC in all cases.

lambda2• 15 years ago

> 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.

Or you could do what Rust <https://github.com/graydon/rust/wiki/Language-FAQ>; does, and have different types of objects; stateful and stateless. Stateless object cannot have cycles (since you can't construct them in stateless objects, unless you're in a lazy language), and so reference counting can be used for stateless objects. Stateful objects, which can have cycles, are managed by the garbage collector.

Rust sounds like a really interesting idea, and I'd love to give it a try, but sadly it's still in the "some assembly required" stage as they work on bootstrapping it so the only real projects that are worthwhile to do with it yet are helping out with the bootstrapping process.

jamii• 15 years ago

For higher-level systems programming (ie not bare metal) I think the approach taken by the Rust language is interesting. Mutable data structures are thread-local and are GCed (GC happens independently per thread). Immutable data structures can be passed between threads, are reference counted and support RAII.

https://github.com/graydon/rust/wiki/Language-FAQ

stonemetal3• 15 years ago

Nothing in the definition of Garbage Collection says it must be a separate post processing step. Therefore reference counting is in fact a garbage collection mechanism. Just because it is an eager algorithm rather than the usual lazy one doesn't change what it does, collect garbage in the system.

yid2• 15 years ago

Right, and garbage collection is just lazy memory manamgement--you go see it either way, so this whole point is rather pedantic.

marshray10• 15 years ago

Nothing in the definition of Garbage Collection says it must be a separate post processing step.

My impression (based on reading up on the state-of-the-art some years ago) was that an actual concurrent-with-normal-execution GC needed to resort to putting a write barrier in front of the useful thread of execution much of the time. This would cause a noticeable perf hit.

There were architectures designed with hardware support for this kind of thing, but chips without it left them in the dust. Whether or not that is an accident of history or for a reason is an interesting discussion.

revetkn• 15 years ago

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

If your use case is teaching how to implement a garbage collector vs. a refcounting system, it is certainly much simpler to implement refcounting. If you are a systems programmer/writing a VM or compiler and do your work at a bare-metal level, then manual memory management/refcounting is probably your best choice.

For everyone else (let's guess over 90% of the programming population), using high-level GC'd languages is significantly simpler and more productive.

barrkel3• 15 years ago

Implementing a stop-the-world, 2-space copying GC, provided you have complete stack, register and type layout data, is trivial. Implementing reference counting is much less so, especially in the presence of threads. Many simple scenarios turn into problems of lock-free programming proportions - and that's just for verifying that memory safety is present, not that the user hasn't introduced bugs with their own threading cock-ups.

(Delphi uses reference counting for interfaces, strings and dynamic arrays, and I am aware of race bugs in strings in particular (which are copy on write); these bugs are hard to fix without murdering performance, yet in practice they are very rare on x86 memory model hardware. So they stay.)

rayiner11• 15 years ago

> 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,

Reference counting isn't conceptually any more simple than garbage collection (you still have to indicate how the underlying alloc() and free() operations are implemented). Further, a proper high performance reference counting system isn't any simpler than a high performance GC. In a multithreaded system you have to keep the reference counts in sync without doing a slow atomic operation every time a pointer is passed around, and you need to back the ref counting system with a high performance malloc()/free() that can handle multithreaded allocation and is resistant to memory fragmentation.

gruseom2• 15 years ago

I like simplicity. Simplicity tends to perform well, and being simple also means it has little space for problems.

Amen.

I saw an old interview with Chuck Moore a while ago in which he said: I like simplicity and efficiency. That struck me. How often do people put those two things together? We're conditioned to think of them as a tradeoff. But if you can have both, shouldn't we be trying hard for that? Which raises another question: what do you have to give up in exchange for both simplicity and efficiency?

chc2• 15 years ago

It's because "simple" can be a measure of different things. C is a pretty simple and straightforward language, but it takes 10 times as much code to do anything, which could be said to be quite a bit more complex.

caf• 15 years ago

I tend to feel that the two often go together. After all, "the key to making a program fast is to make it do as little as possible".

kainosnoema• 15 years ago

In my experience, it takes an incredible amount of effort and experience to solve a complex problem with simplicity and efficiency. It's well worth it, but there's definitely a cost, and not everyone is capable of it.

seanx2• 15 years ago

> I like simplicity. Simplicity tends to perform well, and being simple also means it has little space for problems.

I like simplicity in my code, I am far less concerned about simplicity in the underlying libraries that I use.

GC makes my code simpler and more understandable. I use manual memory allocation when I absolutely need to, and GC languages when I can. In most cases, that means I use a GC language.

teh• 15 years ago

Slightly 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

neilc• 15 years ago

Arena or pool memory allocation is a very old idea, and has been implemented by many different systems (e.g., Apache/APR, PostgreSQL, lcc).

mfukar2• 15 years ago

Hacker News, another place where 10-year-old emails are submitted as news.

wbhart• 15 years ago

Maybe the OP considered it news because it is tangentially related to this patent issue to do with automatically expiring data in hash tables.

mfukar2• 15 years ago

I assumed that's what the comment section is for.

loup-vaillant• 15 years ago

So. 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• 15 years ago

Intel makes both processors and compilers.

marshray10• 15 years ago

Yes, 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• 15 years ago

The 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.

ciupicri2• 15 years ago

There were a couple of machines optimized for LISP some years ago, but guess what? They were beaten by ordinary machines.

jimwise• 15 years ago

Sure -- 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.

vog• 15 years ago

I think you're referring to the following paragraph:

One fundamental fact on modern hardware is that data cache locality is good, and not being in the cache sucks. This is not likely to change.

However, this did not happen to please the "two dominant C/C++ compilers". The reason is much more fundamental:

One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the _chance_ to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory.

But no matter how well you choose: software will only be able to exploit this if it is designed for locality.

If you can fix that (i. e. if you can find a cheap way to produce gigabytes of fast memory that makes chaches obsolete) the current compilers won't stop you from exploiting it: The code that is optimized for locality will still run as fast, and the code that can't be optimized for locality will run orders of magnitudes faster.

So we aren't in a local optimum at all. You can still optimize further "just" by producing faster and cheaper hardware.

kragen11• 15 years ago

One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the chance to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory.

Although all modern high-performance (edit: I mean non-embedded-microcontroller) computers work this way, it's not the only possible way. The Tera MTA takes a different, cacheless approach.

First, the problem with modern RAM in desktop machines is not that it sucks at bandwidth. You can get your bandwidth arbitrarily high by multibanking. Multibanking requires more buses or point-to-point links, but that's a tolerable cost.

The problem with modern RAM is that it sucks at latency, compared to what the CPU would like. Well, what do you do about latency? You make your requests earlier, and make sure you have other things to do in the meantime, when they get back. The Tera did this by having 128 sets of registers – 128 hardware threads — and switching to the next thread on every cycle. That means that, if all the thread slots were full, every thread only executed an instruction every 128 cycles, which is plenty of time to hide the latency of a slow memory fetch, as long as the memory bandwidth was adequate.

So basically every thread gets to pretend that it's running on a machine with zero-latency RAM — memory that's as fast as the registers. And pointer-chasing becomes as fast as looping over an array.

There are some other advantages to this design. Pipelining logic is very simple, because unless your pipeline gets insanely deep, you never have two instructions in the pipeline from the same thread, so you don't have register hazards.

(Cache is still beneficial in such a design, since it reduces the bandwidth that the links to main memory need to support. But the Tera didn't use it.)

I don't really understand why the Tera MTA failed in the market, and I suspect the problems were commercial rather than technical — customers had to take a big risk by porting their software to an unproven HPC platform, a platform whose performance characteristics were completely unlike anything else in the market (and unlike anything you can buy today). So customer uptake was insufficient to provide the cash flow needed to keep updating the design to keep up with Intel and AMD.

The technical reason such a design might fail would be if the silicon resources needed to support an entirely independent core were comparable to the silicon resources needed to support a hardware thread. Consider the GreenArrays GA144 chip: 144 independent cores, each with a tiny amount of independent RAM, on the same chip. Such a chip will be at least as fast as a chip with 144 independent register sets, but a single execution pipeline — in the worst case, it's bottlenecked on getting data out of RAM, and only one of its cores is usable, making it just as fast, while in the best case, it runs 144 times as fast. So a chip with 144 register sets needs to be cheaper — i.e. smaller — than the GA144. (Well, or easier to program, but presumably you can use more mainstream multicore chips to prove the example instead.)

rayiner11• 15 years ago

There is not a fundamental conflict between GC and cache generally. The conflict is with how caches are implemented in most CPUs.

Consider a simple generational collector with a nursery of N cache lines. The allocator will bump allocate into LINE_0, LINE_1... until LINE_N, and then copy all survivors into the mature generation. When it starts allocating again, it will start at LINE_0. Ie: it will touch at least N cache lines before ever coming back to any given cache line. If N > the size of the cache, each allocation will involve a cache miss. Each time the allocator allocates into a cache line, it will have been evicted already, and will need to be brought into the cache before it is written to.

The key observation here is that you're dealing with an artificial W-W dependency, not a real R-W dependency. When the allocator allocates into a cache line, it doesn't care what the data already in that cache line is! The cache line doesn't need to be brought in from memory because it is garbage and will be overwritten completely.

There are lots of solutions to the problem. At every allocation the allocator could simply issue a prefetch for the next line, because it knows it will need it soon. Or, you could have an instruction that simply blows away a cache line, marking it cached+dirty in the coherence protocol without generating a main memory access.

In fact, I'm not sure that modern CPUs don't detect this condition in their write buffers already. Something like Bulldozer's write coalescing cache could certainly do this.

Aside from this issue, generational GC's are very cache friendly. Collection inherently compacts memory, and the order of collecting tends to bring objects onto the same pages and sometimes the same cache lines as the objects that refer to them.

As an aside, the other big cache-thrashing process, marking, can also be made cache friendly on modern architectures. If your CPU has SMT, you can run the marker in a concurrent thread. It can sit there take advantage of the available memory parallelism that most programs leave on the table.

Ygor• 15 years ago

Not really directly connected, but in embedded systems you can actually see a lot of hardware software codesign approaches.

There is an approach called NISC [1] (No Instruction Set Computer), where the instruction set is completely removed and the compiler generates control words directly for the architecture (which can also be designed from scratch and optimized).

[1] http://en.wikipedia.org/wiki/NISC

Jach• 15 years ago

You might enjoy reading this: http://www.thocp.net/biographies/papers/backus_turingaward_l... (I've been casually trying to implement an FFP Machine on an FPGA.)

LarrySDonald• 15 years ago

So.. 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.

ekidd3• 15 years ago

Shortly 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• 15 years ago

Linus 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).

cdavid4• 15 years ago

And 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).

ilcavero• 15 years ago

~$5k for 7 KLOC of bug free C code is a steal, that's impossible to do in less than a couple of months

kragen11• 15 years ago

It's nearly impossible to do in any timeframe. I can think of perhaps two examples in human history where I think it's been done: qmail and seL4. And there may still be bugs in qmail. There may be a few other non-public projects that have achieved less than one bug per 7000 lines of C, but probably not more than one or two.

abcd_f2• 15 years ago

Beg to differ on both points.

Ignoring the 7 KLOC metric (which is fairly useless in estimating the project value for the customer), $5K at $100/h rate of a senior C programmer on a contract works out to about 6 working days, which is a reasonable timeframe for writing well optimized XML-RPC protocol parser. In other words it's neither a steal nor does it take two months to write.

(edit) YMMV by a programmer, but that's what it would've taken me to write it (though I have written a good deal of protocol parsers).

HockeyBiasDotCo• 15 years ago

Agreed.

DanielRibeiro2• 15 years ago

I Guess Linus also made another suggestion which he didn't pursue on this paragraph:

Generational garabage collectors tend to never re-use hot objects, and often do the copying between generations making things even worse on the cache

The suggestion? Just reuse hot objects.

Note, this post is from 2002. Garbage collectors have improved a lot over the last 9 years. Don't evaluate new technology with such old arguments.

jeffdavis• 15 years ago

Linus was quite specific about his problems with GCs. Just saying that "garbage collectors have improved" without specifics, and calling his arguments "old" doesn't add much information.

Can you tell us how they have improved in ways that address Linus's specific concerns? And explain how a generational garbage collector can effectively re-use freshly freed objects before they leave the cache? Which 2011 generational GCs take advantage of that idea?

yid2• 15 years ago

Please don't take this personally, but the fact that your code was N thousand lines doesn't mean the task is inherently an N-thousand line task.

Also, undertaking anything with XML in C is brave, kudos.

ekidd3• 15 years ago

If you know of any way to make the code shorter and more concise, please let me know. I'm always looking for ways to improve.

https://gist.github.com/937200 (two sample files, totaling slightly less than half the project)

Posting 10-year-old code to HN is always a little embarrassing, but please feel free to be brutal. I'll live. :-) I was definitely way too in love with the preprocessor back then.

Here's the corresponding Python code, from shortly after it hit 1,000 lines in late 2001:

http://hg.python.org/cpython-fullhistory/file/7b2d701ec404/L...

I like the Python code rather better, if only because there's so much less explicit memory management. The actual ideas stand out clearly, and there's just so much less code to read. In most cases, I'd happily sacrifice the performance.

ondrasej• 15 years ago

Actually, geting reference counting right and mostly bug-free is much easier, if you use C++ and do the counting via objects on stack (RAII).

VeXocide• 15 years ago

Absolutely not, http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1450.ht... explains why in section D. Implementation difficulty

joe_the_user2• 15 years ago

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.

Then your (client's) problem wasn't reference counting but premature optimization.

Are there situations where you'd like to have code run fifty times faster than native Python. You bet there are, lots and lots of them - for example, in a Unix-clone Kernel. Sorry if somehow you didn't find one of them.

Hopefully you used Valgrind and Formal language specification to reduce the work required.

And to avoid premature optimization, use gprof to find the bottleneck(s) rather than just diving into what seems to need optimization.

HenryR• 15 years ago

You're mixing up 'premature optimisation' and 'unnecessary optimisation'. The first is making code faster that isn't the bottleneck, or dominating performance factor. The second is making something faster than it needs to be. Profiling helps avoid the first, benchmarking helps avoid the second. Both require working (toy) systems, which is hard when you are evaluating which language to begin work in.

Writing a library in C (for reasons of performance) where performance would have been 'good enough' in Python is unnecessary optimisation. Writing your own GC implementation layer in Python because you think that's the bottleneck would be premature optimisation.

EDIT: typo

hristov• 15 years ago

You are probably right, but your experience does not disprove the central point that GC always slows things down. Now this slow down may be worth it in most situations, in fact it may be worth it in 99% of situations, but it is a fact.

In some cases that 50 times increase in speed may be important. In some cases, if something is 50 times slower it would be simply unusable. Linus happens to be working on one of those special cases, so he is quite correct in pointing out that garbage collection will always slow things down.

InclinedPlane• 15 years ago

Context is always important. And there's no such thing as blanket advice that applies to every circumstance. Software development is a hugely varied endeavor, ranging over more orders of magnitude and more variety of application than almost any other industry. It stands to reason that most practices will vary rather considerably depending on context.

Linus writes from a systems perspective. He cares about every nanosecond and every byte. And that's appropriate and even laudable in the context of the linux kernel and core applications. But it's not always appropriate for every situation.

known• 15 years ago

I've used your brilliant XML-RPC in one of my consulting assignments. Thanks.

joshhart2• 15 years ago

Here 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.

jedbrown5• 15 years ago

Show 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.

joshhart2• 15 years ago

Let'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.

marshray10• 15 years ago

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.

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.

dons2• 15 years ago

> 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.

Or teach the compiler about the algebra of arrays and matrices, so it can do the things to the code, that we'd write by hand.

E.g.

* http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp...

* http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.p...

* http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf

* http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf

In all these cases arrays codes are written in a function style, accompanied with special purpose optimizations and/or code generators (in the case of GPU code), layered over an imperative arrays primitive layer, using a memory effects monad.

rayiner11• 15 years ago

You just described an ideal use-case for GC. You allocate a bunch of arrays at the outset, then sit there pounding on them with little to no allocation. A good GC won't cost you anything in this case, since it'll allocate large pointer-free arrays in a separate pool that doesn't get traced.

Haskell isn't a good example, since it's a lazy functional language, but if something like Java isn't just as fast for your case it isn't the GC, it's the code generation. Much harder to do all those fancy loop optimizations in 100 ms in a JIT than in 10s in an offline compiler.

scott_meyer2• 15 years ago

Read your own words "immutability allows for concurrent access" Most GCs mutate (mark bits, semi-space copy, etc.) The immutability of Haskell data structures is an illusion, and from the standpoint of real concurrent access, an expensive one.

ww5206• 15 years ago

For mutating GCs, they stop the world when making changes so there's no erosion of the immutability contract in concurrent access. There are parallel GC systems that works quite well with multiple-core systems.

barrkel3• 15 years ago

Reference 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• 15 years ago

This 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• 15 years ago

GC 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.

Peaker2• 15 years ago

Did you compare the performance of Python with that of other languages that do use GC (e.g: Haskell)?

albertzeyer• 15 years ago

When 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.

alextingle2• 15 years ago

Or as we like to call it, std::shared_ptr

famousactress3• 15 years ago

We 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• 15 years ago

  Date: Fri, 9 Aug 2002 20:28:16 -0700

famousactress3• 15 years ago

Sorry 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.

lambda2• 15 years ago

Is it just me, or does the title say (2002) to give you context?

famousactress3• 15 years ago

That was added later (presumably in response to this comment).

earino• 15 years ago

Guy who writes kernel code cares about performance, film at 11.

iskander• 15 years ago

I'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.

astrange4• 15 years ago

I 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• 15 years ago

That was 2002. Here is the state of the art in 2008: 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• 15 years ago

I think this is another case of everybody thinks about garbage collection the wrong way: 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__• 15 years ago

I 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.

ww5206• 15 years ago

This 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.

astrange4• 15 years ago

I really like it when people reply "usually this doesn't matter" to a discussion in a project where it _does_ matter.

ww5206• 15 years ago

I 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.

kerkeslager• 15 years 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/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• 15 years 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• 15 years ago

I 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.

Linus Torvalds on Garbage Collection (2002)

Related Stories