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

121–130 of 207 posts

Re: Linus Torvalds on Garbage Collection (2002)

#121

Post by marshray »

Vlasta wrote: post #9

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.

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

Re: Linus Torvalds on Garbage Collection (2002)

#122

Post by lukesandberg »

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.

is the ref counting slow because it has to be a protected operation? or is it just the amount of them. if it is due to being protected by locks there are lock free ref counting systems (as described in here: http://www.google.com/url?sa=t&source=web&cd=1&v...) that essentially allow batch refcounting opterations to accumulate in a per thread counter that are only reconciled occasionally. assuming you design your data structures correctly (no false sharing) you can get very high write performance because all your counters are cached and there is no cache invalidation due to competing writes on other processors. of course it takes more memory so it is only suitable for highly shared objects, but it can make a significant difference in a reference counting system. (the article points to scalability issues in the linux ref counting system and how to resolve them)

Re: Linus Torvalds on Garbage Collection (2002)

#123

Post by marshray »

tlholaday wrote: post #41
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?

Intel makes both processors and compilers.

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)

Re: Linus Torvalds on Garbage Collection (2002)

#124

Post by marshray »

jedbrown wrote: post #59
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. Unlik…

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.

Re: Linus Torvalds on Garbage Collection (2002)

#125

Post by marshray »

scott_meyer wrote: post #119
ww520 wrote: post #116

Earlier quoted context omitted.

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

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 there never was a big office suite or even a web browser written primarily in a GC system, despite many years of promises.

Re: Linus Torvalds on Garbage Collection (2002)

#126

Post by seanx »

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

Re: Linus Torvalds on Garbage Collection (2002)

#127

Post by seanx »

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…

And if delphi had complete GC, i would probably still be using it for new projects.

Re: Linus Torvalds on Garbage Collection (2002)

#128

Post by kragen »

lukesandberg wrote: post #122
kragen wrote: post #63

Earlier quoted context omitted.

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.

is the ref counting slow because it has to be a protected operation? or is it just the amount of them. if it is due to being protected by locks there are lock free ref counting systems (as described in here: http://www.google.com/url?sa=t&source=web&cd=1&v... ) that essentially allow batch refcounting opterations to accumulate in a per thread counter that are only reconciled occasionally. assuming you design your dat…

That's awesome! I knew there were faster approaches to ref-counting, but I didn't know about that one, "sloppy counters".

The most common approach to speeding up ref-counting is to ref-count bigger objects — modules rather than individual variables, say.

The simplest way to speed up ref-counting transparently is to statically analyze the code and remove redundant increment and decrement operations. This can be tricky in practice, and I haven't heard of anyone actually doing it.

Re: Linus Torvalds on Garbage Collection (2002)

#129

Post by kragen »

chc wrote: post #102
kragen wrote: post #63

Earlier quoted context omitted.

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.

This is a bit like saying, "Of course C has full type safety. Just use a Haskell implementation written in C." Both your statement and his are technically accurate, but yours is on a subtly different topic.

How is it a bit like that? He complained that Python didn't scale to lots of cores because of the GIL; I said his Python didn't scale because of threading, which interacts badly with the GIL. If you use a shared-nothing approach to parallelizing your Python code, you don't run into that problem. It's not as if shared-state threading happens magically — you have to rewrite your code to use it, too.

Re: Linus Torvalds on Garbage Collection (2002)

#130

Post by DanielRibeiro »

jeffdavis wrote: post #97
DanielRibeiro wrote: post #57

Earlier quoted context omitted.

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…

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…

Yes I can:

- [1, 2] The pauseless collector also has the highly desirable side-benefit of producing improved memory locality. This happens because the algorithm works by attempting to relocate groups of tightly-coupled objects into regions of adjacent memory, providing excellent paging and cache locality properties for those objects. This can also benefit highly multithreaded applications that operate on distinct sets of object data.

If you read the whitepaper on Azul[3] you will get a glimpse of how things got a lot more involved. And all of this gets a lot more complicated when programmming for multiple cores[4].

But not everybody is using the Erlang VM or Sun's JVM (HotSpot). The point is generic: don't assume things are on your platform by watching other platforms. Don't use old data to guide your search, no matter how brilliant/famous the author is.

[1]http://java.sun.com/products/hotspot/docs/whitepaper/Java_Ho...

[2]http://java.sun.com/docs/books/performance/1st_edition/html/...

[3]http://www.infoq.com/articles/azul_gc_in_detail

[4]http://www.javacodegeeks.com/2011/04/erlang-vs-java-memory-a...

Post reply on HN