So I finally have a little bit of time after the Christmas rush to finish off our 3 part post on memory management (see Part 1 and Part 2), by looking at garbage collection. So let’s dive in…
Garbage collection is a feature available to a number of programming languages, most notably .NET languages (e.g. C#), Java and Objective-C (though not currently available on iOS). Basically, garbage collection is kind of like, well, real life garbage collection. When you’re finished with something, you discard it, and at some point in the future everything you’ve discarded will get cleaned up by someone else (i.e. The garbage collector). Sounds like a perfect system, right? Just create what you want, discard it when you’re done and not worry about memory management. Unfortunately, a lot of people (myself included) soon come across the pitfalls of this approach, but with a little knowledge you can play nice with the garbage collector. Firstly, we’ll take a look at how garbage collectors generally work, then at some of the problems we can find ourselves in, and finally the solutions…
What is garbage?
I think the best place to start is to define what garbage actually is. After all, we don’t want the garbage collector to take away things we’re actually using. Garbage is any object that is not currently in use, and can have its memory reclaimed. So how does a garbage collector know which objects are still in use by our program and which can have their memory safely reclaimed to be allocated elsewhere? The key here is accessibility. If there is no way for the object to be accessed (i.e. if nothing is referencing it), then it can’t possibly be in use. So the garbage collector will check every object to see if it can be reached by the program. It does this by taking what are known as the ‘root’ objects of the program (these are any objects that can be directly accessed by the program, such as global instances and any instances currently on the stack) and testing if there is a reference to the object in question from any of these roots to the object, either directly or indirectly. Let’s look at an example…
Suppose, inside a function, you create a new instance of a Car object, and this in turn has four instances of a Wheel object, and each Wheel object has an instance of a Tyre object. If the garbage collector runs while you’re inside your function (so the Car instance is still in scope), the Car instance is now a root object. So when the garbage collector is checking if it should reclaim the memory of a Tyre, it will check if the Tyre is somehow accessible from any of the root objects, by “walking the tree” of all the roots. The tree here refers to the tree of references held by all objects. So the tree for this particular root would look like this:
As you can see, the Tyre instances are linked to the root (the Car instance) by the Car referencing the Wheels, and the Wheels referencing the Tyres, so none of the objects are classed as garbage. If the reference to one of the Wheels in the Car is changed, either to reference another Wheel instance or to be null, then the Wheel that was originally referenced would not be linked to the root any more, and neither would its Tyre, so both of these objects (ringed below) would now be classed as garbage and could be reclaimed by the garbage collector.
Obviously, if you were to store a reference to the now orphaned Wheel or Tyre, then that reference would prevent the objects from being garbage collected.
When does the garbage collector run?
The garbage collector can’t run all the time, as the roots and references in your program will be constantly changing and new objects being created in all sorts of places. Checking the references to all the objects in your program can also take a lot of processor time, which we don’t really want. So, garbage collectors tend to wait around until they are needed, which is usually when your memory usage gets too high. The term “too high” here is entirely dependent on the implementation of the garbage collector and the system you’re running on, so could be anything, which means you can never be entirely sure when exactly the garbage collector will run. The trick here is to try and make sure you keep your memory usage to a minimum so that the garbage collector runs less often, which we’ll look at how to do further down.
What happens when the garbage collector runs?
The garbage collector needs to check all the roots and references to all the objects in your program, which it can’t really do if things keep changing, so it just stops your program running. That’s right, when a garbage collection is triggered, usually by the amount of memory that your program has allocated being too high, it just stops your program running and then checks everything to see what can be cleaned up. Once it has paused your application, it then checks to see which objects that have been allocated can still be reached from the roots. Any that can’t be reached can then be cleaned up. Languages with garbage collectors usually allow Finalizers on objects – a function which will be called on an object when it’s about to be garbage collected so that it can clean up any resources it may have (close files, release hardware resources, etc.). Finalizers shouldn’t really do much work, and releasing of resources should ideally be done using an object’s Dispose function if available (dispose functions are available on C# and Java, as well as a few other languages), but Finalizers can be used to make sure everything is released if the Dispose method hasn’t been called for some reason.
After releasing the memory for any unreachable objects, the garbage collector can then also compact the heap. Allocating and releasing a lot of objects can lead to a fragmented heap (where there are lots of small spaces of unused memory between allocated sections), which can make memory usage a lot less efficient. Because your program has been stopped, the garbage collector is free to move objects around in memory, as long as it updates the references to point to the new locations in memory. When your program resumes, it won’t really matter that objects in memory have been moved around, as all the references will have been updated by the garbage collector. So, the garbage collector can squash up all the allocations that remain, removing the spaces between them.
As a side note, this allows garbage collected languages to be very fast at allocating new objects, as they just need to maintain a pointer to the top of the heap and increment that each time a new object is allocated. The pointer is reset to the new top each time the heap is compacted, so allocation simply consists of adding an offset to a pointer, rather than having to search through the heap for a free space to hold the new object. The trade off obviously comes in the performance penalty when the garbage collector needs to run to reclaim unused space.
So that’s a general overview of the main points of a garbage collector. There are plenty of optimisations and further discussions on garbage collectors, such as generational garbage collectors, but we don’t need to go into them here.
Problem?
Now we come to one of the main problems that people tend to come across with garbage collectors. That is, having the garbage collector run far too often. When working on Blast Buggies (currently on hold until we can get some more time to concentrate on it), we wrote the game in C#/XNA on the PC, though it was designed primarily for XBLA. This is a classic case of needing to test on your target platform. The first time we ran it on the 360, it ran at a whopping 1 frame per second. Turns out the main culprit here was the garbage collector (or rather, our causing it to run too often). On Windows, the .NET garbage collector is very sophisticated and clever, and can run very fast, so wasn’t really a problem when we were developing on PC. The garbage collector on the 360’s .NET implementation is not so clever, so any runs of it are very noticeable. We were running it pretty much once per frame. The problem came from a lot of small allocations, especially things like strings, which were happening every time the game updated or rendered. It’s very easy to forget that each time you concatenate two strings, or get the string representation of a number, you’re constructing a new string, which allocates memory. All these small allocations quickly add up, and cause the garbage collector to run frequently (usually they’re allocations that you’ve created for temporary things and thrown away, so you never actually run out of memory, you just run super slowly as the heap is continually being cleaned up).
So the best way to minimise pauses caused by collection is to make sure they don’t happen. Remember that garbage collectors tend to run when an allocation is requested, so if you can minimise how often allocations happen, you can minimise the pauses in your game. The best way to do this is to allocate everything you’re going to need in one go (usually at the start of a level), then reuse these instances instead of creating new ones and throwing them away. For example, suppose you have a spaceship that fires lots of bullets. If you were allocating a new bullet every time you fired, you could potentially cause a stutter as the garbage collector kicks in once you’ve fired too many bullets, so it can clean up all the unused ones. Depending on your game, this could be anything from an annoying pause every few seconds, to a huge slowdown while the player is firing. Either way, it’s something you want to get rid of. By allocating a pool of bullets at the start of your level, you can just grab one from this pool when you need to, use it, then put it back in the pool when you’re done. No new bullets need to be allocated, and none get freed up, you’ve just got a constant amount of bullets that are sometimes in use, sometimes not. Because you’re no longer allocating new bullets (and all the other objects that they could also reference), your bullet creation isn’t going to cause any garbage collection, so no more slowdown when you’re creating bullets. Yay!
I’d say this is probably the main thing that gets nearly everyone when they start using a garbage collected language. The main point to take away from all this is you need at least have some basic understanding of how the system you’re working with actually handles its memory management, and what the best practices are for the system you’re developing for. If you come across a memory management system (or any other kind) that you’re unfamiliar with, do yourself a favour and research how it works first before just getting into it. You’ll save yourself a lot of time having to go back and re-write things when everything runs terribly. Most people (quite rightly) say that you should never prematurely optimise your code, as you won’t know where your bottlenecks are until you’re near completion, but understanding how the system you’re developing for actually works will help you write more optimal (and less buggy) code in the first place.
So that concludes our 3 part look at memory management. Hopefully you’ve gotten something out of it. If anyone has any questions, comments or suggestions for more articles, let us know in the comments below.