dark mode light mode Search Menu

Garbage Collection

David Villa on Flickr

When a computer runs a program, it’s constantly creating new data. Whether it’s scenery or sprites in a game, records in a database, or the posts on your dash, any program is going to need to create and store data. What actually happens to this data, though? Where does it live and what happens to it when your program closes?

First off, when programs need to store data most of the time they’ll put it in memory, specifically a type of memory called random access memory (RAM). Once in RAM, the information can easily be retrieved or modified. There’s two cases, though, where the program won’t be retrieving the data from RAM. First, computers like desktops and laptops may have the ability to temporarily move some data out of RAM and onto the permanent storage of the hard drive. The operating system may choose to do this with data that programs haven’t accessed in a long time. It’s kind of like taking the stuff you don’t use very much and putting it in a box in the basement. It’ll take a long time to dig it back out, but it’s convenient in the short term.

The other situation is that frequently used data may be stored in low level caches that exist as part of the processor itself. If storing on the hard drive is like putting things in a box in the basement, then the cache is like having your stuff on your desk right next to you. You can’t keep much there, but if you need to keep grabbing the same thing it’s going to be really fast to nab it each time.

The common case, though, is that everything is going to be stored in RAM. Every program starts with a certain amount of memory it gets to use, and if it needs more the program has to ask for it from the operating system. This extra memory that the program asks for is added to something called the heap of the program. Now, every operating system, whether Android or iOS or Windows or Linux, has some way of assigning RAM to programs that are running. When a program closes, all of its memory is reclaimed by the OS and freed up for other programs to use later.

On the other hand, while the program is still running the program is responsible for managing its own heap: both requesting more memory for the heap and for giving memory back to the operating system when it’s no longer needed.

What do we mean by “no longer needed”? Imagine that you have a game that’s running, say an FPS like Overwatch. You finish one match and then start another on a new map. All the massive amount of data needed to render out the old map isn’t needed any longer. If you’re keeping it around after each new match, then you’re just wasting space. With such a big intensive program it’s not going to be long before you end up using up all the memory available on your computer or console! At that point the machine will either have to start storing the data from memory onto permanent storage, which will make everything get slower and slower, or it will just cause the program to crash. Either way, it’s a bad result. When bad things like this happen, they’re called memory leaks.

In older programming languages, this process of requesting and giving back memory used to be handled by the programmer. If you were writing in C, for example, you’d have to specifically to set aside, or allocate, memory with functions like malloc and then free the memory manually. As you can imagine, this can get complicated and is very error prone. It only takes forgetting to free memory in one place to create a memory leak.

If you’ve used basically any recently designed programming language, you don’t have to do this manual memory allocation. Instead, languages such as Python, Ruby, C#, or Scala among many others are all garbage collected. Garbage collection isn’t just one thing but a whole family of techniques for automatically allocating and freeing memory at the right time. The garbage collection is done by something called the runtime system of the language implementation, which has been created for you by whoever made the language implementation. If you’re using an interpreter, which runs the program straight from the source code you’ve written, then the runtime system is a part of the interpreter. If you’re using a compiler, which takes the source code you wrote and turns it into machine code, then the runtime system is going to be an extra bit of code that the compiler tacks onto your program.

Garbage collection can work in a few different ways, but the basic idea is always the same: figure out what data isn’t being used anymore and then free it. This is a really hard problem in many cases and is impossible to do with perfect accuracy in all cases, but at this point garbage collection can do really well. First, we should say that it’s better to be cautious and not label data as garbage if it actually is rather than accidentally label in-use data garbage. Why? Because if you accidentally free memory that the program still needs, you may cause the whole thing to crash.

There’s two basic strategies to figure out whether a piece of data is garbage: either you can try and keep track of how many other things are referencing the piece of data in question, for example the garbage collector could keep track of how many other things are using the data and garbage collect only if no one else is referencing it. Another option is for the garbage collector to try to “chase” references by figuring out what data is obviously still in use and checking what can be reached by the obviously-still-in-use data.

Different techniques for garbage collection have different strengths and weaknesses, which are more involved than we can talk about in a single article. No matter what, though, using garbage collection means that you’re trading off lower speed and greater size in your program for the ease of not having to allocate and free memory yourself. Most of the time, that’s a great tradeoff! The most common place where it’s not a good trade off is when you’re writing code for small lower power devices like the Arduino. It’s also a tradeoff that, until recently, was unacceptable for programming where speed was of extreme importance, things like video games. Now, though, computers are fast enough and runtime systems are more clever so it often doesn’t make much of a difference anymore.

Learn More