Programming

The Go memory model and my broken flag

I wrote the concurrency equivalent of checking whether the refrigerator light is off by repeatedly opening the door:

var ready bool
var value string

func load() {
	value = "finished"
	ready = true
}

func main() {
	go load()
	for !ready {
	}
	fmt.Println(value)
}

It worked on my machine, which is information about my machine rather than evidence that the program is correct.

Two goroutines access ready, one writes it, and there is no synchronization. The same is true for value: seeing ready does not create a language guarantee that the write to value is visible. Compilers and processors may reorder operations where a single goroutine cannot observe the difference. Caches and registers add further opportunities for my intuition to be wrong.

The Go memory model describes which operations establish a “happens before” relationship. If one event happens before another, the effects required by that relationship are visible in the defined order. Goroutine creation, channel communication, mutex operations, and package initialization provide useful ordering guarantees. A hopeful loop around a boolean does not.

The channel version says what I meant:

func load(done chan bool) {
	value = "finished"
	done <- true
}

func main() {
	done := make(chan bool)
	go load(done)
	<-done
	fmt.Println(value)
}

The send happens before the corresponding receive completes. Since value is written before the send, reading it after the receive is properly ordered. Better still, the channel documents the handoff instead of hiding it behind a global flag.

A mutex would also work. Unlocking a mutex and subsequently locking it establishes the required ordering around protected data. The choice is not that channels are holy and mutexes are regrettable. Channels fit ownership transfer and signalling; mutexes fit shared state with a clear invariant. Using the mechanism that expresses the relationship makes the program easier to audit.

This is not merely a question of whether reading and writing a machine-sized boolean is individually atomic. Even if a load cannot tear, atomicity of that one load does not order the separate write to value. “But the flag is only one byte” answers the wrong question with admirable confidence.

The safe rule is pleasantly boring: when multiple goroutines access data and at least one modifies it, arrange synchronization unless the operations use a specifically documented atomic mechanism. Do not infer ordering from sleep calls, observed scheduling, processor brand, or the phase of the moon.

I like Go’s concurrency syntax because it makes the correct version short. That does not make every short concurrent program correct. Goroutines remove ceremony from concurrency, not causality.

gofmt is an AST program

I wanted to rename a field across a pile of Go files. My first impulse was a regular expression. My second, considerably healthier impulse was to remember that Go ships with a parser.

Source code is text, but edits usually concern syntax. The go/parser package reads source into nodes from go/ast. An identifier is an *ast.Ident; a function declaration is an *ast.FuncDecl; an expression has structure beyond where its parentheses happened to land. Once the source is a tree, a tool can ask precise questions instead of hoping a comment does not look executable.

Here is a tiny program that lists function names:

package main

import (
	"fmt"
	"go/ast"
	"go/parser"
	"go/token"
)

func main() {
	fset := token.NewFileSet()
	f, err := parser.ParseFile(fset, "sample.go", nil, 0)
	if err != nil {
		panic(err)
	}
	ast.Inspect(f, func(n ast.Node) bool {
		if fn, ok := n.(*ast.FuncDecl); ok {
			fmt.Println(fn.Name.Name)
		}
		return true
	})
}

token.FileSet connects tree positions to files, lines, and columns. It looks like administrative furniture until an error must say exactly where it found something. Then it becomes the only chair in the room.

After changing a tree, go/printer can write Go source in the standard layout. This is the important lesson of gofmt: parse syntax, then print it consistently. It is not lining up text with an especially ambitious set of regular expressions.

Comments make transformations subtler. Parsing with parser.ParseComments retains comment groups, but moving nodes while preserving the intended comment association still requires care. Imports are another edge. A rename may change whether an import is used, and blindly printing the tree does not make semantic mistakes disappear.

There is also a limit to what the AST alone knows. The syntax tree can tell me that x.Name is a selector expression. It cannot, by itself, tell me which package or type supplied Name. That needs type information. For a local mechanical transformation with an unambiguous syntactic shape, the AST is often enough. For a semantic rename, it may not be.

My field change ended up being a dozen lines around ast.Inspect, followed by formatting and a review of the diff. That was more code than a one-line substitution and much less code than repairing a one-line substitution after it renamed examples, comments, and an unrelated field with the same spelling.

I used to think gofmt was mainly a successful ceasefire in the whitespace wars. It also shows the value of shipping language tools as ordinary libraries: the compiler is not the only program allowed to understand Go source.

Linux Kernel Linked List Explained

I appreciate beautiful, readable code. And if someone were to ask me for an example of beautiful code, I’ve always had the answer ready: the linked list implementation in the Linux kernel.

The code is gorgeous in its simplicity, clarity, and amazing flexibility. If there’s ever a museum for code, this belongs there. It is a masterpiece of the craft.

I was just telling a friend about it while we talked about beautiful code and he found this piece that I share here: Linux Kernel Linked List Explained.

Measuring and tuning Go GC pauses

