sssp

main.c (5981B)

---

 #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"