From 608221c21edb345e4eeeca85385d2e149c3baa30 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sun, 4 Oct 2026 14:24:12 +0100 Subject: Measure 018 stage 2: a graph search in one event, the pairs, and runs to compare across machines (033) --- research/experiments/033-computing/bfs.c | 57 ++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100644 research/experiments/033-computing/bfs.c (limited to 'research/experiments/033-computing/bfs.c') diff --git a/research/experiments/033-computing/bfs.c b/research/experiments/033-computing/bfs.c new file mode 100644 index 0000000..0c2c518 --- /dev/null +++ b/research/experiments/033-computing/bfs.c @@ -0,0 +1,57 @@ +/* The C baseline of research 118: a breadth first search over the graph + * bfs.py writes (u32le nodes, u32le edges, then u32le from and to of each, + * sorted), adjacency as offsets into one array, from each start given. + * bfs GRAPH FROM TO [FROM TO ...]: per search a JSON line, hops, reached + * and the median of ROUNDS runs in microseconds. */ +#define _POSIX_C_SOURCE 200809L +#include +#include +#include +#include + +static double now_us(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return t.tv_sec * 1e6 + t.tv_nsec / 1e3; +} + +static int compare(const void *a, const void *b) { + double x = *(const double *)a, y = *(const double *)b; + return (x > y) - (x < y); +} + +int main(int argc, char **argv) { + FILE *f = fopen(argv[1], "rb"); + uint32_t n, m; + if (!f || fread(&n, 4, 1, f) != 1 || fread(&m, 4, 1, f) != 1) return 1; + uint32_t *from = malloc(4ull * m), *to = malloc(4ull * m), *start = calloc(n + 1, 4); + for (uint32_t k = 0; k < m; ++k) + if (fread(&from[k], 4, 1, f) != 1 || fread(&to[k], 4, 1, f) != 1) return 1; + fclose(f); + for (uint32_t k = 0; k < m; ++k) ++start[from[k] + 1]; + for (uint32_t v = 0; v < n; ++v) start[v + 1] += start[v]; + int32_t *depth = malloc(4ull * n); + uint32_t *queue = malloc(4ull * n); + for (int a = 2; a + 1 < argc; a += 2) { + uint32_t s = (uint32_t)atoi(argv[a]), t = (uint32_t)atoi(argv[a + 1]); + double runs[21]; + uint32_t reached = 0; + for (int r = 0; r < 21; ++r) { + double began = now_us(); + for (uint32_t v = 0; v < n; ++v) depth[v] = -1; + uint32_t head = 0, tail = 0; + queue[tail++] = s; + depth[s] = 0; + while (head < tail) { + uint32_t v = queue[head++]; + for (uint32_t k = start[v]; k < start[v + 1]; ++k) + if (depth[to[k]] < 0) { depth[to[k]] = depth[v] + 1; queue[tail++] = to[k]; } + } + runs[r] = now_us() - began; + reached = tail; + } + qsort(runs, 21, sizeof(*runs), compare); + printf("{\"system\":\"c\",\"from\":%u,\"to\":%u,\"hops\":%d,\"reached\":%u,\"us\":%.1f}\n", s, t, depth[t], reached, runs[10]); + } + return 0; +} -- cgit v1.2.3