Garbage Collection vs. malloc/free(groups.google.com)
groups.google.com
Garbage Collection vs. malloc/free
https://groups.google.com/forum/#!topic/mechanical-sympathy/1TMjVjyyMmA
9 comments
Any pointers on the state of the art?
Which I would add is a production garbage collector, an updated version of the Pauseless one that's got its own paper and is covered in the 2nd edition of the book on garbage collection, http://www.amazon.com/The-Garbage-Collection-Handbook-Manage...
Does require custom hardware or kernel cooperation for speed (e.g. it needs to do batched MMU operations without clearing the TBL on each 2MB page). Looks like it's got a better read barrier than the Pauseless one; that does of course cost extra on stock hardware.
Does require custom hardware or kernel cooperation for speed (e.g. it needs to do batched MMU operations without clearing the TBL on each 2MB page). Looks like it's got a better read barrier than the Pauseless one; that does of course cost extra on stock hardware.
It's amusing to me that on the same thread GC proponents say that high-performance GC is easy (https://news.ycombinator.com/item?id=6485114) and that Java's GC is "far from state of the art" (https://news.ycombinator.com/item?id=6483704).
And so the perpetual argument goes: GC is superior to manual memory management (the latter of which is "adding needless effort to writing software"), and the performance is just as good, and the cases where performance is not just as good will be fixed Real Soon Now.
And so the perpetual argument goes: GC is superior to manual memory management (the latter of which is "adding needless effort to writing software"), and the performance is just as good, and the cases where performance is not just as good will be fixed Real Soon Now.
I'd like to point out that I did not say that a high-performance GC is easy. What I actually said is that a simple GC is easier than simple automatic optimizations. A high-performance GC is the same level of difficulty as good automatic optimization.
Actually the discussion at the newsgroup is more about Java's GC vs malloc/free.
In GC enabled systems programming languages like the Oberon family, Modula-3, D, Sing#, one has finer control over the types of available memory.
- The usual GC allocated memory with the usual set of possible GC implementations
- Stack objects
- Global objects statically allocated
- Manual memory management inside unsafe blocks via untraced GC references
Not all GCs are made alike.
In GC enabled systems programming languages like the Oberon family, Modula-3, D, Sing#, one has finer control over the types of available memory.
- The usual GC allocated memory with the usual set of possible GC implementations
- Stack objects
- Global objects statically allocated
- Manual memory management inside unsafe blocks via untraced GC references
Not all GCs are made alike.
Real-time Java (RTSJ) actually has some very cool mechanisms for fine-tuned control over allocations.
In language garbage collection just makes implementing a compiler that much harder to do and frankly bloats up the runtime. Basic c++ shared pointers take up pretty much 90+% of what people need in GC (non stupid software architecture decisions should make up the remaining 10%).
I have seen problems with stalling caused by kernel memory heap defragging on linux resulting in some serious thrashing. What that means is that the issue of heap fragmentation can be a problem regardless of which language used.
I have seen problems with stalling caused by kernel memory heap defragging on linux resulting in some serious thrashing. What that means is that the issue of heap fragmentation can be a problem regardless of which language used.
"In language garbage collection just makes implementing a compiler that much harder to do"
A simple copying or mark-and-sweep collector is far easier to write than even basic dataflow-analysis optimizations. Implementor effort is hardly an argument against garbage collection; implementing efficient garbage collection is no worse than implementing a good optimizer or efficient code generation.
"Basic c++ shared pointers take up pretty much 90+% of what people need in GC"
They do so in a way that is right in the programmers face, adding needless effort to writing software, and can actually wind up being slower than a modern garbage collector. Shared pointers are a mistake, not quite as bad as auto_ptr but pretty bad nonetheless; the committee should have just introduced a garbage-collected smart pointer class and kept things simple (I guess that would not be the C++ way, though).
A simple copying or mark-and-sweep collector is far easier to write than even basic dataflow-analysis optimizations. Implementor effort is hardly an argument against garbage collection; implementing efficient garbage collection is no worse than implementing a good optimizer or efficient code generation.
"Basic c++ shared pointers take up pretty much 90+% of what people need in GC"
They do so in a way that is right in the programmers face, adding needless effort to writing software, and can actually wind up being slower than a modern garbage collector. Shared pointers are a mistake, not quite as bad as auto_ptr but pretty bad nonetheless; the committee should have just introduced a garbage-collected smart pointer class and kept things simple (I guess that would not be the C++ way, though).
Reference counting, even ignoring the additional expense C++ places on std::shared_ptr by requiring it be thread safe, is far too slow for allocation heavy languages. Only "we don't give a damn" implementations (like CPython) use it, because it is simply not competitive.
Not necessarily true. See "Down for the Count?" ISMM 2012: http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rc-ismm-2...
"This brings the performance of reference counting on par with that of a well tuned mark-sweep collector."
I'm not really convinced. How well does it stack up when the competition is a copying generational collector?
I'm not really convinced. How well does it stack up when the competition is a copying generational collector?
They compare against a copying collector.
... implemented in Jikes RVM which is very far behind Oracle JVM. Herz and Berger (2005) based their experiment on Jikes RVM, too, and incorrectly concluded that GC needs 5x more memory to have acceptable performance comparable to malloc/free. Someone else redid their experiments using Oracle JVM and it turned out that it was not 5x, but 20%.
std::shared_ptr is not thread safe, only the control block shared between all of the std::shared_ptr objects is thread safe. This means you only get a locking penalty when shared_ptr objects are constructed, copied, or destroyed, but not moved, dereferenced, or casted.
Both construction and destruction will allocate or can release memory, respectively, which I would think would bottleneck before any atomics or memory barriers inside shared_ptr. To me, the first likely port of call for improving performance in these cases is therefore a custom memory allocation strategy like a memory pool.
Copying can be a concern, but most containers and standard algorithms should be move aware now. You should be moving shared_ptr's far more often than you copy them.
All that aside, thread-safe by default seems to be the sane decision in this era.
Both construction and destruction will allocate or can release memory, respectively, which I would think would bottleneck before any atomics or memory barriers inside shared_ptr. To me, the first likely port of call for improving performance in these cases is therefore a custom memory allocation strategy like a memory pool.
Copying can be a concern, but most containers and standard algorithms should be move aware now. You should be moving shared_ptr's far more often than you copy them.
All that aside, thread-safe by default seems to be the sane decision in this era.
iOS uses Automatic Reference Counting (ARC, http://en.wikipedia.org/wiki/Automatic_Reference_Counting) by having the compiler add reference counting instructions, while refraining from having the developer add tedious reference counting instructions themselves. I'm not sure if there are significant performance advantages over proper GC.
It's worth noting that Apple has implemented GC in Objective-C on OS X before, but deprecated that in favour of its ARC implementation -- probably because its garbage collection implementation was no good at all (performance-wise).
It's worth noting that Apple has implemented GC in Objective-C on OS X before, but deprecated that in favour of its ARC implementation -- probably because its garbage collection implementation was no good at all (performance-wise).
Apple dropped GC in Objective-C, because they never managed to make it work properly.
By the time ARC was announced, there were still lots of corner cases in the ways code compiled with GC was interacting with code that wasn't compiled with GC enabled.
Plus, if you check Apple's developers documentation from those days, great care was required to make sure the GC could play nice with the C part of Objective-C.
So, in reality the ARC approach was taken, because it was the only way to have a working automated memory management, compatible with Objective-C code overall. Of course, being Apple, they sold it as a better solution for memory management and not as a result from their failure to implement a sound GC for Objective-C.
By the time ARC was announced, there were still lots of corner cases in the ways code compiled with GC was interacting with code that wasn't compiled with GC enabled.
Plus, if you check Apple's developers documentation from those days, great care was required to make sure the GC could play nice with the C part of Objective-C.
So, in reality the ARC approach was taken, because it was the only way to have a working automated memory management, compatible with Objective-C code overall. Of course, being Apple, they sold it as a better solution for memory management and not as a result from their failure to implement a sound GC for Objective-C.
iOS is a technology swamp.
Objective-C uses ref counting and does alright... Hardly a language that doesn't prioritize performance.
Objective-C, a language which uses dynamic dispatch for all method calls and does not do any kind of type-specialized code generation, certainly does not prioritize performance.
It priorities performance in one important respect: by providing direct access to C. It's common in many languages to write performance critical sections in C or even assembly. This is trivial in ObjC, which has C as a subset, so it is done more often than in e.g. Python or Java.
Interoperability with FFIs is one of the advantages of reference counting over GC. You don't have to worry about pinning allocations, allocation coloring, unscanned roots, etc. The ObjC refcounting operations (CFRetain/CFRelease), and the collection types (CFArray, CFString, CFSet...) are all trivially available from C as well.
I speculate that this better interoperability with C is why Apple deprecated GC and went with ARC. We can see Microsoft sort of moving in the same direction with WinRT.
Interoperability with FFIs is one of the advantages of reference counting over GC. You don't have to worry about pinning allocations, allocation coloring, unscanned roots, etc. The ObjC refcounting operations (CFRetain/CFRelease), and the collection types (CFArray, CFString, CFSet...) are all trivially available from C as well.
I speculate that this better interoperability with C is why Apple deprecated GC and went with ARC. We can see Microsoft sort of moving in the same direction with WinRT.
I guess the phrase "prioritize performance" is maybe ambiguous. It's a language that cares a lot about performance, let's say -- sure, it uses dynamic dispatch for its method calls (losing a little speed compared more-static C++ virtual methods, which themselves lose a little speed compared to non-virtual methods), but the implementation itself is very optimized (there's some good blog articles describing the implementation, but I don't have them at hand), and you always have normal function calls as in C if you need maximum speed (as millstone mentioned). C really feels like a first-class language when using Objective-C, and C is a pretty damn fast language.
(As an aside, there was an optional GCed variant of objective-c around for a while. Not sure what the performance impact was vs ref counted.)
(As an aside, there was an optional GCed variant of objective-c around for a while. Not sure what the performance impact was vs ref counted.)
shared_ptr may be slow (I don't know) but you actually make very little "garbage" in C++, so it's not a problem. You're simply forced by the language to have clear ownership of resources most of the time.
This, and if you're using shared_ptr heavily in C++, you're probably doing it wrong, since unique_ptr is usually sufficient. (You could say that shared_ptr has the advantage that you don't have to think about who owns what, but with C++ there's no way around doing some amount of thinking about that, lest you get cycles.)
That's a reasonable defense of std::shared_ptr, but I was not discussing C++ code (I was careful to mention "allocation heavy languages" in my post).
Unless you happen to have a compacting GC. :)
Well since compacting means the expensive task of moving managed memory blocks around to free larger sections that solution certainly comes with a big penalty of it's own.
Better to avoid heap fragmentation to such extents by applying a better allocation strategy imo.
Better to avoid heap fragmentation to such extents by applying a better allocation strategy imo.
That is why generational collectors are so good. It is not common to have huge blocks of memory than also happen to be short lived, and if you do have such a design, you can probably refactor it (or just not use garbage collection there, which any production-grade programming environment should allow by some means).
shared pointers? You must be joking!
People tend to conflate garbage collection with Java's object model, but the two things are distinct. Most of the time when you're talking about performance limitations in Java, you're really concerned about Java's object model, not the GC.
Garbage collection limits your object model, but Java's is much more limited than required for garbage collection. For example, in C++, you might pass small structs on the stack or in registers, while in Java you pass a pointer to a heap allocated object. But there is no reason a garbage collector can't handle value objects allocated on the stack, and indeed the CLR supports that feature.
All a garbage collector prevents you from doing is hiding pointers in integers and the like. But that's not as significant a limitation as not being able to say flat arrays of structs, something that is totally compatible with garbage collection.
Garbage collection limits your object model, but Java's is much more limited than required for garbage collection. For example, in C++, you might pass small structs on the stack or in registers, while in Java you pass a pointer to a heap allocated object. But there is no reason a garbage collector can't handle value objects allocated on the stack, and indeed the CLR supports that feature.
All a garbage collector prevents you from doing is hiding pointers in integers and the like. But that's not as significant a limitation as not being able to say flat arrays of structs, something that is totally compatible with garbage collection.
Java value-types (+ arrays) are in the works. The JVM already does what is known as "scalar replacement" (http://www.stefankrause.net/wp/?p=64) automatically allocating some non-escaping objects on the stack.
I loathe the fact that all intermediate options get left off the table - reference-counting, or single-ownership-with-weak-references, or anything else short of memory-gobbling full GC that breaks your real-time guarantees.
And C++'s hideous shared_ptr system isn't a good thing to point to.
And C++'s hideous shared_ptr system isn't a good thing to point to.
If you have real-time requirements reference counting is worse than GC; it has the same problem of some operations sometimes taking an unexpectedly long amount of time, and the worst-case guarantees are weaker.
Single ownership with weak references is effectively what you have in C, though I guess compiler support for distinguishing which references are weak or strong is nice.
Single ownership with weak references is effectively what you have in C, though I guess compiler support for distinguishing which references are weak or strong is nice.
I believe "Hard Real-Time Reference Counting without External Fragmentation" By T Ritzau[1] solves the problem of unbounded reference counting times.
[1]Google has pdf. BTW, how do i extract a long living pdf link from a google link ?
[1]Google has pdf. BTW, how do i extract a long living pdf link from a google link ?
Weak reference implies a safe error result if you access a weak reference after a "strong" reference has been released, not undefined behavior. Not just a pointer.
For refcounting and real-time, just let me leak the cycles. The non-realtime part of reference counting is the cycle detection, let me control the cycle sweeps and everybody's happy.
For refcounting and real-time, just let me leak the cycles. The non-realtime part of reference counting is the cycle detection, let me control the cycle sweeps and everybody's happy.
> let me control the cycle sweeps and everybody's happy.
Maybe you are happy, but 99.9% of people would probably be very unhappy with that solution. How would you even go about accomplishing that in a way that wouldn't make you lose your mind? I can only imagine the complexity of having to decide how many cycle sweeps need to be done every time I reduce the reference count on an object/struct. I also think the runtime performance of enforcing that kind of limit would out way any possible benefit.
Maybe you are happy, but 99.9% of people would probably be very unhappy with that solution. How would you even go about accomplishing that in a way that wouldn't make you lose your mind? I can only imagine the complexity of having to decide how many cycle sweeps need to be done every time I reduce the reference count on an object/struct. I also think the runtime performance of enforcing that kind of limit would out way any possible benefit.
I think you are referring to deallocating an object graph. Under GC, the cost of deallocating an object graph depends on global state, such as how many unrelated objects are allocated. But in an RC scheme, the cost of deallocating an object graph depends only on that graph itself. This makes RC easier to reason about. The "unexpectedly long" cases can be isolated and optimized separately.
Consider a soft real-time environment like a game. Under RC, the time required to render a single frame depends only on the work done in that frame. Get it to 16 ms and you're done. But under GC, deallocation work can accumulate. A frame that would otherwise render in 16 ms may take much longer, due to the laziness of previous frames. That makes it harder to optimize, and indeed you'll often see advice like "frames must do zero GC allocations." Yikes!
Things may be different in hard real-time systems, which I know use specialized allocation schemes optimized for worst-case latency instead of bandwidth.
Consider a soft real-time environment like a game. Under RC, the time required to render a single frame depends only on the work done in that frame. Get it to 16 ms and you're done. But under GC, deallocation work can accumulate. A frame that would otherwise render in 16 ms may take much longer, due to the laziness of previous frames. That makes it harder to optimize, and indeed you'll often see advice like "frames must do zero GC allocations." Yikes!
Things may be different in hard real-time systems, which I know use specialized allocation schemes optimized for worst-case latency instead of bandwidth.
The stock malloc() in Linux, OS X, Windows, etc, can't make any sort of real time guarantee either.
Its interesting people forget that refcounting is quite cache destroying in the CPU, each upref invalidates memory locations in cache lines that are scattered throughout the address space.
The benefit of malloc/free (or new/delete) is that you have control over your own memory layout to handle optimizations like cache alignment, keeping relevant data contiguous, deferring pauses that would introduce latency and such.
Memory layout is a separate discussion. The kind of layout optimizations you're describing require work, and if you're willing to put in this work, you can do it in GCed environments as well (like the JVM, with finer-grained control coming in future versions).
Otherwise, several/most of the JVM's GCs do a very good job of handling this for you. Objects that were allocated consecutively by the same thread will tend to be kept close together in memory.
Otherwise, several/most of the JVM's GCs do a very good job of handling this for you. Objects that were allocated consecutively by the same thread will tend to be kept close together in memory.
That's contiguity but alignment is a different thing. At a certain point though, the two things become one and the same. On the one hand, you could put in layout optimizations in a GC system. On the other hand, you can use things like shared_ptr and effectively write your own GC even.
I guess the debate really isn't an A vs B thing. It's just a spectrum and deciding which side of the spectrum you want to start on.
I guess the debate really isn't an A vs B thing. It's just a spectrum and deciding which side of the spectrum you want to start on.
> you can use things like shared_ptr and effectively write your own GC even.
This is hardly the case, especially on modern multi-core hardware. Writing a GC that works well in a concurrent environment is a huge undertaking. And unless your system is very simple, you'll often be better off with a good general-purpose GC.
A shared_ptr introduces a lot of contention.
This is hardly the case, especially on modern multi-core hardware. Writing a GC that works well in a concurrent environment is a huge undertaking. And unless your system is very simple, you'll often be better off with a good general-purpose GC.
A shared_ptr introduces a lot of contention.
The thing is that most garbage generated is thread local. In fact, depending on the program, it's likely that most of it follows a stack discipline, albeit one that's not delimited by function boundaries.
A simple GC (or resettable arena allocator) can make use of this knowledge, and be quite a bit faster in those specific cases.
It's hard to beat the man years of work in generic GC that works in all cases, but it's not that hard to beat it in specific situations when the application author knows the details of how the application will do the allocations.
99% of the time, writing your own custom allocation strategies is a waste of time. Sometimes, though, it can be a win, allowing you to allocate and free in a matter of tens of CPU cycles with no GC pauses at all.
A simple GC (or resettable arena allocator) can make use of this knowledge, and be quite a bit faster in those specific cases.
It's hard to beat the man years of work in generic GC that works in all cases, but it's not that hard to beat it in specific situations when the application author knows the details of how the application will do the allocations.
99% of the time, writing your own custom allocation strategies is a waste of time. Sometimes, though, it can be a win, allowing you to allocate and free in a matter of tens of CPU cycles with no GC pauses at all.
>99% of the time, writing your own custom allocation strategies is a waste of time. Sometimes, though, it can be a win, allowing you to allocate and free in a matter of tens of CPU cycles with no GC pauses at all.
Agreed, but again, if you're willing to put that effort in you can do it in a GCed language.
Agreed, but again, if you're willing to put that effort in you can do it in a GCed language.
> What makes a difference is gc pauses. Imho if you can live without managed memory. You can do this in java as well and eliminate gc pauses.
Wait, how can you turn off GC'd managed memory in Java, and do it yourself? I didn't know you could do that in Java?
Wait, how can you turn off GC'd managed memory in Java, and do it yourself? I didn't know you could do that in Java?
You don't turn it off, but you can use off-heap memory (with direct ByteBuffers) and manage it yourself. Some Java applications manage some part of their memory off-heap, but this is a bad idea unless the allocated objects have a well-defined lifecycle.
Now everyone will tell you that you can use ByteBuffer or sun.misc.Unsafe to keep memory off-heap and hence out of sight of the GC.
BUT what that means is that you have create your own custom implementations of the data structures you need and you'll have to write your own memory allocator.
Unless that memory area holds just a simple data BLOB (like a video file) you're always going to be much more productive implementing the entire thing in C++.
BUT what that means is that you have create your own custom implementations of the data structures you need and you'll have to write your own memory allocator.
Unless that memory area holds just a simple data BLOB (like a video file) you're always going to be much more productive implementing the entire thing in C++.
> Unless that memory area holds just a simple data BLOB (like a video file) you're always going to be much more productive implementing the entire thing in C++.
Or use a GC enabled systems programming language, that provides control over what is allocated via GC or via other means.
Or use a GC enabled systems programming language, that provides control over what is allocated via GC or via other means.
You can even write c-like structs over byte-buffers - https://github.com/ztellman/vertigo
Same for plain Java instead of Clojure: http://javolution.org/target/site/apidocs/javolution/io/Stru...
> In my experience the biggest difference is stack allocation
This is the only voice of reason in this thread full of bullshit by monkeys who have obviously never used C to any extent.
This is the only voice of reason in this thread full of bullshit by monkeys who have obviously never used C to any extent.
Current-generation garbage collectors have far better performance, and many research GCs support concurrent, pause-free collection.
(And that leaves aside the non-performance benefits of a GC, in terms of engineering simplicity and bug elimination.)