On Wednesday, 27 July 2016 15:14:13 UTC+3, Carl Ranson wrote:
>
>
> HI all,
>
> So I figured Conways game of life would be a good exercise to get my feet
> wet with go. Specifically i wanted to make the calculation of the next
> board state to be concurrent.
> I started a separate goroutine for each cell and then used a pair of
> channels to synchronize updating to the next state and displaying the
> board.
>
> Would love to hear opinions on this approach? are their better or more
> effective ways to do the same thing?
>
Few unorganized thoughts:
First, when parallelizing things, always consider communication as part of
the computation. Communication can have a significant overhead.
Usually, you should try to ensure that each goroutine does non-trivial
amount of work.
e.g.
type Bitmap [32][32]bool // can be packed more compactly
type Block struct {
Active *Bitmap // = &block.Buffers[0]
Next *Bitmap // = &block.Buffers[1], after each computation swap
Active and Next
Buffers [2]Bitmap
}
type Field struct {
Blocks []Block
}
// Alternatively use two fields instead of swapping at block level...
And each goroutine computes some number of the blocks...
http://www.shodor.org/media/content/petascale/materials/UPModules/GameOfLife/Life_Module_Document_pdf.pdf
Try to avoid pointers in a tight loop. Following a pointer is not free.
This can be simplified:
if c.nw.currentState {
i++
}
with
i += count(c.nw) // define count somewhere
Also take a look at https://golang.org/doc/play/life.go
Of course then there's HashLife, and other that can improve it further.
> Thanks in advance,
> CR
>
>
> package main
>
> import (
> "fmt"
> "math/rand"
> "time"
> )
>
> type Cell struct {
> x int
> y int
> currentState bool
> nw *Cell
> n *Cell
> ne *Cell
> e *Cell
> se *Cell
> s *Cell
> sw *Cell
> w *Cell
> }
>
> func (c *Cell) cell(runChan chan string, doneChan chan string) {
> for {
> // wait until we're allowed to proceed
> _ = <-runChan
>
> // count the number of neighbours
> var i int = 0
> if c.nw.currentState {
> i++
> }
> if c.n.currentState {
> i++
> }
> if c.ne.currentState {
> i++
> }
> if c.e.currentState {
> i++
> }
> if c.se.currentState {
> i++
> }
> if c.s.currentState {
> i++
> }
> if c.sw.currentState {
> i++
> }
> if c.w.currentState {
> i++
> }
>
> // Any live cell with fewer than two live neighbours dies, as if
> caused by under-population.
> // Any live cell with two or three live neighbours lives on to
> the next generation.
> // Any live cell with more than three live neighbours dies, as
> if by over-population.
> // Any dead cell with exactly three live neighbours becomes a
> live cell, as if by reproduction.
>
> nextState := c.currentState
> if c.currentState == true {
> if i < 2 {
> nextState = false
> } else if i == 2 {
> nextState = true
> } else if i == 3 {
> nextState = true
> } else if i > 3 {
> nextState = false
> }
> } else {
> if i == 3 {
> nextState = true
> }
> }
>
> //fmt.Println("calc for ", c.x, c.y, c.currentState, nextState, i)
>
> // report that we're finished the calc
> doneChan <- "done"
>
> // wait for permission to continue
> _ = <-runChan
> c.currentState = nextState
>
> // report that we've done the transition
> doneChan <- "done"
>
> //fmt.Println("assign")
> }
> }
>
> func ring(x int, size int) int {
> // this corrects x to be in the range 0..size-1
> if x < 0 {
> return size + x
> } else if x >= size {
> return 0
> } else {
> return x
> }
> }
>
> func main() {
> const iterations = 10
> const gridSize = 50
> const numCells = gridSize * gridSize
>
> r := rand.New(rand.NewSource(123))
> var cells [numCells]Cell
>
> // set up the cells
> for y := 0; y < gridSize; y++ {
> for x := 0; x < gridSize; x++ {
> cells[x+gridSize*y].x = x
> cells[x+gridSize*y].y = y
> cells[x*gridSize+y].currentState = r.Intn(4) == 0
>
> cells[x+gridSize*y].nw = &cells[ring(x-1, gridSize)+gridSize*
> ring(y-1, gridSize)]
> cells[x+gridSize*y].n = &cells[ring(x, gridSize)+gridSize*ring
> (y-1, gridSize)]
> cells[x+gridSize*y].ne = &cells[ring(x+1, gridSize)+gridSize*
> ring(y-1, gridSize)]
> cells[x+gridSize*y].e = &cells[ring(x+1, gridSize)+gridSize*
> ring(y, gridSize)]
> cells[x+gridSize*y].se = &cells[ring(x+1, gridSize)+gridSize*
> ring(y+1, gridSize)]
> cells[x+gridSize*y].s = &cells[ring(x, gridSize)+gridSize*ring
> (y+1, gridSize)]
> cells[x+gridSize*y].sw = &cells[ring(x-1, gridSize)+gridSize*
> ring(y+1, gridSize)]
> cells[x+gridSize*y].w = &cells[ring(x-1, gridSize)+gridSize*
> ring(y, gridSize)]
> }
> }
>
> calcChan := make(chan string)
> readyChan := make(chan string)
>
> // start a goroutine for each cell
> for i := 0; i < numCells; i++ {
> go cells[i].cell(calcChan, readyChan)
> }
>
> for x := 0; x < iterations; x++ {
>
> // display board
> for y := 0; y < gridSize; y++ {
> for x := 0; x < gridSize; x++ {
> if cells[x+gridSize*y].currentState {
> fmt.Print("X")
> } else {
> fmt.Print(" ")
> }
> }
> fmt.Println("")
> }
>
> fmt.Println("start the calucation")
> for i := 0; i < numCells; i++ {
> calcChan <- ""
> }
>
> fmt.Println("waiting for calculations to complate")
> for i := 0; i < numCells; i++ {
> _ = <-readyChan
> }
>
> fmt.Println("start the transition")
> for i := 0; i < numCells; i++ {
> calcChan <- ""
> }
>
> fmt.Println("waiting for transition to complate")
> for i := 0; i < numCells; i++ {
> _ = <-readyChan
> }
>
> fmt.Println("calculations done. ")
> }
> time.Sleep(2000)
>
> fmt.Println("Done")
>
> }
>
>
>
>
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
