Performance

Where did that Go value escape to?

I changed a small parser to reuse a helper and made it slower. This was irritating because the new version looked cleaner, performed the same amount of useful work, and did not contain the traditional performance feature known as “a very silly loop.”

The reduced example looked like this:

type point struct {
	x, y int
}

func origin() *point {
	p := point{}
	return &p
}

Anyone arriving from C may feel a brief alarm here. p is local, yet the function returns its address. Go makes this safe by deciding where the value must live. The important distinction is not whether the source declares a value inside a function. It is whether the compiler can prove that the value stops being reachable when that function returns.

If it cannot, the value escapes and is allocated somewhere with a lifetime long enough for its uses, normally the heap. If it can prove the value remains local, it can use the goroutine’s stack. This analysis is why Go can permit returning a pointer to a local without turning every local variable into a heap allocation.

A small experiment

I wrote two deliberately uninteresting benchmarks:

var sink *point

func local() int {
	p := point{x: 20, y: 22}
	return p.x + p.y
}

func escaping() int {
	p := point{x: 20, y: 22}
	sink = &p
	return p.x + p.y
}

The arithmetic is identical. The assignment to the package variable is not. After escaping returns, another function can read sink, so p must survive. The compiler cannot put it in a dead stack frame and hope nobody notices.

The compiler can print its decisions. Building with the compiler’s escape-analysis diagnostics enabled is considerably more useful than staring at new(point) and guessing. The exact wording and flags are compiler details and may change, but reports identifying values moved to the heap make a good starting point.

This matters because source syntax alone is a poor allocation detector. new(T) does not decree that T lives on the heap. Returning a value does not decree that a copy must be heap allocated. Conversely, innocent-looking interface conversions, closures, or calls through code the compiler cannot fully inspect may cause values to escape.

Interfaces and hidden addresses

Suppose I replace a direct call with this:

func printAny(v interface{}) {
	fmt.Println(v)
}

func report() {
	p := point{x: 20, y: 22}
	printAny(p)
}

Putting p into an interface constructs an interface value containing dynamic type information and the value’s data. Depending on what the compiler knows about the call and how that data is represented, it may need storage beyond the current frame. The right answer is not “interfaces allocate.” The right answer is to inspect this particular program with this compiler, then measure it. Blanket rules age badly.

Closures offer a more obvious case:

func counter() func() int {
	n := 0
	return func() int {
		n++
		return n
	}
}

The returned function still uses n, so n cannot disappear when counter returns. The compiler arranges storage for the captured variable. This is not a leak. It is the semantics I asked for, delivered with a bill attached.

Stack is not a moral achievement

It is tempting to read an escape report as a list of compiler failures. That is not helpful. Heap allocation is necessary whenever data outlives a call, and Go’s garbage collector exists precisely because many useful objects do. The report says where the compiler could prove a lifetime, not whether the code is virtuous.

Still, allocations have costs. Allocating requires runtime work. More live heap data gives the garbage collector more to consider. A short-lived object may be cheap, but a hot loop producing millions of them deserves attention. I use benchmarks to establish that the path matters, allocation diagnostics to locate candidates, and another benchmark to verify the change. Reversing this order produces beautifully optimized code nobody needed.

Sometimes a small API change keeps a value local. A function can fill a caller-owned value instead of returning a pointer:

func setOrigin(p *point) {
	p.x = 0
	p.y = 0
}

func distance() int {
	var p point
	setOrigin(&p)
	return p.x + p.y
}

Passing an address does not automatically force escape. If the compiler can see that setOrigin does not retain it, p may remain on the caller’s stack. Again, the analysis follows lifetime, not punctuation.

I fixed my parser by removing one retained pointer from a frequently called helper. The result allocated less and recovered the lost time. I did not redesign every function to avoid pointers, because that would exchange a measured problem for a readability problem.

Escape analysis is best treated as an explanation facility. It tells me why the runtime is allocating when a profile says allocation matters. That is much better than the old C technique of declaring stack allocation “fast,” then accidentally returning its address and discovering a more exciting category of performance bug.

Making the Scheduler Show Its Work

Scheduler discussions become folklore quickly, so I built a few experiments that force observable events instead of inferring everything from total runtime.

The first launches workers that announce when they start, wait on a gate, perform fixed CPU work, and announce completion. A channel carries each announcement to one logger goroutine. That gives me a trace without concurrent writes making the output resemble ransom typography.

func worker(id int, gate <-chan bool, events chan<- Event) {
    events <- Event{id, "ready"}
    <-gate
    burnCPU()
    events <- Event{id, "done"}
}

I run the same executable with different GOMAXPROCS values. With one processor thread allowed, CPU-bound completion is serialized even though all workers are runnable. With two, completions overlap in wall time on my dual-core machine. More than two adds runnable work but no additional cores, and eventually loses to scheduling overhead.

The second experiment replaces CPU work with pipe reads. Many goroutines can wait for I/O while the runtime arranges for other work to proceed. Increasing the processor allowance barely changes throughput because the external producer is the limit. This is why one benchmark cannot characterize “goroutine performance.”

The third experiment is intentionally rude: one goroutine runs a tight arithmetic loop with no communication while another tries to report periodically. On this early runtime, the reporter can be delayed noticeably. Scheduling behavior is under active development, and I should not assume the preemption properties of a mature operating-system scheduler.

Adding explicit communication points makes the test cooperative and reflects real pipeline code better. I do not sprinkle meaningless calls into production loops merely to influence today’s runtime; I break large work into units with natural channel operations or function calls, then measure again.

