That all depends on how you manually manage memory. Older versions of malloc performed poorly with frequent allocations.
Bohem GC allocates in large(ish) slabs, so it can manage many small objects more efficiently than OS malloc. Modern malloc replacements like jemalloc also do this for manual allocation.
Malloc() is easy to write in multi-threaded environments. You can just have per-thread pools of allocable memory, which is what most multi-threaded mallocs do. Free() on the other hand isn't. Among other things, what do you do when you free an object? You can return the freed memory to the local pool of the thread that does the free() operation, but that can result in pathological behavior when, e.g. one thread consistently allocates objects while another frees them. In that case, a bunch of free memory accumulates in one thread. Production multi-threaded allocs have mechanisms to rebalance these per-thread pools, but that involves synchronization overhead.
If most objects die before a GC cycle, it can be faster to just stop all threads and reclaim that memory in bulk as Boehm does.
That seems independent of tracing GC versus manual memory management, though, doesn't it? jemalloc/tcmalloc could stop all threads and flush pools in bulk as well if it decided that it was faster to do so. (From looking at the code, jemalloc doesn't, but it could.)
More broadly, if batched deallocation is indeed faster, you can get that behavior in a manually memory-managed scenario. You aren't forced into prompt reclamation. It's just that prompt reclamation is usually faster for cache reasons and improves memory consumption, so malloc implementations take advantage of the opportunity.
Fans of GC claim that GC outperforms malloc() based on some studies that were done a long time ago. The argument is that repeated malloc/frees are less efficient than a bunch of GC allocs and then a single garbage collection.
The reality seems to be a bit different. In practice GC programs tend to use significantly more memory which can impact performance. And the trend towards low GC pause times costs additional CPU. Beyond that we're now using much larger multi gigabyte GC memory pools which can also lead to poor GC performance.
So overall people these days see lower performance with GC systems compared to malloc.
They are only talking about slow, conservative, stop-the-world collectors there.
They have to scan the full heap. You shouldn't compare apples with oranges.
I find the methodology of the research to be solid, the collectors to be representative of the different approaches in the field and the conclusions to be consistent with the gut feeling from experience:
"With only three times as much memory, the collector runs on average 17% slower than explicit memory management. However, with only twice as much memory, garbage collection degrades performance by nearly 70%."
> In practice GC programs tend to use significantly more memory which can impact performance
In which language ?
There are GC enabled programming languages with global and stack static allocation, for example Oberon just to cite one, which was on top HN a few days ago.
Many of the claims that GC outperforms manual memory management compare running dlmalloc to allocate all data with a well-tuned generational garbage collector on something like the Da Capo benchmark suite. Naturally, they find that the ability to get bump allocation in the nursery of a good generational GC ends up outperforming a malloc implementation that was never really designed for that kind of workload.
But the real question, in my mind, is whether a well-tuned systems-level program that uses stack, arena, and heap allocation with a good allocator like jemalloc ends up being better with a garbage collector. And it's really hard for me to see how that could possibly be the case. Performance-conscious systems programmers will use the stack as their nursery, gaining all the benefits of the nursery without the copying, tracing, or delayed reclamation. Modern mallocs like jemalloc or tcmalloc are incredibly good at minimizing fragmentation and satisfying requests quickly, using thread-local caches to avoid synchronization. Most of the time, the tenured generation needs the same bookkeeping that a modern malloc does, so you're not really gaining anything by using GC for that generation. And a GC always has some kind of mark or tracing phase (not to mention at least a write barrier if you want your pause times to be reasonable), which is pure overhead over manual memory management.
Yes, but in a language like Modula-3 you can have your "well-tuned systems-level program that uses stack, arena, and heap allocation with a good allocator", and still have a GC at your disposal.
Sadly HP/Compaq killed the Olivetti/Digital unit and Modula-3 died, but its ideas can still be applied in modern languages, assuming similar capabilities.
You can often trade space complexity for time complexity and concurrency. Garbage collectors typically require integer multiples of the memory footprint of manual memory management to offset the higher intrinsic computational cost of garbage collection algorithms. While malloc() has much less work to do, the default malloc() is often not that fast and it is possible in principle to design a garbage collector that can leverage space complexity to beat the generic malloc().
The caveat is that properly engineered C/C++ hardly ever uses malloc() or similar to manage memory. Relative performance in real systems would be between a garbage collector and one of myriad not-malloc() mechanisms typical of C/C++ that are much faster and often safer than using malloc().
If you are among that subset of programmers that uses malloc() ubiquitously, an argument might be made that a garbage collector is a better choice if you have plenty of memory. However, this argument would be about safety; if you are using malloc() ubiquitously then you obviously do not care about performance prima facie.
This is an argument I don't understand. It is exceedingly common for performance sensitive applications in GC environments not to allocate either, because quite simply allocating/deallocating in any environment is expensive.
Why in the world is it fair to compare C/C++ programs that don't allocate to Java/C# ones that do? Another way of saying this is if you are using new ubiquitously then you obviously do not care about performance prima facie.
At the end of the day GC'd versus manual memory debates seem to fall into 2 axis. Complexity vs correctness and total memory available vs concurrent access to said memory.
At this point in time the difference in performance between a C application and a Java one comes down to correctness and access to low level memory layout primitives, not GC vs manual memory.
> This is an argument I don't understand. It is exceedingly common for performance sensitive applications in GC environments not to allocate either, because quite simply allocating/deallocating in any environment is expensive.
Is that possible? I thought all objects are heap allocated in Java?
No this is bad advice in general! It causes the objects to permanently escape, with the knock-on that any objects stored in that object will also escape etc etc, and to move to the old generation. If you need objects, allocate and use them where you need them. This is more likely to allow scalar replacement, or at least more efficient collection while still in the young generation.
In theory, this sounds true. In practice, it isn't. I've done pooled versus non-pooled tests of objects like Vector3's in libgdx and the difference in memory pressure is fairly huge.
The JVM is really, really smart, but this is a well-understood area where you sometimes have to break the rules and do something stupid (and it is stupid) for the sake of perf.
Primitives aren't allocated. This is why we have `int` and `Integer`; Integer is a boxed int. Java has a fair amount of sugar around doing the change automagically.
Fun fact! Original Java, before they started adding autoboxing, had precisely one place which did heap allocation: the 'new' keyword (which is why it was a keyword). If you avoided the keyword, you could be sure you weren't using the heap.
...which meant you could run (a limited subset of) Java programs on very, very small devices. 8-bit microcontrollers. Such as Maxim's iButton devices, or smart cards.
My memory says that the standard is called kJava, but it seems to be ungoogleable these days, so I could be wrong (and Oracle ate all of Sun's documentation).
I think the primary reason is an accident of history. There was a time where Java programmers were encouraged to not even think about allocation deallocation: "dont worry about it, we have it all covered, use it as freely as free love". The result of all that was a lot of bloated poorly performing software that paid no attention to how much allocations they were making. I still see the effects of that propaganda on many junior programmers. GC makes it safe, not free, and that message was never stressed as much it should have been.
The other reason is that languages that make you allocate explicitly with some burdensome syntax, that allocation is in your face, you cannot be unaware of it. Whereas in other languages someone may be blissfully unaware and still churn out pieces of usable software. The bite comes much later. On languages that were not designed around garbage collection, it is usually a whole lot harder to avoid allocation.
There were other factors at play during this time which roughly coincided with the Dot Come Boom/Bust. In those days it was ship or die, "money was no object" (unintentional pun) and Sun would be happy to spend people out of their perf well by adding more cpus and ram.
> The caveat is that properly engineered C/C++ hardly ever uses malloc() or similar to manage memory.
"Properly engineered" probably isn't the right term. C/C++ code written for speed would not perform heap allocation in its main processing. However, this is true with garbage collected languages as well.
Removing allocation means removing an entire class of data management operations from your program regardless of the language's memory architecture. It's a general speed-optimizing programming style that is irrelevant to manual vs automatic GC.
Relative performance in "real systems" written for speed would be a manual memory management language without using malloc/free, vs GC language without using allocation. However, the more interesting case is comparing real systems which do perform runtime allocation; it's highly dependent on the particular program's characteristics, but GC systems can be both a lot faster and simpler architecturally.
While you're right in theory, it's typically much less feasible to avoid heap allocations in garbage-collected languages. Systems programmers typically manually promote heap allocations to stack allocations in ways that common escape analysis algorithms cannot prove safe (for example, those involving higher order functions).
>However, this is true with garbage collected languages as well.
In theory - in practice trying to avoid GC in managed languages is like putting on a straightjacket, eg. JVM doesn't even have value types, and higher level languages - just forget about it :D
The closest I realistically got to this is C# and even then there are all sort of caveats because even if your code doesn't allocate it's a standard pattern to not care about allocation and stuff allocates all over the place and there are no tools to figure out what allocates and what doesn't from code so you just have to assume everything does unless you wrote it or read/profiled it.
Oberon, Oberon-2, Component Pascal, Modula-3, D, Eiffel all provide C++ like value types.
Arrays, records, objects can be stored on the global segment, stack or heap. So they stress the GC as much as new/malloc stress the C/C++ memory manager.
> "Properly engineered" probably isn't the right term. C/C++ code written for speed would not perform heap allocation in its main processing. However, this is true with garbage collected languages as well.
Not just code written for speed. Stack allocation is easier. There's not much that can go wrong. Heap allocations on the other hand you have to be careful not to leak or free multiple times or free a wrong pointer. So after you've debugged one too many of these bugs, you learn to avoid heap allocations where possible just to make your own life easier.
(This is my experience with C, I don't have enough experience with C++ to know whether it sufficiently takes care of some of that complexity to the point where heap allocation becomes as easy as stack allocation.)
I like that it can be used as a leak detector! I'm not sure I understand the point beyond that but then again I am in love with RAII semantics so I'm probably a bit biased here.
Consider it a safeguard. One one hand it can detect (some) leaks. On the other hand if/when your app leaks it can mitigate the consequences of those leaks.
For some very specific types of apps it can also be sufficient to ditch traditional C/C++ memory management, and you can actually even gain speed doing so.
Consider e.g. code that runs a job. Most of the time you know it will need less than 32MB (or whatever) total over the (short) lifetime of the process.
So you tune the GC accordingly to not trigger any collection at all until above that level. Now most of time, a collection will never get triggered, and you're happy - all the memory is just returned to the system at the end in one swoop.
But if occasionally a job requires lots more, the GC may provide sufficient cleanup to still make it viable not to include any memory management.
My first large CGI-era webapp was in C++ and relied exactly on lots of hacks like deferring all memory de-allocation until exit to improve performance (and it worked very well - it had a considerable performance impact; other hacks included static linking to drastically cut the loading cost). We didn't use a GC; instead we had to take extra care when we knew we were going to make large allocations to do manual de-allocation in those cases if the request was potentially long-running. I'd have loved to use the Boehm GC for that.
This has been around for a long time. The problem is, GC is not just something you can bolt on, it's a fundamental part of the language that colors everything you write -- and it fundamentally clashes with the way C++ is normally written.
In particular, C++ (and Rust, etc.) stresses RAII (Resource Acquisition Is Initialization), in which you write classes with destructors that cause the object to release its resources as soon as it goes out of scope. "Resources" here often means heap memory, but can also mean a whole lot of other things (file handles, child processes, network connections, arbitrary resources on remote network services, etc.).
In GC'd languages, the GC really only handles heap memory. Yes, you can sometimes rely on finalizers to free other kinds of resources, but generally you will find this doesn't work out well: most GC algorithms do not make any guarantees about how soon an unreachable object will be cleaned up, and they tend to use heuristics that assume that the cost of not cleaning up an object is exactly whatever RAM it is using, nothing more. Often, if your process is not allocating any new objects, the GC will never run at all.
Thus in GC'd languages you often see classes with methods like `.close()` or `.dispose()` for eagerly releasing non-local resources. These resources have to be managed manually, just like heap has to be managed in non-GC languages. The beauty of RAII is that you can use it to manage any kind of resource, but GC languages don't typically support RAII because it does not mix well with GC semantics.
These differences completely change how APIs in these languages are designed. Essentially, adding GC to a language -- or removing it -- gives you a different language that happens to share some syntax, and probably not a very good language since all that syntax was designed around a fundamental assumption that no longer holds.
I kind of wonder if a preference for GC languages is in part responsible for the way distributed systems are typically designed these days -- namely, the emphasis on stateless servers, which avoids the need to do remote resource management (which is hard without RAII), at the expense of requiring a lot more machinery to make performant (e.g. complicated caching layers because all state changes have to hit storage which is sllloowwwwwww).
> The problem is, GC is not just something you can bolt on, it's a fundamental part of the language that colors everything you write -- and it fundamentally clashes with the way C++ is normally written.
C++ and C yes, because these are systems languages where everything goes, which make impossible to apply certain classes of GC algorithms.
Apple's failure to make one work in Objective-C is proof of that.
However there were systems programming languages with GC, like Cedar, Oberon and Modula-3. Just like C++, with value by default, stack allocation and since they are safe by default, requiring explicit unsafe blocks, their GCs were better than anything C or C++ can ever get.
Still, ANSI C++11 did get a GC pluggable API.
> these resources have to be managed manually, just like heap has to be managed in non-GC languages.
Only if the programmers are too lazy to learn how to make use of using/try-resource/defer/scope, or higher order functions.
But GC critics always fail to acknowledge these language features.
> using/try-resource/defer/scope, or higher order functions
Those only cover cases where your resource's lifetime matches a stack frame's lifetime. It doesn't cover the case where your resource's lifetime matches the lifetime of some owner object. For that you need destructors, by definition.
Ownership transfer is also very hard to model robustly unless you have linear types / move semantics (which even C++ didn't really have until C++11).
You can map them into higher level constructs that basically are a kind of reference counting on top of GC.
For example, multiple threads sharing a socket connection. Just create a barrier and have a cleanup thread closing the socket when everyone joins.
Similar patterns can be applied to other resources.
Ownership transfer is usually not an issue in GC enabled languages in terms of data structures, specially if every thread keeps the OS resources locally for itself.
>
You can map them into higher level constructs that basically are a kind of reference counting on top of GC.
> For example, multiple threads sharing a socket connection. Just create a barrier and have a cleanup thread closing the socket when everyone joins.
Nobody's saying you can't do it. But RAII makes it way easier.
When you implement reference counting manually, you'll find that you want something like a copy constructor, so you remember to bump the reference count every time a new instance of the object is assigned. Then you find that you'll want the compiler to automatically drop reference counts when the object goes out of scope, so you don't forget. Then you'll find you want move semantics, to allow transfer of references without adjusting the counts. You'll discover you want the correct behavior in the presence of exceptions. In short, you want RAII.
> Nobody's saying you can't do it. But RAII makes it way easier.
Except RAII doesn't work for heap allocated object and then it is back to reference counting.
> You'll discover you want the correct behavior in the presence of exceptions. In short, you want RAII.
Well, then one would have implemented a GC by hand with worse performance, specially in multi-threading contexts, unless there is someone on the team expert in hazard pointers and related performance tricks.
Maybe a performance improvement would be for the ANSI C++ standard to mandate that that compilers give special treatment to *_ptr<>(), so that they can elide needless calls, but I don't see it happening.
In FP languages one can use the concept of transactions, yes the M word, to encapsulate scope based workflows where the resources are to be released at the end.
What I can definitely see killing GC is affine types becoming mainstream, but they need to be made more friendly for the average Joe developer. Rust made them easier than ATS or Cyclone, but still a bit hard.
I think ParaSail's work might also be worth checking in this regard.
It is, but I don't consider it much more manual, as it is done with help of the threading library and super easy in many languages with rich runtime libraries.
Edit: I forgot to say that this is no much different that doing RAII FP style. Those M concepts are great.
Could. A hypothetical new language could be created to facilitate whole-program escape analysis and thus completely avoid both GC and manual memory (resource) management.
>But there is no reason that the RAII pattern couldn't be completely orthogonal to memory management
GC + destructors = very very messy even in languages built with GC in mind, kentonv described the whole non deterministic finalizers nicely but there are also other problems see here :
You could do that, but if you are using RAII, then GC has lost a lot of its value. It is incorrect to access an object after its destructor has executed, so you might as well release its heap resources then and ditch the whole complicated GC.
I suppose in theory you could use GC just for objects that (transitively) don't hold any non-heap resources. But that gets a little weird as if you ever device that you need to stick a non-heap resource in there, suddenly all your code needs to change. (Of course, this is already generally the case in GC languages...)
Thanks for this very informative comment. I had not thought of "close()" and "dispose()" functions as the manual operations equal to manual memory management, but on reflection this is what it boils down to.
The GC won't do anything for stack allocated objects so you can still use the RAII goodness for all of those. You just don't also need to use things like `std::unique_ptr` and `std::shared_ptr` to manage heap allocated objects.
While in C++, RAII is a good practice, it has it's fair share of problems you should not ignore. Debugging, profiling and unit testing are a bitch. Performance becomes completely unpredictable in more complex applications. And then error handling.... Destructors shouldn't throw exceptions - and you don't have any other choice than just catch them all and 'log and forget' - which can be seriously problematic.
Both RAII and the explicit cleanup of resources have their advantages and serious disadvantages. In C++ you better use RAII, in GC'd language, use explicit cleanup. What is better depends on the language.
> I kind of wonder if a preference for GC languages is in part responsible for the way distributed systems are typically designed these days -- namely, the emphasis on stateless servers, which avoids the need to do remote resource management (which is hard without RAII), at the expense of requiring a lot more machinery to make performant (e.g. complicated caching layers because all state changes have to hit storage which is sllloowwwwwww)
Don't wonder, they're not related at all. We have a few stateless services running that are written in C++. They are the only sane option once you start working beyond a certain scale - which is the point when you decide you need a distributed system. The reason for them being stateless is simple: nodes WILL fail. Hardware failures, power outages, line cuts, ... This is not the reason for 'more machinery'. Resource cleanup is hardly a bottleneck? RAII does this for you, but the only difference with GC'd languages is that you need to do this cleanup yourself.
There are other reasons for having to add 'more machinery' to make things performant: going for 'easy' scripting languages to get things up and running in record time - which is important for startups to have something to show for as quickly as possible. Performance at that moment takes a back-seat, and it's hard to go back. Micro-services are becoming a trend for this reason too - you can quickly write your services in <slow hipster scripting language>, get everything up & running, identify your bottlenecks and optimize them. Just look at the upcoming trend there for 'optimizing' distributed applications is to rewrite parts of your service in Go, which is a native compiled GC'd language. Easy to write, little memory overhead with decent execution speed, and designed to do concurrency well. Does it compete with C++? Not at all, but it gets things done that would be pretty damn annoying to do in C++ - and it does it with little memory and CPU overhead.
That - or going for some Java enterpricy application with tons of frameworks which eats up all your memory. Hello 32-core machine with 96Gig ram to generate some silly reports.
> Just look at the upcoming trend there for 'optimizing' distributed applications is to rewrite parts of your service in Go, which is a native compiled GC'd language.
In a way, Java's success was a nail in the coffin of languages like Oberon(-2), Component Pascal and Modula-3, besides the other nails those languages got.
Otherwise we could already be enjoying native compiled GC'd language in the last 20 years, also for systems programming.
> That - or going for some Java enterpricy application with tons of frameworks which eats up all your memory. Hello 32-core machine with 96Gig ram to generate some silly reports.
Yes, that's the standard thinking on distributed systems. I worked on infrastructure at Google for 7.5 years, so I do have some idea how that works.
However, lately I've been building a very stateful distributed system and finding that I can do a lot more with a lot less code and a lot better performance -- while still handling failures just fine.
This is a complex topic and I can't do it justice in an HN post. But, basically, while you always have to be prepared to start over in case of failure, "starting over" on every single request is overkill and adds all kinds of complication and latency to the system. If you instead permit yourself to set up some state and only start over when there's a problem, you can do a lot better.
I'm not a big fan of RAII because it falsely conflates lifetime with reachability. This assumption breaks under a number of circumstances, e.g.:
* Closures capturing their environment and keeping local variables alive longer than intended.
* Debugging code keeping a record of objects.
In either case, you have likely failure modes in that either the resource can be deallocated prematurely and then accessed through a stale reference or that it is kept around longer than its intended lifetime.
RAII also does not provide a solution to a number of resource management scenarios, such as requiring access to an unbounded number of resources of which only a finite number can be reified at any time (e.g. due to the maximum number of file handles a process can manage). The obvious solution – a caching mechanism that will disconnect a resource from its in-memory representation upon eviction and reconnect when it is being used again – needs to attach itself to resource usage, not resource creation and destruction.
Most scenarios where RAII is being used are either trivially handled in any language that supports closures or macros, or benefit from explicit reasoning about resource lifetime, anyway.
Speaking of closures, I think it's no coincidence that RAII first arose in a language that until recently had no such concept; closures both create problems for RAII and also obviate many common use cases.
* Closures capturing their environment and keeping local variables alive longer than intended.
How can that happen to a stack variable (and RAII is about those), given C++11/14's closures ("lambdas") do not prolongate the lifetime of the objects captured by reference? Or did you mean capture by value? (would be really confusing with RAII-ing classes :) )
Properly executed RAII, at least in C++, should never break in the two cases you mention.
The RAAI object should be non-copyable (no copy constructor in C++), so the only way it can be passed by value to a closure is with an explicit move operation, which is not something you would do on mistake. The original copy would now revert to a proper "uninitialized" or "closed" state. Debuggers too are usually well aware of out-of-scope objects, so I don't see the point here.
As for complex scenarios, they are probably less than 1% of the time you'd use RAAI. When you do have complex scenarios that need techinques like caching and pooling - well, yeah, RAAI won't solve them on its own, but the same goes for macros and closures.
Besides that, most RAAI uses just can't be replaced by closures, since you cannot break a loop or return a value from within a closure, for instance (Ruby procs can do that, but there's no equivalent to that in most languages). And both a closure-based and a macro-based solution quickly become an unwieldy nest-fest once you need to deal with multiple resources in a row.
> Properly executed RAII, at least in C++, should never break in the two cases you mention.
So, std::shared_ptr (or anything else that does reference counting) is not properly executed RAII?
> Debuggers too are usually well aware of out-of-scope objects, so I don't see the point here.
I wasn't talking about debuggers, but code that is enabled for debugging purposes. E.g. globally remembering the last N objects passed to a function.
My larger point is that either lifetime or reachability is off. You either have a resource that can still be accessed through a stale handle even though it's been deallocated or one that remains allocated past its intended lifetime.
> closures both create problems for RAII and also obviate many common use cases.
As someone who uses a lot of closures and a lot of RAII, together, I can assure you this is not the case:
- C++ closures are very explicit about what is captured and how (by reference, by copy, by move/ownership transfer). It actually works incredibly well with RAII.
- Closures as an alternative to RAII only works in a small subset of use cases: cases where the resource lifetime is bound to a stack frame. They do not easily model resources owned by objects, nor (ironically) resources used in an asynchronous callback context.
BTW, Rust actually statically guarantees no dangling pointers -- without using GC. And yes, it has closures.
> don't typically support RAII because it does not mix well with GC semantics
Just to expand on this a little, one problem is that no matter how you collect a cycle of objects with finalizers, one of them will see the others in a finalized state. Another problem is resurrection, where the finalizer creates a new reference to self or another finalized object. You could try solving these problems by nulling all references to finalized objects (including self) during GC, but that makes finalizers useless. I don't know any good solution.
Lisp does the equivalent of scope-level RAII with macros. For instance,
(with-open-file (myfile "foo.txt")
...body...)
will execute the body with the opened file bound to variable MYFILE, closing it when the end of the body is reached (or is unrolled away).
Many libraries expose this type of interface, and by Lisp's use of dynamic scoping, nested functions within the scope can access the current state of that particular scoped resource without having to pass it around manually.
In effect, RAII is programmer discipline which can manually repurpose a particular object allocation/deallocation style to support scope behavior, while languages like Lisp can simply work with scope behavior directly.
Would it be conceivable to implement Automatic Reference Counting for C/C++? Basically gets you the advantages of GC without the performance impact of GC cycles, because it does all its magic at compile time.
On a related note I'm excited about Apple open sourcing and porting Swift to Linux with an eye towards server-side code, specifically because of ARC. Garbage collection has been a concern for web services in particular when it comes to 99th percentile latency. Things run fine and then boom, GC runs, slowing down a few unlucky requests. ARC just makes memory-management performance deterministic, no tuning needed.
ARC actually has some interesting advantages over smart pointers. For one, there is a large amount of static analysis done at compile time that allows the system to avoid unnecessary increment/decrements of the reference counter - this can have significant performance improvements in tight inner loops, and can't be achieved using smart pointers.
My experience has been that the awesomeness of ARC's optimizations is greatly overstated. The compiler inserts retain/release pairs around every operation that could potentially need them, and then the optimizer eliminates the redundant ones. Pretty much the only interesting nonlocal optimization it does it turn autoreleased return values into retained returns, which isn't an issue for shared_ptr to begin with.
RAII in C++ solves the same problems as ARC in Obj-C, just don't use raw pointers but smart pointers. But having said that, both approaches are bad. ARC is sort of a crutch in Objective-C because objects are usually (mostly? always?) created on the heap (C++'s equivalent would be new() or make_shared()), but in C++ it is possible (and good style) to minimize this type of 'fine-grained' heap-object usage as much as possible, otherwise you have this huge soup of tiny objects all over the place and a lot of pointer-chasing and cache misses, good luck getting sensible performance out of this mess. It's usually a broken C++ coding-style like this when Java-, C#- or Objective-C benchmarks can claim that they are 'even faster then C++' ;)
Any garbage collection algorithms (of which reference counting algorithms is a subset) for C/C++ need to deal with the fact that it is not possible to do a fully generic gc for C/C++ without either a) being conservative (that is, you will miss out on some memory) or b) putting additional constraints on the developers that the language doesn't.
So yes, you can do ARC for C/C++, but it would need to be opt-in, and it would not be sufficient for all memory allocation in C/C++ because the moment you link in a third party library that doesn't play ball you need to do things differently.
The chosen approach in C++ has largely "smart pointers" - template classes that implement various reference counting semantics - coupled with RAII.
E.g. one part of the problem for a fully generic solution in C/C++ is that in C/C++ nothing stops you from taking an arbitrary bit-pattern and treating it as a pointer and vice versa. As an example, take BPTR's in AmigaOS - core parts of AmigaDOS were written on contract due to time constraints, and they were written in BCPL, and that's where they came from.
BPTR's were pointers that had been bit-shifted right two bits - basically BCPL was treating memory as an array of 32bit quantities. So a lot of pointers in AmigaOS are stored in memory as values that don't actually match any memory address. So one hand your compiler don't know when/where to apply a reference count, and on the other hand a generic non-ref-counting gc won't know whether or not any specific value is a pointer, and if so whether it meant to point at the actual memory address indicated by the value or if it needs to be bit-shifted.
In C this is perfectly legal. But to gc apps that do stuff like that, your gc must either be smart enough to figure out every possible pointer manipulation (meet the halting problem, it wants to have a word), or it needs explicit support from the developer.
What about scalability, if you have more than a few CPU cores? You know how expensive atomic fetch-and-add (aka LOCK XADD) is, right? Atomic compare-and-swap loop is even worse.
Put simply, those things broadcast coherence information on inter-core (and inter-processor) network.
It's ok for a low number of cores, but this solution just won't work well with more CPU cores.
77 comments
[ 1.4 ms ] story [ 156 ms ] threadEdit: That is, is it typical for GCd programs to outperform manually-memory managed programs in multi-threaded environments?
Bohem GC allocates in large(ish) slabs, so it can manage many small objects more efficiently than OS malloc. Modern malloc replacements like jemalloc also do this for manual allocation.
If most objects die before a GC cycle, it can be faster to just stop all threads and reclaim that memory in bulk as Boehm does.
More broadly, if batched deallocation is indeed faster, you can get that behavior in a manually memory-managed scenario. You aren't forced into prompt reclamation. It's just that prompt reclamation is usually faster for cache reasons and improves memory consumption, so malloc implementations take advantage of the opportunity.
The reality seems to be a bit different. In practice GC programs tend to use significantly more memory which can impact performance. And the trend towards low GC pause times costs additional CPU. Beyond that we're now using much larger multi gigabyte GC memory pools which can also lead to poor GC performance.
So overall people these days see lower performance with GC systems compared to malloc.
"With only three times as much memory, the collector runs on average 17% slower than explicit memory management. However, with only twice as much memory, garbage collection degrades performance by nearly 70%."
In which language ?
There are GC enabled programming languages with global and stack static allocation, for example Oberon just to cite one, which was on top HN a few days ago.
But the real question, in my mind, is whether a well-tuned systems-level program that uses stack, arena, and heap allocation with a good allocator like jemalloc ends up being better with a garbage collector. And it's really hard for me to see how that could possibly be the case. Performance-conscious systems programmers will use the stack as their nursery, gaining all the benefits of the nursery without the copying, tracing, or delayed reclamation. Modern mallocs like jemalloc or tcmalloc are incredibly good at minimizing fragmentation and satisfying requests quickly, using thread-local caches to avoid synchronization. Most of the time, the tenured generation needs the same bookkeeping that a modern malloc does, so you're not really gaining anything by using GC for that generation. And a GC always has some kind of mark or tracing phase (not to mention at least a write barrier if you want your pause times to be reasonable), which is pure overhead over manual memory management.
Sadly HP/Compaq killed the Olivetti/Digital unit and Modula-3 died, but its ideas can still be applied in modern languages, assuming similar capabilities.
The caveat is that properly engineered C/C++ hardly ever uses malloc() or similar to manage memory. Relative performance in real systems would be between a garbage collector and one of myriad not-malloc() mechanisms typical of C/C++ that are much faster and often safer than using malloc().
If you are among that subset of programmers that uses malloc() ubiquitously, an argument might be made that a garbage collector is a better choice if you have plenty of memory. However, this argument would be about safety; if you are using malloc() ubiquitously then you obviously do not care about performance prima facie.
Why in the world is it fair to compare C/C++ programs that don't allocate to Java/C# ones that do? Another way of saying this is if you are using new ubiquitously then you obviously do not care about performance prima facie.
At the end of the day GC'd versus manual memory debates seem to fall into 2 axis. Complexity vs correctness and total memory available vs concurrent access to said memory.
At this point in time the difference in performance between a C application and a Java one comes down to correctness and access to low level memory layout primitives, not GC vs manual memory.
Is that possible? I thought all objects are heap allocated in Java?
The JVM is really, really smart, but this is a well-understood area where you sometimes have to break the rules and do something stupid (and it is stupid) for the sake of perf.
Also escape analysis is a thing Java can do to avoid heap allocating objects in general: https://docs.oracle.com/javase/7/docs/technotes/guides/vm/pe...
...which meant you could run (a limited subset of) Java programs on very, very small devices. 8-bit microcontrollers. Such as Maxim's iButton devices, or smart cards.
My memory says that the standard is called kJava, but it seems to be ungoogleable these days, so I could be wrong (and Oracle ate all of Sun's documentation).
The other reason is that languages that make you allocate explicitly with some burdensome syntax, that allocation is in your face, you cannot be unaware of it. Whereas in other languages someone may be blissfully unaware and still churn out pieces of usable software. The bite comes much later. On languages that were not designed around garbage collection, it is usually a whole lot harder to avoid allocation.
"Properly engineered" probably isn't the right term. C/C++ code written for speed would not perform heap allocation in its main processing. However, this is true with garbage collected languages as well.
Removing allocation means removing an entire class of data management operations from your program regardless of the language's memory architecture. It's a general speed-optimizing programming style that is irrelevant to manual vs automatic GC.
Relative performance in "real systems" written for speed would be a manual memory management language without using malloc/free, vs GC language without using allocation. However, the more interesting case is comparing real systems which do perform runtime allocation; it's highly dependent on the particular program's characteristics, but GC systems can be both a lot faster and simpler architecturally.
In theory - in practice trying to avoid GC in managed languages is like putting on a straightjacket, eg. JVM doesn't even have value types, and higher level languages - just forget about it :D
The closest I realistically got to this is C# and even then there are all sort of caveats because even if your code doesn't allocate it's a standard pattern to not care about allocation and stuff allocates all over the place and there are no tools to figure out what allocates and what doesn't from code so you just have to assume everything does unless you wrote it or read/profiled it.
Arrays, records, objects can be stored on the global segment, stack or heap. So they stress the GC as much as new/malloc stress the C/C++ memory manager.
Not just code written for speed. Stack allocation is easier. There's not much that can go wrong. Heap allocations on the other hand you have to be careful not to leak or free multiple times or free a wrong pointer. So after you've debugged one too many of these bugs, you learn to avoid heap allocations where possible just to make your own life easier.
(This is my experience with C, I don't have enough experience with C++ to know whether it sufficiently takes care of some of that complexity to the point where heap allocation becomes as easy as stack allocation.)
For some very specific types of apps it can also be sufficient to ditch traditional C/C++ memory management, and you can actually even gain speed doing so.
Consider e.g. code that runs a job. Most of the time you know it will need less than 32MB (or whatever) total over the (short) lifetime of the process.
So you tune the GC accordingly to not trigger any collection at all until above that level. Now most of time, a collection will never get triggered, and you're happy - all the memory is just returned to the system at the end in one swoop.
But if occasionally a job requires lots more, the GC may provide sufficient cleanup to still make it viable not to include any memory management.
My first large CGI-era webapp was in C++ and relied exactly on lots of hacks like deferring all memory de-allocation until exit to improve performance (and it worked very well - it had a considerable performance impact; other hacks included static linking to drastically cut the loading cost). We didn't use a GC; instead we had to take extra care when we knew we were going to make large allocations to do manual de-allocation in those cases if the request was potentially long-running. I'd have loved to use the Boehm GC for that.
http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...
In particular, C++ (and Rust, etc.) stresses RAII (Resource Acquisition Is Initialization), in which you write classes with destructors that cause the object to release its resources as soon as it goes out of scope. "Resources" here often means heap memory, but can also mean a whole lot of other things (file handles, child processes, network connections, arbitrary resources on remote network services, etc.).
In GC'd languages, the GC really only handles heap memory. Yes, you can sometimes rely on finalizers to free other kinds of resources, but generally you will find this doesn't work out well: most GC algorithms do not make any guarantees about how soon an unreachable object will be cleaned up, and they tend to use heuristics that assume that the cost of not cleaning up an object is exactly whatever RAM it is using, nothing more. Often, if your process is not allocating any new objects, the GC will never run at all.
Thus in GC'd languages you often see classes with methods like `.close()` or `.dispose()` for eagerly releasing non-local resources. These resources have to be managed manually, just like heap has to be managed in non-GC languages. The beauty of RAII is that you can use it to manage any kind of resource, but GC languages don't typically support RAII because it does not mix well with GC semantics.
These differences completely change how APIs in these languages are designed. Essentially, adding GC to a language -- or removing it -- gives you a different language that happens to share some syntax, and probably not a very good language since all that syntax was designed around a fundamental assumption that no longer holds.
I kind of wonder if a preference for GC languages is in part responsible for the way distributed systems are typically designed these days -- namely, the emphasis on stateless servers, which avoids the need to do remote resource management (which is hard without RAII), at the expense of requiring a lot more machinery to make performant (e.g. complicated caching layers because all state changes have to hit storage which is sllloowwwwwww).
C++ and C yes, because these are systems languages where everything goes, which make impossible to apply certain classes of GC algorithms.
Apple's failure to make one work in Objective-C is proof of that.
However there were systems programming languages with GC, like Cedar, Oberon and Modula-3. Just like C++, with value by default, stack allocation and since they are safe by default, requiring explicit unsafe blocks, their GCs were better than anything C or C++ can ever get.
Still, ANSI C++11 did get a GC pluggable API.
> these resources have to be managed manually, just like heap has to be managed in non-GC languages.
Only if the programmers are too lazy to learn how to make use of using/try-resource/defer/scope, or higher order functions.
But GC critics always fail to acknowledge these language features.
Those only cover cases where your resource's lifetime matches a stack frame's lifetime. It doesn't cover the case where your resource's lifetime matches the lifetime of some owner object. For that you need destructors, by definition.
Ownership transfer is also very hard to model robustly unless you have linear types / move semantics (which even C++ didn't really have until C++11).
For example, multiple threads sharing a socket connection. Just create a barrier and have a cleanup thread closing the socket when everyone joins.
Similar patterns can be applied to other resources.
Ownership transfer is usually not an issue in GC enabled languages in terms of data structures, specially if every thread keeps the OS resources locally for itself.
> For example, multiple threads sharing a socket connection. Just create a barrier and have a cleanup thread closing the socket when everyone joins.
Nobody's saying you can't do it. But RAII makes it way easier.
When you implement reference counting manually, you'll find that you want something like a copy constructor, so you remember to bump the reference count every time a new instance of the object is assigned. Then you find that you'll want the compiler to automatically drop reference counts when the object goes out of scope, so you don't forget. Then you'll find you want move semantics, to allow transfer of references without adjusting the counts. You'll discover you want the correct behavior in the presence of exceptions. In short, you want RAII.
Except RAII doesn't work for heap allocated object and then it is back to reference counting.
> You'll discover you want the correct behavior in the presence of exceptions. In short, you want RAII.
Well, then one would have implemented a GC by hand with worse performance, specially in multi-threading contexts, unless there is someone on the team expert in hazard pointers and related performance tricks.
Maybe a performance improvement would be for the ANSI C++ standard to mandate that that compilers give special treatment to *_ptr<>(), so that they can elide needless calls, but I don't see it happening.
In FP languages one can use the concept of transactions, yes the M word, to encapsulate scope based workflows where the resources are to be released at the end.
What I can definitely see killing GC is affine types becoming mainstream, but they need to be made more friendly for the average Joe developer. Rust made them easier than ATS or Cyclone, but still a bit hard.
I think ParaSail's work might also be worth checking in this regard.
Edit: I forgot to say that this is no much different that doing RAII FP style. Those M concepts are great.
But there is no reason that the RAII pattern couldn't be completely orthogonal to memory management.
GC + destructors = very very messy even in languages built with GC in mind, kentonv described the whole non deterministic finalizers nicely but there are also other problems see here :
http://ericlippert.com/2015/05/18/when-everything-you-know-i...
And the new Perl, they say
I suppose in theory you could use GC just for objects that (transitively) don't hold any non-heap resources. But that gets a little weird as if you ever device that you need to stick a non-heap resource in there, suddenly all your code needs to change. (Of course, this is already generally the case in GC languages...)
Both RAII and the explicit cleanup of resources have their advantages and serious disadvantages. In C++ you better use RAII, in GC'd language, use explicit cleanup. What is better depends on the language.
> I kind of wonder if a preference for GC languages is in part responsible for the way distributed systems are typically designed these days -- namely, the emphasis on stateless servers, which avoids the need to do remote resource management (which is hard without RAII), at the expense of requiring a lot more machinery to make performant (e.g. complicated caching layers because all state changes have to hit storage which is sllloowwwwwww)
Don't wonder, they're not related at all. We have a few stateless services running that are written in C++. They are the only sane option once you start working beyond a certain scale - which is the point when you decide you need a distributed system. The reason for them being stateless is simple: nodes WILL fail. Hardware failures, power outages, line cuts, ... This is not the reason for 'more machinery'. Resource cleanup is hardly a bottleneck? RAII does this for you, but the only difference with GC'd languages is that you need to do this cleanup yourself.
There are other reasons for having to add 'more machinery' to make things performant: going for 'easy' scripting languages to get things up and running in record time - which is important for startups to have something to show for as quickly as possible. Performance at that moment takes a back-seat, and it's hard to go back. Micro-services are becoming a trend for this reason too - you can quickly write your services in <slow hipster scripting language>, get everything up & running, identify your bottlenecks and optimize them. Just look at the upcoming trend there for 'optimizing' distributed applications is to rewrite parts of your service in Go, which is a native compiled GC'd language. Easy to write, little memory overhead with decent execution speed, and designed to do concurrency well. Does it compete with C++? Not at all, but it gets things done that would be pretty damn annoying to do in C++ - and it does it with little memory and CPU overhead.
That - or going for some Java enterpricy application with tons of frameworks which eats up all your memory. Hello 32-core machine with 96Gig ram to generate some silly reports.
In a way, Java's success was a nail in the coffin of languages like Oberon(-2), Component Pascal and Modula-3, besides the other nails those languages got.
Otherwise we could already be enjoying native compiled GC'd language in the last 20 years, also for systems programming.
> That - or going for some Java enterpricy application with tons of frameworks which eats up all your memory. Hello 32-core machine with 96Gig ram to generate some silly reports.
You can have this in C++ as well. Hello CORBA.
However, lately I've been building a very stateful distributed system and finding that I can do a lot more with a lot less code and a lot better performance -- while still handling failures just fine.
This is a complex topic and I can't do it justice in an HN post. But, basically, while you always have to be prepared to start over in case of failure, "starting over" on every single request is overkill and adds all kinds of complication and latency to the system. If you instead permit yourself to set up some state and only start over when there's a problem, you can do a lot better.
* Closures capturing their environment and keeping local variables alive longer than intended.
* Debugging code keeping a record of objects.
In either case, you have likely failure modes in that either the resource can be deallocated prematurely and then accessed through a stale reference or that it is kept around longer than its intended lifetime.
RAII also does not provide a solution to a number of resource management scenarios, such as requiring access to an unbounded number of resources of which only a finite number can be reified at any time (e.g. due to the maximum number of file handles a process can manage). The obvious solution – a caching mechanism that will disconnect a resource from its in-memory representation upon eviction and reconnect when it is being used again – needs to attach itself to resource usage, not resource creation and destruction.
Most scenarios where RAII is being used are either trivially handled in any language that supports closures or macros, or benefit from explicit reasoning about resource lifetime, anyway.
Speaking of closures, I think it's no coincidence that RAII first arose in a language that until recently had no such concept; closures both create problems for RAII and also obviate many common use cases.
* Closures capturing their environment and keeping local variables alive longer than intended.
How can that happen to a stack variable (and RAII is about those), given C++11/14's closures ("lambdas") do not prolongate the lifetime of the objects captured by reference? Or did you mean capture by value? (would be really confusing with RAII-ing classes :) )
The RAAI object should be non-copyable (no copy constructor in C++), so the only way it can be passed by value to a closure is with an explicit move operation, which is not something you would do on mistake. The original copy would now revert to a proper "uninitialized" or "closed" state. Debuggers too are usually well aware of out-of-scope objects, so I don't see the point here.
As for complex scenarios, they are probably less than 1% of the time you'd use RAAI. When you do have complex scenarios that need techinques like caching and pooling - well, yeah, RAAI won't solve them on its own, but the same goes for macros and closures.
Besides that, most RAAI uses just can't be replaced by closures, since you cannot break a loop or return a value from within a closure, for instance (Ruby procs can do that, but there's no equivalent to that in most languages). And both a closure-based and a macro-based solution quickly become an unwieldy nest-fest once you need to deal with multiple resources in a row.
So, std::shared_ptr (or anything else that does reference counting) is not properly executed RAII?
> Debuggers too are usually well aware of out-of-scope objects, so I don't see the point here.
I wasn't talking about debuggers, but code that is enabled for debugging purposes. E.g. globally remembering the last N objects passed to a function.
My larger point is that either lifetime or reachability is off. You either have a resource that can still be accessed through a stale handle even though it's been deallocated or one that remains allocated past its intended lifetime.
As someone who uses a lot of closures and a lot of RAII, together, I can assure you this is not the case:
- C++ closures are very explicit about what is captured and how (by reference, by copy, by move/ownership transfer). It actually works incredibly well with RAII.
- Closures as an alternative to RAII only works in a small subset of use cases: cases where the resource lifetime is bound to a stack frame. They do not easily model resources owned by objects, nor (ironically) resources used in an asynchronous callback context.
BTW, Rust actually statically guarantees no dangling pointers -- without using GC. And yes, it has closures.
Just to expand on this a little, one problem is that no matter how you collect a cycle of objects with finalizers, one of them will see the others in a finalized state. Another problem is resurrection, where the finalizer creates a new reference to self or another finalized object. You could try solving these problems by nulling all references to finalized objects (including self) during GC, but that makes finalizers useless. I don't know any good solution.
Many libraries expose this type of interface, and by Lisp's use of dynamic scoping, nested functions within the scope can access the current state of that particular scoped resource without having to pass it around manually.
In effect, RAII is programmer discipline which can manually repurpose a particular object allocation/deallocation style to support scope behavior, while languages like Lisp can simply work with scope behavior directly.
https://github.com/rongarret/Ciel
Open Dylan (http://opendylan.org/), a Lisp-like language without Lisp-like syntax, also can use Boehm or the Memory Pool System.
On a related note I'm excited about Apple open sourcing and porting Swift to Linux with an eye towards server-side code, specifically because of ARC. Garbage collection has been a concern for web services in particular when it comes to 99th percentile latency. Things run fine and then boom, GC runs, slowing down a few unlucky requests. ARC just makes memory-management performance deterministic, no tuning needed.
So yes, you can do ARC for C/C++, but it would need to be opt-in, and it would not be sufficient for all memory allocation in C/C++ because the moment you link in a third party library that doesn't play ball you need to do things differently.
The chosen approach in C++ has largely "smart pointers" - template classes that implement various reference counting semantics - coupled with RAII.
E.g. one part of the problem for a fully generic solution in C/C++ is that in C/C++ nothing stops you from taking an arbitrary bit-pattern and treating it as a pointer and vice versa. As an example, take BPTR's in AmigaOS - core parts of AmigaDOS were written on contract due to time constraints, and they were written in BCPL, and that's where they came from.
BPTR's were pointers that had been bit-shifted right two bits - basically BCPL was treating memory as an array of 32bit quantities. So a lot of pointers in AmigaOS are stored in memory as values that don't actually match any memory address. So one hand your compiler don't know when/where to apply a reference count, and on the other hand a generic non-ref-counting gc won't know whether or not any specific value is a pointer, and if so whether it meant to point at the actual memory address indicated by the value or if it needs to be bit-shifted.
In C this is perfectly legal. But to gc apps that do stuff like that, your gc must either be smart enough to figure out every possible pointer manipulation (meet the halting problem, it wants to have a word), or it needs explicit support from the developer.
What about scalability, if you have more than a few CPU cores? You know how expensive atomic fetch-and-add (aka LOCK XADD) is, right? Atomic compare-and-swap loop is even worse.
Put simply, those things broadcast coherence information on inter-core (and inter-processor) network.
It's ok for a low number of cores, but this solution just won't work well with more CPU cores.
Good for a mobile phone with two cores.