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

61–70 of 207 posts

Re: Linus Torvalds on Garbage Collection (2002)

#61

Post by yid »

stonemetal wrote: post #38
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…

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.

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

Re: Linus Torvalds on Garbage Collection (2002)

#62

Post by kragen »

ilcavero wrote: post #47
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?…

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

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.

Re: Linus Torvalds on Garbage Collection (2002)

#63

Post by kragen »

cdavid wrote: post #56
ekiru wrote: post #42

Earlier quoted context omitted.

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

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.

Re: Linus Torvalds on Garbage Collection (2002)

#64

Post by pnathan »

IgorPartola wrote: post #23
zerohp wrote: post #10

Earlier quoted context omitted.

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.

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

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

Re: Linus Torvalds on Garbage Collection (2002)

#65

Post by albertzeyer »

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.

Re: Linus Torvalds on Garbage Collection (2002)

#66

Post by kragen »

stcredzero wrote: post #33
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…

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…

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

Re: Linus Torvalds on Garbage Collection (2002)

#67

Post by famousactress »

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.

Re: Linus Torvalds on Garbage Collection (2002)

#68

Post by abstractfactory »

stcredzero wrote: post #33
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…

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…

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.

Re: Linus Torvalds on Garbage Collection (2002)

#69

Post by abcd_f »

ilcavero wrote: post #47
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?…

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

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

Re: Linus Torvalds on Garbage Collection (2002)

#70

Post by kenjackson »

BenoitEssiambre wrote: post #29
jasongullickson wrote: post #7

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

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

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.

Post reply on HN