commit a8652f8cf6db80450a5663292d85fc3501985455
Author: Mikołaj Lenczewski <mblenczewski@gmail.com>
Date: Mon, 23 Feb 2026 22:10:30 +0000
Initial commit
Diffstat:
9 files changed, 322 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,4 @@
+sssp
+
+**/.*.swp
+tags
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,18 @@
+The MIT-Zero License
+
+Copyright (c) 2026 Mikołaj Lenczewski <mikolaj@lenczewski.org>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/README b/README
@@ -0,0 +1,3 @@
+SSSP Benchmarking
+==============================================================================
+Benchmarking Dijkstra's algorithm, Bellman-Ford, and DMMSY on sparse graphs.
diff --git a/bellman_ford.c b/bellman_ford.c
@@ -0,0 +1,6 @@
+int
+bellman_ford(struct arena *scratch, struct graph *graph,
+ struct node const *src, double *dists, va_list ap)
+{
+ return -1;
+}
diff --git a/build.sh b/build.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -ex
+
+cc -o sssp main.c -O0 -g3 -Wall -Wextra -lm
diff --git a/clean.sh b/clean.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -ex
+
+rm -rf sssp
diff --git a/dijkstra.c b/dijkstra.c
@@ -0,0 +1,6 @@
+int
+dijkstra(struct arena *scratch, struct graph *graph,
+ struct node const *src, double *dists, va_list ap)
+{
+ return -1;
+}
diff --git a/dmmsy.c b/dmmsy.c
@@ -0,0 +1,6 @@
+int
+dmmsy(struct arena *scratch, struct graph *graph,
+ struct node const *src, double *dists, va_list ap)
+{
+ return -1;
+}
diff --git a/main.c b/main.c
@@ -0,0 +1,269 @@
+#define _GNU_SOURCE 1
+
+#include <assert.h>
+#include <inttypes.h>
+#include <stdalign.h>
+#include <stdarg.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+
+// helper definitions
+
+#define MSECS 1000ull
+#define USECS 1000000ull
+#define NSECS 1000000000ull
+
+#define KiB(v) (1024ull * (v))
+#define MiB(v) (1024 * KiB(v))
+#define GiB(v) (1024 * MiB(v))
+
+#define ARRLEN(arr) (sizeof (arr) / sizeof (arr)[0])
+
+#define ISPOW2(v) (((v) & ((v) - 1)) == 0)
+#define IS_ALIGNED(v, a) (((v) * ((a) - 1)) == 0)
+#define ALIGN_PREV(v, a) ((v) & ~((a) - 1))
+#define ALIGN_NEXT(v, a) ALIGN_PREV((v) + ((a) - 1), (a))
+
+struct arena {
+ void *ptr;
+ size_t cap, len;
+};
+
+static void
+arena_reset(struct arena *arena)
+{
+ arena->len = 0;
+}
+
+static void *
+arena_alloc(struct arena *arena, size_t size, size_t align)
+{
+ assert(ISPOW2(align));
+ assert(size);
+
+ uintptr_t begin = (uintptr_t) arena->ptr;
+ uintptr_t end = begin + arena->cap;
+
+ uintptr_t aligned = ALIGN_NEXT(begin + arena->len, align);
+ if (aligned + size > end)
+ return NULL;
+
+ arena->len = (aligned - begin) + size;
+
+ return (void *) aligned;
+}
+
+#define PUSH_ARRAY(arena, T, n) \
+ arena_alloc((arena), sizeof(T) * (n), alignof(T))
+#define PUSH_SIZED(arena, T) PUSH_ARRAY((arena), T, 1)
+
+static uintmax_t
+nanosecs(void)
+{
+ struct timespec now;
+ clock_gettime(CLOCK_MONOTONIC_RAW, &now);
+
+ return (uintmax_t) (now.tv_sec * NSECS) + now.tv_nsec;
+}
+
+// graph definitions
+
+#define MAX_EDGE_WEIGHT 10000
+#define EDGES_PER_NODE 10
+
+struct node;
+
+struct edge {
+ struct node *src, *dst;
+ struct edge *next;
+ double w;
+};
+
+struct node {
+ struct edge *edges;
+};
+
+struct graph {
+ struct node *nodes;
+ size_t nodes_count;
+
+ struct edge *edges;
+ size_t edges_count;
+};
+
+struct graph
+random_graph(struct arena *scratch, size_t nodes, size_t edges_per_node)
+{
+ assert(nodes);
+ assert(edges_per_node);
+ assert(edges_per_node <= nodes);
+
+ struct graph graph;
+ memset(&graph, 0, sizeof graph);
+
+ graph.nodes_count = nodes;
+ graph.edges_count = nodes * edges_per_node;
+
+ // allocate memory for graph
+ graph.nodes = PUSH_ARRAY(scratch, struct node, graph.nodes_count);
+ assert(graph.nodes);
+
+ graph.edges = PUSH_ARRAY(scratch, struct edge, graph.edges_count);
+ assert(graph.edges);
+
+ // initialise graph nodes and edges
+ struct edge *edge = &graph.edges[0];
+ for (size_t n = 0; n < graph.nodes_count; n++) {
+ struct node *node = &graph.nodes[n];
+ node->edges = NULL;
+
+ for (size_t e = 0; e < edges_per_node; e++) {
+ edge->src = node;
+
+ do {
+ edge->dst = &graph.nodes[random() % graph.nodes_count];
+ } while (edge->dst == edge->src);
+
+ edge->next = node->edges;
+ edge->w = (double) (random() % MAX_EDGE_WEIGHT);
+
+ node->edges = edge;
+
+ edge++;
+ };
+ }
+
+ return graph;
+}
+
+// algorithms under test
+
+typedef int (*sssp_t)(struct arena *scratch, struct graph *graph,
+ struct node const *src, double *dists, va_list ap);
+
+int
+dijkstra(struct arena *scratch, struct graph *graph,
+ struct node const *src, double *dists, va_list ap);
+
+int
+bellman_ford(struct arena *scratch, struct graph *graph,
+ struct node const *src, double *dists, va_list ap);
+
+int
+dmmsy(struct arena *scratch, struct graph *graph,
+ struct node const *src, double *dists, va_list ap);
+
+// benchmarking harness
+
+size_t graph_sizes[] = {
+ 1000,
+ 10000,
+ 100000,
+ 1000000,
+};
+
+struct {
+ char *name;
+ sssp_t algo;
+} algorithms[] = {
+ { "dijkstra", dijkstra, },
+ { "bellman-ford", bellman_ford, },
+ { "dmmsy", dmmsy, },
+};
+
+static uintmax_t
+bench(struct arena *arena, size_t nodes, sssp_t algorithm, double distances[nodes], ...)
+{
+ va_list ap;
+ va_start(ap, distances);
+
+ arena_reset(arena);
+
+ // seed random to ensure identical graphs between algorithms
+ srandom(nodes);
+
+ struct graph graph = random_graph(arena, nodes, EDGES_PER_NODE);
+
+ struct node *src = graph.nodes + (random() % graph.nodes_count);
+ uintmax_t begin = nanosecs();
+
+ int res = algorithm(arena, &graph, src, distances, ap);
+ if (res < 0) {
+ return -1;
+ }
+
+ uintmax_t end = nanosecs();
+
+ va_end(ap);
+
+ return end - begin;
+}
+
+int
+main(void)
+{
+ for (size_t i = 0; i < ARRLEN(graph_sizes); i++) {
+ // calculate bounds for our memory
+ size_t max_nodes = graph_sizes[i];
+ size_t distances = max_nodes;
+ size_t max_edges = max_nodes * EDGES_PER_NODE;
+ size_t algorithm_scratch_space = MiB(16); // TODO: what is the limit?
+ uintmax_t max_memory = sizeof(struct node) * max_nodes
+ + sizeof(double) * distances
+ + sizeof(struct edge) * max_edges
+ + algorithm_scratch_space;
+
+ printf("======================================================================\n");
+ printf("max nodes: %11zu, max edges: %11zu, max memory: %" PRIuMAX "\n",
+ max_nodes, max_edges, max_memory);
+ printf("======================================================================\n");
+
+ struct arena arena;
+ arena.cap = max_memory;
+ arena.ptr = malloc(arena.cap);
+ assert(arena.ptr);
+
+ // find true distances
+ double *golden = malloc(sizeof *golden * distances);
+ assert(golden);
+ memset(golden, 0, sizeof *golden * distances);
+
+ (void) bench(&arena, max_nodes, dijkstra, golden);
+
+ for (size_t j = 0; j < ARRLEN(algorithms); j++) {
+ char *name = algorithms[j].name;
+ sssp_t algo = algorithms[j].algo;
+
+ double *results = PUSH_ARRAY(&arena, double, distances);
+ assert(results);
+ memset(results, 0, sizeof *results * distances);
+
+ uintmax_t elapsed_ns = bench(&arena, max_nodes, algo, results);
+ uintmax_t elapsed_ms = (elapsed_ns * MSECS) / NSECS;
+
+ int res = memcmp(results, golden, sizeof *results * distances);
+ if (res == 0) {
+ printf("algorithm: %20s, "
+ "elapsed ns: %11" PRIuMAX ", "
+ "elapsed ms: %11" PRIuMAX "\n",
+ name, elapsed_ns, elapsed_ms);
+ } else {
+ printf("algorithm: %20s, RESULT MISMATCH!\n",
+ name);
+ }
+ }
+
+ free(golden);
+ free(arena.ptr);
+ }
+
+ return 0;
+}
+
+#include "dijkstra.c"
+#include "bellman_ford.c"
+#include "dmmsy.c"
