Concurrency

You can find all the code for this chapter here

Here’s the setup: a colleague has written a function, CheckWebsites, thatchecks the status of a list of URLs.

  1. package concurrency
  3. type WebsiteChecker func(string) bool
  5. func CheckWebsites(wc WebsiteChecker, urls []string) map[string]bool {
  6.     results := make(map[string]bool)
  8.     for _, url := range urls {
  9.         results[url] = wc(url)
  10.     }
  12.     return results
  13. }

It returns a map of each URL checked to a boolean value - true for a goodresponse, false for a bad response.

You also have to pass in a WebsiteChecker which takes a single URL and returnsa boolean. This is used by the function to check all the websites.

Using dependency injection has allowed them to test the function withoutmaking real HTTP calls, making it reliable and fast.

Here’s the test they’ve written:

  1. package concurrency
  3. import (
  4.     "reflect"
  5.     "testing"
  6. )
  8. func mockWebsiteChecker(url string) bool {
  9.     if url == "waat://furhurterwe.geds" {
  10.         return false
  11.     }
  12.     return true
  13. }
  15. func TestCheckWebsites(t *testing.T) {
  16.     websites := []string{
  17.         "http://google.com",
  18.         "http://blog.gypsydave5.com",
  19.         "waat://furhurterwe.geds",
  20.     }
  22.     want := map[string]bool{
  23.         "http://google.com":          true,
  24.         "http://blog.gypsydave5.com": true,
  25.         "waat://furhurterwe.geds":    false,
  26.     }
  28.     got := CheckWebsites(mockWebsiteChecker, websites)
  30.     if !reflect.DeepEqual(want, got) {
  31.         t.Fatalf("Wanted %v, got %v", want, got)
  32.     }
  33. }

The function is in production and being used to check hundreds of websites. Butyour colleague has started to get complaints that it’s slow, so they’ve askedyou to help speed it up.

Write a test

Let’s use a benchmark to test the speed of CheckWebsites so that we can see theeffect of our changes.

  1. package concurrency
  3. import (
  4.     "testing"
  5.     "time"
  6. )
  8. func slowStubWebsiteChecker(_ string) bool {
  9.     time.Sleep(20 * time.Millisecond)
  10.     return true
  11. }
  13. func BenchmarkCheckWebsites(b *testing.B) {
  14.     urls := make([]string, 100)
  15.     for i := 0; i < len(urls); i++ {
  16.         urls[i] = "a url"
  17.     }
  19.     for i := 0; i < b.N; i++ {
  20.         CheckWebsites(slowStubWebsiteChecker, urls)
  21.     }
  22. }

The benchmark tests CheckWebsites using a slice of one hundred urls and usesa new fake implementation of WebsiteChecker. slowStubWebsiteChecker isdeliberately slow. It uses time.Sleep to wait exactly twenty milliseconds andthen it returns true.

When we run the benchmark using go test -bench=. (or if you’re in Windows Powershell go test -bench="."):

  1. pkg: github.com/gypsydave5/learn-go-with-tests/concurrency/v0
  2. BenchmarkCheckWebsites-4               1        2249228637 ns/op
  3. PASS
  4. ok      github.com/gypsydave5/learn-go-with-tests/concurrency/v0        2.268s

CheckWebsites has been benchmarked at 2249228637 nanoseconds - about two anda quarter seconds.

Let’s try and make this faster.

Write enough code to make it pass

Now we can finally talk about concurrency which, for the purposes of thefollowing, means ‘having more than one thing in progress’. This is somethingthat we do naturally everyday.

For instance, this morning I made a cup of tea. I put the kettle on and then,while I was waiting for it to boil, I got the milk out of the fridge, got thetea out of the cupboard, found my favourite mug, put the teabag into the cup andthen, when the kettle had boiled, I put the water in the cup.

What I didn’t do was put the kettle on and then stand there blankly staring atthe kettle until it boiled, then do everything else once the kettle had boiled.

If you can understand why it’s faster to make tea the first way, then you canunderstand how we will make CheckWebsites faster. Instead of waiting fora website to respond before sending a request to the next website, we will tellour computer to make the next request while it is waiting.

Normally in Go when we call a function doSomething() we wait for it to return(even if it has no value to return, we still wait for it to finish). We say thatthis operation is blocking - it makes us wait for it to finish. An operationthat does not block in Go will run in a separate process called a goroutine.Think of a process as reading down the page of Go code from top to bottom, going‘inside’ each function when it gets called to read what it does. When a separateprocess starts it’s like another reader begins reading inside the function,leaving the original reader to carry on going down the page.

