Any hard data on GC vs explicit memory management performance?

Question

I recently read the excellent article "The Transactional Memory / Garbage Collection Analogy" by Dan Grossman. One sentence really caught my attention:

In theory, garbage collection can improve performance by increasing spatial locality (due to object-relocation), but in practice we pay a moderate performance cost for software engineering benefits.

Until then, my feeling had always been very vague about it. Over and over, you see claims that GC can be more efficient, so I always kept that notion in the back of my head. After reading this, however, I started having serious doubts.

As an experiment to measure the impact on GC languages, some people took some Java programs, traced the execution, and then replaced garbage collection with explicit memory management. According to this review of the article on Lambda the ultimate, they found out that GC was always slower. Virtual memory issues made GC look even worse, since the collector regularly touches way more memory pages than the program itself at that point, and therefore causes a lot of swapping.

This is all experimental to me. Has anybody, and in particular in the context of C++, performed a comprehensive benchmark of GC performance when comparing to explicit memory management?

Particularly interesting would be to compare how various big open-source projects, for example, perform with or without GC. Has anybody heard of such results before?

EDIT: And please focus on the performance problem, not on why GC exists or why it is beneficial.

Cheers,

Carl

PS. In case you're already pulling out the flame-thrower: I am not trying to disqualify GC, I'm just trying to get a definitive answer to the performance question.

Answer 1

It is the fact that developers are human and miss things that caused the need for garbage collectors in the first place. With that being said let me say that garbage collection will always be slower than perfect explicit memory management. And garbage collection can often be faster than imperfect explicit memory management given the fact that garbage collectors clean up the things that developers tend to forget.

Answer 2

The cost of memory allocation is generally much lower in a garbage collected memory model, then when just using new or malloc explicitly because garbage collectors generally pre-allocate this memory. However, explicit memory models may also do this (using memory pools or memory areas); making the cost of memory allocation equivalent to a pointer addition.

As Raymond Chen and Rico Mariani pointed out, managed languages tend to out perform unmanaged languages in the general case. However, after pushing it, the unmanaged language can and will eventually beat the GC/Jitted language.

The same thing is also evident in the Computer Language Shootout because even though C++ tends to rank higher than Java most of the time, you'll often see C++ implementations jumping trough various hoops (such as object pools) to achieve optimal performance. Garbage collected languages, however, tend to have easier to follow and more straight forward implementations because the GC is better at allocating (small chunks of) memory.

However, performance isn't the biggest difference when it comes to GC vs non-GC; arguably it's the deterministic finalization (or RIIA) of non-GC (and reference counted) languages that is the biggest argument for explicit memory management because this is generally used for purposes other than memory management (such as releasing locks, closing file or window handles et cetera). 'Recently' however C# introduced the using / IDisposable construct to do exactly this.

Another problem with garbage collection is that the systems they use tend to be rather complex to prevent memory leaks. However, this also makes it way more difficult to debug and track down once you do have a memory leak (yes, even garbage collected languages can have memory leaks).

On the flip side, the garbage collected language can do the most optimal thing at the most optimal time (or approximately) without having to burden the developer with that task. This means that developing for a GC language might be more natural, so you can focus more on the real problem.

Answer 3

In theory, a well profiled program can inform an intelligent GC subsystem to attain the described speedups over manually memory management. These speedups may not be visible without long runtimes, to amortize the fixed startup cost of GC.

In practice, you will likely NOT realize these speedups with present-day GC implementations. Furthermore, you will NOT get a definitive answer, because there will always be pathologically bad scenarios for both cases.

Answer 4

In theory, GC may be faster in some cases, but I have never seen that, and I doubt I ever will. Also, C++ with GC such as the Boehm GC will probably always be slower because it is conservative. With all the pointer fiddling in C++, the GC has to pretend everything is a pointer. With a language like Java, it can know exactly what is and isn't a pointer, so it may have the potential to be faster.

Answer 5

Here's an experiment that I like to run:

1. Start up a program written in a garbage collected environment (like .NET or Java).
2. Start up a similar program written in a non garbage collected environment (like C or C++).
3. Use the programs and see which one is more responsive.

Objectivity improvement: get your grandmother to do step 3.

It's all well and good to quote theoretical performance of optimal GC implementations but the fact of the matter is that in real world scenarios programs written in garbage collected languages do not perform as well as native applications. This is why large projects where performance translates directly into user experience still program in C++. The classic example of this is game programming.

Another, perhaps counterintuitive, example of this is the Eclipse IDE. While it may be written in Java the entire graphical subsystem had to be rewritten to produce acceptable performance. The solution: make GUI elements lightweight wrappers around native (C/C++) components (SWT).

I understand the draw of garbage collected environments. Memory management is hard to get right. And a lot of work. The bottom line though is this: knowing how your program is supposed to behave gives you (the programmer) an edge over a machine trying to guess.

Answer 6

There are quite a bit of different arguments given here. I want to start by making clear that you cannot really make a 1:1 comparison. Each has its pros and cons, and any code snippet will be more appropriate for one or the other system. That is as much to say, on the contrary, that you must know whether you have GC or not to write efficient code.

