The Computer Language
Benchmarks Game

chameneos-redux Go #2 program

source code

/* The Computer Language Benchmarks Game
 * http://benchmarksgameshootout.alioth.debian.org/
 *
 * contributed by The Go Authors.
 * modified by roger peppe
 * atomics by Bert Gijsbers.
 */

package main

import (
    "flag"
    "fmt"
    "runtime"
    "strconv"
    atom "sync/atomic"
)

const (
    // three colors in alphabetic order
    blue uint32 = 1 + iota
    red
    yellow
    colBits = 2
    colMask = 1<<colBits - 1
    noone   = 0
)

func complement(col1, col2 uint32) uint32 {
    switch col1 {
    case blue:
        switch col2 {
        case blue:
            return blue
        case red:
            return yellow
        case yellow:
            return red
        }
    case red:
        switch col2 {
        case blue:
            return yellow
        case red:
            return red
        case yellow:
            return blue
        }
    case yellow:
        switch col2 {
        case blue:
            return red
        case red:
            return blue
        case yellow:
            return yellow
        }
    }
    panic("Invalid colour in complement")
}

var colname = [...]string{
    blue:   "blue",
    red:    "red",
    yellow: "yellow",
}

// A creature is a naming identifier + a colour
type creature uint32

func newCreature(name, col uint32) creature {
    return creature(name<<colBits | col)
}

func (crea creature) name() uint32 {
    return uint32(crea) >> colBits
}

func (crea creature) colour() uint32 {
    return uint32(crea) & colMask
}

// mutate updates the colour after a mate was found
func (crea creature) mutate(mate creature) creature {
    newColour := complement(crea.colour(), mate.colour())
    return creature(uint32(crea)&^colMask | uint32(newColour))
}

// word type-converts a creature to a single word
func (crea creature) word() uint32 {
    return uint32(crea)
}

// mall organizes meetings between creatures
type mall struct {
    meetings   *uint32   // count number of meetings
    waiter     *uint32   // waiting creature if non-zero
    handshakes []*uint32 // mating handshakes indexed by name
}

// result is sent by a creature when game ends
type result struct {
    met  int // number of meetings with any
    same int // number of meetings with self
}

// game configuration
type game struct {
    colours []uint32
    results chan result
}

// total meetings per game of pallmall
var meetings = 600

func init() {
    if flag.Parse(); flag.NArg() > 0 {
        meetings, _ = strconv.Atoi(flag.Arg(0))
    }
}

// main starts two games and outputs results
func main() {
    game1 := &game{[]uint32{blue, red, yellow}, make(chan result)}
    go game1.pallmall()

    game2 := &game{[]uint32{blue, red, yellow, red, yellow,
        blue, red, yellow, red, blue}, make(chan result)}
    go game2.pallmall()

    printColours()
    game1.report()
    game2.report()
}

// printColours prints colour complements.
func printColours() {
    for col1 := blue; col1 <= yellow; col1++ {
        for col2 := blue; col2 <= yellow; col2++ {
            fmt.Printf("%s + %s -> %s\n",
                colname[col1], colname[col2],
                colname[complement(uint32(col1), uint32(col2))])
        }
    }
    fmt.Print("\n")
}

// report game colours and results
func (game *game) report() {
    // print game colours
    msg := ""
    for _, col := range game.colours {
        msg += " " + colname[col]
    }
    fmt.Println(msg)

    // wait for game results
    total := 0
    for _ = range game.colours {
        result := <-game.results
        total += result.met
        fmt.Printf("%d%s\n", result.met, spell(result.same))
    }
    fmt.Printf("%s\n\n", spell(total))
}

// pallmall starts a new game
func (game *game) pallmall() {
    // assuming a cache line size of 64 bytes.
    // give each element its own cache line to reduce contention.
    slab := make([]uint32, (4+len(game.colours))*16)
    handshakes := make([]*uint32, len(game.colours)+1)
    mall := &mall{&slab[16], &slab[2*16], handshakes}
    // each colour is one new creature
    for i, col := range game.colours {
        handshakes[i+1] = &slab[(3+i)*16]
        creature := newCreature(uint32(i+1), col)
        go creature.play(mall, game.results)
    }
}

// play realizes meetings for one creature with other creatures
func (crea creature) play(mall *mall, ended chan<- result) {
    handshake := mall.handshakes[crea.name()]
    result := result{}
    // obtain a license for a new meeting, until meetings are over
    for atom.AddUint32(mall.meetings, 1) <= uint32(2*meetings) {
        var mate creature
        for {
            // see if some other is already inside
            other := atom.LoadUint32(mall.waiter)
            if other == noone {
                // the room is still empty; try to get in first
                if atom.CompareAndSwapUint32(mall.waiter, noone, crea.word()) {
                    // we got in first; now wait for second creature
                    for i := 0; other == noone; i++ {
                        if i >= 50 {
                            // limit idle spinning
                            runtime.Gosched()
                        }
                        other = atom.LoadUint32(handshake)
                    }
                    // we found a mate
                    mate = creature(other)
                    // reset
                    *handshake = noone
                    break
                }
            } else {
                // someone is inside; try to enter as second
                if atom.CompareAndSwapUint32(mall.waiter, other, noone) {
                    // we found a mate
                    mate = creature(other)
                    // tell our mate about ourselves.
                    atom.StoreUint32(mall.handshakes[mate.name()], crea.word())
                    break
                }
            }
        }
        // update our colour
        crea = crea.mutate(mate)
        // count successful meetings
        result.met++
        if mate.name() == crea.name() {
            // count meetings with ourselves
            result.same++
        }
    }
    ended <- result
}

var digits = [...]string{
    " zero", " one", " two", " three", " four",
    " five", " six", " seven", " eight", " nine"}

func spell(n int) string {
    msg := digits[n%10]
    for n /= 10; n != 0; n /= 10 {
        msg = digits[n%10] + msg
    }
    return msg
}
    

notes, command-line, and program output

NOTES:
32-bit Ubuntu one core
go version go1.7 linux/386


Wed, 21 Sep 2016 17:02:32 GMT

MAKE:
/usr/local/src/go/bin/go build -o chameneosredux.go-2.go_run
2.51s to complete and log all make actions

COMMAND LINE:
./chameneosredux.go-2.go_run 6000000

PROGRAM OUTPUT:
blue + blue -> blue
blue + red -> yellow
blue + yellow -> red
red + blue -> yellow
red + red -> red
red + yellow -> blue
yellow + blue -> red
yellow + red -> blue
yellow + yellow -> yellow

 blue red yellow
3994528 zero
4001094 zero
4004378 zero
 one two zero zero zero zero zero zero

 blue red yellow red yellow blue red yellow red blue
1195075 zero
1201638 zero
1201643 zero
1201640 zero
1201642 zero
1201642 zero
1198360 zero
1198362 zero
1201642 zero
1198356 zero
 one two zero zero zero zero zero zero