# How does garbage collection compare to reference counting? [duplicate]

I starting working through an online course on iOS development in the new language from Apple, Swift. The instructor made a point that raised this question in my mind. He said something to the effect of:

There's no need to worry about memory management because it's all taken care of for you by reference counting, and this means there's no need to worry about understanding how garbage collection works.

When I heard this I thought to myself, "why would anyone use garbage collection when you can simply use reference counting?"

So how do the two approaches compare?

• There's actually quite a nice description over in Wikipedia's section on garbage collection: (en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29). The short list of cons for reference counting are: cycles, space overhead, speed overhead, requires atomicity, not realtime - although frankly I don't think GC approaches solve all these problems well either. I'm leaving the answer space for better answers. However, one interesting detail is that GC and reference counting both can still have leaks by keeping object references unintentionally; internal knowledge is still valuable! Commented May 30, 2015 at 5:43
• Ref counting is a technique (quite limited) for garbage collection. However, it works poorly with circular references. Learn also about weak pointers. Read the GC handbook for more. Commented May 30, 2015 at 12:23
• @JTrana: In 32 bit Objective-C, they use a clever trick to use 1 byte for reference counts: Since most of the time the count is small, 0-127 means reference count from 1 to 128 (it is never 0). 128-255 means the reference count is stored in a hash table, and the real value is (reference count from hash table) + (1 byte count - 192). You can just increase / decrease the reference count byte unless 128 is decreased / 255 is increased where you need to modify the hash table entry. Commented May 30, 2015 at 12:27
• So increasing the reference count from 128 to 129 is expensive, and then increasing / decreasing by a total of 64 is just slightly expensive. Commented May 30, 2015 at 12:28
• @gnasher729 Thanks for the details, that's interesting... Commented May 30, 2015 at 15:42

To understand how the two approaches compare we need to first examine how they work and the weaknesses of each.

Automatic Reference counting or ARC, is a form of garbage collection in which objects are deallocated once there are no more references to them, i.e. no other variable refers to the object in particular. Each object, under ARC, contains a reference counter, stored as an extra field in memory, which is incremented every time you set a variable to that object (i.e. a new reference to the object is created), and is decremented every time you set a reference to the object to nil/null, or a reference goes out of scope (i.e. it is deleted when the stack unwinds), once the reference counter goes down to zero, the object takes care of deleting itself, calling the destructor and freeing the allocated memory. This approach has a significant weakness, as we shall see below.

"There's no need to worry about memory management because it's all taken care of for you by reference counting," that's actually a misconception you still do need to take care to avoid certain conditions, namely circular references, in order for ARC to function correctly. A circular reference is when an object A holds a strong reference to an object B, which itself holds a strong reference to the same object A, in this situation neither object is going to be deallocated because in order for A to be deallocated its reference counter must be decremented to zero, but at least one of those references is object B, for object B to be deallocated, its reference counter must also be decremented to 0, but at least one of those references is object A, can you see the problem? ARC solves this by allowing the programmer to give compiler hints about how different object references should be treated, there are two types of references: strong references and weak references. Strong references are, as I mentioned above, a type of reference which prolongs the life of the referenced object (increments its reference counter), weak references are a type of reference which does not prolong the life of an object (that is, it does not increment the object's reference counter), but that would mean the referenced object could get deallocated and you'd would be left with an invalid reference pointing to junk memory. In order for this situation to be avoided, the weak reference is set to a safe value (e.g. nil in Objective-C) once the object is deallocated, thus the object has an extra responsibility of keeping track of all weak references and setting them to a safe value once it deletes itself. Weak references are usually used in a child-parent object relation, the parent holds a strong reference to all it's child objects, whereas the child objects hold a weak reference to the parent, the rationale being that in most cases if you no longer care about the parent object, you most likely no longer care about the child objects either.

Tracing garbage collection (i.e. what is most often referred to as simply garbage collection) involves keeping a list of all root objects (i.e. those stored in global variables, the local variables of the main procedure, etc) and tracing which objects are reachable (marking each object encountered) from those root objects. Once the garbage collector has gone through all the objects referenced by the root objects, the GC now goes through every allocated object, if it is marked as reachable it stays in memory, if it is not marked as reachable it is deallocated, this is known as the mark-and-sweep algorithm. This has the advantage of not suffering from the circular reference problem as: if neither the mutually referenced object A and object B are referenced by any other object reachable from the root objects, neither object A nor object B are marked as reachable and are both deallocated. Tracing garbage collectors run in certain intervals pausing all threads, which can lead to inconsistent performance (sporadic pauses). The algorithm described here is a very basic description, modern GC's are usually much more advanced using an object generation system, tri-color sets etc, and also perform other tasks such as defragmentation of the program's memory space by moving the objects to a contiguous storage space, this is the reason why GC'ed languages such as C# and Java do not allow pointers. One significant weakness of tracing garbage collectors is that class destructors are no longer deterministic, that is the programmer cannot tell when an object is going to be garbage collected in-fact GC'ed languages do not even allow the programmer to specify a class destructor, thus classes can no longer be used to encapsulate the management of resources such as file handles, database connections, etc. The responsibility is left on the programmer to close open files, database connections manually, hence why languages such as Java have a finally keyword (in the try,catch block) to make sure the cleanup code is always executed before the stack unwinds, whereas in C++ (no GC) such resources are handled by a wrapper object (allocated on the stack) which acquires the resource in the constructor and releases it in the destructor, which is always called as the object is removed from the stack.

