Monthly Archives: June 2013

How to write benchmarks in Go

This post continues a series on the testing package I started a few weeks back. You can read the previous article on writing table driven tests here. You can find the code mentioned below in the https://github.com/davecheney/fib repository.

Introduction

The Go testing package contains a benchmarking facility that can be used to examine the performance of your Go code. This post explains how to use the testing package to write a simple benchmark.

You should also review the introductory paragraphs of Profiling Go programs, specifically the section on configuring power management on your machine. For better or worse, modern CPUs rely heavily on active thermal management which can add noise to benchmark results.

Writing a benchmark

We’ll reuse the Fib function from the previous article.

func Fib(n int) int {
        if n < 2 {
                return n
        }
        return Fib(n-1) + Fib(n-2)
}

Benchmarks are placed inside _test.go files and follow the rules of their Test counterparts. In this first example we’re going to benchmark the speed of computing the 10th number in the Fibonacci series.

// from fib_test.go
func BenchmarkFib10(b *testing.B) {
        // run the Fib function b.N times
        for n := 0; n < b.N; n++ {
                Fib(10)
        }
}

Writing a benchmark is very similar to writing a test as they share the infrastructure from the testing package. Some of the key differences are

  • Benchmark functions start with Benchmark not Test.
  • Benchmark functions are run several times by the testing package. The value of b.N will increase each time until the benchmark runner is satisfied with the stability of the benchmark. This has some important ramifications which we’ll investigate later in this article.
  • Each benchmark must execute the code under test b.N times. The for loop in BenchmarkFib10 will be present in every benchmark function.

Running benchmarks

Now that we have a benchmark function defined in the tests for the fib package, we can invoke it with go test -bench=.

% go test -bench=.
PASS
BenchmarkFib10   5000000               509 ns/op
ok      github.com/davecheney/fib       3.084s

Breaking down the text above, we pass the -bench flag to go test supplying a regular expression matching everything. You must pass a valid regex to -bench, just passing -bench is a syntax error. You can use this property to run a subset of benchmarks.

The first line of the result, PASS, comes from the testing portion of the test driver, asking go test to run your benchmarks does not disable the tests in the package. If you want to skip the tests, you can do so by passing a regex to the -run flag that will not match anything. I usually use

go test -run=XXX -bench=.

The second line is the average run time of the function under test for the final value of b.N iterations. In this case, my laptop can execute Fib(10) in 509 nanoseconds. If there were additional Benchmark functions that matched the -bench filter, they would be listed here.

Benchmarking various inputs

As the original Fib function is the classic recursive implementation, we’d expect it to exhibit exponential behavior as the input grows. We can explore this by rewriting our benchmark slightly using a pattern that is very common in the Go standard library.

func benchmarkFib(i int, b *testing.B) {
        for n := 0; n < b.N; n++ {
                Fib(i)
        }
}

func BenchmarkFib1(b *testing.B)  { benchmarkFib(1, b) }
func BenchmarkFib2(b *testing.B)  { benchmarkFib(2, b) }
func BenchmarkFib3(b *testing.B)  { benchmarkFib(3, b) }
func BenchmarkFib10(b *testing.B) { benchmarkFib(10, b) }
func BenchmarkFib20(b *testing.B) { benchmarkFib(20, b) }
func BenchmarkFib40(b *testing.B) { benchmarkFib(40, b) }

Making benchmarkFib private avoids the testing driver trying to invoke it directly, which would fail as its signature does not match func(*testing.B). Running this new set of benchmarks gives these results on my machine.

BenchmarkFib1   1000000000               2.84 ns/op
BenchmarkFib2   500000000                7.92 ns/op
BenchmarkFib3   100000000               13.0 ns/op
BenchmarkFib10   5000000               447 ns/op
BenchmarkFib20     50000             55668 ns/op
BenchmarkFib40         2         942888676 ns/op

