Garbage collector in Go: solving the problem of responsiveness in Go 1.5

This material is a translation of a blog post in real time by the guys from Sourcegraph from the GopherCon 2015 conference, which takes place these days in Denver, Colorado. Full video and slides of the report will be added to the post as soon as they are available.

Richard L. Hudson (Rick) is famous for his work in memory management, including the invention of the Train, Sapphire and Mississippi Delta algorithms, as well as GC stack maps, which allowed for garbage collection in statically-typed languages like Java, C # and Go. Under his authorship were published documents about runtimes of languages, memory management, multithreading, synchronization, memory models and transactional memory. Rick is now a member of the Go team at Google and is working on the problems of the garbage collector and runtime.

')
In economics, there is the concept of "closed loop", when one process strengthens another, which leads to the strengthening of the first. Historically, in the computer world, such a “closed loop” was between the development of hardware and software. The processors became faster, which contributed to the writing of more powerful software, which, in turn, stimulated a further increase in the speed of the processors and the power of the computer as a whole. This cycle worked until about 2004, when Moore's Law stopped working.

Nowadays, a twofold increase in the number of transistors does not mean a twofold acceleration of programs. More transistors == more processor cores, but the programs did not evolve enough to use more cores. And precisely because modern programs do not use multi-core to the fullest, the guys developing processors simply do not add more cores. The loop is dead.

Go's long-term mission is to restart this cycle, giving the world more parallel, competitive programs. A more short-term mission is to increase acceptance of Go by the global developer community. And one of the biggest complaints about Go at the moment is that the garbage collector’s pauses are too long.

When their team initially took up the problem, he jokingly says that their initial reaction, as engineers, was not to solve the problem itself, but to find a workaround, something like this:

add eye tracking to computers, and start the garbage collector when no one is looking
show the network idle icon during the garbage collection phase, and blaming for the pauses is not a garbage collector, but network latency or something else

But Russ Cox, for some reason, flunked these ideas in the bud, and they decided to roll up their sleeves and actually improve the garbage collector at Go. They came up with an algorithm that reduces GC pauses, but makes the program a little slower. Go programs will become a bit slower in exchange for guaranteed low pauses of garbage collection phases.

What delays can we distinguish?

Nanosecond: Grace Hopper compared time with distance. Nanosecond is 11.8 inches.
Microsecond: 5.4 microseconds is the time it takes for the light to travel 1 mile in a vacuum.
Milliseconds:
- 1: 1MB sequential read with SSD.
- 20: Reading 1MB from a rotating disk.
- 50: Threshold perception (reaction threshold)
- 50+: Various Network Delays
- 300: Blinking eyes

So how much garbage collection work can we have in one millisecond?

Java GC vs Go GC

Go:

thousand gorutin
channel synchronization
runtime is written in Go using its features like regular code
control of spatial locality (you can embed structures, internal pointers (& foo.field))

Java:

dozens of Java threads
synchronization through objects / locks
runtime written in C
objects are linked via pointers

The biggest difference here is the issue of spatial locality. In Java, everything is a pointer, but in Go you can embed structures one into another. When you have to follow links to many levels in depth, this can create a lot of problems for the garbage collector.

Garbage Collection Basics

Here is a brief example of how a garbage collector works. Usually, it consists of two phases:

Scan Phase: Determine which items in the heap are reachable. This includes pointers to stacks, registers, global variables, and further pointers on the heap.
Marking Phase: Pass through the pointer graph. Mark objects as achievable during the execution of the program. From the point of view of the garbage collector, the easiest way is to “stop the world” so that the pointers do not change during this phase at all. A really parallel garbage collector is very difficult to do, because pointers are constantly changing. The program uses so-called “write barriers” to write to the garbage collector that this object does not need to be captured. In practice, however, recording barriers can produce even worse results than “stopping the world”.

Garbage collector in Go

The new Go garbage collection algorithm uses a combination of write barriers and short pauses to “stop the world.” Here are its phases:

This is how the garbage collector in Go 1.4 looked like:

And this is how it looks in Go 1.5:

Notice that the pause for “stop the world” is much shorter. While running the parallel garbage collector, it uses 25% of the processor.

Here are the test results:

In previous versions of Go, garbage collector pauses were generally much longer and increased as the size of the heap grew. In Go 1.5, garbage collector pauses have become more than an order of magnitude smaller.

If you bring the numbers closer, you can see that there is still a weak positive correlation between the heap size and the duration of GC pauses. But they know the reason and it will be eliminated in Go 1.6.

There is a small performance penalty with the new algorithm, but this penalty decreases as the heap volume grows.

Looking to the future

Tell people that garbage collector pauses are no longer a problem in Go. Looking to the future, they plan to tinker up with the garbage collector to achieve even shorter pauses, more productivity and more predictability. They want to find the optimal ratio in this compromise. The development of Go 1.6 will depend on feedback, so they are very much waiting for feedback from the community.