first program, game of life in go

[Carl Ranson]

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?

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")

}

[Egon]

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.

[Carl Ranson]

Thanks Egon,

Ok, I take your point that one needs to strike a balance with the work done in each goroutine to achieve optimum performance.
i understand that each goroutine doing a subblock of the board using bitmaps would be faster, but as a learning exercise i'm keeping it simple. In fact I was pleasantly surprised by how simply the code came out once I could think about each cell's calculation as a discrete process.

one part of your answer I didn't understand was the bit about pointers.

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

what would the count function do that alleviates it from the need to follow the pointer? Are you saying that testing the pointer for nil costs less than dereferencing the pointer? even if true that doesn't help me here as every cell always has 8 neighbors (its not dependent on the cell being live or not)

one of the reasons I used pointers here was to avoid each goroutine from fighting over access to the boards array. they only care about the adjacent cells after all.

thanks,
CR

[Charles Haynes]

"Naive" implementations of life are fun as a learning exercise, but if you actually want to compute life you need to know about "Hashlife." It'd be fun to see Hashlife implemented in Go.

-- Charles

https://en.wikipedia.org/wiki/Hashlife

Representation

The field is typically treated as a theoretically infinite grid, with the pattern in question centered near the origin. A quadtree is used to represent the field. Given a square of 2^2k cells, 2^k on a side, at the kth level of the tree, the hash table stores the 2^k-1-by-2^k-1 square of cells in the center, 2^k-2 generations in the future. For example, for a 4x4 square it stores the 2x2 center, one generation forward; and for an 8x8 square it stores the 4x4 center, two generations forward.

Hashing

While a quadtree trivially has far more overhead than other simpler representations (such as using a matrix of bits), it allows for various optimizations. As the name suggests, it uses hash tables to store the nodes of the quadtree. Many subpatterns in the tree are usually identical to each other; for example the pattern being studied may contain many copies of the same spaceship, or even large swathes of empty space. These subpatterns will all hash to the same position in the hash table, and thus many copies of the same subpattern can be stored using the same hash table entry. In addition, these subpatterns only need to be evaluated once, not once per copy as in other Life algorithms.

This itself leads to significant improvements in resource requirements; for example a generation of the various breeders and spacefillers, which grow at polynomial speeds, can be evaluated in Hashlife using logarithmic space and time.

Superspeed and caching

A further speedup for many patterns can be achieved by evolving different nodes at different speeds. For example, one could compute twice the number of generations forward for a node at the (k+1)-th level compared to one at the kth. For sparse or repetitive patterns such as the classical glider gun, this can result in tremendous speedups, allowing one to compute bigger patterns at higher generations faster, sometimes exponentially. To take full advantage of this feature, subpatterns from past generations should be saved as well.

Since different patterns are allowed to run at different speeds, some implementations, like Gosper's own hlife program, do not have an interactive display, but simply compute a preset end result for a starting pattern, usually run from the command line. More recent programs such as Golly, however, have a graphical interface that can drive a Hashlife-based engine.

The typical behavior of a Hashlife program on a conducive pattern is as follows: first the algorithm runs slower compared to other algorithms because of the constant overhead associated with hashing and building the tree; but later, enough data will be gathered and its speed will increase tremendously – the rapid increase in speed is often described as "exploding".

--
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...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jordan Krage]

| one of the reasons I used pointers here was to avoid each goroutine from fighting over access to the boards array. they only care about the adjacent cells after all.

What's to fight over? Concurrent reads are no problem, and the writes are independent of one another. Rather than storing the pointers ahead of time, you could defer your index offset math, and get/set directly to the array via index.

[Egon]

On Thursday, 28 July 2016 03:40:39 UTC+3, Carl Ranson wrote:

Thanks Egon,

Ok, I take your point that one needs to strike a balance with the work done in each goroutine to achieve optimum performance.
i understand that each goroutine doing a subblock of the board using bitmaps would be faster, but as a learning exercise i'm keeping it simple. In fact I was pleasantly surprised by how simply the code came out once I could think about each cell's calculation as a discrete process.

one part of your answer I didn't understand was the bit about pointers.

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

what would the count function do that alleviates it from the need to follow the pointer? Are you saying that testing the pointer for nil costs less than dereferencing the pointer? even if true that doesn't help me here as every cell always has 8 neighbors (its not dependent on the cell being live or not)

Those were two separate points :)... I guess using bullet-points would have made it clearer.

One was just about pointer derefing, the other about the repetitive code.

PS: using an array could make it shorter as well, e.g. [8]*Cell

[Carl Ranson]

Anyone got any thoughts on the way I've used channels to synchronize things?
Would I be much better off using chan bool instead of chan string for signaling?

I've seen some code that suggests that chan interface{} is a valid. what can you send on that?

thanks,
CR

[Carl Ranson]

ok, fair enough. I guess I'm just used to thinking of concurrency in database terms where locking is involved.

[chris dollin]

On 28 July 2016 at 09:04, Carl Ranson <carl....@gmail.com> wrote:

> I've seen some code that suggests that chan interface{} is a valid.
> what can you send on that?

Anything.

The receiver has to know what to do with it,
of course.

Chris

--
Chris "allusive" Dollin