23

I've read in many places (heck, I've even written so myself) that garbage collection could (theoretically) be faster than manual memory management.

However, showing is a lot harder to come by than telling.
I have never actually seen any piece of code that demonstrates this effect in action.

Does anyone have (or know where I can find) code that demonstrates this performance advantage?

|improve this question
  • 5
    the problem with GC is that most implementations are not deterministic so 2 runs can have vastly different results, not to mention it's hard to isolate the right variables to compare – ratchet freak Jul 4 '13 at 19:49
  • @ratchetfreak: If you know of any examples that are only faster (say) 70% of the time, that's fine with me too. There must be some way to compare the two, in terms of throughput at least (latency probably wouldn't work). – Mehrdad Jul 4 '13 at 19:56
  • 1
    Well, this is a bit tricky because you could always manually do whatever gives the GC an edge over what you did manually. Perhaps it's better to restrict this to "standard" manual memory management tools (malloc()/free(), owned pointers, shared pointers with refcount, weak pointers, no custom allocators)? Or, if you permit custom allocators (which may be more realistic or less realistic, depending on what kind of programmer you assume), put restrictions on the effort put into those allocators. Otherwise, the manual strategy "copy what the GC does in this case" is always at least as fast as GC. – user7043 Jul 4 '13 at 20:41
  • 1
    By "copy what the GC does" I didn't mean "build your own GC" (though note that this is theoretically possible in C++11 and beyond, which introduces optional support for a GC). I meant, as I've worded it earlier in the same comment, "do what gives the GC an edge over what you did manually". For example, if Cheney-like compaction helps this application a lot, you might manually implement a similar allocation + compaction scheme, with custom smart pointers to handle pointer fixup. Also, with techniques like a shadow stack, you can do root finding in C or C++, at the expense of extra work. – user7043 Jul 4 '13 at 21:15
  • 1
    @Ike: It's okay. See why I asked the question though? That was the entire point of my question -- people come up with all sorts of explanations that should make sense but everyone stumbles when you ask them to provide a demonstration that proves what they say is correct in practice. The entire point of this question was to once and for all show that this can actually happen in practice. – Mehrdad Jan 6 '16 at 4:24
26

See http://blogs.msdn.com/b/ricom/archive/2005/05/10/416151.aspx and follow all of the links to see Rico Mariani vs Raymond Chen (both very competent programmers at Microsoft) dueling it out. Raymond would improve the unmanaged one, Rico would respond by optimizing the same thing in the managed ones.

With essentially zero optimization effort, the managed versions started off many times faster than the manual. Eventually the manual beat the managed, but only by optimizing to a level that most programmers would not want to go to. In all versions, the memory usage of the manual was significant better than the managed.

|improve this answer
  • +1 for citing an actual example with code :) although proper use of C++ constructs (such as swap) isn't that hard, and would probably get you there quite easily performance-wise... – Mehrdad Jul 4 '13 at 21:11
  • 5
    You may be able to outdo Raymond Chen on performance. I am confident that I can't unless he's out of it due to being sick, I'm working many times harder, and I got lucky. I don't know why he didn't choose the solution you would have chosen. I'm sure he had reasons for it – btilly Jul 4 '13 at 21:56
  • I copied Raymond's code here, and to compare, I wrote my own version here. The ZIP file that contains the text file is here. On my computer, mine runs in 14 ms and Raymond's runs in 21 ms. Unless I did something wrong (which is possible), his 215-line code is 50% slower than my 48-line implementation, even without using memory-mapped files or custom memory pools (which he did use). Mine is half as long as the C# version. Did I do it wrong, or do you observe the same thing? – Mehrdad Jul 5 '13 at 8:39
  • 1
    @Mehrdad Pulling out an old copy of gcc on this laptop I can report that neither your code nor his will compile, let alone do anything with it. The fact that I'm not on Windows likely explains that. But let's assume that your numbers and code are correct. Do they perform the same on a decade old compiler and computer? (Look at when the blog was written.) Maybe, maybe not. Let's suppose that they are, that he (being a C programmer) did not know how to use C++ properly, etc. What are we left with? – btilly Jul 5 '13 at 14:29
  • 1
    We are left with a reasonable C++ program which can be translated into managed memory and sped up. But where the C++ version can be optimized and sped up farther. Which is what we all are in agreement is the general pattern that always happens when managed code is faster than unmanaged. However we still have a concrete example of reasonable code from a good programmer that was faster in a managed version. – btilly Jul 5 '13 at 14:31
