A Garbage Collector for C and C++

> 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.

> In particular, C++ (and Rust, etc.) stresses RAII (Resource Acquisition Is Initialization)

But there is no reason that the RAII pattern couldn't be completely orthogonal to memory management.

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.

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.

> 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.

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.

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.

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.

Don't you know about the std:: smart pointers?

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.

Reference counting?

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.

C++/CX does ARC for C++ for those of us on Windows, but it comes with the cost of making C++ classes into COM ones.

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.

CLASP (https://github.com/drmeister/clasp), a Common Lisp, can optionally use one of Boehm or the Memory Pool System (http://www.ravenbrook.com/project/mps).

Open Dylan (http://opendylan.org/), a Lisp-like language without Lisp-like syntax, also can use Boehm or the Memory Pool System.