20170403:TP:Go:Goroutine

Introduction

This week we start playing with Go's concurrency. We will also see the benchmarking possibilities of go test.

Yout git repo should follow the same organisation as before, using the directory name tutorial20170403.

Vector Sum

• Path: tutorial20170403/divide_conquer

We want to implement a classical pattern in parallel code: divide and conquer parallel sum. The idea is pretty simple, we decompose the sum of a vector using a recursive pattern and run in parallel the recursive calls.

In order to occupy our processors we will run a dummy square root function on values in the array and use floating point numbers.

We won't create a main package but use go testing tools, so you can just create a package divide_conquer starting with following template:

package divide_conquer
 
/* mySqrt(f) a stupid expensive square root */
func mySqrt(f float32) (r float32) {
	r = f
	for i := 0; i < 100; i++ {
		r = (r + f/r) / 2
	}
	return
}
 
/* Sum(v) sequential sum of element in v, using mySqrt */
func Sum(v []float32) (r float32) {
	r = 0
	for _, x := range v {
		r += mySqrt(x)
	}
	return
}
 
/* ParallelSum(v) computes the sum using go-routines */
func ParallelSum(v []float32) (r float32) {
	// FIX ME
	return
}

The parallel algorithm look like this:

ParallelSum(v):
  # Stop divide when size < 256
  if len(v) < 256:
    return Sum(v)
  left = run in parallel ParallelSum(v[ : len(v) / 2])
  right = ParallelSum(v[len(v) / 2 : ])
  wait for left
  return left + right

In order to implement the run in parallel and the waiting part, we need a go-routine and a channel for the result, this your job !

• Implement the function ParallelSum(v)

Benchmark and Testing

We already used the go test command for testing, we'll now use it for benchmarking. Like, testing, we need to create (in the same directory) a file whose name ends in _test.go and (specific to benchmarking) we need to add functions of the form BenchmarkXX(b). I provide a simple benchmark for our code:

package divide_conquer
 
import (
	"math/rand"
	"testing"
)
 
const (
	SIZE = 10000000
)
 
func rfill(v []float32) {
	for i, _ := range v {
		v[i] = rand.Float32()
	}
}
 
func BenchmarkSum(b *testing.B) {
	v := make([]float32, SIZE)
	rfill(v)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		Sum(v)
	}
}
 
func BenchmarkParallelSum(b *testing.B) {
	v := make([]float32, SIZE)
	rfill(v)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		ParallelSum(v)
	}
}

You can now run it (provided you implemented the required functions):

shell> go test -bench .
BenchmarkSum-8           	       1	6081211295 ns/op
BenchmarkParallelSum-8   	       1	1113401369 ns/op
PASS
ok  	tutorials/20170403/divide_conquer	7.827s

Note: the ending path is on my machine, it may differ for you.

You can also add some tests (see previous sessions), a good idea is to test not with random array like in my benchmarks but with arrays full of 1s, or a value for which you can pre-compute the result (like 4, which in our case should return something like 2 * SIZE … )

Parallel Tree Compare

• Path: tutorial20170403/same_tree and tutorial20170403/tree

This exercise is purely pedagogical, the goal is to play a little bit with go-routines and channels, don't look for performances here.

The idea: we want to compare the list of keys (in pre-order of encounter) of two binary trees, for that we implement a walk function that traverse the tree and emit in a channel the keys and concurrently compare the obtained keys.

Getting and testing inputs from channel

During the lectures, we have seen the that we can get inputs from a channel c using the syntax <-c, in fact we can also test for availability of inputs. A simple example:

package main
 
import "fmt"
 
func main() {
	c := make(chan int)
	go func() {
		for i := 0; i < 10; i++ {
			c <- i
		}
		// close(c) indicate the end of the stream
		close(c)
	}()
	for {
		// try to get value from c
		x, ok := <-c
		if !ok {
			// c is closed !
			break
		}
		fmt.Println(x)
	}
}

As you can see, you can close the channel in the go-routine, this will indicate the end of the stream, thus when getting values from the channel, if the boolean is false, we know that we reach the end of the stream.