As for performance, both have performance penalties. Automatic reference counting delivers a more consistent performance, no pauses, but slows down your application as a whole as every assignment of an object to a variable, every deallocation of an object, etc, will need an associated incrementation/decrementation of the reference counter, and taking care of reassigning the weak references and calling each destructor of each object being deallocated. GC does not have the performance penalty of ARC when dealing with object references; however, it incurs pauses while it is collecting garbage (rendering unusable for real-time processing systems) and requires a large memory space in order for it to function effectively such that it is not forced to run, thus pausing execution, too often.

As you can see both have their own advantages and disadvantages, there is no clear cut ARC is better or GC is better, both are compromises.

PS: ARC also becomes problematic when objects are shared across multiple threads requiring atomic incrementation/decrementation of the reference counter, which itself presents a whole new array of complexities and problems. This should answer your question as to "why would anyone use garbage collection".

• This is largely correct, although it's not really true that classes in managed languages can't be used to encapsulate OS resources. In .NET, there's an interface (`IDisposable`) and a whole set of guidance around doing just that. Commented May 30, 2015 at 19:58
• "Tracing garbage collectors run in certain intervals pausing all threads...rendering unusable for real-time processing systems". That is a common misconception. Here is a concrete counter example: researcher.watson.ibm.com/researcher/files/us-groved/…
– J D
Commented Sep 29, 2015 at 19:29
• "Automatic reference counting delivers a more consistent performance, no pauses". That is another common misconception. Non-deferred reference counting (like ARC) has worse case unbounded pause times when the last reference to a DAG falls out of scope, worse than even the simplest incremental GC. Boehm even found that RC has worse max pause times than Hotspot: hpl.hp.com/techreports/2003/HPL-2003-215.pdf
– J D
Commented Sep 29, 2015 at 19:31
• "requires a large memory space". I often see that asserted, even by experts, but I have never seen any evidence to support that belief. RC keeps objects alive until the end of scope whereas tracing garbage collectors do not. flyingfrogblog.blogspot.co.uk/2013/10/…
– J D
Commented Sep 29, 2015 at 19:34
• @ALXGTV: "requires a large memory space". This has now been tested and disproven by the "iOS Memory Performance" section of the following benchmark where Swift uses 4x more memory than either Java (RoboVM) or C# (Xamarin). medium.com/@harrycheung/…
– J D
Commented Feb 9, 2016 at 15:38

The instructor is wrong. You better know how garbage collection and reference counting works.

With garbage collection, the problem is that you may still have left some reference to an object around somewhere. There was a case where an early self-driving vehicle crashed because references to information about previous locations were stored in an array and never became garbage, so after 45 minutes it ran out of memory and crashed. I think not literally, it stopped driving, but it might have crashed as well.

With reference counting, the problem is that you may have cyclic references A->B->A or A->B->C->...->Z->A, and no reference count ever goes to zero. That's why you have weak references and you need to know when to use them.

Both ways, you need to understand how things work, or you will get into trouble. Performance wise, if you ask Java developers they say garbage collection is faster; if you ask say Objective-C developers they say reference counting is faster. Studies prove what they want to prove. If it makes a difference, you should reduce the number of allocations, not switch languages.

You also need to know about weak references, basically a reference to an object that doesn't keep the object alive. And you need to know what happens exactly once it has been decided that an object should be thrown out; in Java I think there are ways how an object could become alive again, in Objective-C / Swift once the reference count is zero, that object is going to go away no matter what you try to hold on to it. Well, unless you add a line for (;;) ; in the dealloc / deinit method :-(

