Linus Torvalds on Garbage Collection (2002)
gcc.gnu.org
gcc.gnu.org
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.
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.
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.
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()
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.
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.
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).
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...
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.
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...
In fact, it's been adopted into modern versions of the C++ standard itself. std::tr1::shared_ptr and std::shared_ptr.
[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
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.
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.
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 functions that return potentially shared, or potentially newly allocated, blobs of memory is painful in a manual memory management environment, because every function call becomes a resource management problem. You can't even freely chain multiple invocations (y = f(g(h(x)))) because, what if there's a problem with g? How do you then free the return value of h? How to you cheaply and easily memoize a function without GC, where the function returns a value that must be allocated on the heap, but might be shared?
Writing code that leans towards expressions rather than statements, functions rather than procedures, immutability rather than mutability, referentially transparent rather than side-effecting and stateful, gives you big advantages. You can compose your code more easily and freely. You can express the intent of the code more directly, letting you optimize at the algorithm level, while the ease of memoization lets you trade space for speed without significantly impacting the rest of your program. Doing this without GC is very awkward.
GC, used wisely, is the key to maintainable programs that run quickly. You can write maintainable yet less efficient programs, or highly efficient yet less maintainable programs, easily enough in its absence; but its presence frees up a third way.
I've written code in a reference counted language(python) which processes about a gigabyte of data per second from the network, with hard real time requirements - all on one machine with multiple cpus/cores. The code is fully unit tested, doc tested, and functionally tested. It's also short, runs on multiple platforms and has been maintained by other people than myself. My personal experience is that you can write highly efficient maintainable code with reference counting.
Reference counting manages memory automatically for you, but it also lets to manage memory manually when needed too. For many situations, it's the best of both worlds.
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 some way or another. The usual approach to refcounting releases resources as soon as they are no longer required (either by free()ing immediately or by sending it to a pool of unused resources), thus doesn't leave garbage around, and doesn't need a collector thread or mechanism to.
There are partial-GC implementations of refcounting, either because items are not free()d when they reach zero references, or to automatically detect reference loops which are not handled directly.
I agree with Torvalds on this matter. GC as it is promoted today is a giant step that gives programmers one benefit, solving one problem, while introducing a immeasurable pile of complexity to the system creating another pile of problems that are still not fixed today. And to fix some of these problems (like speed) you have to introduce more complexity.
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. Refcounting is simple and elegant, you just have to take care of reference loops, which also has another simple solution, that is weak references. I can teach a class of CS students everything they need to know to design a refcounting resource management system in one lesson.
GC is the opposite: it is big, complex, and a problem that the more you try to fix it, the more complex it becomes. The original idea is simple, but nobody uses the original idea because it performs so badly. To teach the same class how to design a GC system that performs as well as we expect today, an entire semester may not be enough.
In a way, I do as well.
GC as it is promoted today is a giant step that gives programmers one benefit, solving one problem, while introducing a immeasurable pile of complexity to the system creating another pile of problems that are still not fixed today. And to fix some of these problems (like speed) you have to introduce more complexity.
There are plenty of contexts where speed is a non-issue. In those cases, GC has been a huge win. The conceptual simplicity is the important part. The cost of the resources that would be saved with explicit and optimized memory management would be far outweighed by the resources required to implement such things.
The original idea is simple, but nobody uses the original idea because it performs so badly.
This is simply not true.
In the context of IO-bound enterprise systems, 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, and unless you are doing an exceptionally intense operation, you couldn't tell the difference. Properly tuned generational GC can be a truly fantastic seeming thing!
However, I will agree that the concerns Linus highlights are real, and that refcounting systems, like the one in iOS are by far better choices in many contexts.
EDIT: The above system I victimized, I only victimized in the TEST environment, but it was populated with something like 2-week old production data. The application in question is a traditional client/server desktop app used by a major energy company and had 800 active users at the time, handling millions in transactions every minute.
IDEA: If someone had an augmented ref-counting system with a runtime containing an optional cycle-detector and something like LINT but for the runtime reference graph, one would get most of the benefits of GC with the efficiency of the ref-counting system. I half expect someone to tell me that this already exists for Python.
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 them into a tenured garbage object.
> I half expect someone to tell me that this already exists for Python.
Yes, that's how Python works, except that I don't know what you mean by "something like LINT but for the runtime reference graph."
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, you have a memory leak, or that you're using references in some other stupid or suboptimal way. I'm not even sure if there's a way to automatically detect anything like the last category, though the first two are certainly detectable. Basically, you take most of the infrastructure of GC, and you just turn it into a runtime advisor to warn devs and testers of mistakes.
http://www.research.ibm.com/people/d/dfb/publications.html
Scholar cluster:
http://scholar.google.com/scholar?q=bacon+unified+theory+gar...
Incidentally, it is not even remotely true that reference counting is more efficient than tracing GC in all cases.
Or you could do what Rust <https://github.com/graydon/rust/wiki/Language-FAQ>; does, and have different types of objects; stateful and stateless. Stateless object cannot have cycles (since you can't construct them in stateless objects, unless you're in a lazy language), and so reference counting can be used for stateless objects. Stateful objects, which can have cycles, are managed by the garbage collector.
Rust sounds like a really interesting idea, and I'd love to give it a try, but sadly it's still in the "some assembly required" stage as they work on bootstrapping it so the only real projects that are worthwhile to do with it yet are helping out with the bootstrapping process.
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.
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/refcounting is probably your best choice.
For everyone else (let's guess over 90% of the programming population), using high-level GC'd languages is significantly simpler and more productive.
(Delphi uses reference counting for interfaces, strings and dynamic arrays, and I am aware of race bugs in strings in particular (which are copy on write); these bugs are hard to fix without murdering performance, yet in practice they are very rare on x86 memory model hardware. So they stay.)
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 without scanning the stack for root objects, passing them in manually, I still think there's some amount of non-portable code in there.
That said, I'm using my GC for new stuff when the objects aren't too temporary. We'll see how it works out.
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<const T> 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.
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.
Reference counting isn't conceptually any more simple than garbage collection (you still have to indicate how the underlying alloc() and free() operations are implemented). Further, a proper high performance reference counting system isn't any simpler than a high performance GC. In a multithreaded system you have to keep the reference counts in sync without doing a slow atomic operation every time a pointer is passed around, and you need to back the ref counting system with a high performance malloc()/free() that can handle multithreaded allocation and is resistant to memory fragmentation.
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?
That's one thing that's so intriguing about Moore. He's a living specimen of an alternate computing history. I sometimes wonder what would have happened if he had been in, say, Backus's position at the dawn of high-level languages.
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.
[Edit] Not that I have a problem with older posts, btw.. I actually really like them most of the time. But the date would give everyone a better opportunity to evaluate whether they want to read the article, and would be reading it with reasonable context.
Date: Fri, 9 Aug 2002 20:28:16 -0700If you've written any data intensive application you know that a GC doesn't solve memory issue. It's just a different strategy.
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?
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)
A lot of this is that a few small low-budget research groups were building lisp machines at a time when the big players suddenly started pouring all their efforts into developing commodity single-user graphical workstations. But it's also true that developments in GC technology -- developments which Torvalds seems unaware of in this 2002 post, even though they were 15-20 years old by then -- made GC really fast even on hardware not designed with GC in mind.
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 slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the _chance_ to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory.
But no matter how well you choose: software will only be able to exploit this if it is designed for locality.
If you can fix that (i. e. if you can find a cheap way to produce gigabytes of fast memory that makes chaches obsolete) the current compilers won't stop you from exploiting it: The code that is optimized for locality will still run as fast, and the code that can't be optimized for locality will run orders of magnitudes faster.
So we aren't in a local optimum at all. You can still optimize further "just" by producing faster and cheaper hardware.
Although all modern high-performance (edit: I mean non-embedded-microcontroller) computers work this way, it's not the only possible way. The Tera MTA takes a different, cacheless approach.
First, the problem with modern RAM in desktop machines is not that it sucks at bandwidth. You can get your bandwidth arbitrarily high by multibanking. Multibanking requires more buses or point-to-point links, but that's a tolerable cost.
The problem with modern RAM is that it sucks at latency, compared to what the CPU would like. Well, what do you do about latency? You make your requests earlier, and make sure you have other things to do in the meantime, when they get back. The Tera did this by having 128 sets of registers – 128 hardware threads — and switching to the next thread on every cycle. That means that, if all the thread slots were full, every thread only executed an instruction every 128 cycles, which is plenty of time to hide the latency of a slow memory fetch, as long as the memory bandwidth was adequate.
So basically every thread gets to pretend that it's running on a machine with zero-latency RAM — memory that's as fast as the registers. And pointer-chasing becomes as fast as looping over an array.
There are some other advantages to this design. Pipelining logic is very simple, because unless your pipeline gets insanely deep, you never have two instructions in the pipeline from the same thread, so you don't have register hazards.
(Cache is still beneficial in such a design, since it reduces the bandwidth that the links to main memory need to support. But the Tera didn't use it.)
I don't really understand why the Tera MTA failed in the market, and I suspect the problems were commercial rather than technical — customers had to take a big risk by porting their software to an unproven HPC platform, a platform whose performance characteristics were completely unlike anything else in the market (and unlike anything you can buy today). So customer uptake was insufficient to provide the cash flow needed to keep updating the design to keep up with Intel and AMD.
The technical reason such a design might fail would be if the silicon resources needed to support an entirely independent core were comparable to the silicon resources needed to support a hardware thread. Consider the GreenArrays GA144 chip: 144 independent cores, each with a tiny amount of independent RAM, on the same chip. Such a chip will be at least as fast as a chip with 144 independent register sets, but a single execution pipeline — in the worst case, it's bottlenecked on getting data out of RAM, and only one of its cores is usable, making it just as fast, while in the best case, it runs 144 times as fast. So a chip with 144 register sets needs to be cheaper — i.e. smaller — than the GA144. (Well, or easier to program, but presumably you can use more mainstream multicore chips to prove the example instead.)
This started happening in earnest about 20 years ago in the supercomputer market, which is where the Tera was sold. About 10 years ago, it started happening in desktop CPUs (check out Herb Sutter's article about "the end of the free lunch") and now it's starting to happen in embedded microcontrollers, with the Parallax Propeller and the GreenArrays chips.
As it happens, the Tera didn't lose to faster single-threaded supercomputer CPUs. By the time the MTA came out, even the most stalwart defenders of the fast-single-threaded-performance approach, like the Cray SV1 and the NEC SX-5, had succumbed to the necessity of CPU parallelism. But the approach that was taking over the supercomputer market at the time was actually far more parallel, and far more difficult to program efficiently --- NUMA machines and then Beowulfs.
So that's why I don't think it was single-threaded programs that made the Tera fail in the supercomputer market.
The question of how to meaningfully parallelize XML and HTML parsing, compilation, text processing in general, and web browsers are very interesting indeed. It's not obvious how to do it, but it might turn out to be tractable. A group at Berkeley was doing some research on it in 2007 and 2008: http://www.eecs.berkeley.edu/~lmeyerov/projects/pbrowser/
Thanks for the references. I'm in embedded systems but I hadn't heard of the Parallax Propeller before, it's an interesting architecture.
If multithreaded or massively multicore processors were a viable alternative, you could get deterministic timings without sacrificing throughput. You could even do away with interrupts. The GreenArrays chip doesn't have interrupts at all; instead, its cores go into a low-power shutdown state whenever they're waiting on I/O.
But that's all pretty speculative.
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.
There is an approach called NISC [1] (No Instruction Set Computer), where the instruction set is completely removed and the compiler generates control words directly for the architecture (which can also be designed from scratch and optimized).
I was wondering how that was different from Cocoa on Objective-C.
See: http://developer.apple.com/library/mac/#documentation/Cocoa/...
Or would the mere act of using cocoa in one part of my application somehow prevent me from exploiting such an opportunity in another part of my application?
My instinct says that, for example, a plain C library that used such techniques would not cease to function just by being linked into a cocoa application.
What I meant, however, is that most nontrivial Cocoa apps are likely to end up with a checkerboard allocation pattern, where the client allocated, controlled-lifetime objects are interspersed with Cocoa library allocated autoreleased objects with somewhat longer lifetimes, which may interfere to some extent with any strategy relying on controlling your object lifetime.
Still, people can and do avoid autoreleasing objects if their lifetimes are well known in advance.
Objective C also has the 'new' garbage collection system and there is autorelease which uses a memory pool and releases at some later point.
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.
If you think long and hard about each place you call 'new' in java Android apps, it is possible to get a smooth interface. However, the language doesn't encourage it by default like on iOS and you have to put time into it you usually don't have.
For users, milliseconds of jitters and blockiness everywhere is a huge turn off. It feels like the device is struggling to handle simple tasks and it destroys the belief in the UI metaphor of physical objects that have inertia and flow, stretch and bounce when you touch and flick them.
IMO, because it makes such a huge difference to users, UI programming should always happen in a high performance language and environment. One way to attain this performance is to eschew garbage collection. This is also a problem in web browsers where the UI is often written in javascript.
At the very least those who make programing environments, languages or GCs used for building user interfaces should optimize how their environments promote good use of local hardware cache and acceleration. There is a reason why UI rendering often relies on video hardware that is not totally unlike a desktop high performance computer.
Yet for WP7 its also silky smooth. The main issue on WP7 for user apps isn't GC at all, but rather the network (creating long lists of images that you're getting from a web service). Once people learned some techniques for dealing with that on the device the experience for 3rd party apps was just as silky as iOS apps -- yet a full generational GC.
The GC is an excuse (unless its not well written), not the reason.
From the article: "Garbage collection is simulating a computer with an infinite amount of memory. The rest is mechanism."
Whether or not it's reference counting or generational, the goal is still to simulate infinite memory. That way, you can focus on the high-level problems instead of the technical memory-related details. So it's not necessarily a bad mindset to have.
It also doesn't allow circular data structures, which are quit hard to implement if all you have are strings anyway.
Anything remotely like a non-trivial dataset should not be run in pure Python, based on my experience.
Though his argument about cache does still hold.
I don't think Linus ever intended to declare GC as evil or wrong. He was calling it out as a very poor choice that people persist in making for certain domains.
It would not have to hold, but I have not heard of any such scheme being implemented.
For applications operating at a higher level, or where any calculation that's going on is taking up a trivial amount of CPU time compared to (say) waiting for the user, then the overhead of reference counting (and the mistakes that are associated with that) is probably not worth it.
In UI scripts or something else running on multiple levels of abstraction, preventing memory leaks and allowing developers to quickly prototype is much more important. Cache performance does not even come into it. It would be crazy to advocate manually managing memory there.
shared_ptr is a really nice thing in C++. (For those who don't know: It is a ref-counting pointer with automatic freeing.) And its behavior is very deterministic. In many cases in complex C++ applications, you want to use that.
That seems like a reasonable compromise and I'm surprised that more languages don't do it.
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.
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 premature optimization.
If the goal is to speed up GCC, there are a long list of things to do before you have to worry about L1/L2 cache miss. Header file processing (or re-processing) is one of the biggest time sinks during compilation.
http://gcc.gnu.org/onlinedocs/cpp/Once_002dOnly-Headers.html
Processing header files in the first place is certainly a problem affecting C, but I believe optimizations take more time. Parsing is a much larger problem for C++.
My point is: run the profiler, see what are the bottlenecks, and pick those areas for optimization. Rather than speculating that L1/L2 cache misses are causing the major delay. If they ran the profiler and L1/L2 cache misses are really the problem, then I have nothing else to say.
This is just mmap for Clang. For GCC it... isn't. The other one you mentioned is called a compile server and nobody seems to have cared enough to implement it.
> If they ran the profiler and L1/L2 cache misses are really the problem, then I have nothing else to say.
That's an interesting problem in doing a lot of lookup from main memory since the data structures are too big to fit in L1/L2. But that usage is not allocating a lot of short lived objects and freeing them, and reusing the freed memory right the way for next allocations. That's what Linus arguing for to reused the L1/L2 for the short lived objects, and thus GC is inappropriate. I would imagine compilers typically allocate objects that have long lifetime, such as declarations that have scope through the whole compile cycle. Also if memory allocation/deallocation is really a performance problem, then don't deallocate, just reuse the buffers. Reusing the same set of buffers would make sure they are hot in L1/L2.
Anyway it has been an interesting discussion.
newnode->count = 1;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.
Dense matrix kernels should get better than 90% of FPU peak. Unlike sparse kernels, dense kernels are no longer bandwidth limited, but cache reuse in both L1 and L2, as well as friendly TLB behavior is important to good performance.
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.
It's an interesting question though. I'm a Haskell beginner, but I'm pretty experienced with Scala. Let me try to see how using sliding compares with a tight Java loop on statically allocated data for convolutions/filters.
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.
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/papers/stencil/stencil-icfp...
* http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.p...
* http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf
* http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf
In all these cases arrays codes are written in a function style, accompanied with special purpose optimizations and/or code generators (in the case of GPU code), layered over an imperative arrays primitive layer, using a memory effects monad.
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 instructions so it cannot possibly be better than 50% of FPU peak (the limit is actually lower because this kernel is/should be bandwidth limited). As for parallelism, I'll quote Bill Gropp [1]
The easiest way to make software scalable is to make it sequentially inefficient.
[1] http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&#...
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.
More likely imperfect strictness analysis, etc. Haskell is a pure functional lazy language, after all. Getting within 65% of C's performance on a tight numeric kernel is heroic.
Haskell isn't a good example, since it's a lazy functional language, but if something like Java isn't just as fast for your case it isn't the GC, it's the code generation. Much harder to do all those fancy loop optimizations in 100 ms in a JIT than in 10s in an offline compiler.
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.
As for web browsers... every web browser has a GC...
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?
If your problem is with pauses during GC, well guess what computers pause all the times. Whenever you move your mouse or type on the keyboard, they generate interrupts that pause the whole CPU and it has to handle them. Those pauses don't seem to be a problem. If the small pauses in GC are acceptable in general usage, why not use them?
If you want hard guarantee, that's what realtime system is for.
It's possible that things were different in 2002, but I don't really think this is the case now. In general, I make the node immutable and never copy it (copying an immutable object makes no sense). In a well-designed code base, mutations happen within the function where the data is created (read: on the stack, where cache locality is a given). Immutability also addresses Linus' concerns with thread-safety. And that's not accounting for concerns which Linus DOESN'T mention, such as increased development speed and correct program behavior.
I'm not the only one saying this. Josh Bloch, for example, recommends immutability and cites cache reasons (http://www.ibm.com/developerworks/java/library/j-jtp02183/in...). And many languages (Haskell, Clojure) are designed heavily around avoiding mutation and sharing nodes within data structures.
This talk of copying nodes to avoid your objects changing out from under you sounds a lot like what I call "writing C in Java". Linus is looking at this from the perspective of, "If they took away explicit memory management from C, this is how I would do it." But OF COURSE if you just bolt a feature like GC into a language that didn't have it before, it won't work well. Effective cache usage in a GCed system requires other language constructs (like immutability).
Now, after all that, I won't make the claim that immutability in a GCed language like Java or C# is faster or even as fast as C with explicit memory management: it would take a lot of profiling code and comparing its functionality to make that claim with any kind of certainty. But it doesn't seem like Linus has done that profiling and comparison either.
Unsurprisngly, things have changed. Many of Linus's complaints were valid, and we've learned how to address them.
GC systems are no better in this regard. I was told of an interesting hack in a Java program that implemented a large cache of objects by serializing them into a large memory block so that the GC saw it as one big object and didn't traverse it. This resulting in dramatically reduced GC pause times (10x+). When needed, objects were deserialized from the array. Disgusting, but effective.
It is getting harder and harder to beat compilers with hand-coded assembly without an enormous amount of effort, though.
Couldn't agree more. We were actually laughing in the office when an office mate brought up such a paper many years ago.
"I really think it's the mindset that is the biggest problem."
Linus is a superhero 20+ years working on the supertask of changing people's mindset.