Voir la source de 20170403:TP:Go:Goroutine

[[category:EPITA:TP:20162017]]

== Introduction ==

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

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

== Vector Sum ==

* '''Path:''' <tt>tutorial20170403/divide_conquer</tt>

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 <tt>divide_conquer</tt> starting with following template:

<source lang="go">
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
}
</source>

The parallel algorithm look like this:

<pre>
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
</pre>

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 <tt>ParallelSum(v)</tt>'''

=== Benchmark and Testing ===

We already used the <tt>go test</tt> 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 <tt>_test.go</tt> and (specific to benchmarking) we need to add functions of the form <tt>BenchmarkXX(b)</tt>. I provide a simple benchmark for our code:

<source lang="go">
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)
	}
}
</source>

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

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

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 <tt>1</tt>s, or a value for which you can pre-compute the result (like <tt>4</tt>, which in our case should return something like <tt>2 * SIZE</tt> … )

== Parallel Tree Compare ==

* '''Path:''' <tt>tutorial20170403/same_tree</tt> and <tt>tutorial20170403/tree</tt>

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 <tt>c</tt> using the syntax <tt> <-c</tt>, in fact we can also test for availability of inputs. A simple example:

<source lang="go">
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)
	}
}
</source>

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 <tt>for</tt> loop with this:

<source lang="go">
	for x := range c {
		fmt.Println(x)
	}
</source>

=== 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 <tt>String()</tt> method attached to tree, it provides a pretty-printer facility for using with function from the <tt>fmt</tt> module.

<source lang="go">
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
}
</source>

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 <tt>tree</tt> package:

<source lang="go">
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
}
</source>

=== Comparing trees ===

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

<source lang="go">
package main

import (
	"fmt"
	"tutorial20170403/tree"
)

func main() {
	t := tree.New(3, 1)
	fmt.Println(t)
}
</source>

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:'''

<source lang="go">
/* 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
}
</source>

Note the type of the channel: <tt>chan<- int</tt> 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:

<pre>
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 !
</pre>

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

<source lang="go">
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 ...
}
</source>

* '''Complete the code, run, enjoy'''

<source lang="go">
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))
}
</source>

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