5

The rule of thumb is that there are no free lunches.

GC takes away the headache of manual memory management and reduces the probability of making mistakes. There are some situations where some particular GC strategy is the optimal solution for the problem, in which case you'll pay no penalty for using it. But there are others where other solutions will be faster. Since you can always simulate higher abstractions from a lower level but not the other way around you can effectively prove that there is no way higher abstractions can be faster than the lower ones in the general case.

GC is a special case of manual memory management

It may be a lot of work or more error prone to get better performance manually but that's a different story.

|improve this answer
  • 1
    That makes no sense to me. To give you a couple of concrete examples: 1) the allocators and write barriers in production GCs are hand-written assembler because C is too inefficient so how will you beat that from C, and 2) tail call elimination is an example of an optimisation done in high-level (functional) languages that is not done by the C compiler and, therefore, cannot be done in C. Stack walking is another example of something done below the level of C by high-level languages. – Jon Harrop Jan 27 '16 at 0:03
  • 1
    1) I'd have to see the specific code to comment but if the hand written allocators/barriers in assembler are faster then use hand written assembler. Not sure what that has to do with GC. 2) Take a look here: stackoverflow.com/a/9814654/441099 the point is not whether some non-GC language can do tail recursion elimination for you. The point is that you can transform your code to be as fast or faster. Whether the compiler of some specific language can do this for you automatically is a matter of convenience. In a low enough abstraction you can always do this yourself if you wish. – Guy Sirton Jan 27 '16 at 0:34
  • 1
    That tail call example in C only works for the special case of a function calling itself. C cannot handle the general case of functions tail calling each other. Dropping to assembler and assuming infinite time for development is a Turing tarpit. – Jon Harrop Jan 27 '16 at 0:54
2

It's easy to construct an artificial situation where GC is infinitely more efficient than manual methods - just arrange that there is only one "root" for the garbage collector, and that everything is garbage, so the GC step is instantly completed.

If you think about it, that is the model used when garbage collecting the memory allocated to a processes. The process dies, all it's memory is garbage, we're done. Even in practical terms, a process that starts, runs, and dies leaving no trace might be more efficient than one that starts and runs forever.

For practical programs, written in languages with garbage collection, the advantage of garbage collection is not speed but correctness, and simplicity.

|improve this answer
  • If it's easy to construct an artificial example, would you mind showing a simple one? – Mehrdad Jul 4 '13 at 20:46
  • 1
    @Mehrdad He did explain a simple one. Write a program where the GC version fails to do a garbage run before exiting. The manual memory managed version will be slower because it was explicitly tracking and freeing stuff. – btilly Jul 4 '13 at 20:52
  • 2
    @btilly: "Write a program where the GC version fails to do a garbage run before exiting."... failing to do garbage collection in the first place is a memory leak due to the lack of a functioning GC, not a performance improvement due to the presence of a GC! That's like calling abort() in C++ before the program exits. It's a meaningless comparison; you're not even garbage-collecting, you're just letting memory leak. You can't say garbage collection is faster (or slower) if you're not garbage-collecting to begin with... – Mehrdad Jul 4 '13 at 20:56
  • To make an extreme example, you'd have to define a complete system with your own heap and heap management, which would be a great student project but too large to fit in this margin. You'd do pretty well by writing a program that allocates and deallocates random sized arrays, in a way designed to be stressful to non-gc memory management methods. – ddyer Jul 4 '13 at 21:00
  • 3
    @Mehrdad Not so. The scenario is that the GC version never happened to hit the threshold at which it would have done a run, not that it would have failed to perform correctly on a different data set. That is trivially going to be very good for the GC version, though not a good predictor of eventual performance. – btilly Jul 4 '13 at 21:04
2

It should be considered that GC is not just a memory management strategy; it also makes demands on the entire design of the language and runtime environment, that impose costs (and benefits). For example, a language that supports GC has to be compiled into a form where pointers can't be hidden from the garbage collector, and generally where they can't be constructed except by carefully managed system primitives. Another consideration is the difficulty of maintaining response time guarantees, as GC imposes some steps that have to be allowed to run to completion.

Consequently, if you have a language that is garbage collected, and compare the speed with manually managed memory in the same system, you still have to pay the overhead to support garbage collection even if you're not using it.

|improve this answer
2

