Programming

Have you ever wondered how FORs impact your code? How they are limiting your design and more important how they are transforming your code into an amount of lines without any human meaning?

How can you not want to read an article that starts like that? I had to steal the intro from the original. Seriously, I have used FOR since I learned BASIC back in the day. I never thought about how it was limiting my design. I. Must. Learn. How.

The article I am referring to is, Avoiding FORs – Anti-If Campaign. Eager learner I, I could not not read it.

After the resplendent intro, Avoiding FOR goes on to show “how to transform a simple example of a for […], to something more readable and well designed.”

It takes this unreadable piece of code — that I now recognize as unreadable:

[java]
public class Department {

private List resources = new ArrayList();

public void addResource(Resource resource) {
    this.resources.add(resource);
}

public void printSlips() {

    for (Resource resource : resources) {
        if(resource.lastContract().deadline().after(new Date())) {

            System.out.println(resource.name());
            System.out.println(resource.salary());
        }
    }
}

}[/java]

My eyes hurt already. Thankfully the author transforms the aberration above into this clean, much more readable snippet:

[java]public class ResourceOrderedCollection {

    private Collection<Resource> resources = new ArrayList<Resource>();



public ResourceOrderedCollection() {
    super();
}

public ResourceOrderedCollection(Collection<Resource> resources) {
    this.resources = resources;
}

public void add(Resource resource) {
    this.resources.add(resource);
}

public void forEachDo(Block block) {
    Iterator<Resource> iterator = resources.iterator();

    while(iterator.hasNext()) {
        block.evaluate(iterator.next());
    }

}

public ResourceOrderedCollection select(Predicate predicate) {

    ResourceOrderedCollection resourceOrderedCollection = new ResourceOrderedCollection();

    Iterator<Resource> iterator = resources.iterator();

    while(iterator.hasNext()) {
        Resource resource = iterator.next();
        if(predicate.is(resource)) {
            resourceOrderedCollection.add(resource);
        }
    }

    return resourceOrderedCollection;
}

}

public class Department {

private List<Resource> resources = new ArrayList<Resource>();

public void addResource(Resource resource) {
    this.resources.add(resource);
}

public void printSlips() {
    new ResourceOrderedCollection(this.resources).select(new InForcePredicate()).forEachDo(new PrintSlip());
}

}[/java]

Wait, what? Is this an Onion article?

Snarky Mode Off.

I understand what the author wanted to do, but really, the example used is so off the left field that it’s not even funny.

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.

I was timing a small word counter and noticed that making the map with a rough size helped more than I expected.

func count(words []string) map[string]int {
	m := make(map[string]int, len(words))
	for _, word := range words {
		m[word]++
	}
	return m
}

Of course len(words) is an overestimate when words repeat. It was still cheaper than repeatedly growing a map created with make(map[string]int).

A Go map is a hash table arranged as buckets. A hash of the key chooses a bucket, then the runtime examines entries in that bucket for a matching key. The bucket stores several keys and values rather than allocating a separate node for each item. That is a useful contrast with the traditional chained hash table I first learned, where every collision grew a little linked list and the allocator got invited to dinner.

When too many entries accumulate, the table grows. Growth is not free: keys and values must end up in buckets appropriate for the larger table. Supplying a reasonable hint lets the runtime start closer to the required size. It is a hint, not a promise about exact allocation, and writing make(map[K]V, oneMillion) because perhaps one day there may be a million entries is not optimization. It is interior decorating for an empty warehouse.

The representation explains a few visible rules. Map elements are not addressable. If the table grows and moves entries among buckets, a pointer to an element would become troublesome. This is illegal:

p := &m["answer"]

For a struct value, retrieve it, change the copy, and assign it back; or store pointers as the map values when that ownership model makes sense.

Iteration order is another thing not to build upon. The language does not specify it. Bucket layout and table state are implementation details, so code that happens to print keys in a pleasant order today has merely received a temporary kindness. Sort the keys when order matters.