The event channel affects the experiment, of course. Observing a scheduler changes timing by adding synchronization. I keep messages outside the inner loop and compare against an uninstrumented wall-clock run. The trace explains ordering; it does not provide cycle-accurate truth.

These results belong to the May 2011 snapshot and my machine. They are not a specification of future Go scheduling, and I am deliberately avoiding an internal diagram that will expire before the ink dries. The practical findings are modest: concurrency is not parallelism, blocking and CPU work stress different paths, and processor settings should follow measurements. Schedulers are quite willing to show their work, but only if the experiment asks a specific question.

Cache Lines Beat Clever Loops

I translated a matrix filter from C to Go and then spent an afternoon optimizing arithmetic that was not the main cost. The profile pointed at memory movement, so I reduced the problem to traversal order.

The matrix is stored in one slice in row-major order. These loops calculate the same sum:

for y := 0; y < height; y++ {
    for x := 0; x < width; x++ {
        sum += pixels[y*width+x]
    }
}
for x := 0; x < width; x++ {
    for y := 0; y < height; y++ {
        sum += pixels[y*width+x]
    }
}

The first walks adjacent elements. The second jumps by an entire row. On a large image the row-wise loop is much faster because each fetched cache line supplies several values used immediately. The column-wise loop asks the processor to fetch many lines and uses a small part of each before moving on.

Bounds checks and multiplication were my original suspects. Hoisting the row offset made the code clearer and helped a little:

for y := 0; y < height; y++ {
    row := pixels[y*width:(y+1)*width]
    for x := 0; x < width; x++ {
        sum += row[x]
    }
}

But traversal order remained the large effect. A more sophisticated arithmetic trick could not compensate for unfriendly access.

I benchmark with enough data to exceed the small caches, repeat the operation, and verify the sum so the compiler cannot discard the work. These are 2011 compiler snapshots, so absolute timings and optimization behavior are temporary facts. The memory hierarchy is less temporary.

I alternate test order as well. Running one version first every time can give it consistently colder data and turn benchmark order into a hidden input.

This also affects data structure choice. A slice of small structures may have better locality than a slice of pointers to separately allocated structures. The latter adds pointer chasing and gives the allocator freedom to scatter objects. It may still be right when identity and independent lifetimes matter, but it is not free.

My practical conclusion is embarrassingly physical: visit data in the order it lies in memory. Before unrolling loops or translating a bit trick from C, inspect the access pattern. The processor is very fast when fed and becomes an expensive space heater when asked to wait.

One Thread, Two Threads

I ran two independent CPU loops in goroutines and expected my dual-core machine to halve the time. It did not. Expectations remain the cheapest profiler available and the least accurate.

This runtime defaults to limited processor use. Setting GOMAXPROCS=2 for the experiment allowed Go work to execute on two operating-system threads:

$ time GOMAXPROCS=1 ./spin
real  0m3.84s

$ time GOMAXPROCS=2 ./spin
real  0m2.17s

The result is not exactly half. Both loops touch memory, the scheduler has work, and the rest of the machine has declined to disappear for my benchmark.

Goroutines and parallel execution are separate ideas. Thousands of goroutines can make a concurrent design clear while one thread runs them. Increasing the thread allowance can provide parallelism when there is independent CPU work and hardware to execute it.

The early scheduler also has rough edges. A tight loop with no calls may delay other goroutines more than I expect from mature thread schedulers. I add real synchronization rather than relying on hopeful fairness, and I test the weekly runtime I intend to use.

For I/O-heavy programs, two processor threads may change little. For CPU loops, it can help until memory bandwidth or coordination dominates. The variable is a knob, not a turbo button. Turbo buttons at least had a satisfying light.

Counting Bits Like the Kernel

Kernel code contains algorithms that look unnecessarily peculiar until the constraints are visible. Population count, the number of set bits in a machine word, is a good example.

The obvious C version examines every bit:

unsigned int count_bits(unsigned long word)
{
        unsigned int n = 0;

        while (word) {
                n += word & 1;
                word >>= 1;
        }
        return n;
}

This performs one iteration for every bit position up to the highest set bit. A sparse bitmap still pays for all the zeros in between.

Brian Kernighan’s familiar operation removes the lowest set bit at each iteration:

unsigned int count_bits(unsigned long word)
{
        unsigned int n = 0;

        while (word) {
                word &= word - 1;
                n++;
        }
        return n;
}

Subtracting one flips the lowest set bit to zero and turns lower zeros into ones. The & keeps everything above that bit and clears the changed suffix. The loop therefore runs once per set bit.

That is excellent for sparse words and less impressive for dense ones. Kernels also use table lookups and architecture-specific instructions where available. A byte table has predictable work but adds memory access; a processor instruction can win decisively but needs dispatch or compile-time selection. There is no universally fastest source fragment independent of data and machine.

Word width matters too. Kernel types and helpers make that choice explicit, while a casual userspace benchmark can accidentally compare different widths and announce a victory produced by less work.

I benchmarked the two loops over generated sparse and dense arrays, keeping generation outside the timed section. As expected, the clear-lowest-bit version dominated sparse input. Dense input narrowed the gap considerably. Repeating one constant word produced lovely numbers and measured the compiler more than the routine, so I stopped doing that.

The broader lesson from kernel work is to understand the representation before admiring the trick. Bitmaps pack state compactly and permit word-at-a-time operations, but contention, cache placement, and scan direction can matter more than shaving an instruction from population count.

I like this algorithm because its mechanism fits in one sentence and its performance caveat requires another. Most optimization stories should have both sentences. The ones with only the first usually end in a benchmark that accidentally proves the author’s laptop exists.