Apart from confirming the exponential behavior of our simplistic Fib function, there are some other things to observe in this benchmark run.

  • Each benchmark is run for a minimum of 1 second by default. If the second has not elapsed when the Benchmark function returns, the value of b.N is increased in the sequence 1, 2, 5, 10, 20, 50, … and the function run again.
  • The final BenchmarkFib40 only ran two times with the average was just under a second for each run. As the testing package uses a simple average (total time to run the benchmark function over b.N) this result is statistically weak. You can increase the minimum benchmark time using the -benchtime flag to produce a more accurate result.
    % go test -bench=Fib40 -benchtime=20s
    PASS
    BenchmarkFib40        50         944501481 ns/op

Traps for young players

Above I mentioned the for loop is crucial to the operation of the benchmark driver. Here are two examples of a faulty Fib benchmark.

func BenchmarkFibWrong(b *testing.B) {
        for n := 0; n < b.N; n++ {
                Fib(n)
        }
}

func BenchmarkFibWrong2(b *testing.B) {
        Fib(b.N)
}

On my system BenchmarkFibWrong never completes. This is because the run time of the benchmark will increase as b.N grows, never converging on a stable value. BenchmarkFibWrong2 is similarly affected and never completes.

A note on compiler optimisations

Before concluding I wanted to highlight that to be completely accurate, any benchmark should be careful to avoid compiler optimisations eliminating the function under test and artificially lowering the run time of the benchmark.

var result int

func BenchmarkFibComplete(b *testing.B) {
        var r int
        for n := 0; n < b.N; n++ {
                // always record the result of Fib to prevent
                // the compiler eliminating the function call.
                r = Fib(10)
        }
        // always store the result to a package level variable
        // so the compiler cannot eliminate the Benchmark itself.
        result = r
}

Conclusion

The benchmarking facility in Go works well, and is widely accepted as a reliable standard for measuring the performance of Go code. Writing benchmarks in this manner is an excellent way of communicating a performance improvement, or a regression, in a reproducible way.

Stress test your Go packages

This is a short post on stress testing your Go packages. Concurrency or memory correctness errors are more likely to show up at higher concurrency levels (higher values of GOMAXPROCS). I use this script when testing my packages, or when reviewing code that goes into the standard library.

#!/usr/bin/env bash -e

go test -c
# comment above and uncomment below to enable the race builder
# go test -c -race
PKG=$(basename $(pwd))

while true ; do 
        export GOMAXPROCS=$[ 1 + $[ RANDOM % 128 ]]
        ./$PKG.test $@ 2>&1
done

I keep this script in $HOME/bin so usage is

$ cd $SOMEPACKAGE
$ stress.bash
PASS
PASS
PASS

You can pass additional arguments to your test binary on the command line,

stress.bash -test.v -test.run=ThisTestOnly

The goal is to be able to run the stress test for as long as you want without a test failure. Once you achieve that, uncomment go test -c -race and try again.

How to install Go 1.1 on CentOS 5.9

Important Go 1.0 or 1.1 has never supported RHEL5 or CentOS5. In fact, I don’t think Go will even compile on RHEL5/CentOS5 after version 1.3. Please do not interpret anything in this article as a statement that Go does support RHEL5 or CentOS5.


Introduction

Go has never supported RedHat 5 or CentOS 5. We’ve been pretty good at getting that message out, but it still catches a few people by surprise. The reason these old releases are not supported is the Linux kernel that ships with them, a derivative of 2.6.18, does not provide three facilities required by the Go runtime.

These are

  1. Support for the O_CLOEXEC flag passed to open(2). We attempt to work around this in the os.OpenFile function, but not all kernels that do not support this flag return an error telling us they don’t support it. The result on RHEL5/CentOS5 systems is file descriptors can leak into child processes, this isn’t a big problem, but does cause test failures.
  2. Support for accept4(2). accept4(2) was introduced in kernel 2.6.28 to allow O_CLOEXEC to be set on newly accepted socket file descriptors. In the case that this syscall is not supported, we fall back to the older accept(2) syscall at a small performance hit.
  3. Support for high resolution vDSO clock_gettime(2). vDSO is a way of projecting a small part of the kernel into your process address space. This means you can call certain syscalls (known as vsyscalls) without the cost of a trap into kernel space or a context switch. Go uses clock_gettime(2) via the vDSO in preference to the older gettimeofday(2) syscall as it is both faster, and higher precision.

