Autumn Golang Diary

[This fragment is available in an audio version.]

I’ve posted here about my experiences with Go since 2013 and I guess it’s too late to stop now. This one is truly miscellaneous, just a bunch of things that built up in “should write about this” notes to myself while working on Quamina.

Switch switch switch · Back in 2013 I wrote about now nice the Go switch statement is. The Quamina work has really brought this home, by way of constructs like this:

    switch {
    case stepExisting == nil && stepNew == nil:
      uComb[i] = nil
    case stepExisting != nil && stepNew == nil:
      uComb[i] = stepExisting
    case stepExisting == nil && stepNew != nil:
      uComb[i] = stepNew
    case stepExisting != nil && stepNew != nil:
      uComb[i] = mergeOneDfaStep(stepExisting, stepNew, memoize)
    }

I mean, sure, I could compose equivalent if-then-elses; but I could do it in half-dozen different ways, with varying readability, while resisting the temptation to optimize prematurely. I’m drifting into the lane of looking at every if and wondering if it could be a switch.

Dot dot dot! · I can’t imagine that this delightful little thing is unique to Go but somehow I’ve never worked with it before.

  // append a whole array
  var a, b []foo
  a = append(a, b...)

  // print some args
  log.Printf(format, args...)

  // varargs
  func x(numbers ...int)

  // varargs are slice-i-fied
  func (m *matchSet) addX(exes ...X) *matchSet {
    if len(exes) == 0 {
      return m
    }
  }

Volatility · Go is good at concurrency, and the best way to write concurrent code is with channels (watch out for buffering). But sometimes you need old-fashioned access control. And speaking as a one-time Java-head, I pretty quickly found myself wondering “What’s the equivalent of volatile?” It’s atomic.Value.

type fieldMatcher struct {
  updateable atomic.Value // always holds an *fmFields
}

type fmFields struct {
  transitions         map[string]*valueMatcher
  // other fields…
}

func (m *fieldMatcher) fields() *fmFields {
  return m.updateable.Load().(*fmFields)
}

func (m *fieldMatcher) update(fields *fmFields) {
  m.updateable.Store(fields)
}

This works really well for a “read-mostly” variable. In this case, one thread can be updating the fieldMatcher while lots of others are reading it. So you build a new set of fields then blast it in with that update() function, which is atomic. The runtime will get around to garbage-collecting the copy you replaced when the other threads finish up with it.

I’ve discovered that if you have relatively little contention, the cost of the atomic operation is close to zero. If you have a lot, it’s not, but the penalty seems to increase smoothly, which is a tribute to the runtime.

It’d be kind of nice if you could make the atomic.Value strongly typed. Like, you know, a generic?

Generics feaugh · I wrote a whole blog piece about Go generics back in May, in which I grumbled quite a bit about them but came to peace with using them.

I’m back to grumbling. Maybe it’s me not them, but I’m not that stupid and not that fussy, and I keep getting nasty surprises when I try to do something reasonable-looking with a genericized type. There’s a performance bug-fix coming into Quamina which as a side effect will remove the last remaining generic type. That’s not the reason I’m doing it but it makes me happy.

Slice slice slice! · Now, for what I think is my biggest Go eye-opener, all these years in: You can do nearly everything with slices. Coming from Java, with its huge repertoire of List and Stack and Queue types, I frequently wondered “Where’s the standard type for <one of those Java things>?” In almost every case the answer is “You can do that with a slice.”

Here are a stack and a queue, for unsigned integers:

type Stack struct {
  x []uint
}

func (s *Stack) push(i uint) {
  s.x = append(s.x, i)
}
func (s *Stack) pop() int {
  if len(s.x) == 0 {
    return -1
  }
  index := len(s.x) - 1
  popped := s.x[index]
  s.x = s.x[:index]
  return int(popped)
}

type Queue struct {
  x []uint
}

func (q *Queue) write(i uint) {
  q.x = append(q.x, i)
}
func (q *Queue) read() int {
  // signal empty queue
  if len(q.x) == 0 {
    return -1
  }
  r := q.x[0]
  q.x = q.x[1:]
  return int(r)
}

Those pop and read implementations seem to take more lines of code than they ought to, and while it’s too late to add queue- and stack-oriented built-ins, it might be nice to add some of these calls to Go’s slices package.

Slice performance · Given that you can do everything with slices, more or less, one hopes that the implementation has been fanatically optimized. I hope that, anyhow, because when I was grinding away optimizing Quamina, I thought I was nearing victory when the profiler reported the code was spending a high proportion of its time updating them, on the grounds that I was unlikely to write code that was better-optimized than the builtin append().

However, there are a couple of things to keep an eye on that are probably pretty obvious but still worth mentioning:

1. It’s easy and idiomatic to say var foo []bar and then add things to it with append. Turns out that if you know how long foo is apt to get, you can get a remarkable performance improvement by saying
   foo := make([]bar, 0, MAX_SIZE_GUESS)
   

2. If you look at those Queue and Stack implementations, and assume they’re going to be heavily used, it’s pretty likely that the Stack is going to be way more efficient, because as it gets longer and shorter, the runtime will probably have to reallocate it less and less.

   My profiling supports this guess; I had a structure where I stashed units of work and then retrieved them, and while it didn’t need stack semantics, it ran faster with that kind of implementation.

Slice gripes · Nothing is perfect. Here’s a problem I have in Quamina. The process of merging automata requires code like you see in the first sample above. It turns out that merging steps can easily generate duplicates, so to keep things sane, you need to deduplicate your steps. Glance back at that code sample and you’ll notice that the mergeOneDfaStep function has a memoize argument. Here’s the start of mergeOneDfaStep:

func mergeOneDfaStep(step1, step2 *dfaStep, memoize map[dfaStepKey]*dfaStep) *dfaStep {
  var combined *dfaStep

  // to support automata that loop back to themselves (typically on *) we have to stop recursing (and also
  //  trampolined recursion)
  mKey := dfaStepKey{step1: step1, step2: step2}
  combined, ok := memoize[mKey]
  if ok {
    return combined
  }

This is a straightforward memoization: If you call the function and it’s already been called with those arguments, don’t re-compute a new value, just return what you did before. And if you do have to compute a new value, save it in memoize before you return.

This was a lot harder than I’d hoped, because I wanted to index on the content of the arguments. The code above doesn’t actually do that, because if your type is a struct with a slice field, you can’t use it as a map key.

Sigh. I’ve figured out workarounds, but I still have problems and I know that in some cases I’m not deduplicating fully.

What I think I want is a new kind of thing in Go: An immutable slice. It’s not as though this is an exotic idea, since Go’s built-in string type is just an immutable []byte. This is why you can index a map with a string but not a []byte. If there were a way to make an arbitrary []Foo immutable then I could index with that and it would make my deduplication problem easier.

I wonder if I’m the only person with this gripe?

It dawns on me that Java has a pretty good solution to this problem: java.object.hashCode(). For pretty well any type in Java, if I want to key a Map with it, all I have to do is override this and I’m good to go. Feels clean to me.

Anyhow… · Go mostly doesn’t get in my way. The code runs acceptably fast. The readability is superior, in my opinion, to any other programming language I’ve used. My thanks to the team.

Contributions