What is garbage collection in programming?

Every program uses memory while it runs: for the text you type, the pictures on screen, the enemies in a game. When the program is done with a piece of memory, someone has to give it back, or the program slowly fills up. So what is garbage collection? It is the part of many programming languages that finds memory the program can no longer use and frees it automatically, so the programmer does not have to.

This guide explains why garbage collection exists, how a collector decides what counts as garbage, what it costs, and how to follow the idea by hand, using Microsoft's documentation and the encyclopedia entry on the subject. It ends with the free browser game Tank City Reboot, where Garbage collection is a power-up.

What is garbage collection? The plain answer

Wikipedia's entry on garbage collection) calls it a form of automatic memory management. The collector reclaims memory that the program set aside but no longer refers to. That unused memory is the "garbage".

The idea is old. The same entry says John McCarthy invented it around 1959, to make memory easier to manage in the Lisp language. Today many languages depend on it, including Java, C#, Go and most scripting languages, and JavaScript, the language of web pages, uses it too.

Why programs need it: memory that is never given back

Without a collector, the programmer manages memory by hand: they say which pieces of memory to give back, and when. C and C++ were designed to work this way. It gives the programmer full control, and it is easy to get wrong in three ways:

• A memory leak. The program forgets to free memory it no longer needs. Leaks add up, and Wikipedia notes they can lead to the program running out of memory.
• A dangling pointer. The program frees memory but still holds a reference to it, then uses that reference later. By then the memory may hold something else, with unpredictable results.
• A double free. The program frees the same memory twice, after it may already have been handed out again.

Microsoft's fundamentals of garbage collection for .NET names the first two as exactly the problems automatic memory management can eliminate: forgetting to free an object, and using memory that has already been freed.

How a garbage collector decides what is garbage

The most common kind is called a tracing collector. Microsoft's page describes how the .NET one works, in three steps.

1. Start from the roots. Roots are the places the program is using right now: local variables in running code, static fields, and a few places inside the runtime.
2. Follow every reference. From each root, the collector follows the references to other objects, then their references, and so on, building a map of everything reachable.
3. Free the rest. Any object not on the map is unreachable. No part of the program can ever use it again, so it is garbage, and its memory is released. When it finds enough garbage, it also moves the surviving objects together, so free memory is in one piece.

Microsoft adds an idea called generations. New objects start in generation 0, and newer objects tend to have shorter lives. Objects that survive a collection move up to generations 1 and 2. Because collecting a small part of memory is faster than collecting all of it, the collector can clean one generation at a time instead of the whole heap.

There is a second kind, called reference counting. Each object keeps a count of how many references point to it, and it is freed the moment the count reaches zero. Wikipedia notes its weak spot: two objects that point to each other never reach zero, so systems like CPython, the main version of Python, add a separate check for these cycles.

A worked example: following the references by hand

Picture a small tank game written in a garbage-collected language. The program keeps a list called enemies, and that list is a root. Follow what happens to one enemy tank.

1. The tank appears. The program creates a tank object and adds it to enemies. A root points to the list, and the list points to the tank, so the tank is reachable.
2. The tank is destroyed. The program removes it from enemies. Now nothing points to that tank object. It is unreachable.
3. The collector runs. It starts from the roots, follows the list, and never reaches the old tank. The tank's memory is freed. The programmer wrote no code to free it.
4. The leak a collector cannot fix. Now suppose the program also keeps a variable called lastHit that points to the last tank hit, and never clears it. The destroyed tank is still reachable through lastHit, so it is not garbage, and it stays in memory.

Step 4 is the lesson. Wikipedia says garbage collection prevents certain kinds of memory leaks, not all of them. A collector frees what nothing points to, not what you have stopped caring about. Clearing references you no longer need is still the programmer's job.

The cost: pauses and overhead

Garbage collection is not free. Wikipedia lists two costs:

• Overhead. Finding garbage takes processor time and memory of its own, which can slow a program down.
• Unpredictable pauses. The moment a collection happens is hard to predict, which can cause stalls. That matters in programs that must respond instantly. Collectors that work in small steps, or alongside the program, reduce these pauses, with their own trade-offs.

Microsoft's page says a collection starts on its own when memory is running low or when the program has set aside more than a threshold. A program can ask for one directly with GC.Collect, but Microsoft says that in almost all cases you do not have to. Garbage collection also only handles memory: Wikipedia notes that things like open files and network connections are usually closed by other means. Our guide to multithreading and our guide to what a kernel does cover two more ideas about how programs run.

Learn the idea by playing: the Garbage collection power-up

Tank City Reboot is a tank game set inside a computer: your antivirus tank guards the CPU core on a circuit board, and every enemy, power-up and wall is named for a real computing idea. Twenty malware tanks come at the core each stage, four at a time. Garbage collection is the power-up that wipes out every enemy on the field at once.

Its card gives the real idea in one line: "Garbage collection finds memory that no part of a program uses any more and frees it." Next to it is the Breakpoint power-up, which freezes every enemy for eight seconds; its card explains that a breakpoint makes a debugger pause a running program at a chosen line. The game teaches the word and one idea, not how to program. The second game, Tank City Zero Day, names its upgrades the same way.

Frequently asked questions

What is garbage collection in simple words?

The part of a programming language that finds memory the program can no longer reach and frees it automatically, so the programmer does not have to.

Which languages use garbage collection?

Wikipedia lists Java, C#, Go and most scripting languages, and JavaScript uses it too. C and C++ were designed for memory managed by hand.

Can a program still leak memory with garbage collection?

Yes. The collector only frees objects nothing refers to, so an object you forgot to let go of, held by a variable you never clear, stays in memory.

Does garbage collection slow a program down?

It can. Finding garbage takes processor time, and a collection can cause short, hard-to-predict pauses.

Get started

Play Tank City Reboot: it is free, plays in your browser on a computer or a phone, and needs no account. Watch for the Garbage collection power-up, and see what it does when four malware tanks are closing in.