Introduction

Imagine a populated parking lot.

A parking lot, with both parked cars and free parking spots

The Android Parking Lot

Cars are coming in, cars are going out.
Some cars might occupy one parking spot. Whereas the bigger ones might occupy the whole parking lot.
People are generally mad here.

This is the memory.

And then there’s Recycler Bill, the garbage collector. His only purpose in life is to gather the trash from the parking lot.

When they leave, people put their trash in a sterile bag and leave it on their parking spot for Bill to collect.

Now, Bill has a problem — some people do not pack their trash in a bag. Instead, they leave a pile of trash on the parking spot.

Unfortunately, Bill cannot collect the pile of trash as he is not paid enough for this job. The trash would then occupy the parking spots indefinitely.

These are memory leaks.

A parking lot, having both cars and trash bags on the parking spots

One memory leak in the second row, the second parking spot

When a new car tries to park here, and there’s not enough space for it… the parking lot explodes, and Bill explodes as well.

This is an OutOfMemoryException.

Bill is more than a mere garbage collector. In his hands lies the fate of the parking lot.

Let’s follow Recycler Bill in his journey of becoming the best garbage collector in the parking lot.
Oh, but don’t tell him he’s the only one around. 😁

Dalvik Bill (up until Android 4.4)

Things are not going that well for the parking lot.

It’s quite expensive to park here. So, it is recommended to park only if necessary.

Moreover, Bill irritates the people as everyone has to stop during some parts of the garbage collection. No cars are entering or leaving the parking lot until Bill finishes cleaning.

So how did Bill get the job with all these inconveniences?

The job of a garbage collector seems straightforward. However, the intricate technique of Bill made him stand out from the other garbage collectors. He calls his technique Mark and Sweep.

To begin with, Bill noticed that it is not that effective to collect garbage that often. Instead, he waits until the parking lot is full. Only then, he proceeds with the garbage collection.

Bill is collecting the garbage in two steps:

He traverses the parking lot, marking the parking spots that the cars occupy. This is the step in which he pauses all the traffic inside the parking lot.
Knowing which spots the cars occupy, he sweeps the unmarked parking spots, which contain the packed trash. He doesn’t touch the unpacked trash as it is still above his pay grade.

This seems to be working for the parking lot, but Bill remarks a new problem.

After he collects the garbage, there are a lot of gaps left in the parking lot. What if the military comes and requests a big contiguous array of parking spots for their tanks?

This problem is heap fragmentation.

Some time passes and Bill comes up with a solution.

At night time, when there is not much traffic in the parking lot, he would lift all the cars with his super-hero strength and realign them so that it creates a contiguous space of free parking spots.

This is heap compaction when the application is in the background.

A parking lot, having all cars on the first row, and empty parking spots on the second row

Compacted parking lot

But still, if the military came during day time, the parking lot would most likely explode.

ART Bill

Throughout the years, Bill has improved his technique.

Now, Bill has received a promotion and he can realign the parking lot during the day time as well. The military can come now with the tanks since Bill can accommodate that.

This is heap compaction even if the application is in the foreground.

The parking lot has advanced as well. The price has gone down and now people are less reticent in parking here.

The parking lot does not pause anymore when Bill marks the occupied spots. The overall garbage collection process is 3x times faster now.

Moreover, the digitalisation of the parking lot made it a lot easier for Bill to track for how much time did each car occupy their parking spot. With this knowledge, Bill now groups the cars in generations.

There are three heap generations:

Young generation (which is further divided into three containers — Eden, S0, S1)
Old generation
Permanent generation

When a car parks for long enough, Bill moves the car to the old generation, followed by the permanent generation.

Each generation has its own dedicated upper limit on the space the parked cars can occupy there. If a generation reaches its limit, Bill starts the garbage collection for that generation only.