Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linus Torvalds on Garbage Collection (2002)

gcc.gnu.org

Post reply on HN
Print view View original

111–120 of 207 posts

Re: Linus Torvalds on Garbage Collection (2002)

#111

Post by ori_b »

kragen wrote: post #63
cdavid wrote: post #56

Earlier quoted context omitted.

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

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

Python doesn't do code analysis to determine when it's effectively doing obj.refs++; obj.refs-- repeatedly.

This sort of analysis is useful, and if the interpreter had been designed to do any optimization along with jitting, would probably come nearly for free. Reference counting could be far far cheaper than it is in python. (How much cheaper? I don't know - it'd need work to figure it out)

Re: Linus Torvalds on Garbage Collection (2002)

#112

Post by pjkundert »

VeXocide wrote: post #74
ondrasej wrote: post #71

Earlier quoted context omitted.

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

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

Actually, yes. The boost::smart_ptr is highly effective. Prior to that existing, I wrote a similar ref-counting library that has been deployed to hundreds of remote sites, running high-reliability industrial control code.

While complex, the ref-counting implementation gave me something that a GC system just can't deliver:

Determinism.

This system is running on a 300MHz embedded x86 hosts, in a solid-state industrial computer, and has to provide sub-millisecond timing with only occasional hiccups >1ms acceptable. I am unaware of a GC system that could deliver this.

These boxes run for years, with no memory leaks. The cost was, of course, ensuring that no "loops" of objects get created. This was a small price to pay for the benefits. Having written large systems using both GC and ref-counting, I still lean toward ref-counting, even if determinism isn't a strong requirement.

Of course, I'm one of those guys who loves C++, so take my opinions with a grain of salt...

Re: Linus Torvalds on Garbage Collection (2002)

#113

Post by scott_meyer »

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.

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.

Re: Linus Torvalds on Garbage Collection (2002)

#114

Post by ww520 »

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.

Re: Linus Torvalds on Garbage Collection (2002)

#115

Post by pohl »

microtherion wrote: post #96
pohl wrote: post #48

Earlier quoted context omitted.

Thank you, that makes sense. So, if I understand this correctly: if one wanted to take advantage of an opportunity to do some cache-friendly reallocation, then avoiding autorelease pools would be necessary.

That's rarely a realistic option if you use any Cocoa library code. autorelease is a pretty fundamental aspect of the Cocoa design.

Wouldn't it be more accurate to say that it's not a realistic option for objects that come from or depend on Cocoa library code?

Or would the mere act of using cocoa in one part of my application somehow prevent me from exploiting such an opportunity in another part of my application?

My instinct says that, for example, a plain C library that used such techniques would not cease to function just by being linked into a cocoa application.

Re: Linus Torvalds on Garbage Collection (2002)

#116

Post by ww520 »

scott_meyer wrote: post #113
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.

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.

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.

Re: Linus Torvalds on Garbage Collection (2002)

#117

Post by marshray »

pjkundert wrote: post #112
VeXocide wrote: post #74

Earlier quoted context omitted.

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

Actually, yes. The boost::smart_ptr is highly effective. Prior to that existing, I wrote a similar ref-counting library that has been deployed to hundreds of remote sites, running high-reliability industrial control code. While complex, the ref-counting implementation gave me something that a GC system just can't deliver: Determinism. This system is running on a 300MHz embedded x86 hosts, in a solid-state industrial…

I, too, love C++ and the boost smart pointer library.

In fact, it's been adopted into modern versions of the C++ standard itself. std::tr1::shared_ptr and std::shared_ptr.

Re: Linus Torvalds on Garbage Collection (2002)

#118

Post by marshray »

barrkel wrote: post #51
revetkn wrote: post #44

Earlier quoted context omitted.

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

I've implemented both in C++.

See http://svn.boost.org/svn/boost/trunk/boost/smart_ptr/shared_... as an example of reference counting. Add in some atomic increment/decrement primitives and that's literally all there is to implement in one header file.

But even the lightest weight GC collector I could make had a significant C++ implementation file with lots of nontrivial pointer operations and loops in it. Even without scanning the stack for root objects, passing them in manually, I still think there's some amount of non-portable code in there.

That said, I'm using my GC for new stuff when the objects aren't too temporary. We'll see how it works out.

Re: Linus Torvalds on Garbage Collection (2002)

#119

Post by scott_meyer »

ww520 wrote: post #116
scott_meyer wrote: post #113

Earlier quoted context omitted.

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.

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.

You write "stop the world" and "concurrent access" in the same sentence. What is up with that? When we manage to go for 10 years without getting 5 or 6 papers claiming to "solve the concurrent/pauseless GC problem" then, perhaps, it might be reasonable to present the problem as "solved."

Re: Linus Torvalds on Garbage Collection (2002)

#120

Post by kerkeslager »

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

Post reply on HN