Intro to (images in) Go – concurrency

This post is part of a series. For a listing of all the posts, as well as instructions on running the code, see here.

Turns out that despite all the shilly-shallying in the previous posts, we didn’t talk about one of Go’s most useful features, built-in concurrency implemented using go-routines and channels. Today seems like as good a day as any to give it a shot.

Concurrency in Go

Concurrency in Go is really pretty simple, when invoking a function we want to run in parallel to the execution flow, we just use the go keyword before the method invocation:

speak() // call the speak function and return when done
go speak() // create a go-routine in which speak run, returning immediately

To communicate between go-routines, channels are used. A channel is a typed conduit, which is most easily understood by means of an example:

var ch = make(chan string)

func speak() {
  s := <-ch
  fmt.Println(s) 
}

func main() {
  go speak()
  ch<-"hi"
}

First off, we create a channel ch with the type string. The speak function waits for input from this channel, and prints anything it receives before returning.

In the main function, we create a go-routine with go speak. Once this is done, our speak function is executing in parallel with our main function, until it reaches the point where it encounters <-ch. It then pauses waiting for input on the channel. The main function meanwhile gets around to sending something down the channel ch. When this happens, the speak function continues executing, jovially printing out “hi”.

Shoehorning in some image processing

I’ll be honest, it was a bit of a challenge to think of nice clean example of how to use concurrency to generate an image. So instead, here is something a little more convoluted: imagine a network of nodes (e.g. towns on a map) where each nodes is connected to the 5 nearest nodes. This might look something like this:

Network

I won’t go into the full details of how this is set up, as it’ll distract from talking about concurrency. The full nodes.go source is on github if you’re interested and want to play around with the parameters.

The important part is the Node object, which is defined as follows:

type Node struct {
  Position Vector
  Ch       chan *Node
  Peers    []*Node
  Canvas   *Canvas
  Power    uint8
}

So, each Node has a position, a channel to receive messages from other nodes on, a set of nearby peers and a power value.

To demonstrate concurrency, what we’ll do is hook up each Node, so that when it receives a message from another node, it will draw a line onto the canvas to visualize this. It will then send a message onto another node (that has yet to receive the message). The power is simply a way of keeping track of which nodes have been visited and showing how far a message has travelled.

Here’s an example of such a message propagating through a 50 node network:

Single message

The message starts off in yellow, and changes to red as it loses power with every step.

How does this work then?

Of course it would be possible to write this in a non-concurrent way, but that would be no fun. In our setup, no Node has a full understanding of the network as a whole, and only knows how to blindly send on messages to its peers. However, put together this suffices for the message to traverse the network. Here’s the relevant code:

func (n *Node) Listen() {
  // Listen for incoming connection on node's channel
  for {
    peer := <-n.Ch
    peer.Power -= 5
    n.Power = peer.Power
    n.Canvas.DrawLine(color.RGBA{255, n.Power, 0, 255}, n.Position, peer.Position)
    // Retransmit to random node
    if n.Power > 0 {
      go n.Send()
    }
  }
}

func (n *Node) Send() {
  for _, target := range n.Peers {
    if target.Power == 0 {
      target.Ch <- n
      break
    }
  }
}

Once you get your head around channels, there really isn’t much here. The Listen method just sits there, waiting for an incoming connection on n.Ch. Once it receives it, it decrements the Power, draws the line and sends a new message using Send(). Send is even simpler, it picks a peer that has yet to receive a message and sends a message to its channel Ch.

Let’s get things going

With all our nodes primed and ready for signals all that remains is to power up one Node and instruct it to send a message.

    node.Power = 255
    go node.Send()

Now we can have some fun fiddling with the parameters and seeing what results we get. One thing that is pretty neat is that we can concurrently kick off multiple signals from different nodes and have them propagate the network at the same time.

Here’s the same 50 node network as before, but with 10 messages propagating, note how some messages get cut off by others and are forced to die early.

10 messages

Or why not have 2500 nodes and see what happens?

2500 nodes

Or if that seems like too little, how about 25000?

25000 nodes

Fat-free threading

For the 25000 example above, the simulation ran no slower than when there were 100 nodes (although the initial network calculation is slow there). Go-routines are by design very light-weight, and this makes Go a great choice for writing concurrent code, e.g. for web servers.

As always, be sure to check out the full code on github

  • http://www.asetechs.com/ Patrick Toca

    Bravo. This post is really pedagogic (Clear, to the point with an excellent example).

  • Clint Ryan

    What’s the best way to compile and run this?
    I’m super interested in playing around with it

    • pheelicks

      You should just be able to “go get github.com/felixpalmer/go_images” or just clone the repo to get the code. To run it, I normally just cd into the go_images directory and execute “go run nodes.go canvas.go vector.go”. Check out the previous blog posts for details – as well as http://golang.org/doc/code.html for getting Go installed (it’s pretty easy).

  • ibi sum

    If I knew what I’d doing with canvas, I’d add realtime display capabilities to this demo app – as it renders to a static .png, its a matter of demonstrating concurrency in actuality, but not with a realtime view. Still, great tutorial and very much appreciated – well done on establishing a clear writing style and care for the readers understanding!

    • pheelicks

      I really like that idea, and will perhaps try and code it up for a future post.

  • Addis Hadababa

    It’s hard to think of an image processing algorithm that could benefit from concurrency?

    Really?

    One of the many possibilities are image convolutions (kernels)? We routinely process them in parallel using golang, and it’s awesome!

    Here is a simple example of a median blur (useful in creating “Tron”-like, retro-80s futuristic effects): take the original image and clone a new one with the same dimensions. For each 3×3 square in the original, compute a statistical average over all color channels. Then write this new value to the corresponding 3×3 pixel square in the new image. That’s it! You don’t even need channels if the kernels are not overlapping! For systems which have many CPUs you will notice a huge speedup when processing gigantic images ;)

  • Ege Özcan

    This was very helpful for understanding the concurrency capabilities of go. I’d have liked to see more comments on the code but it’s not a big deal really. Thank you very much.

  • http://blog.carlsensei.com/ Carl

    peer := <-n.Ch
    peer.Power -= 5
    n.Power = peer.Power

    Am I crazy? Isn’t that a racing bug?

  • Guest

    Looking at the code, it seems that the various levels take the same time to draw because you only block for a fixed 1 second. The real question with this form, would be at what level the complexity starts to fail rendering.