My argument is you must know your environment and code acordingly. That will make your code efficient. Moving from one paradigm to the other and coding the same style will make your code more inefficient than what the GC really helps/takes away.

Case:

A program makes thousands of heap memory allocations for short lived objects. That is, it allocates and deallocates many times, with different size of objects.

On a non-GC environment, for each allocation you would end up calling malloc, and that requires locating in the list of free memory fragments the most suitable one (according to the specific malloc implementation). The memory is used and then it is freed with free [or new/delete in C++...]. The cost of memory management is the cost of locating the fragments.

On a GC environment, with a movable GC as java or .net are, after each GC run all free memory is contiguous. The cost of acquiring memory for an object is cheap, really cheap (<10 cpu instructions in Java VM). At each GC run, only alive objects are located and moved to the beginning of the appropriate memory region (usually it is a different region than the original one). The cost of memory management is primarily the cost of moving all reachable (alive) objects. Now, the premise is that most objects are shortlived so at the end the cost may be smaller than that of a non-GC system. One million objects allocated and freed (forgotten) on a single GC run amount to no extra cost.

Conclusion: In GC languages you can create all local objects on the heap. They are cheap. On the other hand, in non-GC systems, a bunch of allocations, deallocations and new allocations is expensive. The memory is fragmented and the cost of malloc increases... In non-GC systems you should use the stack as much as possible, using the heap out of necessity.

That has another implication. People used to one of the two memory systems will tend to write inefficient programs in the other. They are used to some idioms that are probably bad on the other system.

A clear example is a non-managed programmer that is used to allocate an object and reuse (reset its internal pointers with new elements as required) is used to that way of thinking: allocation is expensive, reusing is cheap. Now, if the same exact code is moved to a generational GC environment (Java, .net - both are move-generational-GC), you get a funny effect. In Java generational GC the system will perform minor collections only on the younger generations, only processing older generations in full collections. But an object in the young generation could be referred to by objects in the older generation, so extra work has to be performed to keep track of this old-to-young references. In particular in Java 1.4.1 garbage collector the system will mark the memory card (sub-part of page) where the old object resides and it then includes all the marked cards for processing during the minor collection, effectively increasing the amount of work that the GC has to perform and possibly impacting performance.

The object was alive during 1, 2, 3... GC runs, and it was moved that many times around, finally is moved to the old generation where it will not be moved in each GC run but can just stand there... but alas, the programmer forces the object to become a younger. It is moved once again, and it will again be moved each time the GC runs up to the time where it becomes old again.

To make a sensible comparison, you would need to get to programmers that know the environment write different pieces of code that solve the same problem with the same algorithms with different mind sets about memory management. Then compare the results of both of them.

Answer 7

As @dribeas points out, the biggest 'confound' to the experiment in the (Hertz&Berger) paper is that code is always written under some 'implicit assumptions' about what is cheap and what is expensive. Apart from that confound, the experimental methodology (run a Java program offline, create an oracle of object lifetimes, instrument back in the 'ideal' alloc/free calls) is actually quite brilliant and illuminating . (And my personal opinion is that confound does not detract too much from their results.)

