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

81–90 of 207 posts

Re: Linus Torvalds on Garbage Collection (2002)

#81

Post by gerner »

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.

Thank you for making this point. To my great dismay I see more and more people think that you need concurrent threads in one process in order to scale. It seems as if many programmers believe this as scripture and subsequently have difficulty thinking about distributed systems (not just multi-core, but multi-host).

Re: Linus Torvalds on Garbage Collection (2002)

#83

Post by SpikeGronim »

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.

The drawback with multiple processes is that they each have all the compiled bytecode on their heap. When I "import nltk" my heap goes from ~12 to ~36 MB. Add a few more dependencies and you end up wasting a non-trivial amount of RAM on python heaps.

Re: Linus Torvalds on Garbage Collection (2002)

#84

Post by rayiner »

vog wrote: post #54
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…

There is not a fundamental conflict between GC and cache generally. The conflict is with how caches are implemented in most CPUs.

Consider a simple generational collector with a nursery of N cache lines. The allocator will bump allocate into LINE_0, LINE_1... until LINE_N, and then copy all survivors into the mature generation. When it starts allocating again, it will start at LINE_0. Ie: it will touch at least N cache lines before ever coming back to any given cache line. If N > the size of the cache, each allocation will involve a cache miss. Each time the allocator allocates into a cache line, it will have been evicted already, and will need to be brought into the cache before it is written to.

The key observation here is that you're dealing with an artificial W-W dependency, not a real R-W dependency. When the allocator allocates into a cache line, it doesn't care what the data already in that cache line is! The cache line doesn't need to be brought in from memory because it is garbage and will be overwritten completely.

There are lots of solutions to the problem. At every allocation the allocator could simply issue a prefetch for the next line, because it knows it will need it soon. Or, you could have an instruction that simply blows away a cache line, marking it cached+dirty in the coherence protocol without generating a main memory access.

In fact, I'm not sure that modern CPUs don't detect this condition in their write buffers already. Something like Bulldozer's write coalescing cache could certainly do this.

Aside from this issue, generational GC's are very cache friendly. Collection inherently compacts memory, and the order of collecting tends to bring objects onto the same pages and sometimes the same cache lines as the objects that refer to them.

As an aside, the other big cache-thrashing process, marking, can also be made cache friendly on modern architectures. If your CPU has SMT, you can run the marker in a concurrent thread. It can sit there take advantage of the available memory parallelism that most programs leave on the table.

Re: Linus Torvalds on Garbage Collection (2002)

#85

Post by cageface »

barrkel wrote: post #46

Reference counting is GC; a poor form if it's the only thing you rely on, but it is automatic memory management all the same. Generational GC will frequently use the (L2/L3) cache size itself as its smallest generation, meaning it shouldn't suffer from the pathologies talked about by Linus here. What GC really gives you, though, is the freedom to write code in a functional and referentially transparent way. Writing f…

This is the essential point. GC may not be appropriate in all contexts, but, when it is, it tremendously improves the expressiveness of the language.

Re: Linus Torvalds on Garbage Collection (2002)

#87

Post by gruseom »

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.

Amen.

I saw an old interview with Chuck Moore a while ago in which he said: I like simplicity and efficiency. That struck me. How often do people put those two things together? We're conditioned to think of them as a tradeoff. But if you can have both, shouldn't we be trying hard for that? Which raises another question: what do you have to give up in exchange for both simplicity and efficiency?

Re: Linus Torvalds on Garbage Collection (2002)

#88

Post by koenigdavidmj »

stonemetal wrote: post #4
wladimir wrote: post #2

[2002] Though his argument about cache does still hold.

I could see it holding for say Java or C#, but for a single assignment languages like SML or Haskell I don't think it would hold. It seems like changing single assignment to mutation would be one of the first memory related optimizations you would make. While it is easiest to think of that as A1 = A0 + B is a mutation of A, there is nothing that says it should be so limited.

And sure enough, graph colouring register allocators work just as well for allocating chunks of memory as they do for allocating registers.

Re: Linus Torvalds on Garbage Collection (2002)

#89

Post by mfukar »

wbhart wrote: post #49
mfukar wrote: post #32

Hacker News, another place where 10-year-old emails are submitted as news .

Maybe the OP considered it news because it is tangentially related to this patent issue to do with automatically expiring data in hash tables.

I assumed that's what the comment section is for.

Re: Linus Torvalds on Garbage Collection (2002)

#90

Post by lobster_johnson »

bcl wrote: post #16
jasongullickson wrote: post #7

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

In ObjC the retain/release memory management system uses reference counters. When the count hits zero the object is deallocated so that does sound like what Linus is talking about. Objective C also has the 'new' garbage collection system and there is autorelease which uses a memory pool and releases at some later point.

Objective-C also has the autorelease pool, which allows for a bit more flexibility in that you don't need to pay as much attention to the refcount.

You can also optimize allocations using zones, which are like mini-heaps that collect a bunch of objects and allow you to release all of them with a single deallocation -- very handy if you have a ton of small objects (like a DAG) where you know for a fact that when the root is deallocated, all the nodes should be freed as well.

Post reply on HN