Installing Go from source

As RHEL5/CentOS5 are not supported, there are no binary packages available on the golang.org website. To install Go you will need to use the source tarball, in this case we’re using the Go 1.1.1 release. I’m using a CentOS 5.9 amd64 image running in a vm.

Install prerequisites

The packages required to build Go on RedHat platforms are listed on the Go community wiki.

$ sudo yum install gcc glibc-devel

Download and unpack

We’re going to download the Go 1.1.1 source distribution and unpack it to $HOME/go.

$ curl https://go.googlecode.com/files/go1.1.1.src.tar.gz | tar xz
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100 8833k  100 8833k    0     0   710k      0  0:00:12  0:00:12 --:--:--  974k
$ ls
Desktop  go

Build

$ cd go/src
$ ./make.bash
# Building C bootstrap tool.
cmd/dist

# Building compilers and Go bootstrap tool for host, linux/amd64.
lib9
libbio
...
Installed Go for linux/amd64 in /home/dfc/go
Installed commands in /home/dfc/go/bin

Add go to PATH

$ export PATH=$PATH:$HOME/go/bin
$ go version
go version go1.1.1 linux/amd64

Known issues

As described above, RHEL5/CentOS5 are not supported as their kernel is too old. Here are some of the known issues. As RHEL5/CentOS5 are unsupported, they will not be fixed.

Test failures

You’ll notice above to build Go I ran make.bash, not the recommended all.bash, to skip the tests. Due to the lack of working O_CLOEXEC support, some tests will fail. This is a known issue and will not be fixed.

$ ./run.bash
...
--- FAIL: TestExtraFiles (0.05 seconds)
        exec_test.go:302: Something already leaked - closed fd 3
        exec_test.go:359: Run: exit status 1; stdout "leaked parent file. fd = 10; want 9\n", stderr ""
FAIL
FAIL    os/exec 0.489s

Segfaults and crashes due to missing vDSO support

A some point during the RHEL5 release cycle support for vDSO vsyscalls was added to RedHat’s 2.6.18 kernel. However that point appears to differ by point release. For example, for RedHat 5, kernel 2.6.18-238.el5 does not work, whereas 2.6.18-238.19.1.el5 does. Running CentOS 5.9 with kernel 2.6.18.348.el5 does work.

$ ./make.bash
...
cmd/go
./make.bash: line 141:  8269 segmentfault  "$GOTOOLDIR"/go_bootstrap clean -i std

In summary, if the your Go programs crash or segfault using RHEL5/CentOS5, you should try upgrading to the latest kernel available for your point release. I’ll leave the comments on this article open for a while so people can contribute their known working kernel versions, perhaps I can build a (partial) table of known good configurations.

You don’t need to set GOROOT, really

Introduction

This is a short post to explain why it is not necessary to set $GOROOT when compiling or using Go.

TL;DR

In general1 it is not necessary to set the $GOROOT environment variable when compiling or using Go 1.0 or later. In fact, setting $GOROOT can lead to hard to debug problems if you have multiple versions of Go present on your computer.

You still need to set $GOPATH. Since Go 1.0 setting $GOPATH has been highly recommended, and with the release of Go 1.1, it is considered mandatory.

Why isn’t GOROOT required anymore ?

You’re still reading ? Excellent. Now for some history.

The history of the GO* environment variables

Go old timers may remember when not only $GOROOT, but $GOOS and $GOARCH were required environment variables. These were required because the Makefile based build system used lots of includes which used $GOROOT as their base path.

By the time the go tool was introduced, prior to Go 1.0, $GOOS and $GOARCH were optional as the build scripts were able to detect the host’s operating system and cpu architecture. With the release of Go 1.0, and the introduction of the cmd/dist bootstrap build tool, $GOOS and $GOARCH became truly optional. They are now only used when cross compiling.

