Benchmark of some simple minesweeper code

minesweeper_bm.cpp

#include <benchmark/benchmark.h>
#include <random>
#include <cstdio>
#include <queue>

static const int MINE = -1;
static const int NUM_MINES = 10000;

struct Cell {
    int value;
    int r, c;
    bool flagged = false;
    bool revealed = false;
};

static const int NUM_ROWS = 500;
static const int NUM_COLS = 500;
static const int NUM_CELLS = NUM_ROWS * NUM_COLS;

Cell board[NUM_CELLS];

inline int coordConv(int r, int c) {
    return r * NUM_COLS + c;
}

// Various uniform distributions. The distrubtions for the mine row and col
// are the same but just for the general case, separate ones are used
static std::mt19937 eng;
static std::uniform_int_distribution<> distMineLocR(0, NUM_ROWS - 1);
static std::uniform_int_distribution<> distMineLocC(0, NUM_COLS - 1);
static std::uniform_int_distribution<> dist(-1, 8);

static void initBoard() {
    // Deterministic seed so that trials work with the same data
    eng.seed(2319);

    // Initialize board to all blank
    for (int i = 0; i < NUM_ROWS; i++) {
        for (int j = 0; j < NUM_COLS; j++) {
            int c = coordConv(i, j);
            board[c].value = 0;
            board[c].r = i;
            board[c].c = j;
        }
    }

    // Place mines on the board and modfiy adjacent squares' number value
    for (int n = 0; n < NUM_MINES; n++) {
        int mineLocR = distMineLocR(eng);
        int mineLocC = distMineLocC(eng);
        int mineLoc = coordConv(mineLocR, mineLocC);
        board[mineLoc].value = MINE;
        for (int i = mineLocR - 1; i <= mineLocR + 1; i++) {
            if (i < 0 || i >= NUM_ROWS) continue;
            for (int j = mineLocC - 1; j <= mineLocC + 1; j++) {
                if (j < 0 || j >= NUM_COLS) continue;
                if (i == mineLocR && j == mineLocC) continue;
                int c = coordConv(i, j);
                if (board[c].value >= 0) board[c].value += 1;
            }
        }
    }
}

// Test just initialization of the board to get a baseline since
// we call this every trial for testing revealing a cell
static void BM_InitBoard(benchmark::State& state) {
    for (auto _ : state) {
        initBoard();
    }
}

BENCHMARK(BM_InitBoard);

// Goes through and reveals all cells adj. to target cell except
// for mines.
//
// If one of the revealed cells is a blank, then its adj. cells
// are revealed
static void revealCell(int tr, int tc) {
    bool visited[NUM_CELLS];
    for (int i = 0; i < NUM_CELLS; i++) visited[i] = false;
    std::queue<Cell*> q;
    int tcoord = coordConv(tr, tc);
    q.push(&board[tcoord]);
     while (!q.empty()) {
        Cell* cell = q.front();
        q.pop();
        if (cell->value == 0) {
            cell->revealed = true;
            for (int i = cell->r - 1; i <= cell->r + 1; i++) {
                if (i < 0 || i >= NUM_ROWS) continue;
                for (int j = cell->c - 1; j <= cell->c + 1; j++) {
                    if (j < 0 || j >= NUM_COLS) continue;
                    if (i == cell->r && j == cell->c) continue;
                    int coord = coordConv(i, j);
                    if (!visited[coord]) {
                        q.push(&board[coord]);
                        visited[coord] = true;
                    }
                }
            }
        }
     }
}

static void BM_RevealCell(benchmark::State& state) {
    for (auto _ : state) {
        initBoard();
        revealCell(0, 0);
    }
}

BENCHMARK(BM_RevealCell);

BENCHMARK_MAIN();