Personally, my gut-feel is that using a GC-ed runtime means accepting a factor-of-three performance hit to your application (GC'd will be 3x slower). But the real landscape of programs is littered with confounds, and you'd be likely to find a huge scatterplot of data if you could perform the 'ideal' experiment on lots of programs across many application domains, with GC sometimes winning and Manual often winning. (And the landscape is continually changing - will the results change when multicore (and software designed for multicore) is mainstream?)

See also my answer to

http://stackoverflow.com/questions/354124/are-there-statistical-studies-that-indicates-that-python-is-more-productive/354249#354249

which has the thesis that "due to so many confounds, all evidence about software engineering is anecdotal".

Answer 8

See also

http://prog21.dadgum.com/40.html

which discusses the "sufficiently smart" compiler. The landscape of CS/software is riddled with ideas/techiques which can be in theory more performant than the status-quo. But it's all snake oil.

GC is expensive today, and may always be.

Answer 9

Side note: another interesting experiment to run, that I haven't seen people try, is to compare with just leaking. Call alloc and never free. It's an interesting alternative.

Except for long-running server apps, you'll never run out of memory in practice, the OS will just start using disk for virtual memory (machines have effectively infinite memory, up to the limits of virtual address space, which I think is huge now with 64-bit machines). This highlights that a GC is nothing more than a device for improving locality. Leaked/dead objects don't "hurt" when you have infinite memory, except that memory comes in hierarchies and you want to keep the 'live' objects nearby and fast and the 'dead' objects on the faraway/slow memory. If each object was allocated on a different page, then the OS virtual memory system would effective be a GC.

Answer 10

This turns into another flamewar with a lot of "my gut feeling". Some hard data for a change (papers contain details, benchmarks, graphs, etc.):

http://www.cs.umass.edu/~emery/pubs/04-17.pdf says:

"Conclusion. The controversy over garbage collection’s performance impact has long overshadowed the software engineering benefi it provides.This paper introduces a tracing and simulation-based oracular memory manager. Using this framework, we execute a range of unaltered Java benchmarks using both garbage collection and explicit memory management. Comparing runtime, space consumption, and virtual memory footprints, we find that when space is plentiful, the runtime performance of garbage collection can be competitive with explicit memory management, and can even outperform it by up to 4%. We fi that copying garbage collection canrequire six times the physical memory as the Lea or Kingsley allocators to provide comparable performance."

When you have enough memory, copying GC becomes faster than explicit free() - http://www.cs.ucsb.edu/~grze/papers/gc/appel87garbage.pdf

It also depends on what language you use - Java will have to do a lot of rewriting (stack, objects, generations) on each collection and writing a multithreaded GC that doesn't have to stop the world in JVM would be a great achievement. On the other hand, you get that almost for free in Haskell where GC time will rarely be >5%, while alloc time is almost 0. It really depends what you're doing and in what environment.

Answer 11

GC will always be slower than the extreme alternative: perfect, non-deterministic memory management.

The questions are:

• Are the differences large enough to quibble about?
• Are the drawbacks of one technique enough to cause us to seriously consider the other?

There are other areas in which managed subsystems have won out over unmanaged ones:

In general, a program will always run slower on a multitasking operating system than on a uni-tasking one -- or a computer with no OS.

In general, a program will always run slower on a system with virtual memory than on one without.

Except in extreme circumstances, do we seriously consider computer systems without VM and without an OS?

Answer 12

Berger's paper is being cited a lot, but it is comparing real garbage collectors against a purely theoretical, offline, optimal algorithm. So while it may tell you something about theoretical limits, it says very little about the performance of real garbage collectors versus real implementations of malloc and free. A study that I like better took real programs and compared explicit malloc and free with Hans Boehm's conservative garbage collector:

The Measured Cost of Conservative Garbage Collection by Ben Zorn

This study isn't perfect, and Zorn is careful to note that if the programs knew they were using a garbage collector, some could be made faster. But the hard data is this: - In real programs originally written to use malloc and free, garbage-collected versions run at about the same speed but require twice as much memory. Zorn argues fairly convincingly that if you know you have GC, you can make things faster, but it's hard to eliminate the memory penalty.

I learned more from this careful experimental study than from Berger's study of an unimplementable, idealized memory manager.

Answer 13

One pragmatic issue is that with explicit MM it is generally a lot easier to profile, identify the bottleneck, and resolve it.

With a GC system, when your nice O(N) code turns out to trash the GC in a pathological way that makes it O(heap size), it can be harder to work out what is going wrong. Sometimes even as hard as fixing a memory corruption.

Answer 14

After discussion on another answer, a disadvantage which turns out is that GC can alter the asymptotic complexity. Soru's comment stated it implicitly without examples, and one comment is not enough to explain it. Thanks to Jon Harrop for the example he suggested and useful comments on this answer. However, a good GC should still amortize the costs (given enough memory, as always), as I explain in the end.

With a GC system, when your nice O(N) code turns out to trash the GC in a pathological way that makes it O(heap size), it can be harder to work out what is going wrong.

First, this happens often when the size of the working set is close to the maximum heap size. The GC is invoked too often and thus everything slows down. Install the Scala plugin for Eclipse and you'll feel it.

Usually, however, having enough memory space and a generational GC prevent it, if your algorithm just produce lots of garbage quickly detectable as such: it won't survive long enough to get out of the nursery.

Here's an example for an exception to that: let us take "map f list", and assume each application of f does consume live memory, by saving a reference to the returned value in a hash-table. The asymptotic complexity, here, should still be O(1).

The generational GC won't be able to free memory by collecting the nursery, thus a major collection (O(heap content)) is invoked somewhat periodically. Hence, we get that runtime is at least proportional to (heap content size) * n * (space consumed by each call to f) / (nursery size).

The GC will actually increase nursery size up to the specified maximum, and then the above happens again for n big enough. However, if the specified maximum is Big-Theta(max. heap size) and thus Omega(heap content size), major collections become infrequent, and the cost of minor collections is proportional to produced data (and thus to the runtime needed to produce them). This is similar to when you need to copy a container to resize it: by growing it enough, you can amortize the cost of copying (or of GC) and make it comparable to the cost needed to cause the copy.

This whole answer does not take in consideration the issue of pause times - collections become infrequent but are long. It implicitly assumes that stack scanning time is constant - but it should be indeed, unless your algorithm is non-tail-recursive and therefore risks problems anyway on the big inputs considered here.

Finally, it is not about incremental garbage collectors. They solve the problem at the root, but they are used mostly for real-time GC, because of the overhead they add to memory reads. Azul System solved this on their own custom HW with their Pauseless GC, thanks to HW support to optimize this overhead. They also recently claim to have solved the problem also for x86, see this "press release" and this article. But it's definitely under development and does not run without changes to the OS. When that's done, and if the performance is as they suggest, maybe the problem will be solved also for us normal mortals.