Escape Analysis in Go: Stack vs. Heap

What do you think the following C code will do?

#include <stdio.h>

int* f() {
    int a;
    a = 42;
    return &a;
}

void main()
{
    printf("%d", *f());
}

If you’re a Go programmer, you may be surprised by the answer:

main.c:6:12: warning: function returns address of local variable [-Wreturn-local-addr]                                                 
Segmentation fault (core dumped)

We get a seg fault - which the compiler warned us about.

Here’s an equivalent program in Go. As expected, this program will print 42 to stdout.

package main

import (
	"fmt"
)

func f() *int {
	a := 42
	return &a
}

func main() {
	fmt.Printf("%d", *f())
}

Stack vs. Heap

The difference between these two programs comes down to where the compiler determines a should be stored in memory: on the stack or on the heap.

In C, the variable lives in the stack frame of f(). When the function returns, the stack is popped and the memory addresses of any variables in that frame become invalid. Accessing them leads to a segmentation fault.

Similarly in Go, the compiler will also try to allocate a variable to the local stack frame of the function in which it is declared. However, it is also able to perform escape analysis: if it cannot prove that a variable is not referenced after the function returns, then it allocates it on the heap instead.

We can see this in action by compiling the above program with the following flags:

> go build -o ./main -gcflags=-m ./main.go
# command-line-arguments
./main.go:7:6: can inline f
./main.go:13:21: inlining call to f
./main.go:13:12: inlining call to fmt.Printf
./main.go:8:2: moved to heap: a
./main.go:13:19: *(*int)(~r0) escapes to heap
./main.go:13:12: []interface {} literal does not escape
<autogenerated>:1: .this does not escape

The compiler moved a to the heap. (Additionally, we can also see that the compiler applied an optimisation to inline the call to f()).

Garbage Collection

It’s important to note that, unlike the stack, the heap does not clean up after itself. As the heap grows, the Garbage Collector (GC) must tidy it up by removing variables that will no longer be used by your program.

To understand this more deeply, let’s create a trace of a very similar program, using Dave Cheney’s excellent pkg/profile:

package main

import (
	"fmt"

	"github.com/pkg/profile"
)

func f() *int {
	a := 42
	return &a
}

func main() {
	defer profile.Start(profile.TraceProfile, profile.ProfilePath(".")).Stop()
	for i := 0; i < 1000000; i++ {
		fmt.Printf("%d", *f())
	}
}

We can inspect the results by running go tool trace trace.out:

You can see the heap footprint increasing with time. At a certain point, the GC runs and cleans up the heap, before it starts growing again.

If we rewrite the program so that there is no reference to a outside of the stack frame, then the variable doesn’t escape to the heap.

package main

import (
	"github.com/pkg/profile"
)

func f() int {
	a := 42
	return a
}

func main() {
	defer profile.Start(profile.TraceProfile, profile.ProfilePath(".")).Stop()
	for i := 0; i < 1000000; i++ {
		f()
	}
}

// go build -o ./main -gcflags=-m ./main.go
// # command-line-arguments
// ./main.go:7:6: can inline f
// ./main.go:15:4: inlining call to f
// ./main.go:13:21: ... argument does not escape

Now we can see that the heap does not grow:

Goroutine Stacks

Consider this program. We can see that a does not escape to the heap, since it is not modified “above” f’s stack frame, (only “below”, in g’s).

package main

func g(a *int) {
	*a++
}

func f() int {
	a := 42
	g(&a)
	return a
}

func main() {
	for i := 0; i < 1000000; i++ {
		f()
	}
}

// go build -o ./main -gcflags=-m ./main.go
// # command-line-arguments
// ./main.go:9:6: can inline g
// ./main.go:13:6: can inline f
// ./main.go:15:3: inlining call to g
// ./main.go:22:4: inlining call to f
// ./main.go:22:4: inlining call to g
// ./main.go:9:8: a does not escape

What happens if we execute g in a goroutine? We find that a escapes to the heap.

package main

func g(a *int) {
	*a++
}

func f() int {
	a := 42
	go g(&a) // yes, this is a race condition, but this is just a demo :)
	return a
}

func main() {
	for i := 0; i < 1000000; i++ {
		f()
	}
}

// go build -o ./main -gcflags=-m ./main.go
// # command-line-arguments
// ./main.go:3:6: can inline g
// ./main.go:3:8: a does not escape
// ./main.go:8:2: moved to heap: a

This is because each goroutine has its own stack. As a result, the compiler cannot guarantee that f’s stack hasn’t been popped (invalidating a) when g accesses it. Therefore, the variable must live on the heap.

The stack allocated to a goroutine is initially very small, which helps keep goroutines very lightweight. The stack will then grow and shrink in size as required. As of Go 1.3, a goroutine’s stack is a contiguous block of memory. To grow the stack, it allocates a segment that is twice the size of the old stack, before copying over the old stack data to the new. As a result, the underlying memory addresses of your variables will change. The way this is implemented is very interesting - I recommend this excellent post from Cloudfare to understand this more deeply. As a demonstration, consider the following program:

package main

const size = 1024

func main() {
	s := "foobar"
	stackCopy(&s, 0, [size]int{})
}

func stackCopy(s *string, c int, a [size]int) {
	println(c, s)
	c++
	if c == 24 {
		return
	}
	stackCopy(s, c, a)
}

Here we recursively call stackCopy to grow the stack, up to 24 stack frames deep, printing the underlying memory address of the string in each frame.

go run ./main.go
0 0xc000107f68
1 0xc000107f68
2 0xc000117f68 // change!
3 0xc000117f68
4 0xc000117f68
5 0xc000117f68
6 0xc000137f68 // change!
7 0xc000137f68
8 0xc000137f68
9 0xc000137f68
10 0xc000137f68
11 0xc000137f68
12 0xc000137f68
13 0xc000137f68
14 0xc000177f68 // change!
15 0xc000177f68
16 0xc000177f68
17 0xc000177f68
18 0xc000177f68
19 0xc000177f68
20 0xc000177f68
21 0xc000177f68
22 0xc000177f68
23 0xc000177f68
24 0xc000177f68
25 0xc000177f68
26 0xc000177f68
27 0xc000177f68
28 0xc000177f68
29 0xc000177f68
30 0xc0001f7f68 // change!
...

We can see that the memory address s changes for every time the stack depth doubles.

For further reading, I recommend this excellent post from Ardan Labs. For some limitations on escape analysis in Go, checkout this post.

Conclusion

The way a variable is used - not declared - determines whether it lives on the stack or the heap. Garbage collection in Go is an extremely useful property of the language. It reduces the likelihood of memory leaks and frees up your time so you can focus on the business logic of your application. Still, remember that this luxury does come at a cost.

I would like to note that in my experience, there are often other bottlenecks in my programs that can be addressed before optimising heap usage. The GC is highly optimised. As always, use profiling to understand your program before blindly applying optimisations.

If you wish to control the frequency with which the GC runs, you have a couple of options. The GOGC environment variable can be used to control the ratio of heap growth that triggers the GC. Alternatively, you may decide to use a ballast.

As always, if you’ve got comments, questions or feedback you can hit me up on Twitter ✌️