One request in a test server occasionally took much longer than its neighbours. Rather than convict the collector from one latency graph, I recorded request times and the runtime’s pause samples on the same workload.

The current collector stops application work while it traces the reachable heap. runtime.ReadMemStats exposes NumGC, PauseTotalNs, and a ring of recent PauseNs values. I sampled before and after a fixed five-minute run, then compared only collections added during that window. Mixing in old pauses made short tests look wonderfully stable or mysteriously awful depending on what had run first.

That pause is easy to describe and harder to judge. A short command-line tool may never care. A busy service with latency requirements can care very much, even if its average throughput looks fine. Averages are talented at concealing the request somebody was actually waiting for.

My first table kept four numbers for each run: requests per second, the 50th and 99th percentile request latency, collection count, and the largest observed GC pause. Average latency alone hid the event I cared about.

The naive handler allocated a buffer for every item:

func checksum(items [][]byte) uint32 {
	var sum uint32
	for _, item := range items {
		buf := make([]byte, len(item))
		copy(buf, item)
		for _, b := range buf {
			sum += uint32(b)
		}
	}
	return sum
}

The copy served no purpose. Removing it reduced collections and improved the long tail. This was not clever tuning; I had simply stopped manufacturing garbage.

The collector’s job depends on both allocated volume and live data. Producing temporary objects quickly causes collections to happen more often. Retaining a large graph gives each marking pass more reachable memory to inspect. These are different problems: one concerns allocation rate, the other heap size and object reachability.

After that fix I tried GOGC=50, the default 100, and 200, restarting the process for each run. Lowering it collected more often with a smaller heap. Raising it collected less often but used more memory. On this service, 200 helped the tail a little and increased memory enough that I kept the default. That is a result, not a disappointment.

Manual runtime.GC() calls were useful to prove that the latency recorder could see a pause. They did not belong in the handler. Forcing collection chooses when to pay and can easily turn an occasional pause into a dependable stream of them.

The useful knob came last. First came a repeatable load, pause deltas from the same time window, and removal of an accidental allocation. Otherwise GOGC is just a dial with excellent opportunities for superstition.

Container changes in C++11

The recently approved C++11 standard brings a lot of welcome changes to C++ that modernize the language a little bit. Among the many changes, we find that containers have received some special love.

Initialization

C++ was long behind modern languages when it came to initializing containers. While you could do

[cpp]int a[] = {1, 2, 3};[/cpp]

for simple arrays, things tended to get more verbose for more complex containers:

[cpp]
vector v;
v.push_back(“One”);
v.push_back(“Two”);
v.push_back(“Three”);
[/cpp]

C++11 has introduced an easier, simpler way to initialize this:

[cpp]
vector v = {“One”, “Two”, “Three”};
[/cpp]

The effects of the changes are even better for things like maps, which could get cumbersome quickly:

[cpp]
map<string, vector > m;
vector v1;
v1.push_back(“A”);
v1.push_back(“B”);
v1.push_back(“C”);

vector v2;
v2.push_back(“A”);
v2.push_back(“B”);
v2.push_back(“C”);

m[“One”] = v1;
m[“Two”] = v2;
[/cpp]

This can now be expressed as:

[cpp]
map<string, vector> m = One,

                             {"Two", {"Z", "Y", "X"}}};

[/cpp]

Much simpler and in line with most modern languages. As an aside, there’s another change in C++11 that would be easy to miss in the code above. The declaration

[cpp]map<string, vector> m;[/cpp]

was illegal until now due to » always being evaluated to the right-shift operator; a space would always be required, like

[cpp]map<string, vector > m[/cpp]

No longer the case.

Iterating

Iterating through containers was also inconvenient. Iterating the simple vector v above:

[cpp]
for (vector::iterator i = v.begin();

 i != v.end(); i++)
cout << i << endl;[/cpp]

Modern languages have long had some foreach equivalent that allowed us easier ways to iterate through these structures without having to explicitly worry about iterators types. C++11 is finally catching up:

[cpp]
for (string s : v)

cout << s << endl;

[/cpp]

As well, C++11 brings in a new keyword, auto, that will evaluate to a type in compile-type. So instead of

[cpp]
for (map<string, vector >::iterator i = m.begin();

 i != m.end(); i++) {

[/cpp]

we can now write

[cpp]
for (auto i = m.begin(); i != m.end(); i++) {
[/cpp]

and auto will evaluate to map<string, vector>::iterator.

Combining these changes, we move from the horrendous

[cpp]
for (map<string, vector >::iterator i = m.begin();

 i != m.end(); i++)
for (vector<string>::iterator j = i->second.begin();
     j != i->second.end(); j++)
    cout << i->first << ': ' << *j << endl;

[/cpp]

to the much simpler

[cpp]
for (auto i : m)

for (auto j : i.second)
    cout << i.first << ': ' << j << endl;

[/cpp]

Not bad.

C++11 support varies a lot from compiler to compiler, but all of the changes above are already supported in the latest versions of GCC, LLVM, and MSVC compilers.