• I would also add that modern languages provide data structures to abstract and automate memory management. Java has weak collections which serve well for e.g. caches that automatically clean themselves up as needed. C++11 has shared pointers that use reference counting and work correctly with move semantics and stack unwinding.
– user22815
Commented May 30, 2015 at 21:28
• @Snowman: "modern languages...Java...C++" . There's something so very wrong with that. :-)
– J D
Commented Feb 9, 2016 at 15:42
• @gnasher729: "Studies prove what they want to prove". The vast majority of GC research over the past 56 years has concluded that tracing is faster than reference counting though a few die hards continue to pursue RC, e.g. in "Down for the count? Getting reference counting back in the ring" users.cecs.anu.edu.au/~steveb/downloads/pdf/rc-ismm-2012.pdf
– J D
Commented Feb 9, 2016 at 15:44
• @JonHarrop Like it or not, both languages are alive and well, receiving continuing updates as of this comment (C++ 17 is under development, and Java 9 is expected Q3 2016). And these are not minor tweaks: they are receiving major features that one would expect from a programming language in 2016.
– user22815
Commented Feb 9, 2016 at 18:52
• I've downvoted as you started with "having a reference around". Keeping references around is a problem in any scheme, including RC and direct allocation. It's probably worse with the latter as you won't just run out of memory but are left with a reference (/pointer) to deallocated memory. "Studies prove what they want to prove" seems to dismiss the entirety of science. "You also need to know about weak references": first of all, you make that claim twice, once just for RC. Entire classes of programmers happily create products without ever knowing about weak refs despite your claim. Commented Mar 5, 2020 at 11:27

Manual memory management, reference counting, and garbage collection all have their pro's and con's:

• Manual memory management: Unbeatable fast, but prone to bugs due to errors in freeing the memory. Also, oftentimes you will need to implement at least reference counting on top of manual memory management yourself when you get several objects that all require a single object to remain alive.

• Reference counting: Small overhead (incrementing/decrementing a counter and a zero check is not that expensive), allows easy management of quite complex data structures, where every object may be referenced by several others. The deficiency is that reference counting requires references not to be circular. Once you get reference circles, you leak memory.

Weak references may be used to break some reference cycles, however, they come with quite a bit of additional costs:

1. Weak references require a second reference count to manage the weak reference itself. Likely, the weak reference is another object that needs to be allocated independently, incurring a significant overhead in memory consumption.

2. Destroying an object in the presence of weak references requires atomically resetting the weak reference that belongs to the object and decrementing the reference count. Otherwise you get erratic behavior of the weak references. I'm not into the details, but I believe this can be hard to achieve in a lock-free fashion.

This can all be done, but it's not as simple as reference counting without weak references.

• Garbage collection: Can cope with all possible dependency graphs, but has quite severe performance impact. After all, the garbage collector has to prove somehow that an object is not reachable anymore before it can collect it. Modern garbage collectors are quite good at avoiding long lags while they do their work, but the work needs to be done somehow. This is especially bad for real-time applications that need to guarantee a response within a given time frame.

As you see, the three methods all have situations where they are best: If you can easily do manual management and your program has tight performance constraints, manual memory management may be the way to go. And as long as you can use reference counting over garbage collection, that's considerably faster and does not incur spurious lags. Nevertheless, sometimes you must use garbage collection because you cannot guarantee cycle free references.

Languages that use garbage collection for everything have just decided that ease of use is more important to them than allowing for performance sensitive applications.

• The claim that reference counting has better real-time behavior than tracing GCs is oft repeated and makes intuitive sense, but as it turns out the best known realtime tracing GCs beat the best known realtime reference-counting GCs when it comes to pause times. For example, Metronome's pause times are less than the context switching time of a modern realtime OS! So, if you can afford threads, you can afford a tracing GC as well. (And as it turns out, proving correctness and upper bounds of tracing GCs seems to be much easier than for reference-counting GCs.) Commented May 30, 2015 at 9:46
• As an aside, the C++ standard library provides everything neccessary for managing unique/shared/weak pointers, so one can get (all?) the advantages of ARC where it might help without giving up the advantages of doing it manually... Commented May 30, 2015 at 13:22
• Note that manual memory management is only unbeatable if you can match the rather sophisticated locality optimizations of a good relocating GC (ref-counted or tracing). If you can't, cache misses will eat your gains. See e.g. RC-Immix for explorations of how important this is. Commented May 30, 2015 at 20:12
• If GC vs reference counting makes a measurable difference, then you are spending a lot of time creating and destroying objects anyway, so maybe you should try to avoid that. (And I think modern Java compilers can figure out sometimes that an object will be created and will become garbage very soon after, so they don't bother creating the object at all). Commented May 31, 2015 at 15:59
• @Snowman While I buy your "Computers (even phones) are fast" in general, that does not mean that you can ignore performance considerations everywhere. As I said in a comment above, I work in a field where computing never can be fast enough. And I strongly object to your assertion "algorithms are highly optimized": It is true that highly optimized algorithms are known, but that does not translate into them being implemented: The number of people who can do proper optimization is wanning (precisely because "computers are fast"!), leading to tons of suboptimal algorithms in new code. Commented Feb 9, 2016 at 20:47