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

141–150 of 207 posts

Re: Linus Torvalds on Garbage Collection (2002)

#141

Post by dons »

jedbrown wrote: post #137
dons wrote: post #132

Earlier quoted context omitted.

> It would be interesting to see any Haskell implementations that are competitive. 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. Or teach the compiler about the algebra of arrays and matrices, so it can do the things to the code, that we'd write by hand. E.g. * http://www.cse.unsw.edu.au/~benl/paper…

This is a worthwhile research topic, but it doesn't really answer my question. From the first paper you cite: The single threaded Handwritten C version is about 45% faster than our best Haskell result, which is achieved with 3 threads. Meanwhile, there is no performance model so we don't know how good the C version is. The paper doesn't even report a simple fraction of FPU or bandwidth peak. It is not using SSE instr…

Oh, I'm certainly not arguing that you're going to beat hand tuned straightline code. I'm just pointing out that dropping into assembly isn't the only possibly path.

Re: Linus Torvalds on Garbage Collection (2002)

#142

Post by sb »

kragen wrote: post #128
lukesandberg wrote: post #122

Earlier quoted context omitted.

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…

Just for the record: Pramod Joisha did static analysis of redundant reference counting operations in 2006 in the Bartok C# research compiler (http://www.hpl.hp.com/personal/Pramod_Joisha/Publications/is...). IIRC, doing it improves performance significantly.

Re: Linus Torvalds on Garbage Collection (2002)

#143

Post by astrange »

iskander wrote: post #98

I'm very suspicious of anyone (even Linus) claiming that gcc is slow because of its memory management. The codebase is crufty and convoluted--- it's probably slow for a thousand different reasons. If you refactored into a clean design and rewrote the beast in OCaml (or any other language with a snappy generational collector), you'd probably get a large performance boost.

I think your argument consists of "gcc is slow because I don't understand the code layout".

One of the problems affecting the C frontend and backend is poor cache locality due to pointer chasing in their data structures, and they currently do switch between GC memory and manually allocated zones (obstacks) to improve this.

Re: Linus Torvalds on Garbage Collection (2002)

#144

Post by astrange »

ww520 wrote: post #114

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…

I really like it when people reply "usually this doesn't matter" to a discussion in a project where it _does_ matter.

Re: Linus Torvalds on Garbage Collection (2002)

#145

Post by joe_the_user »

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

Was my library about 50 times faster? Sure, I could parse 1,500+ XML-RPC requests/second. Did anybody actually benfit from this speed? Probably not.

Then your (client's) problem wasn't reference counting but premature optimization.

Are there situations where you'd like to have code run fifty times faster than native Python. You bet there are, lots and lots of them - for example, in a Unix-clone Kernel. Sorry if somehow you didn't find one of them.

Hopefully you used Valgrind and Formal language specification to reduce the work required.

And to avoid premature optimization, use gprof to find the bottleneck(s) rather than just diving into what seems to need optimization.

Re: Linus Torvalds on Garbage Collection (2002)

#146

Post by sb »

ori_b wrote: post #111
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.

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)

Recently, there has been some work on removing redundant reference count operations in the Python interpreter. The following paper describes how it can be done: http://portal.acm.org/citation.cfm?id=1869631.1869633.

Regarding the performance impact of reference counting, the following facts are important:

- Switching from immediate reference counting to deferred reference counting (L.P. Deutsch and D.G. Bobrow, 1976 [1]) eliminates about 90pct of all reference count operations in Smalltalk (Berkeley Smalltalk '82, that is) [2]

- A very good account of reference counting can be found in either Dave Ungar's excellent PhD thesis [3] and Dave Ungar and Dave Patterson's in-depth analysis of Smalltalk performance [4].

[1] An efficient, incremental, automatic garbage collector (http://www.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/p...)

[2] High performance storage reclamation in an object-based memory system (http://techreports.lib.berkeley.edu/accessPages/CSD-84-167.h...)

[3] The Design and Evaluation of A High Performance Smalltalk System (http://www.eecs.berkeley.edu/Pubs/TechRpts/1986/5376.html)

[4] Berkeley Smalltalk: Who knows where the time goes? (Chapter 11 of http://www.iam.unibe.ch/~ducasse/FreeBooks/BitsOfHistory/)

Re: Linus Torvalds on Garbage Collection (2002)

#147

Post by cdavid »

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.

You are playing with words here: of course you can run multiple python instances to scale your application on multiple-cores, that's a trivial statement. But I was talking about python the interpreter (more exactly cpython). There are legitimate cases where multi-threading is the natural, elegant solution, and cpython, mostly because of reference counting, prevents that.

Re: Linus Torvalds on Garbage Collection (2002)

#148

Post by jedbrown »

dons wrote: post #141
jedbrown wrote: post #137

Earlier quoted context omitted.

This is a worthwhile research topic, but it doesn't really answer my question. From the first paper you cite: The single threaded Handwritten C version is about 45% faster than our best Haskell result, which is achieved with 3 threads. Meanwhile, there is no performance model so we don't know how good the C version is. The paper doesn't even report a simple fraction of FPU or bandwidth peak. It is not using SSE instr…

Oh, I'm certainly not arguing that you're going to beat hand tuned straightline code. I'm just pointing out that dropping into assembly isn't the only possibly path.

If you're not within 10% for these kernels, chances are that memory is being used differently. This gets to a further matter which I think is perhaps the greatest failure of current multi/many-core programming paradigms: assuming a flat memory model. Efficient parallel computation has much less to do with computation than with data movement. Recent and future architectures have deeply hierarchical memory systems so any paradigm that does not expose the location of physical pages (within some appropriate abstraction) will have a hard time delivering consistent, understandable performance. Performance should not vary an order of magnitude based on whether memory was faulted (allocation is irrelevant) using a batch of threads with different affinity than those that access it later. But this is the current state of affairs.

I would very much like to see a paradigm where a memory distribution (roughly a high-level representation of the mapping to physical memory) was a first-class concept. Suppose that new memory could be allocated or remapped to have certain compatibility relative to the mapping of another block. Then you could associate tasks with certain coupling between two distributions.

Re: Linus Torvalds on Garbage Collection (2002)

#149

Post by kragen »

stcredzero wrote: post #140
kragen wrote: post #66

Earlier quoted context omitted.

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

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 Here's the thing: Most of the rest of the app was rather close to the case it's optimized for. I don't know what you mean by "something like LINT but for the runtime reference graph." Something that tells you that you've created a reference graph with a cycle,…

Great Circle commercialized the Boehm collector back in the 1990s, and I seem to recall that most of their customers were using it to tell them when they had a memory leak or reused freed memory, not to remove the need for reference counting altogether. But it didn't tell you about cyclic references, unless they resulted in a memory leak.

Re: Linus Torvalds on Garbage Collection (2002)

#150

Post by cdavid »

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…

The problem with most methods to improve ref counting speed is that it generally breaks existing C extensions. For that reason alone, I don't expect cpython to significantly change its way of doing things in that area for a long time.
Post reply on HN