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

201–207 of 207 posts

Re: Linus Torvalds on Garbage Collection (2002)

#201

Post by kragen »

fanf2 wrote: post #199
kragen wrote: post #62

Earlier quoted context omitted.

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.

http://www.dt.e-technik.uni-dortmund.de/~ma/qmail-bugs There are also some DNS-related bugs that are not on this list.

Thanks! I hadn't seen those, although I knew of 1.4. I think 1.1, 1.3, and 1.4 are actual bugs, if the reports are accurate; I'm pretty sure Dan disagreed with Wietse about 1.1. Three bugs in about 15000 lines of code doesn't quite rise to the level of less than one bug per 7000 lines of code, so maybe that's only been done once, in seL4.

What are the DNS-related bugs?

Re: Linus Torvalds on Garbage Collection (2002)

#202

Post by rayiner »

ori_b wrote: post #196
rayiner wrote: post #162

Earlier quoted context omitted.

This sort of analysis does not come easily. Say you have: def bar(): return some_constructor() def foo(): b = bar() Here the decrement is in bar() and the increment is in foo(). You have no way to elide the operation without doing inter-procedural analysis, which is hard.

You don't need to catch all the cases to see a big improvement. Just the most common ones.

The problem is in a language like Python, where everything is broken up into little functions, you're not going to catch the most common uses without doing inter-procedural analysis.

Re: Linus Torvalds on Garbage Collection (2002)

#203

Post by marshray »

rayiner wrote: post #167
marshray wrote: post #125

Earlier quoted context omitted.

It's an interesting problem that will probably never be solved, only optimized and amortized. That makes it good for papers! The most efficient scheme probably is a "stop the world" system. The regular program might mutate concurrently and the GC could indeed be concurrent, but making them run at the same time is a real challenge. Of course, people don't like it when their app pauses. I think it's noteworthy that the…

Re: office suites, the code bases of the major office suites pre-date the rise of Java, which brought GC into the mainstream. Lot's of apps bigger and more complex than an office suite have been written in Java. As for web browsers... every web browser has a GC...

office suites, the code bases of the major office suites pre-date the rise of Java, which brought GC into the mainstream.

Yes, but Java and GC proponents talked up the possibility at the time. There were various projects to do pure-java office suites and web browsers. The time or two I tried them they were memory pigs and slow.

Lot's of apps bigger and more complex than an office suite have been written in Java.

Many that take take heavy user interactivity? Eclipse perhaps, but IBM had to come up with a custom native-code UI toolkit to implement it. I still considered it too slow to use until the last year or so.

As for web browsers... every web browser has a GC...

Last I looked (a long time ago) my impression was that DOM and Javascript interpreter objects were usually refcounted internally. Did this changed?

Re: Linus Torvalds on Garbage Collection (2002)

#204

Post by marshray »

rayiner wrote: post #163
marshray wrote: post #118

Earlier quoted context omitted.

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

Of course you're leaving out the malloc()/free() implementation that the ref-counting scheme depends on that the GC doesn't.

Perhaps I was thinking that that's usually provided by the operating system "for free". Hard to imagine an actual nontrivial GC system not needing basic malloc/free at some point anyway. Come to think of it, I think I actually tried implementing something like that once.

Alternatively, you could implement a simple first-fit free-block-list scheme in a small amount of code. It might not look terribly different from something a GC might do anyway.

Still, I think it's a fair point.

Re: Linus Torvalds on Garbage Collection (2002)

#205

Post by marshray »

barrkel wrote: post #138
marshray wrote: post #118

Earlier quoted context omitted.

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

Unless you modified an existing or wrote a new C++ compiler, no, you haven't really (don't forget what you're piggy-backing on when the compiler is invoking ctors and dtors for you too). Boost shared pointers are toys; they don't deal with copy-on-write semantics. C++ exception safety is also hilariously difficult to get right (this adds to the refcounting problem); the language is broken by design.

Unless you modified an existing or wrote a new C++ compiler, no, you haven't really

Not sure which thing you're saying "I haven't really". But yeah, at times I have experimented with code that replaced built-in C++-runtime-library functionality.

(don't forget what you're piggy-backing on when the compiler is invoking ctors and dtors for you too).

Ctor/dtors by themselves don't, by themselves, generally allocate heap objects.

Boost shared pointers are toys; they don't deal with copy-on-write semantics.

I don't think that CoW is an essential feature of every allocation tracking scheme. Still, if you declare shared_ptr you can copy when you need to.

The std::unique_ptr and "move" semantics in C++11 are filling in some of those gaps in the core language.

C++ exception safety is also hilariously difficult to get right (this adds to the refcounting problem)

Be honest - it is exceptional conditions in all forms of programming are "hilariously difficult". C programs typically handle it sporadically or dedicate 50% of the code bulk (evenly throughout the program) to handling such conditions. C++ exceptions are tools to help you to put all that danger into a single facility which you can then point to and be horrified by. This is a great improvement.

the language is broken by design.

As someone else once replied to me, Yeah, if your definition of broken is awesome. :-)

It just depends on what you want out of your language. I like other languages too.

Re: Linus Torvalds on Garbage Collection (2002)

#206

Post by marshray »

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.

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.

Re: Linus Torvalds on Garbage Collection (2002)

#207

Post by known »

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've used your brilliant XML-RPC in one of my consulting assignments. Thanks.
Post reply on HN