Parallel Mandelbrot Set Using Golang
Tags: go, programming, performance
Published: 2021-06-17 23:58:39


This post explains how to generate a Mandelbrot set in parallel using Golang `goroutines`. 

Source code here: https://github.com/GiselaMD/parallel-mandelbrot-go 

## Mandelbrot Set

For those that are interest in what's a Mandelbrot set, check https://en.wikipedia.org/wiki/Mandelbrot_set 

The set formula is based on the position of `x` and `y` coordinates:

```
x = x*x - y*y + a
y = 2*x*y + b
```

We also check if `x*x + y*y > 4` to set the color.

But instead of going into math details, I would like to explain how we can use `gourotines` to render that Mandelbrot set on the screen.

## Getting into the code

This program is based on 4 main values that are going to impact the performance and resolution of the Mandelbrot set.

```
maxIter = 1000
samples = 200

numBlocks  = 64
numThreads = 16
```

- `maxIter` defines how many times the mandelbrot formula will be calculated, resulting on `x` and `y` values.

- `samples` is the number of interactions that generates RGB color values.

- `numBlocks` is in how many pieces do you want to divide the image.

- `numThreads` is the number of `gourotines` that will be created.

To render the result on the screen I've used the Pixel library (github.com/faiface/pixel). On the main function we have something like this:

```go
func main() {
	pixelgl.Run(run)
}
```

Calling pixelgl.Run puts PixelGL in control of the main function and there's no way for us to run any code in the main function anymore. That's why we need to pass another function inside pixelgl.Run, which is the `run` function. 

```go
func run() {
	log.Println("Initial processing...")
	pixelCount = 0
	img = image.NewRGBA(image.Rect(0, 0, imgWidth, imgHeight))
	cfg := pixelgl.WindowConfig{
		Title:  "Parallel Mandelbrot in Go",
		Bounds: pixel.R(0, 0, imgWidth, imgHeight),
		VSync:  true,
	}

	win, err := pixelgl.NewWindow(cfg)
	if err != nil {
		panic(err)
	}
	log.Println("Rendering...")
	start := time.Now()
	workBuffer := make(chan WorkItem, numBlocks)
	threadBuffer := make(chan bool, numThreads)
	drawBuffer := make(chan Pix, pixelTotal)

	workBufferInit(workBuffer)
	go workersInit(drawBuffer, workBuffer, threadBuffer)
	go drawThread(drawBuffer, win)

	for !win.Closed() {
		pic := pixel.PictureDataFromImage(img)
		sprite := pixel.NewSprite(pic, pic.Bounds())
		sprite.Draw(win, pixel.IM.Moved(win.Bounds().Center()))
		win.Update()

		if showProgress {
			fmt.Printf("\r%d/%d (%d%%)", pixelCount, pixelTotal, int(100*(float64(pixelCount)/float64(pixelTotal))))
		}

		if pixelCount == pixelTotal {
			end := time.Now()
			fmt.Println("\nFinished with time = ", end.Sub(start))
			pixelCount++

			if closeOnEnd {
				break
			}
		}
	}
}
```

The `run` function is responsible for initialising and updating the window as well as creating the channels that will be used for our `gourotines`.

The `workBuffer` is the channel responsible for adding the information of each block (based on `numBlocks`). Inside the `workBufferInit`, the initial and final `x` and `y` values are sent to the channel so that each `gourotines` that gets that piece of the image to work on can calculate the color without needing to know the global data, only what's the range of `x` and `y` of that block.

```go
func workBufferInit(workBuffer chan WorkItem) {
	var sqrt = int(math.Sqrt(numBlocks))

	for i := sqrt - 1; i >= 0; i-- {
		for j := 0; j < sqrt; j++ {
			workBuffer <- WorkItem{
				initialX: i * (imgWidth / sqrt),
				finalX:   (i + 1) * (imgWidth / sqrt),
				initialY: j * (imgHeight / sqrt),
				finalY:   (j + 1) * (imgHeight / sqrt),
			}
		}
	}
}
```

The `threadBuffer` is responsible for creating `goroutines` based on the `numThreads` and controlling when a `goroutine` is done with its work so we can run another in its place. That logic inside `workersInit` `goroutine`.

```go
func workersInit(drawBuffer chan Pix, workBuffer chan WorkItem, threadBuffer chan bool) {
	for i := 1; i <= numThreads; i++ {
		threadBuffer <- true
	}

	for range threadBuffer {
		workItem := <-workBuffer

		go workerThread(workItem, drawBuffer, threadBuffer)
	}
}
```