Go 1.0 also introduced $GOPATH based workspaces. If you’ve read this far, you probably know what a $GOPATH workspace is. But in case you don’t, this is documented on the golang.org website, and in this screencast.

Okay, so I don’t need $GOOS or $GOARCH, but what about $GOROOT ?

$GOROOT has always been defined as a pointer to the root of your Go installation. In the old Makefile based build system, it was used as the base path for including other Makefiles, and since Go 1.0 it is used by the go tool to find the compiler (stored in $GOROOT/pkg/tool/$GOOS_$GOARCH) and the standard library (also in $GOROOT/pkg/$GOOS_$GOARCH). If you are a Java user, $GOROOT is similar in effect to $JAVA_HOME.

When you compile Go from source, the value of $GOROOT is automatically discovered2 (it is one directory up from the all.bash script) and then embedded into the go tool built from that source tree. You can see this when you run go env

% echo $GOROOT

% go env GOROOT
/home/dfc/go

The binary distributions you download from the golang.org website, or install from your operating system distribution also have the correct $GOROOT value embedded into the go tool binary. Here is an example from a Ubuntu 12.04 system which ships with Go 1.0.

% dpkg -l golang-{go,src} | grep ^ii
ii  golang-go        2:1-5        Go programming language compiler
ii  golang-src       2:1-5        Go programming language compiler - source files
% which go
/usr/bin/go
% go env GOROOT
/usr/lib/go

You can see that the go tool is installed in /usr/bin/go and $GOROOT is embedded as /usr/lib/go.

So, why shouldn’t I set $GOROOT anymore ?

You should not set $GOROOT because the correct value is already embedded in the go tool.

Setting $GOROOT will override the value stored in the go tool which could lead to the go tool from one version of Go pointing to the compiler and standard library from another version.

There are only two cases that where you may have to set a $GOROOT environment. These are both described in the installation page on the golang.org website. For completeness I will recap them here

  • You are a Linux, FreeBSD or OS X user using the the zip or tarball binary downloads from the golang.org website. These binaries have a $GOROOT value of /usr/local/go and recommend you unpack them into that location. If you choose not to do this, then you must set $GOROOT to the location you chose.
  • You are a Windows user using the zip binary download from the golang.org website. These binaries have a $GOROOT value of C:\Go. If you place Go somewhere else on your system then you must set $GOROOT to the location you chose.

Super nerdy bonus detail

This post has explained how $GOROOT is automatically discovered when compiling from source. I’ve also shown that the build scripts can detect when that value doesn’t match the path that all.bash is invoked from. So, how do operating system distributions set $GOROOT when they normally compile Go in a temporary build directory or chroot? The answer is the $GOROOT_FINAL value, which is used to override the $GOROOT location stored in the go tool.

For example, the Debian/Ubuntu build process will supply a value for $GOROOT_FINAL of /usr/lib/go. This frees it to leave $GOROOT unset, making the build process happy. After the build, the build process will install the go tool in /usr/bin, and the compilers, sources and packages in /usr/lib/go.


  1. There are a few cases where it is required if using the binary distributions of Go, which are described in this post.
  2. That is, if you haven’t set $GOROOT. Although the build system will detect when the parent directory of all.bash does not match $GOROOT.

Writing table driven tests in Go

This article is intended as a short introduction to the mechanics and syntax of writing a table driven test in Go. Supporting this article is a small repository, https://github.com/davecheney/fib, which contains all the code mentioned below.

Introduction

I enjoy writing table driven tests in Go. While not unique to the language, table driven tests leverage several features, composite literals and anonymous structs, to allow you to write related tests in a compact form.

As an example, please consider the case of testing this overused function

package fib

// Fib returns the nth number in the Fibonacci series.
func Fib(n int) int {
        if n < 2 {
                return n
        }
        return Fib(n-1) + Fib(n-2)
}

The table structure

At the heart of all table driven tests is the table itself, which provides the inputs and expected results of the function under test. In most cases the table is a slice of anonymous structs, which allows the table to be written in a compact form.

