commit 5ab1a8521791268d1fd111b8472449cff2f48126
Author: MikoĊaj Lenczewski <mikolaj@lenczewski.org>
Date: Mon, 3 Nov 2025 11:48:42 +0000
Initial commit
Diffstat:
7 files changed, 312 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+bin/
diff --git a/README b/README
@@ -0,0 +1,6 @@
+conway
+==============================================================================
+Conway's "Game of Life". Implemented in C11, to test out the effect of pgo.
+To switch between display and benchmarking, edit conway.c. To test out LLVM's
+built-in PGO, run build_instr_pgo.sh. To test out LLVM's sampling PGO, run
+build_sample_pgo.sh. For debugging, run build.sh.
diff --git a/build.sh b/build.sh
@@ -0,0 +1,12 @@
+#!/bin/sh
+
+CC="${CC:-clang}"
+
+WARNINGS="-Wall -Wextra -Wno-format-pedantic -Wno-unused-parameter"
+CFLAGS="-std=c11 -O0 -g3"
+
+set -ex
+
+mkdir -p bin
+
+$CC -o bin/conway conway.c $WARNINGS $CFLAGS
diff --git a/build_instr_pgo.sh b/build_instr_pgo.sh
@@ -0,0 +1,32 @@
+#!/bin/sh
+
+CC="${CC:-clang}"
+
+WARNINGS="-Wall -Wextra -Wno-format-pedantic -Wno-unused-parameter"
+CFLAGS="-std=c11 -O3"
+
+PGOFLAGS="-g3 -fcs-profile-generate -funique-internal-linkage-names"
+
+set -ex
+
+mkdir -p bin
+
+$CC -o bin/conway-inst conway.c $WARNINGS $CFLAGS $PGOFLAGS
+
+for i in $(seq 1 5); do
+ LLVM_PROFILE_FILE="bin/conway-%p.profraw" taskset -c 0 ./bin/conway-inst
+done
+
+llvm-profdata merge -output=bin/pgo.profdata bin/conway-*.profraw
+
+$CC -o bin/conway-nopgo conway.c $WARNINGS $CFLAGS
+
+for i in $(seq 1 5); do
+ taskset -c 0 ./bin/conway-nopgo
+done
+
+$CC -o bin/conway-pgo conway.c $WARNINGS $CFLAGS -fprofile-instr-use=bin/pgo.profdata
+
+for i in $(seq 1 5); do
+ taskset -c 0 ./bin/conway-pgo
+done
diff --git a/build_sample_pgo.sh b/build_sample_pgo.sh
@@ -0,0 +1,30 @@
+#!/bin/sh
+
+CC="${CC:-clang}"
+
+WARNINGS="-Wall -Wextra -Wno-format-pedantic -Wno-unused-parameter"
+CFLAGS="-std=c11 -O3"
+
+PGOFLAGS="-g3 -gline-tables-only -fdebug-info-for-profiling -funique-internal-linkage-names"
+PROFGEN="$(which llvm-profgen-19)"
+
+set -ex
+
+mkdir -p bin
+
+$CC -o bin/conway-inst conway.c $WARNINGS $CFLAGS $PGOFLAGS
+
+perf record -o bin/pgo.profraw -b -e BR_INST_RETIRED.NEAR_TAKEN:uppp taskset -c 0 ./bin/conway-inst
+$PROFGEN --binary=./bin/conway-inst --perfdata=bin/pgo.profraw --output=bin/pgo.profdata
+
+$CC -o bin/conway-nopgo conway.c $WARNINGS $CFLAGS
+
+for i in $(seq 1 5); do
+ taskset -c 0 ./bin/conway-nopgo
+done
+
+$CC -o bin/conway-pgo conway.c $WARNINGS $CFLAGS -fprofile-sample-use=bin/pgo.profdata
+
+for i in $(seq 1 5); do
+ taskset -c 0 ./bin/conway-pgo
+done
diff --git a/clean.sh b/clean.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -ex
+
+rm -rf bin
diff --git a/conway.c b/conway.c
@@ -0,0 +1,226 @@
+#define _GNU_SOURCE 1
+
+#include <assert.h>
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#define BOARD_SIZE 64
+
+#define NEIGHBOURS 8
+static int const neighbour_dx[NEIGHBOURS] = { -1, 0, +1, -1, +1, -1, 0, +1 };
+static int const neighbour_dy[NEIGHBOURS] = { -1, -1, -1, 0, 0, +1, +1, +1 };
+
+#define LIMIT_LONELY 2
+#define LIMIT_CROWDED 4
+
+enum cell_state {
+ CELL_DEAD,
+ CELL_ALIVE,
+};
+
+struct cell {
+ enum cell_state state;
+};
+
+struct board {
+ struct cell *buf;
+ size_t width, height;
+};
+
+static inline struct cell *
+board_cell(struct board *board, size_t x, size_t y)
+{
+ if (0 <= x && x < board->width && 0 <= y && y < board->height)
+ return &board->buf[(y * board->width) + x];
+
+ return NULL;
+}
+
+void
+board_init(struct board *board, size_t width, size_t height)
+{
+ board->buf = malloc(width * height * sizeof *board->buf);
+ assert(board->buf);
+
+ board->width = width;
+ board->height = height;
+}
+
+void
+board_reset(struct board *board)
+{
+ memset(board->buf, 0, board->width * board->height * sizeof *board->buf);
+}
+
+void
+board_scramble(struct board *board)
+{
+ for (size_t j = 0; j < board->height; j++) {
+ for (size_t i = 0; i < board->width; i++) {
+ struct cell *cell = board_cell(board, i, j);
+ cell->state = (random() % 2) ? CELL_ALIVE : CELL_DEAD;
+ }
+ }
+}
+
+void
+board_copy(struct board const *restrict src, struct board *restrict dst)
+{
+ assert(src->width == dst->width);
+ assert(src->height == dst->height);
+
+ memcpy(dst->buf, src->buf, src->width * src->height * sizeof *src->buf);
+}
+
+int
+board_cmp(struct board const *restrict board, struct board const *restrict copy)
+{
+ assert(board->width == copy->width);
+ assert(board->height == copy->height);
+
+ return memcmp(board->buf, copy->buf, board->width * board->height * sizeof *board->buf);
+}
+
+void
+board_print(struct board *board)
+{
+ for (size_t j = 0; j < board->height; j++) {
+ for (size_t i = 0; i < board->width; i++) {
+ struct cell *cell = board_cell(board, i, j);
+
+ char repr = (cell->state == CELL_ALIVE) ? 'X' : ' ';
+ printf(" %c ", repr);
+ }
+ printf("\n");
+ }
+}
+
+void
+board_evaluate_cell(struct board *restrict board, struct board *restrict shadow,
+ size_t x, size_t y)
+{
+ size_t neighbours = 0;
+ for (size_t i = 0; i < NEIGHBOURS; i++) {
+ size_t px = x + neighbour_dx[i];
+ size_t py = y + neighbour_dy[i];
+
+ struct cell *neighbour = board_cell(board, px, py);
+ if (!neighbour)
+ continue;
+
+ if (neighbour->state == CELL_ALIVE)
+ neighbours++;
+ }
+
+ struct cell *save = board_cell(shadow, x, y);
+
+ if (LIMIT_LONELY < neighbours && neighbours < LIMIT_CROWDED) {
+ save->state = CELL_ALIVE;
+ } else {
+ save->state = CELL_DEAD;
+ }
+}
+
+void
+board_evaluate(struct board *restrict board, struct board *restrict shadow)
+{
+ for (size_t j = 0; j < board->height; j++) {
+ for (size_t i = 0; i < board->width; i++) {
+ board_evaluate_cell(board, shadow, i, j);
+ }
+ }
+}
+
+void
+benchmark(struct board *board, struct board *shadow)
+{
+ struct board *cur = board, *old = shadow, *tmp;
+
+ struct timespec start, end;
+ clock_gettime(CLOCK_MONOTONIC_RAW, &start);
+
+ size_t iters = 1000000;
+ for (size_t i = 0; i < iters; i++) {
+ board_evaluate(cur, old);
+
+ tmp = cur;
+ cur = old;
+ old = tmp;
+
+
+ }
+
+ clock_gettime(CLOCK_MONOTONIC_RAW, &end);
+
+ uintmax_t mult = 1000000000;
+ uintmax_t nanos = (end.tv_sec - start.tv_sec) * mult + (end.tv_nsec - start.tv_nsec);
+
+ printf("%zu iters in %" PRIuMAX " nsec: %" PRIuMAX " iters/sec\n",
+ iters, nanos, (iters * mult) / nanos);
+}
+
+void
+display(struct board *board, struct board *shadow)
+{
+ struct board *cur = board, *old = shadow, *tmp;
+
+ uintmax_t delay = 250 * 1000000;
+
+ size_t iter = 0;
+ while (board_cmp(cur, old)) {
+ board_evaluate(cur, old);
+
+ printf("iteration: %zu\n", iter++);
+ board_print(cur);
+ printf("\n");
+
+ /* swap around current board with shadow board */
+ tmp = cur;
+ cur = old;
+ old = tmp;
+
+ struct timespec time = {
+ .tv_sec = delay / 1000000000,
+ .tv_nsec = delay % 1000000000,
+ };
+
+ nanosleep(&time, NULL);
+ }
+}
+
+int
+main(void)
+{
+ srandom(time(NULL));
+
+ const size_t width = BOARD_SIZE;
+ const size_t height = BOARD_SIZE;
+
+ struct board board, shadow;
+
+ board_init(&board, width, height);
+ board_init(&shadow, width, height);
+
+ board_scramble(&board);
+
+#if 0
+ printf("initial\n=====================================\n");
+ board_print(&board);
+ printf("\n");
+#endif
+
+ // display(&board, &shadow);
+ benchmark(&board, &shadow);
+
+#if 0
+ printf("final\n=====================================\n");
+ board_print(&board);
+ printf("\n");
+#endif
+
+
+}
