Sunday, November 10, 2013

Go-ogle map-delbrot

Go-ogle Map-delbrot

In a previous post I looked at using Python to write a mandelbrot server that could be used as a custom source in google maps.

I thought I'd try to do the same using Go.

It starts by defining some structures for mandelbrot requests. I separate the request and the description structures so that when we can cache the data based only on the description. Note that the mand_request has a mand_desc anonymous field, which allows us to transparently access the mand_desc fields from a mand_request.

type mand_desc struct{
 w, h int
 max_it int
 sx, ex, sy, ey float64 

type mand_request struct{
 out io.Writer
 donechan chan int

We then create a channel that accepts a mand_requests, we'll be pushing requests to this later:

var mand_request_channel = make(chan mand_request)

We'll store calculated images in a cache (a map of Image.Palletted pointers (an object from the default Image package) keyed by a mand_desc object):

var cache = map[mand_desc] *image.Paletted {}

To enable concurrent processing we have to explicitly set the runtime.GOMAXPROCS variable. We set it to the number of CPUs in the system, and start a goroutine for each one:

for i := 0; i < runtime.NumCPU(); i++ {
 go mand_handler(mand_request_channel)

The mand_handler function waits for a request and creates the mandelbrot or uses the previously cached version. Then we encode the data and write it to the io.writer in the mand_request. Finally we put a value into the donechan just to indicate we've finished.

func mand_handler(inchannel chan mand_request) {
 for m := range(inchannel) {
  ret, ok := cache[m.mand_desc]
  if !ok{
   ret = make_mand(m.w, m.h, m.max_it,, m.ex,, m.ey)
   cache[m.mand_desc] = ret
  } else {
   fmt.Println("Hitting cache!")
  png.Encode(m.out, ret)
  m.donechan <- 1

The rest of the code sets up the HTTP server and creates the mandellbrot image. The full code can be found on GitHub.

Go and Python

Comparing the two versions, there's probably more in common than there are differences. Both rely on libraries to do a lot of the hard work (HTTP server, png compression) but in fact the Go program used only standard libraries, whereas Python needed numpy and matplotlib (which admittedly are so common as to almost be standard).

Speed Comparison

Although Go is compiled, and a lot closer to the hardware then Python, I was expecting the two to be a similar speed - most of the time is spent in squaring and adding complex numbers, which numpy does in compiled code anyway. The Python code is fundamentally less efficient in a few ways: 
  • It still squares and add pixels that have already diverged whereas the Go code moves onto the next pixel immediately
  • I'm using the numpy abs function to see if the pixels have diverged, which has a square root per pixel (the go version compares x^2 to limit^2 instead - it would be possible to do this in Python at the expense of readability)
  • The Python version has to iterate through all pixels once per iteration. The Go version deals with one pixel at a time for all iterations. This is probably faster, as it can keep the pixel data in the cache over the iterations. Maybe.
So having said all that, here's the results (for requesting 100 images, serially):
LanguageTime (s)

Here we can see just how much faster (surprisingly to me) the Go code is. I tried replacing the np.abs(m)>2 call with np.real(m*m.conjugate())>4 instead (saving a square root, but needing to go in and out of Python more times) and it slowed things down by about 10%. So Go is significantly faster than Python in this case.

Final Thoughts

After playing with Python for a while, it's nice to return to a compiled language to see just how fast things can be. The nice features of Go are the extensive standard libraries, the speed, and the goroutine and channel philosophy. It doesn't have anywhere near the number of third-party libraries that Python has however. Go feels like a lean (it's closer to C than C++), fast language with a small number of really helpful higher level abstractions (channels, maps, slices) combined with very lightweight concurrency (goroutines).