var fibTests = []struct {
        n        int // input
        expected int // expected result
}{
        {1, 1},
        {2, 1},
        {3, 2},
        {4, 3},
        {5, 5},
        {6, 8},
        {7, 13},
}

If you wished, you could give the struct a name, in which case the table definition would look something like this

type fibTest struct {
        n        int
        expected int
}

var fibTests = []fibTest {
        {1, 1}, {2, 1}, {3, 2}, {4, 3}, {5, 5}, {6, 8}, {7, 13},
}

Hooking it up

Now that we have the table of inputs and results defined, we need to write a driver function to iterate through the inputs and compare the results to their expected value. Rather than one Test function per set of values, we can use the range clause to loop over each test case.

func TestFib(t *testing.T) {
        for _, tt := range fibTests {
                actual := Fib(tt.n)
                if actual != tt.expected {
                        t.Errorf("Fib(%d): expected %d, actual %d", tt.n, tt.expected, actual)
                }
        }
}

In this example we range over all the fibTests defined above, assigning their value in turn to tt. We then call Fib passing in the value of tt.n and compare the result, stored in actual, with the value of tt.expected.

The use of the names actual and expected show my JUnit heritage, others may prefer names like want and got. You should choose something that works for you and gives a clear meaning in your test code.

The use of t.Errorf instead of t.Fatalf is a personal preference. As Fib is a pure function it is safe to continue the loop after a failure. I find this generally reduces test whack-a-mole by returning all the failures at once.

Conclusion

In my introduction I said that table driven tests are one my favorite parts of the Go language. They allow you to write unit tests in a concise fashion, hopefully leading to greater test coverage at a lower line count. If done correctly, adding additional test cases is as simple as a new element in the test table.

This is certainly not the only way that tests could be written in Go, nor the only way to write table driven tests. The Go standard library contains many examples of this form of testing which are worth studying. In particular I suggest the tests for the math and time packages are an excellent starting point.

At the other end of the spectrum is this table driven test of the Juju status command which defines its own language of helpers to populate the table structure. Although this elevates the table driven test to ninja levels, it still contains the same components and concepts, and right at the bottom of the file you’ll find a simple function driving each test.

How Go uses Go to build itself

This post is based on a talk I gave to the Sydney Go users group in mid April 2013 describing the Go build process.


Frequently on mailing list or IRC channel there are requests for documentation on the details of the Go compiler, runtime and internals. Currently the canonical source of documentation about Go’s internals is the source, which I encourage everyone to read. Having said that, the Go build process has been stable since the Go 1.0 release, so documenting it here will probably remain relevant for some time.

This post walks through the nine steps of the Go build process, starting with the source and ending with a fully tested Go installation. For simplicity, all paths mentioned are relative to the root of the source checkout, $GOROOT/src.

For background you should also read Installing Go from source on the golang.org website.

Step 1. all.bash

% cd $GOROOT/src
% ./all.bash

The first step is a bit anticlimactic as all.bash just calls two other shell scripts; make.bash and run.bash. If you’re using Windows or Plan 9 the process is the same, but the scripts end in .bat or .rc respectively. For the rest of this post, please substitute the extension appropriate for your operating system.

Step 2. make.bash

. ./make.bash --no-banner

make.bash is sourced from all.bash so that calls to exit will terminate the build process properly. make.bash has three main jobs, the first job is to validate the environment Go is being compiled in is sane. The sanity checks have been built up over the last few years and generally try to avoid building with known broken tools, or in environments where the build will fail.

Step 3. cmd/dist