There is also no general protection for concurrent access. A map operation changes more than the apparent key/value pair when it triggers growth or updates bucket metadata. I put a mutex around shared maps rather than trying to reason that two writers probably hash to different buckets. “Probably” is a peculiar synchronization primitive.

My practical rule is now simple: give make an honest size estimate when one is already available, never depend on iteration order, and make ownership of a map boringly clear. Knowing about buckets is useful. Trying to outsmart them from application code generally is not.

Two rows in a parser changed at once. I had stored each row by appending to a scratch slice, and enough spare capacity let the next row reuse the first row’s backing array.

scratch := make([]byte, 0, 64)
first := append(scratch, "Troy"...)
scratch = scratch[:0]
second := append(scratch, "Abed"...)

fmt.Printf("%q %q\n", first, second)

Both printed "Abed". No assignment to first appeared in the debugger, which sent me looking in entirely the wrong place.

The quickest diagnostic was printing lengths, capacities, and the first-element addresses at the point each slice was saved:

fmt.Printf("first  len=%d cap=%d p=%p\n", len(first), cap(first), &first[0])
fmt.Printf("second len=%d cap=%d p=%p\n", len(second), cap(second), &second[0])

Matching addresses exposed the alias. Capacity was the clue: resetting the length to zero did not discard the storage. The next append was allowed to write there.

The saved row needed ownership, so I copied it:

row := make([]byte, len(scratch))
copy(row, scratch)
rows = append(rows, row)

For scratch data that is consumed before reuse, sharing capacity is exactly the optimization I want. For data stored beyond that reuse, it is an ownership bug. I now inspect cap and backing addresses before staring at the append line as if it had betrayed me.

One caution: taking &s[0] requires a non-empty slice. In this parser the rows are non-empty; a general diagnostic needs to check len(s) first. That tiny check is cheaper than another afternoon blaming the debugger.

I lost half an hour today to an interface that was not nil even though the pointer I had put in it most certainly was. This is the smallest version of my mistake:

type File struct{}

func open() *File { return nil }

func main() {
	var f interface{} = open()
	fmt.Println(f == nil) // false
}

At first this looks like the language is being difficult merely to keep programmers alert. It is not. An interface value contains two things: a description of the concrete type and the concrete value itself. The interface above is approximately (*File, nil). A nil interface is (nil, nil). Those are not the same pair.

This is also why assigning an integer or a pointer to an interface is more than painting a different type on the same bits. The runtime needs enough information to identify the dynamic type, copy the value, compare it where permitted, and find methods. For an empty interface that amounts to a type descriptor and data. A non-empty interface also needs a table connecting its method set to implementations for the concrete type.

The table is prepared for a particular concrete-type/interface-type combination. A call such as

type Stringer interface { String() string }

func print(s Stringer) {
	fmt.Println(s.String())
}

can therefore dispatch through a known slot in that table. It does not have to search every method by name on every call. The implicit satisfaction of interfaces feels dynamic at the source level, but the machinery is quite disciplined.

There are practical consequences besides the nil trap. Copying an interface copies its pair of words, not necessarily an independent copy of everything reachable through the value. Comparing two interfaces first considers their dynamic types, then compares their dynamic values; putting a slice in an interface and comparing it will still panic because slices are not comparable. An interface does not confer diplomatic immunity on its contents.

Type assertions fit the same model. v, ok := x.(*File) asks whether the dynamic type in x is *File; it does not inspect the pointer and reject it merely because its value is nil. If the assertion succeeds, v may still be nil. The two-result form is useful because a failed assertion then reports ok == false instead of panicking and turning a routine check into theatre.

I like this representation because it explains several language rules at once. It also gives me a better debugging question. Instead of asking “is this interface nil?”, I now ask “what type and value did I put in it?” Usually that is the question I should have asked before blaming the compiler.