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 -nWith 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 OneOur 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 SortThe 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.
mainpackage mainimport ( "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 SortNice!.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?ConclusionOur 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.
.