gcc -O2 -Wall -Werror -ggdb -o cmd/dist/dist -Icmd/dist cmd/dist/*.c

Once the sanity checks are complete, make.bash compiles cmd/dist. cmd/dist replaces the Makefile based system which existed before Go 1 and manages the small amounts of code generation in pkg/runtime. cmd/dist is a C program which allows it to leverage the system C compiler and headers to handle most of the host platform detection issues. cmd/dist always detects your host’s operating system and architecture, $GOHOSTOS and $GOHOSTARCH. These may differ from any value of $GOOS and $GOARCH you may have set if you are cross compiling. In fact, the Go build process is always building a cross compiler, but in most cases the host and target platform are the same. Next, make.bash invokes cmd/dist with the bootstrap argument which compiles the supporting libraries, lib9, libbio and libmach, used by the compiler suite, then the compilers themselves. These tools are also written in C and are compiled by the system C compiler.

echo "# Building compilers and Go bootstrap tool for host, $GOHOSTOS/$GOHOSTARCH."
buildall="-a"
if [ "$1" = "--no-clean" ]; then
 buildall=""
fi
./cmd/dist/dist bootstrap $buildall -v # builds go_bootstrap

Using the compiler suite, cmd/dist then compiles a version of the go tool, go_bootstrap. The go_bootstrap tool is not the full go tool, for example pkg/net is stubbed out which avoids a dependency on cgo. The list of directories containing packages or libraries be compiled, and their dependencies is encoded in the cmd/dist tool itself, so great care is taken to avoid introducing new build dependencies for cmd/go.

Step 4. go_bootstrap

Now that go_bootstrap is built, the final stage of make.bash is to use go_bootstrap to compile the complete Go standard library, including a replacement version of the full go tool.

echo "# Building packages and commands for $GOOS/$GOARCH."
"$GOTOOLDIR"/go_bootstrap install -gcflags "$GO_GCFLAGS" \
    -ldflags "$GO_LDFLAGS" -v std

Step 5. run.bash

Now that make.bash is complete, execution falls back to all.bash, which invokes run.bash. run.bash‘s job is to compile and test the standard library, the runtime, and the language test suite.

bash run.bash --no-rebuild

The --no-rebuild flag is used because make.bash and run.bash can both invoke go install -a std, so to avoid duplicating the previous effort, --no-rebuild skips the second go install.

# allow all.bash to avoid double-build of everything
rebuild=true
if [ "$1" = "--no-rebuild" ]; then
 shift
else
 echo '# Building packages and commands.'
 time go install -a -v std
 echo
fi

Step 6. go test -a std

echo '# Testing packages.'
time go test std -short -timeout=$(expr 120 \* $timeout_scale)s
echo

Next run.bash is to run the unit tests for all the packages in the standard library, which are written using the testing package. Because code in $GOPATH and $GOROOT live in the same namespace, we cannot use go test ... as this would also test every package in $GOPATH, so an alias, std, was created to address the packages in the standard library. Because some tests take a long time, or consume a lot of memory, some tests filter themselves with the -short flag.

Step 7. runtime and cgo tests

The next section of run.bash runs a set of tests for platforms that support cgo, runs a few benchmarks, and compiles miscellaneous programs that ship with the Go distribution. Over time this list of miscellaneous programs has grown as it was found that when they were not included in the build process, they would inevitably break silently.

Step 8. go run test

(xcd ../test
unset GOMAXPROCS
time go run run.go
) || exit $?

The penultimate stage of run.bash invokes the compiler and runtime tests in the test folder directly under $GOROOT. These are tests of the low level details of the compiler and runtime itself. While the tests exercise the specification of the language, the test/bugs and test/fixedbugs sub directories capture unique tests for issues which have been found and fixed. The test driver for all these tests is $GOROOT/test/run.go which is a small Go program that runs each .go file inside the test directory. Some .go files contain directives on the first line which instruct run.go to expect, for example, the program to fail, or to emit a certain output sequence.

Step 9. go tool api

echo '# Checking API compatibility.'
go tool api -c $GOROOT/api/go1.txt,$GOROOT/api/go1.1.txt \
    -next $GOROOT/api/next.txt -except $GOROOT/api/except.txt

The final step of run.bash is to invoke the api tool. The api tool’s job is to enforce the Go 1 contract; the exported symbols, constants, functions, variables, types and methods that made up the Go 1 API when it shipped in 2012. For Go 1 they are spelled out in api/go1.txt, and Go 1.1, api/go1.1.txt. An additional file, api/next.txt identifies the symbols that make up the additions to the standard library and runtime since Go 1.1. Once Go 1.2 ships, this file will become the contract for Go 1.2, and there will be a new next.txt. There is also a small file, except.txt, which contains exceptions to the Go 1 contract which have been approved. Additions to the file are not expected to be taken lightly.

Additional tips and tricks

You’ve probably figured out that make.bash is useful for building Go without running the tests, and  likewise, run.bash is useful for building and testing the Go runtime. This distinction is also useful as the former can be used when cross compiling Go, and the latter is useful if you are working on the standard library.

Update: Thanks to Russ Cox and Andrew Gerrand for their feedback and suggestions.

Why is a Goroutine’s stack infinite ?

Occasionally new Gophers stumble across a curious property of the Go language related to the amount of stack available to a Goroutine. This typically arises due to the programmer inadvertently creating an infinitely recursive function call. To illustrate this, consider the following (slightly contrived) example.

package main

import "fmt"

type S struct {
        a, b int
}

// String implements the fmt.Stringer interface
func (s *S) String() string {
        return fmt.Sprintf("%s", s) // Sprintf will call s.String()
}

func main() {
        s := &S{a: 1, b: 2}
        fmt.Println(s)
}

Were you to run this program, and I do not suggest that you do, you’d find that your machine would start to swap heavily, and will probably become unresponsive unless you’re quick to hit ^C before things become unsalvageable  Because I know the first thing everyone will do is try to run this program in the playground, I’ve saved you the bother.

Most programmers have run into problems with infinite recursion before, and while it is fatal to their program, it isn’t usually fatal to their machine. So, why are Go programs different ?

One of the key features of Goroutines is their cost; they are cheap to create in terms of initial memory footprint (as opposed to the 1 to 8 megabytes with a traditional POSIX thread) and their stack grows and shrinks as necessary. This allows a Goroutine to start with a single 4096 byte stack which grows and shrinks as needed without the risk of ever running out.

To implement this the linker (5l, 6l, 8l) inserts a small preamble at the start of each function1, which checks to see if the amount of stack required for the function is below the amount currently available. If not, a call is made to runtime⋅morestack, which allocates a new stack page2, copies the arguments from the caller, then returns control to the original function which can now execute safely. When that function exits, the process is undone, its return arguments are copied back to the stack frame of the caller and the unneeded stack space released.

By this process the stack is effectively infinite, and assuming that you’re not continually straddling the boundary between two stacks, colloquially known as stack splitting, is very cheap.

There is however one detail I have withheld until now, which links the accidental use of a recursive function to a serious case of memory exhaustion for your operating system, and that is, when new stack pages are needed, they are allocated from the heap.

As your infinite function continues to call itself, new stack pages are allocated from the heap, permitting the function to continue to call itself over and over again. Fairly quickly the size of the heap will exceed the amount of free physical memory in your machine, at which point swapping will soon make your machine unusable.

The size of the heap available to Go programs depends on a lot of things, including the architecture of your CPU and your operating system, but it generally represents an amount of memory that exceeds the physical memory of your machine, so your machine is likely to swap heavily before your program ever exhausts its heap.

In Go 1.1 there was a strong desire to increase the maximum size of the heap for both 32 bit and 64 bit platforms, and this has exacerbated the problem to some extent, ie, it is unlikely that you will have 128Gb3 of physical memory in your system.

As a final comment, there are several open issues (linklink) regarding this problem, but a solution that does not extract a performance penalty on properly written programs has yet to be found.

Notes
  1. This also applies to methods, but as methods are implemented as functions where the first argument is the method receiver, there is no practical difference when discussion how segmented stacks work in Go.
  2. Using the word page does not imply that only fixed, 4096 byte, allocations are possible, if necessary runtime⋅morestack will allocate a larger amount, probably rounded to a page boundary.
  3. 64 bit Windows platforms only permit a 32Gb heap due to a late change in the Go 1.1 release cycle.