Garbage collection loop in Game of Life

Question

I'm working on a Game Of Life clone as my first project. I'm still relatively new to programming, so my code is probably not really optimised.

The biggest bottleneck is in my Start() method, but that contains a lot of Unity3D specific methods which most people here probably don't know about. That's why I'm leaving that out.

My second bottleneck is somewhere in my Update() method. In here, I'm looping through my array which is currently 100 by 100 large, 10.000 in total.

I've been checking with the built-in profiler of Unity3D, and this reports that the biggest bottleneck is the garbage collection.

I also tried to put half of the loop in another thread, but that didn't work out properly, because it needs to look up cells in the other half.

If you see any other ways to improve my code, and not just the performance, feel free to let me know. But please, keep it simple, as I'm still relatively new to programming.

The relevant code:

void Update()       
{
    timeElapsed += Time.deltaTime;                  // this will add deltaTime to timeElapsed,
    if (timeElapsed >= timeBetween)                 // until timeElapsed exceeds timeBetween, 
    {                                               // which allows a new generation to be calculated
        timeElapsed -= timeBetween; 
        if (gameState == GameState.Game_Playing)
        {               
            grid = CheckAdjacent(grid);             // draw new generation
            UpdateInformation();                    // update information variables
        }
    }
}

public static void DrawGeneration(bool[,] grid)
{
    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            cubeGrid[x,y].renderer.enabled = grid[x,y]; // enables the renderer for active cells.
        }
    }
}

private void UpdateInformation()
{
    generation++; //counts the generations
}

public static int GetAliveCells ()
{
    int i = 0;
    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            if (grid[x, y]) // counts the number of alive cells
                i++;
        }
    }       
    return i;
}   

bool IsCellAlive(int adjacentCount, bool isAlive)
{
    if (isAlive)
        return liveRule.Contains(adjacentCount);
    else
        return becomeAliveRule.Contains(adjacentCount);
}

private bool[,] CheckAdjacent(bool[,] grid)
{
    int adjacentSquares = 0;
    bool[,] newGrid = new bool[gridX, gridY];

    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            adjacentSquares = 0;                

            if (grid[calcX(x - 1), calcY(y - 1)])
                adjacentSquares++;              
            if (grid[calcX(x), calcY(y - 1)])
                adjacentSquares++;              
            if (grid[calcX(x + 1), calcY(y -1)])
                adjacentSquares++;              

            if (grid[calcX(x - 1), calcY(y)])
                adjacentSquares++;
            if (grid[calcX(x + 1), calcY(y)])
                adjacentSquares++;

            if (grid[calcX(x - 1), calcY(y + 1)])
                adjacentSquares++;
            if (grid[calcX(x), calcY(y + 1)])
                adjacentSquares++;
            if (grid[calcX(x + 1), calcY(y + 1)])
                adjacentSquares++;

            newGrid[x,y] = IsCellAlive(adjacentSquares, grid[x,y]);
        }
    }       
    return newGrid; 
}

private int calcX(int x)
{
    x += gridX;
    return (x % gridX);
}

private int calcY(int y)
{
    y += gridY;
    return (y % gridY);
}

Answer 1

1. I would advise you to count neighbours from alive points, not for cells to be checked. Null a 100x100 int array Neighbours. For every alive cell add +1 into every neighbouring cell in Neighbours. After the pass you have number of neighbours for the every cell, but time used is about 1/4 at most, because you saved the time not counting neighbours for zero cells.

2. You are taking left neighbours for utmost left cells, for example. Out of boundaries! You are blocking this by taking a function and modulo and thus making the toroid out of plane, but thus you are counting much longer - division or modulo are slow, functions even more slow. Simply count neighbours normally for the field except boundaries, otherwards for the four sides and four corners. More to write, but less to count later.

3. If you want a shorter code, you could use a help arrays ( I have invented them for myself in 1978)

   // neighbor-vectors in xy coordinates clockwise from algebraic x axis.
   int [8] dx={1,1,0,-1,-1,-1,0,1};
   int [8] dy={0,-1,-1,-1,0,1,1,1};
   

   and in counting neighbours for a cell do:

   if(cell[x,y]>0)
   for(i=0;i<8;i++){
      x1=x+dx[i];
      y1=y+dy[i];
      if(x1>=0 & x1<100 & y1>=0 & y1<100){
          neighbours[x1,y1]++;
      }
   }
   

4. Count the time spent for different activities, for not to waste time on optimizing part that takes 0.1% of time.

   So you can throw off many objects, not to create them at all. Only hold 2 desk in 2x100x100 array - each time one will be active, the other will be old. You can even count neighbours and later make living/dead cells on the same desk. No garbage collection.

Answer 2

@Gangnus made some very good suggestions. But additionally, two ideas.

1. Instead of having a grid of bool and calculate each cell, why not have an intermediate grid of int?

2. Another improvement might be to harness the power of parallel processing: http://www.dotnetcurry.com/ShowArticle.aspx?ID=608
   Instead of using regular for cycles, and since each iteration is independent from all other iterations, you can convert for(int i=0; i<10; i++) { ... } into Parallel.For(0, 10, i => { ... });.

This second one is more advanced than what you are looking for and specifically asked, but very interesting nevertheless. You can still disregard it and look into only the first one.

So your CheckAdjacent method could be:

private bool[,] CheckAdjacent(bool[,] grid) {
    int[,] newGrid = new int[gridX, gridY];
    Parallel.For(0, gridX, x => {
        Parallel.For(0, gridY, y => {
            if(grid[x,y]) {
                IncrementNeighbours(newGrid, x ,y);
            }
        });
    });
    bool[,] newGridBools = new bool[gridX, gridY];
    Parallel.For(0, gridX, x => {
        Parallel.For(0, gridY, y => {
            newGridBools[x,y] = IsCellAlive(newGridBools[x,y], grid[x,y]);
        });
    });
    return newGridBools;
}

// @Gangnus' code fits perfectly. YOINK! <3
// This can probably be improved; but what for, if it works perfect?
static readonly int [8] dx={1,1,0,-1,-1,-1,0,1};
static readonly int [8] dy={0,-1,-1,-1,0,1,1,1};
private void IncrementNeighbours( int[,] newGrid, int x, int y ) {
    for(i=0; i<8; i++){
        x1=x+dx[i];
        y1=y+dy[i];
        if(x1>=0 & x1<100 & y1>=0 & y1<100){
            neighbours[x1,y1]++;
        }
    }
}