For each `workItem` that we receive from the `workBuffer` (each block) we create a `goroutine` called `workerThread` to handle all the Mandelbrot set logic.

```go
func workerThread(workItem WorkItem, drawBuffer chan Pix, threadBuffer chan bool) {
	for x := workItem.initialX; x < workItem.finalX; x++ {
		for y := workItem.initialY; y < workItem.finalY; y++ {
			var colorR, colorG, colorB int
			for k := 0; k < samples; k++ {
				a := height*ratio*((float64(x)+RandFloat64())/float64(imgWidth)) + posX
				b := height*((float64(y)+RandFloat64())/float64(imgHeight)) + posY
				c := pixelColor(mandelbrotIteraction(a, b, maxIter))
				colorR += int(c.R)
				colorG += int(c.G)
				colorB += int(c.B)
			}
			var cr, cg, cb uint8
			cr = uint8(float64(colorR) / float64(samples))
			cg = uint8(float64(colorG) / float64(samples))
			cb = uint8(float64(colorB) / float64(samples))

			drawBuffer <- Pix{
				x, y, cr, cg, cb,
			}

		}
	}
	threadBuffer <- true
}
```

```go
func mandelbrotIteraction(a, b float64, maxIter int) (float64, int) {
	var x, y, xx, yy, xy float64

	for i := 0; i < maxIter; i++ {
		xx, yy, xy = x*x, y*y, x*y
		if xx+yy > 4 {
			return xx + yy, i
		}
		// xn+1 = x^2 - y^2 + a
		x = xx - yy + a
		// yn+1 = 2xy + b
		y = 2*xy + b
	}

	return xx + yy, maxIter
}

func pixelColor(r float64, iter int) color.RGBA {
	insideSet := color.RGBA{R: 0, G: 0, B: 0, A: 255}

	// check if it's inside the set
	if r > 4 {
		// return hslToRGB(float64(0.70)-float64(iter)/3500*r, 1, 0.5)
		return hslToRGB(float64(iter)/100*r, 1, 0.5)
	}

	return insideSet
}
```

The `drawBuffer` is the channel that receives the values from the `goroutines` that are calculating the Mandelbrot set and once it receives data, the `drawThread` `goroutine` sets the pixel RGB value into the image and then the `run` function updates the window.

```go
func drawThread(drawBuffer chan Pix, win *pixelgl.Window) {
	for i := range drawBuffer {
		img.SetRGBA(i.x, i.y, color.RGBA{R: i.cr, G: i.cg, B: i.cb, A: 255})
		pixelCount++
	}
}
```

We also have some utils functions for generating random data and converting hsl and hue to RGB:

```go
var randState = uint64(time.Now().UnixNano())

func RandUint64() uint64 {
	randState = ((randState ^ (randState << 13)) ^ (randState >> 7)) ^ (randState << 17)
	return randState
}

func RandFloat64() float64 {
	return float64(RandUint64() / 2) / (1 << 63)
}

func hueToRGB(p, q, t float64) float64 {
	if t < 0 { t += 1 }
	if t > 1 { t -= 1 }
	switch {
	case t < 1.0 / 6.0:
		return p + (q - p) * 6 * t
	case t < 1.0 / 2.0:
		return q
	case t < 2.0 / 3.0:
		return p + (q - p) * (2.0 / 3.0 - t) * 6
	default:
		return p
	}
}

func hslToRGB(h, s, l float64) color.RGBA {
	var r, g, b float64
	if s == 0 {
		r, g, b = l, l, l
	} else {
		var q, p float64
		if l < 0.5 {
			q = l * (1 + s)
		} else {
			q = l + s - l * s
		}
		p = 2 * l - q
		r = hueToRGB(p, q, h + 1.0 / 3.0)
		g = hueToRGB(p, q, h)
		b = hueToRGB(p, q, h - 1.0 / 3.0)
	}
	return color.RGBA{ R: uint8(r * 255), G: uint8(g * 255), B: uint8(b * 255), A: 255 }
}
```

Final result:
![Parallel Mandelbrot gif](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0347aexi0s5q565myzzk.gif)

![Parallel Mandelbrot image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y7eqrzj9zcy5ep9bozf4.png)

That's it for today!

Hope you enjoy it 😊

🇧🇷 This post is also available in Portuguese published by Daniel who collaborated in this project. Check his post: https://danielferreiradev.medium.com/fractal-de-mandelbrot-paralelo-usando-golang-4ba497d9bbc5

Source code here: https://github.com/GiselaMD/parallel-mandelbrot-go