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.
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 GCs take advantage of that idea?
You can Google "nursery generation" for some examples:
http://www.google.com/search?q=gc+nursery+generation
The original theory was that most objects in a functional language are extremely short-lived, and you want to reclaim them quickly. But if you GC your nursery generation after every few kB of allocations, you'll also keep the memory in L1 and L2 cache.
The ideal size of a nursery generation (and the value of reusing hot memory) should be measured empirically.
Of course, most popular scripting language GCs are non-copying, reference-counting collectors, which means they ignore techniques that were well-understood back in the 80s. However, this has not been a barrier to the adoption of Python, Ruby, etc., because the business value of high-performance code is often minimal.
- [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...
Python uses such reference counting (although it also has a GC fallback to ensure cyclic structures are collected).
You are correct, though, that ref-counting overhead is one of the main reasons Python is slow.
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.
Say you do "import smtplib" in your main file. Now that module is imported -- forever. I don't know the internals of Python well enough, but I bet that the module reference has strong references to its contents, so that even if nobody is actually calling anything in smtplib, it will be there in case someone does. The same should be true about modules importing other modules; they stay visible at the scope-level, so they are permanently loaded.
So for those cases it would make sense to keep them separate from global garbage collection. I'm pretty sure that the method tables of all the classes in the system take up considerable space, probably in the order of megabytes for many apps.
It is indeed unfortunate when the limitations of our platforms force us to contort our code to improve performance, but that is just as true of multithreading as of multi-process programming. The difference between the complexity of the two is small.
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)
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/)
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.The key to speed is to not share state, which Python can do fine. It's called fork.
I think the GIL has made people in the python community too defensive: the GIL does not prevent from building scalable architectures in many cases, but it still sucks, and it would be better without. That's a limitation (and a tradeoff because it made development and integration with C easier). And there are scalable architectures based on threads (example: http://www.mailinator.com/tymaPaulMultithreaded.pdf) - "thread suck" has became a meme which slightly bothers me in general. Not a panacea, but a good solution when applicable.
There are also some DNS-related bugs that are not on this list.
What are the DNS-related bugs?
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).
Also, undertaking anything with XML in C is brave, kudos.
https://gist.github.com/937200 (two sample files, totaling slightly less than half the project)
Posting 10-year-old code to HN is always a little embarrassing, but please feel free to be brutal. I'll live. :-) I was definitely way too in love with the preprocessor back then.
Here's the corresponding Python code, from shortly after it hit 1,000 lines in late 2001:
http://hg.python.org/cpython-fullhistory/file/7b2d701ec404/L...
I like the Python code rather better, if only because there's so much less explicit memory management. The actual ideas stand out clearly, and there's just so much less code to read. In most cases, I'd happily sacrifice the performance.
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.
Writing a library in C (for reasons of performance) where performance would have been 'good enough' in Python is unnecessary optimisation. Writing your own GC implementation layer in Python because you think that's the bottleneck would be premature optimisation.
EDIT: typo
Regardless of this distinction, I think the same conclusions follow; the original problem had little to do with reference counting as such.
While complex, the ref-counting implementation gave me something that a GC system just can't deliver:
Determinism.
This system is running on a 300MHz embedded x86 hosts, in a solid-state industrial computer, and has to provide sub-millisecond timing with only occasional hiccups >1ms acceptable. I am unaware of a GC system that could deliver this.
These boxes run for years, with no memory leaks. The cost was, of course, ensuring that no "loops" of objects get created. This was a small price to pay for the benefits. Having written large systems using both GC and ref-counting, I still lean toward ref-counting, even if determinism isn't a strong requirement.
Of course, I'm one of those guys who loves C++, so take my opinions with a grain of salt...
[1]http://domino.watson.ibm.com/comm/research_projects.nsf/page... [2]http://www.youtube.com/watch?v=uL2D3qzHtqY
If you mean that reference counting, on average, tends to result in fewer amounts of random/unpredictable pauses than most GCs, then I agree.
*with a lot of collaries
In fact, it's been adopted into modern versions of the C++ standard itself. std::tr1::shared_ptr and std::shared_ptr.
In some cases that 50 times increase in speed may be important. In some cases, if something is 50 times slower it would be simply unusable. Linus happens to be working on one of those special cases, so he is quite correct in pointing out that garbage collection will always slow things down.
Linus writes from a systems perspective. He cares about every nanosecond and every byte. And that's appropriate and even laudable in the context of the linux kernel and core applications. But it's not always appropriate for every situation.
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? Sure, I could parse 1,500+ XML-RPC requests/second. Did anybody actually benfit from this speed? Probably not.
But the real problem is even bigger: Virtually every reference-counting codebase I've ever seen was full of bugs and memory leaks, especially in the error-handling code. I don't think more than 5% of programmers are disciplined enough to get it right.
If I'm paying for the code, I'll prefer GC almost every time. I value correctness and low costs, and only worry about performance when there's a clear business need.