Faster is dubious. However, it can be ultra-fast, imperceptible, or faster if it's hardware supported. There were designs like that for LISP machines a long time ago. One built the GC into the memory subsystem of the hardware as such that main CPU didn't know it was there. Like many later designs, the GC ran concurrently with the main processor with little or no need for pauses. A more modern design is Azul Systems Vega 3 machines that run Java code way faster than JVM's using purpose-built processors and a pauseless GC. Google them if you want to know how fast GC (or Java) can be.

|improve this answer
2

I have done quite a bit of work on this and described some of it here. I benchmarked the Boehm GC in C++, allocating using malloc but not freeing, allocating and freeing using free and a custom-built mark-region GC written in C++ all vs OCaml's stock GC running a list-based n-queens solver. OCaml's GC was faster in all cases. The C++ and OCaml programs were deliberately written to perform the same allocations in the same order.

You can, of course, rewrite the programs to solve the problem using only 64-bit integers and no allocations. Although faster that would defeat the point of the exercise (which was to predict the performance of a new GC algorithm I was working on using a prototype built in C++).

I have spent many years in industry porting real C++ code to managed languages. In almost every single case I observed substantial performance improvements, many of which were probably due to GC trumping manual memory management. The practical limitation is not what can be accomplished in a microbenchmark but what can be accomplished before a deadline and GC-based languages offer such huge productivity improvements that I never looked back. I still use C and C++ on embedded devices (microcontrollers) but even that is changing now.

|improve this answer
  • +1 thanks. Where can we see and run the benchmark code? – Mehrdad Jan 27 '16 at 0:26
  • The code is scattered about the place. I posted the mark-region version here: groups.google.com/d/msg/… – Jon Harrop Jan 27 '16 at 0:36
  • 1
    There are results for both thread safe and unsafe in there. – Jon Harrop Jan 27 '16 at 5:02
  • 1
    @Mehrdad:"Have you eliminated such potential sources of error?". Yes. OCaml has a very simple compilation model with no optimisations such as escape analysis. OCaml's representation of the closure is actually substantially slower than the C++ solution so it should really use a custom List.filter as the C++ does. But, yes, you are certainly quite right that some RC operations can be elided. However, the biggest problem I see in the wild is that people don't have the time to perform such optimisations by hand on large industrial code bases. – Jon Harrop Jan 28 '16 at 22:04
  • 2
    Yes, absolutely. No additional effort to write but writing code isn't the bottleneck with C++. Maintaining code is. Maintaining code with this kind of incidental complexity is a nightmare. Most industrial code bases are millions of lines of code. You just don't want to have to deal with that. I've seen people convert everything to shared_ptr just to fix concurrency bugs. The code is a lot slower but, hey, now it works. – Jon Harrop Jan 29 '16 at 0:42
-1

Such an example necessarily has a bad manual memory allocation scheme.

Assume the best garbage collector GC. It internally has methods to allocate memory, determine what memory can be freed, and methods to finally free it. Together these take less time than all of GC; some time is spent in the other methods of the GC.

Now consider a manual allocator that uses the same allocation mechanism as GC, and whose free() call just sets aside the memory to be freed by the same method as GC. It doesn't have a scan phase, nor does it have any of the other methods. It necessarily takes less time.

|improve this answer
  • 2
    A garbage-collector can often free up many objects, without having to put the memory into a useful state after each one. Consider the task of removing from an array-list all items meeting a certain criterion. Removing a single item from an N-item list is O(N); removing M items from a list of N, one at a time is O(M*N). Removing all items meeting a criterion in a single pass through the list, however, is O(1). – supercat Mar 10 '14 at 2:57
  • @supercat: free can also collect batches. (And of course removing all items meeting a criterion is still O(N), if only because of the list traversal itself) – MSalters Mar 10 '14 at 10:18
  • Removing all items meeting a criterion is at least O(N). You're correct that free could operate in a batch-collect mode if each memory item had a flag associated with it, though GC can still come out ahead in some situations. If one has M references which identify L distinct items out of a set of N things, the time to remove every reference to which no reference exists and consolidate the remainder is O(M) rather than O(N). If one has M extra space available, the scaling constant can be quite small. Further, compactification in a non-scanning GC system requires... – supercat Mar 10 '14 at 16:08
  • @supercat: Well, it's certainly not O(1) as your last sentence in the first comment states. – MSalters Mar 10 '14 at 16:10
  • 1
    @MSalters: "And what would prevent a deterministic scheme from having a nursery?". Nothing. OCaml's tracing garbage collector is deterministic and uses a nursery. But it is not "manual" and I think you are misusing the word "deterministic". – Jon Harrop Jan 27 '16 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.