Blog

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.

Last night, as I tried getting my three year-old to sleep so I could play my brand-new copy of NHL 13, I had an epiphany of sorts. It dawned on me how much videogames influenced my real-life pleasures. And the story actually started a long time ago.

Of the games we bought, only one I can still remember: NHL Hockey. To that day, I had only a general idea of what hockey was: Soccer on the ice. We picked it simply because the clerk there told us it was good.

Back to how it influenced my real-life, playing the game got me into Hockey as a sport. A Brazilian hooked on Hockey? Not supposed to happen, but one likes what one likes. It also indirectly started my love affair with Canada, but that’s a different story. Following Hockey was not easy until I found a radio that streamed games and later the League started offering live vide streaming for which I have been gladly paying an exorbitant amount of money for half a decade or so. I’ve experienced a similar effect thanks to the Madden and NBA Live series, but NHL Hockey will always be a special case for me.

I realized that thru hockey I’ve made friends, some of whom are real good friends. And all of this started because a couple of decades ago we got some pirated games in a Saturday afternoon.

Want to make a comment or suggestion? Do you feel like you need to correct me for not fitting the Standard Brazilian Specification? Feel free to talk to (or scream at) me, I’m @robteix on App.net and also on Twitter.

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.

I wrapped a C checksum function and called it once per 32-byte record. The C loop won its isolated benchmark, yet the complete program lost. I had measured the work and ignored the doorway.

The fix was not exotic:

// One crossing for the whole buffer.
sum := C.checksum((*C.uchar)(unsafe.Pointer(&buf[0])), C.size_t(len(buf)))

I benchmarked batches of 1, 16, 256, and 4096 records from the same input. On my machine the one-record version managed about 7 MB/s; batches of 16 reached 58 MB/s, 256 reached 170 MB/s, and 4096 changed little at 174 MB/s. These are not portable constants. The flattening was the useful result: by 256 records, the checksum was work again and the bridge was no longer the benchmark.

I also timed the pure Go checksum in the same harness. It reached 112 MB/s. That made the decision less silly: either stay in Go and keep the simple boundary, or batch enough for C’s faster loop to pay its admission fee. Calling C per record was the one clearly bad option.

The batch API takes a contiguous buffer plus record metadata and returns all checksums at once. It also makes ownership easy to state: the buffer remains valid during the call, and C retains no Go pointer afterward.

The caveat is the empty slice: &buf[0] is invalid when len(buf) == 0, so real code checks length first. C memory needs C lifetime rules, callbacks need even more care, and a blocking C call affects runtime scheduling differently from an ordinary Go function.

I picked 256 records because larger batches bought almost nothing and delayed results. The benchmark supplied both halves of that choice; “fewer cgo calls” by itself would have pushed the batch size toward absurdity.