To tell Go to start a new goroutine we turn a function call into a gostatement by putting the keyword go in front of it: go doSomething().

  1. package concurrency
  3. type WebsiteChecker func(string) bool
  5. func CheckWebsites(wc WebsiteChecker, urls []string) map[string]bool {
  6.     results := make(map[string]bool)
  8.     for _, url := range urls {
  9.         go func() {
  10.             results[url] = wc(url)
  11.         }()
  12.     }
  14.     return results
  15. }

Because the only way to start a goroutine is to put go in front of a functioncall, we often use anonymous functions when we want to start a goroutine. Ananonymous function literal looks just the same as a normal function declaration,but without a name (unsurprisingly). You can see one above in the body of thefor loop.

Anonymous functions have a number of features which make them useful, two ofwhich we’re using above. Firstly, they can be executed at the same time thatthe’re declared - this is what the () at the end of the anonymous function isdoing. Secondly they maintain access to the lexical scope they are defined in -all the variables that are available at the point when you declare the anonymousfunction are also available in the body of the function.

The body of the anonymous function above is just the same as the loop body wasbefore. The only difference is that each iteration of the loop will start a newgoroutine, concurrent with the current process (the WebsiteChecker function)each of which will add its result to the results map.

But when we run go test:

  1. --- FAIL: TestCheckWebsites (0.00s)
  2.         CheckWebsites_test.go:31: Wanted map[http://google.com:true http://blog.gypsydave5.com:true waat://furhurterwe.geds:false], got map[]
  3. FAIL
  4. exit status 1
  5. FAIL    github.com/gypsydave5/learn-go-with-tests/concurrency/v1        0.010s

A quick aside into a parallel(ism) universe…

You might not get this result. You might get a panic message thatwe’re going to talk about in a bit. Don’t worry if you got that, just keeprunning the test until you do get the result above. Or pretend that you did.Up to you. Welcome to concurrency: when it’s not handled correctly it’s hard topredict what’s going to happen. Don’t worry - that’s why we’re writing tests, tohelp us know when we’re handling concurrency predictably.

… and we’re back.

We are caught by the original tests CheckWebsites is now returning anempty map. What went wrong?

None of the goroutines that our for loop started had enough time to addtheir result to the results map; the WebsiteChecker function is too fast forthem, and it returns the still empty map.

To fix this we can just wait while all the goroutines do their work, and thenreturn. Two seconds ought to do it, right?

  1. package concurrency
  3. import "time"
  5. type WebsiteChecker func(string) bool
  7. func CheckWebsites(wc WebsiteChecker, urls []string) map[string]bool {
  8.     results := make(map[string]bool)
  10.     for _, url := range urls {
  11.         go func() {
  12.             results[url] = wc(url)
  13.         }()
  14.     }
  16.     time.Sleep(2 * time.Second)
  18.     return results
  19. }

Now when we run the tests you get (or or don’t get - see above):

  1. --- FAIL: TestCheckWebsites (0.00s)
  2.         CheckWebsites_test.go:31: Wanted map[http://google.com:true http://blog.gypsydave5.com:true waat://furhurterwe.geds:false], got map[waat://furhurterwe.geds:false]
  3. FAIL
  4. exit status 1
  5. FAIL    github.com/gypsydave5/learn-go-with-tests/concurrency/v1        0.010s

This isn’t great - why only one result? We might try and fix this by increasingthe time we wait - try it if you like. It won’t work. The problem here is thatthe variable url is reused for each iteration of the for loop - it takesa new value from urls each time. But each of our goroutines have a referenceto the url variable - they don’t have their own independent copy. So they’reall writing the value that url has at the end of the iteration - the lasturl. Which is why the one result we have is the last url.

To fix this:

  1. package concurrency
  3. import (
  4.     "time"
  5. )
  7. type WebsiteChecker func(string) bool
  9. func CheckWebsites(wc WebsiteChecker, urls []string) map[string]bool {
  10.     results := make(map[string]bool)
  12.     for _, url := range urls {
  13.         go func(u string) {
  14.             results[u] = wc(u)
  15.         }(url)
  16.     }
  18.     time.Sleep(2 * time.Second)
  20.     return results
  21. }

By giving each anonymous function a parameter for the url - u - and thencalling the anonymous function with the url as the argument, we make sure thatthe value of u is fixed as the value of url for the iteration of the loopthat we’re launching the goroutine in. u is a copy of the value of url, andso can’t be changed.

Now if you’re lucky you’ll get:

  1. PASS
  2. ok      github.com/gypsydave5/learn-go-with-tests/concurrency/v1        2.012s

But if you’re unlucky (this is more likely if you run them with the benchmark as you’ll get more tries)

  1. fatal error: concurrent map writes
  3. goroutine 8 [running]:
  4. runtime.throw(0x12c5895, 0x15)
  5.         /usr/local/Cellar/go/1.9.3/libexec/src/runtime/panic.go:605 +0x95 fp=0xc420037700 sp=0xc4200376e0 pc=0x102d395
  6. runtime.mapassign_faststr(0x1271d80, 0xc42007acf0, 0x12c6634, 0x17, 0x0)
  7.         /usr/local/Cellar/go/1.9.3/libexec/src/runtime/hashmap_fast.go:783 +0x4f5 fp=0xc420037780 sp=0xc420037700 pc=0x100eb65
  8. github.com/gypsydave5/learn-go-with-tests/concurrency/v3.WebsiteChecker.func1(0xc42007acf0, 0x12d3938, 0x12c6634, 0x17)
  9.         /Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker.go:12 +0x71 fp=0xc4200377c0 sp=0xc420037780 pc=0x12308f1
  10. runtime.goexit()
  11.         /usr/local/Cellar/go/1.9.3/libexec/src/runtime/asm_amd64.s:2337 +0x1 fp=0xc4200377c8 sp=0xc4200377c0 pc=0x105cf01
  12. created by github.com/gypsydave5/learn-go-with-tests/concurrency/v3.WebsiteChecker
  13.         /Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker.go:11 +0xa1
  15.         ... many more scary lines of text ...

This is long and scary, but all we need to do is take a breath and read thestacktrace: fatal error: concurrent map writes. Sometimes, when we run ourtests, two of the goroutines write to the results map at exactly the same time.Maps in Go don’t like it when more than one thing tries to write to them atonce, and so fatal error.

This is a race condition, a bug that occurs when the output of our software isdependent on the timing and sequence of events that we have no control over.Because we cannot control exactly when each goroutine writes to the results map,we are vulnerable to two goroutines writing to it at the same time.

Go can help us to spot race conditions with its built in race detector.To enable this feature, run the tests with the race flag: go test -race.

You should get some output that looks like this:

  1. ==================
  2. WARNING: DATA RACE
  3. Write at 0x00c420084d20 by goroutine 8:
  4.   runtime.mapassign_faststr()
  5.       /usr/local/Cellar/go/1.9.3/libexec/src/runtime/hashmap_fast.go:774 +0x0
  6.   github.com/gypsydave5/learn-go-with-tests/concurrency/v3.WebsiteChecker.func1()
  7.       /Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker.go:12 +0x82
  9. Previous write at 0x00c420084d20 by goroutine 7:
  10.   runtime.mapassign_faststr()
  11.       /usr/local/Cellar/go/1.9.3/libexec/src/runtime/hashmap_fast.go:774 +0x0
  12.   github.com/gypsydave5/learn-go-with-tests/concurrency/v3.WebsiteChecker.func1()
  13.       /Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker.go:12 +0x82
  15. Goroutine 8 (running) created at:
  16.   github.com/gypsydave5/learn-go-with-tests/concurrency/v3.WebsiteChecker()
  17.       /Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker.go:11 +0xc4
  18.   github.com/gypsydave5/learn-go-with-tests/concurrency/v3.TestWebsiteChecker()
  19.       /Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker_test.go:27 +0xad
  20.   testing.tRunner()
  21.       /usr/local/Cellar/go/1.9.3/libexec/src/testing/testing.go:746 +0x16c
  23. Goroutine 7 (finished) created at:
  24.   github.com/gypsydave5/learn-go-with-tests/concurrency/v3.WebsiteChecker()
  25.       /Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker.go:11 +0xc4
  26.   github.com/gypsydave5/learn-go-with-tests/concurrency/v3.TestWebsiteChecker()
  27.       /Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker_test.go:27 +0xad
  28.   testing.tRunner()
  29.       /usr/local/Cellar/go/1.9.3/libexec/src/testing/testing.go:746 +0x16c
  30. ==================

The details are, again, hard to read - but WARNING: DATA RACE is prettyunambiguous. Reading into the body of the error we can see two differentgoroutines performing writes on a map:

Write at 0x00c420084d20 by goroutine 8:

is writing to the same block of memory as

Previous write at 0x00c420084d20 by goroutine 7:

On top of that we can see the line of code where the write is happening:

/Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker.go:12

and the line of code where goroutines 7 an 8 are started:

/Users/gypsydave5/go/src/github.com/gypsydave5/learn-go-with-tests/concurrency/v3/websiteChecker.go:11

Everything you need to know is printed to your terminal - all you have to do isbe patient enough to read it.

Channels

We can solve this data race by coordinating our goroutines using channels.Channels are a Go data structure that can both receive and send values. Theseoperations, along with their details, allow communication between differentprocesses.

In this case we want to think about the communication between the parent processand each of the goroutines that it makes to do the work of running theWebsiteChecker function with the url.

  1. package concurrency
  3. type WebsiteChecker func(string) bool
  4. type result struct {
  5.     string
  6.     bool
  7. }
  9. func CheckWebsites(wc WebsiteChecker, urls []string) map[string]bool {
  10.     results := make(map[string]bool)
  11.     resultChannel := make(chan result)
  13.     for _, url := range urls {
  14.         go func(u string) {
  15.             resultChannel <- result{u, wc(u)}
  16.         }(url)
  17.     }
  19.     for i := 0; i < len(urls); i++ {
  20.         result := <-resultChannel
  21.         results[result.string] = result.bool
  22.     }
  24.     return results
  25. }

Alongside the results map we now have a resultChannel, which we make inthe same way. chan result is the type of the channel - a channel of result.The new type, result has been made to associate the return value of theWebsiteChecker with the url being checked - it’s a struct of string andbool. As we don’t need either value to be named, each of them is anonymouswithin the struct; this can be useful in when it’s hard to know what to namea value.

Now when we iterate over the urls, instead of writing to the map directlywe’re sending a result struct for each call to wc to the resultChannelwith a send statement. This uses the <- operator, taking a channel on theleft and a value on the right:

  1. // Send statement
  2. resultChannel <- result{u, wc(u)}

The next for loop iterates once for each of the urls. Inside we’re usinga receive expression, which assigns a value received from a channel toa variable. This also uses the <- operator, but with the two operands nowreversed: the channel is now on the right and the variable thatwe’re assigning to is on the left:

  1. // Receive expression
  2. result := <-resultChannel

We then use the result received to update the map.

By sending the results into a channel, we can control the timing of each writeinto the results map, ensuring that it happens one at a time. Although each ofthe calls of wc, and each send to the result channel, is happening in parallelinside its own process, each of the results is being dealt with one at a time aswe take values out of the result channel with the receive expression.

We have paralellized the part of the code that we wanted to make faster, whilemaking sure that the part that cannot happen in parallel still happens linearly.And we have communicated across the multiple processes involved by usingchannels.

When we run the benchmark:

  1. pkg: github.com/gypsydave5/learn-go-with-tests/concurrency/v2
  2. BenchmarkCheckWebsites-8             100          23406615 ns/op
  3. PASS
  4. ok      github.com/gypsydave5/learn-go-with-tests/concurrency/v2        2.377s

23406615 nanoseconds - 0.023 seconds, about one hundred times as fast asoriginal function. A great success.

Wrapping up

This exercise has been a little lighter on the TDD than usual. In a way we’vebeen taking part in one long refactoring of the CheckWebsites function; theinputs and outputs never changed, it just got faster. But the tests we had inplace, as well as the benchmark we wrote, allowed us to refactor CheckWebsitesin a way that maintained confidence that the software was still working, whiledemonstrating that it had actually become faster.

In making it faster we learned about

  • goroutines, the basic unit of concurrency in Go, which let us check morethan one website at the same time.
  • anonymous functions, which we used to start each of the concurrent processesthat check websites.
  • channels, to help organize and control the communication between thedifferent processes, allowing us to avoid a race condition bug.
  • the race detector which helped us debug problems with concurrent code

Make it fast

One formulation of an agile way of building software, often misattributed to KentBeck, is:

Make it work, make it right, make it fast

Where ‘work’ is making the tests pass, ‘right’ is refactoring the code, and‘fast’ is optimizing the code to make it, for example, run quickly. We can only‘make it fast’ once we’ve made it work and made it right. We were lucky that thecode we were given was already demonstrated to be working, and didn’t need to berefactored. We should never try to ‘make it fast’ before the other two stepshave been performed because

Premature optimization is the root of all evil— Donald Knuth