I’m trying to implement Conway’s game of life in C. This is the method I’m using in order to compute the number of neighbours around each cell.

This part of the code appears to be quite slow (73,5% of the total time of execution) 4.16s:

void generar_sumas_total(CELL_TYPE *tablero, CELL_TYPE *tab_sum, INDEX_TYPE Y, INDEX_TYPE X) {
    INDEX_TYPE i, j;

    #pragma omp parallel for schedule(static)
    for (i = 0; i < Y; i++) {
        INDEX_TYPE top_row = (i == 0) ? Y - 1 : i - 1;
        INDEX_TYPE bottom_row = (i == Y - 1) ? 0 : i + 1;

        for (j = 0; j < X; j++) {
            INDEX_TYPE left_col = (j == 0) ? X - 1 : j - 1;
            INDEX_TYPE right_col = (j == X - 1) ? 0 : j + 1;

            CELL_TYPE sum = tablero[top_row * X + left_col] + 
                            tablero[top_row * X + j] + 
                            tablero[top_row * X + right_col] + 
                            tablero[i * X + left_col] + 
                            tablero[i * X + j] + 
                            tablero[i * X + right_col] + 
                            tablero[bottom_row * X + left_col] + 
                            tablero[bottom_row * X + j] + 
                            tablero[bottom_row * X + right_col];

            tab_sum[i * X + j] = sum;
        }
    }
}

Previous to this combined method, I had these two separate methods that were more efficient (22%+3,59%), 2.95s:

void generar_sumasV ( CELL_TYPE *tabIn, CELL_TYPE *tabSum, INDEX_TYPE Y, INDEX_TYPE X )
{
    INDEX_TYPE i, j;
    INDEX_TYPE lastRowIdx = (Y - 1) * X;

    // precompute first and last rows
    CELL_TYPE firstRowSum, lastRowSum;

    #pragma omp parallel for private(j)
    for (j = 0; j < X; j++) {
        CELL_TYPE t0 = tabIn[j];
        CELL_TYPE t1 = tabIn[lastRowIdx + j];
        CELL_TYPE t2 = tabIn[X + j];
        CELL_TYPE t3 = tabIn[lastRowIdx - X + j];

        firstRowSum = t0 + t1 + t2;
        lastRowSum = t0 + t1 + t3;

        tabSum[j] = firstRowSum; // First row
        tabSum[lastRowIdx + j] = lastRowSum; // Last row
    }

    INDEX_TYPE currentRowIdx, prevRowIdx, nextRowIdx;
    #pragma omp parallel for private(j)
    for (i = 1; i < Y - 1; i++) {
        prevRowIdx = (i - 1) * X;
        currentRowIdx = i * X;
        nextRowIdx = (i + 1) * X;
        for (j = 0; j < X; j++) {
            tabSum[currentRowIdx + j] = tabIn[prevRowIdx + j] + tabIn[currentRowIdx + j] + tabIn[nextRowIdx + j];
        }
    }
}


void generar_sumasH(CELL_TYPE *tabSumV, CELL_TYPE *tabSumH, INDEX_TYPE Y, INDEX_TYPE X)
{
    INDEX_TYPE i, j, fX = 0;

    // Precompute the first and last columns outside the main loop
    for (i = 0; i < Y; i++)  // For all rows of board
    {
        // Calculate for the first column in the row
        CELL_TYPE left = tabSumV[fX + X - 1];  // wrap-around left
        CELL_TYPE middle = tabSumV[fX];
        CELL_TYPE right = tabSumV[fX + 1];
        tabSumH[fX] = left + middle + right;

        // Calculate for the middle columns in the row
        for (j = 1; j < X - 1; j++)
        {
            left = tabSumV[fX + j - 1];
            middle = tabSumV[fX + j];
            right = tabSumV[fX + j + 1];
            tabSumH[fX + j] = left + middle + right;
        }

        // Calculate for the last column in the row
        left = tabSumV[fX + X - 2];
        middle = tabSumV[fX + X - 1];
        right = tabSumV[fX];  // wrap-around right
        tabSumH[fX + X - 1] = left + middle + right;

        fX += X;  // NEXT ROW
    }
}

called consecutively as so:

    generar_sumasV    ( tablero, tab_sum1, Y, X );
    generar_sumasH    ( tab_sum1, tab_sum2, Y, X );

In this case the bottleneck (other than omp) seems to be actualizar_tabler_con_cambios, which has the following code:

void actualizar_tablero_con_cambios(CELL_TYPE *tabIn, CELL_TYPE *tabSum, INDEX_TYPE Y, INDEX_TYPE X, int *cambios)
{
    INDEX_TYPE i, j;
    CELL_TYPE old, vecinos;
    int local_changes = 0;

    #pragma omp parallel for private(j, old, vecinos) reduction(+:local_changes)
    for (i = 0; i < Y; i++)
    {
        for (j = 0; j < X; j++)
        {
            old = tabIn[i * X + j];
            vecinos = tabSum[i * X + j];
            CELL_TYPE new_value = (old & (vecinos == 4)) | (vecinos == 3);
            tabIn[i * X + j] = new_value;
            local_changes += (old != new_value);
        }
    }
    *cambios = local_changes;
}

I don’t know which direction I should take from this two options in order to achieve as much performance as possible – I thought combining the two sum methods into one would increase the performance, but it’s clearly not working.

My question is, which other solutions can I use that are more efficient than both of these options, or how can I modify my current code to make it faster.

I know the code can be sped up by at least 3x.