Blog

A couple of days ago, I was listening to one of my favourite podcasts, The Frequency, when one of the hosts, Dan Benjamin, thought of a cool domain name, ohitson.com and checked to see if it was available. Turns out it was and he said he was registering right there and then. Now, two things: (a) I was listening to a recorded podcast, not live; and (b) I thought to myself, damn it! it is a cool domain name.

The next day, I launched Hover and checked the domain name and to my surprise it was available. I simply thought either Dan had given up on it or, most likely, I had misunderstood the domain name he was talking about and fortunately that had made me thing of this cool domain name. I even checked Google to make sure “Oh, it’s on” was really written like that 😛

Obviously I went ahead and registered the name. After that, I listed to that day’s The Frequency and heard Dan tell Haddie something to the effect of “oh, I forgot to register that domain yesterday!” That’s when I thought, oh-oh, maybe I had heard the correct domain name.

As it turns out, I was just listening to today’s episode and guess what? Dan mentions that someone registered it due to his mention on the show (which is technically true.)

But I am a nice guy. I offered to transfer the domain to Dan for free just a few minutes ago. Not sure he’ll see my posts to app.net or Twitter. If not, I’ll try again a few times. I really don’t have any intention to keep this domain name as long as he still wants it. Sounds unfair.

Update 7 Nov 2012: can you believe he actually accepted my offer? What a douche! Just kidding, it was the Fair Thing to Do™ and I’m happy to say the domain has been transferred to His Benjaminship already.

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.