Game of life is running slow

user_14611638 0
Viewed 164

I am trying to simulate n-dimensional game of life for first t=6 time steps. My Nim code is a straightforward port from Python and it works correctly but instead of the expected speedup, for n=4, t=6 it takes 2 seconds to run, which is order of magnitude slower than my CPython version. Why is my code so slow? What can I do to speed it up? I am compiling with -d:release and --opt:speed

I represent each point in space with a single 64bit integer. That is, I map (x_0, x_1, ..., x_{n-1}) to sum x_i * 32^i. I can do that since I know that after 6 time steps each coordinate -15<=x_i<=15 so I have no overflow.

The rules are:

alive - has 2 or 3 alive neigbours: stays alive
      - different number of them: becomes alive
dead - has 3 alive neighbours: becomes alive
     - else: stays dead

Below is my code. The critical part is the proc nxt which gets set of active cells and outputs set of active cells next time step. This proc is called 6 times. The only thing I'm interested in is the number of alive cells.

I run the code on the following input:

.##...#.
.#.###..
..##.#.#
##...#.#
#..#...#
#..###..
.##.####
..#####.

Code:

import sets, tables, intsets,  times, os, math

const DIM = 4
const ROUNDS = 6
const REG_SIZE = 5
const MAX_VAL = 2^(REG_SIZE-1)

var grid = initIntSet()

# Inits neighbours
var neigbours: seq[int]
proc initNeigbours(base,depth: int) =
    if depth == 0: 
        if base != 0:
            neigbours.add(base)
    else:
        initNeigbours(base*2*MAX_VAL-1, depth-1)
        initNeigbours(base*2*MAX_VAL+0, depth-1)
        initNeigbours(base*2*MAX_VAL+1, depth-1)
initNeigbours(0,DIM)
echo neigbours

# Calculates next iteration:
proc nxt(grid: IntSet): IntSet =
    var counting: CountTable[int]
    for x in grid:
        for dx in neigbours:
            counting.inc(x+dx)
    for x, count in counting.pairs:
        if count == 3 or (count == 2 and x in grid):
            result.incl(x)

# Loads input
var row = 0
while true:
    var line = stdin.readLine
    if line == "":
        break
    for col in 0..<line.len:
        if line[col] == '#':
            grid.incl((row-MAX_VAL)*2*MAX_VAL + col-MAX_VAL)
    inc row

# Run computation
let time = cpuTime()
for i in 1..ROUNDS:
    grid = nxt(grid) 

echo "Time taken: ", cpuTime() - time
echo "Result: ", grid.len
discard stdin.readLine
nim-lang
1 Answers

Your code runs in my computer in about 0.02:

Time taken: 0.020875947
Result: 2276

Time taken: 0.01853268
Result: 2276

Time taken: 0.021355269
Result: 2276

I changed the part where the input is read to this:

# Loads input
var row = 0
let input = open("input.txt")
for line in input.lines:
  for i, col in line:
    if col == '#':
      grid.incl((row-MAX_VAL)*2*MAX_VAL + i-MAX_VAL)
  inc row
input.close()

But it shouldn't impact the performance, it just looks better to my eyes. I compiled with:

nim c -d:danger script.nim

Using Nim 1.4.2. -d:danger is the flag for maximum speed before entering deeper waters.

But even compiling in debug mode:

$ nim c -r script.nim

Time taken: 0.07699487199999999
Result: 2276

Way faster than 2 seconds. There has to be other problem in your end. Sorry for the non-answer.

user_16885900
Related