This mode (closing channel) can be used to perform range iteration on channel, in the previous example, you can replace infinite for loop with this:

	for x := range c {
		fmt.Println(x)
	}

Tree Implementation

For the tree implementation, I provide a simple package with required code: type definition, tree creation function and helper for pretty-printing. Take a look at the code for usage, note the String() method attached to tree, it provides a pretty-printer facility for using with function from the fmt module.

package tree
 
import "fmt"
 
type Tree struct {
	Key         int
	Left, Right *Tree
}
 
/*
  New(depth, k) generates a tree of height depth and with key in the range k to
  k+size, keys are assigned using pre-order.
*/
func New(depth int, k int) (t *Tree) {
	key := k
	return recNew(depth, &key)
}
 
/*
 t.String() returns a string representation for use with fmt printers
*/
func (t *Tree) String() string {
	if t != nil {
		// Note: once defined, it works even inside the function !
		return fmt.Sprintf("(%v%v%v)", t.Key, t.Left, t.Right)
	}
	return ""
}
 
func recNew(depth int, k *int) (t *Tree) {
	if depth >= 0 {
		key := *k
		*k += 1
		left := recNew(depth-1, k)
		right := recNew(depth-1, k)
		t = &Tree{key, left, right}
	}
	return
}

Just for the fun, here is a function that sums the keys of a tree using go-routines, it is intended for inclusion in an another package (like a main) not inside the tree package:

func KeySum(t *tree.Tree) int {
	if t == nil {
		return 0
	}
	r := t.Key
	c := make(chan int)
	go func() {
		c <- KeySum(t.Left)
	}()
	r += KeySum(t.Right)
	r += <-c
	return r
}

Comparing trees

We now build our main package in tutorial20170403/same_tree. Create your main package file in that directory, you can just test the tree construction and pretty print like this:

package main
 
import (
	"fmt"
	"tutorial20170403/tree"
)
 
func main() {
	t := tree.New(3, 1)
	fmt.Println(t)
}

In order to compare binary trees we want to walk through both the trees. For that we want to create a function that takes a tree and a channel, emits all keys on the channel (using a DFS in pre-order) and then close the channel. You'll need a recursive function and a calling function (the calling function just call the recursive function and close the channel).

• Implement the following functions:

/* WalkTree(t, out) performs a DFS on t and emits keys on channel out, channel is closed when finished */
func WalkTree(t *tree.Tree, out chan<- int) {
	// FIX ME
}
 
/* the recursive sub-function for WalkTree(t, out) */
func walk(t *tree.Tree, out chan<- int) {
	// FIX ME
}

Note the type of the channel: chan<- int indicating a sending only channel (you can't receive data from it.)

Next, we need to implement comparison. The idea is to launch the walk on both trees using in separate go-routine (with their own channel) and get keys from both at the same time.

We follow this schema:

Compare(t1, t2):
  c1 int channel for t1
  c2 int channel for t2
  run in parallel WalkTree(t1, c1)
  run in parallel WalkTree(t2, c2)
  infinite loop:
    get x1 from c1
    get x2 from c2
    try following tests:
      c1 or c2 is closed but not both:
        return false
      both are closed:
        return true
      x1 != x2:
        return false
      otherwise: continue !

In order to properly (using go-style programming) implement the try following tests block, you will need a switch<tt> statement. Remember in Go, you can use a switch this way:

switch {
case cond1:
        // do something when cond1 is true
case cond2:
        // do something when cond2 is true
// more cases ...
default:
        // if no previous condition where true ...
}

• Complete the code, run, enjoy

package main
 
import (
	"fmt"
	"tutorial20170403/tree"
)
 
func WalkTree(t *tree.Tree, out chan<- int) {
        // FIX ME
}
 
func walk(t *tree.Tree, out chan<- int) {
        // FIX ME
}
 
func Compare(t1, t2 *tree.Tree) bool {
        // FIX ME
}
 
func main() {
	t1 := tree.New(3, 1)
	fmt.Println(t1)
 
	t2 := tree.New(3, 1)
	fmt.Println(t2)
 
	fmt.Println(Compare(t1, t2))
}

• Do some more testing, choose bigger depths, build trees with different keys (change the second parameters) …