Linus Torvalds on Garbage Collection (2002) • Hacker News Board

Re: Linus Torvalds on Garbage Collection (2002)

#51

Post by barrkel » Fri, Apr 22, 2011, 3:32 PM UTC

revetkn wrote: post #44

jfr wrote: post #25

> 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 som…

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/refc…

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

Re: Linus Torvalds on Garbage Collection (2002)

#52

Post by ciupicri » Fri, Apr 22, 2011, 3:33 PM UTC

loup-vaillant wrote: post #35

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?

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

Re: Linus Torvalds on Garbage Collection (2002)

#53

Post by HockeyBiasDotCo » Fri, Apr 22, 2011, 3:34 PM UTC

ekidd wrote: post #37

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?…

Agreed.

Re: Linus Torvalds on Garbage Collection (2002)

#54

Post by vog » Fri, Apr 22, 2011, 3:35 PM UTC

loup-vaillant wrote: post #35

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?

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.

Re: Linus Torvalds on Garbage Collection (2002)

#55

Post by Ygor » Fri, Apr 22, 2011, 3:37 PM UTC

loup-vaillant wrote: post #35

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?

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

Re: Linus Torvalds on Garbage Collection (2002)

#56

Post by cdavid » Fri, Apr 22, 2011, 3:37 PM UTC

ekiru wrote: post #42

ekidd wrote: post #37

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?…

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

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

Re: Linus Torvalds on Garbage Collection (2002)

#57

Post by DanielRibeiro » Fri, Apr 22, 2011, 3:38 PM UTC

ekidd wrote: post #37

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?…

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.

Re: Linus Torvalds on Garbage Collection (2002)

#58

Post by yid » Fri, Apr 22, 2011, 3:41 PM UTC

ekidd wrote: post #37

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?…

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.

Re: Linus Torvalds on Garbage Collection (2002)

#59

Post by jedbrown » Fri, Apr 22, 2011, 3:41 PM UTC

joshhart wrote: post #39

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.

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.

Re: Linus Torvalds on Garbage Collection (2002)

#60

Post by sklivvz1971 » Fri, Apr 22, 2011, 3:42 PM UTC

shin_lao wrote: post #21

sklivvz1971 wrote: post #13

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.

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.

It's a strategy _I_don't_need_to_concern_with_ :-)