Hello Go

Gopher saying “Hello world!”

For the past couple of months I’ve taken a liking to Go for various biased reasons so to showcase the beauty and simplicity of Go we’ll walkthrough a classic little “Hello World” program.

Saying Hello

There are a bunch of ways we could get to an output that contains “Hello world!” Preferably this would include a blockchain and neural network on a serverless architecture for maximum hype factor but, doing that would be a complete overkill and not to mention over budget for doing something as simple as printing to standard output.

Instead we’ll just do a permutation sort on the input string until we get the desired output of “Hello world!”.

A flowchart of a typical hello world program

Implementing this in Go is fairly straight forward, we’ll make a slice out of the target string to turn it into runes and shuffle it using rand.Shuffle until it matches the target string.

// hello.go
package main
import (
  "fmt"
  "math/rand"
)
func main() {
  t := "Hello World!"
  s := []rune(t)
  
  for {
    rand.Shuffle(len(s), func(i int, j int) {
      s[i], s[j] = s[j], s[i]
    })
    if string(s) == t {
      break
    }
  }
  fmt.Println(string(s))
}

We’ll run this with go run hello.go

Terrific! we got our minimal highly efficient working “Hello World” program!

Tracking Progress

We got the basics down but it would be nice to have some kind of progress log with the permutation count and value so let’s add that.

// hello.go
package main
import (
  "fmt"
  "math/rand"
)
func main() {
  t := "Hello World!"
  s := []rune(t)
  for {
    rand.Shuffle(len(s), func(i int, j int) {
      s[i], s[j] = s[j], s[i]
    })
    fmt.Println(string(s))
    if string(s) == t {
      break
    }
  }
}

We’ll build this with go build hello.go

Great! we’ve got output!

Now as for adding the permutation count there’s no need to include that kind of overhead into our executable since we can just pipe it into an external command, like cat(1) which has a line number option.

$ hello | cat -n

With the default seed it takes thirty-eight million five hundred twenty-eight thousand nine hundred sixty-seven iterations for us to reach the “Hello world” permutation.

Note: If you are on Microsoft Windows without a UNIX like environment you might want to re-evaluate your life choices at this moment.

Many Is More Than One

Our program is actually already fairly quick to compute considering what it needs to do, the garbage collector isn’t bogging us down much either despite the fact that we constantly are creating new strings.

We can still make it go faster by making the string generation concurrent, this in turn will enable Go to schedule our computation to run in parallel across multiple hardware threads when possible.

Go’s concurrency model is based around self contained co-routines that communicate by passing messages over channels which is often described using Gophers as a metaphor.

So what we‘ll do is force a bunch of cutsy little Gophers do all the work of trying to guess and yell the correct permutation back to us over a channel while we just sit in the main area deciding if it’s the right or wrong answer.

A flow chart of Gopher Sort

The majority of our implementation will remain the same. We’ll extract the permutation shuffling into a function which sends messages to our channel, in our main function we iterate over the messages testing them for equivalence to our target string.

// hello.main
package main
import (
  "fmt"
  "math/rand"
)
func main() {
  t := "Hello world!"
  c := make(chan string)
  for i := 0; i < 32; i++ {
    go gopher(t, c)
  }
  for s := range c {
    fmt.Println(s)
    if s == t {
      break
    }
  }
}
func gopher(t string, c chan string) {
  s := []rune(t)
  for {
    rand.Shuffle(len(s), func(i, j int) {
      s[i], s[j] = s[j], s[i]
    })
    c <- string(s)
  }
}

Success! we’ve got Gophers working concurrently together!

How Many Is A Crowd?

What kind of performance gains did we get from this? Well we’ve actually degraded the performance.

More is not always better and it turns out there is no budget for a thread ripper for this lesson as initially planned so putting 32 Gophers to work on 4 threads means that they may need to wait in their designated queues before being allowed to do their work.

So exactly how many is too many? Conventional wisdom would say one per hardware thread but there is only one way to find out and that is to measure it.

We’ll measure the clock time it takes for the program to complete with time(1).

A plot of Gopher efficiency at performing Gopher Sort

Nice! we have data, six is definitivly the optimal number of gophers… err wait a minute we have a problem here!

Since our program is based around psuedo-randomness, it becomes non-deterministic and fairly erratic once we introduce our go routines.

Go routines by themselves introduce non-determinism here because we are not doing any kind of locking, and there’s no guarantee which order we receive the messages. That means that we end up getting a data race but it’s a non issue and doesn’t matter in this scenario.

The reason we get funky plot is because we use the default psuedo-random source. While the source itself is deterministic by default and safe to use concurrently without running into technical issues, we do run into a conceptual one.

Since every Gopher is using the same source, the chance of a Gopher getting the correct guess is drastically reduced because the “hint” that could have given that Gopher the correct answer is given to another Gopher who makes another wrong guess with it.

Nice! we understand our data, benchmarking stupid sort is… interesting?

Conclusion

Our Gophers can’t work well on their own since they’re not sure if they said the right thing, so in this case adding more screaming Gophers did not help us out much.

We did learn that Gophers can perform monkey sort, the algorithm is interspecies compatible!

If you’re not into Go and want to learn Go in ways that do not involve awesome algorithms and beanbags I’d recommend giving “The Go Programming Language” a go.