summaryrefslogtreecommitdiff
path: root/libguile/whippet/benchmarks/quads.c
diff options
context:
space:
mode:
Diffstat (limited to 'libguile/whippet/benchmarks/quads.c')
-rw-r--r--libguile/whippet/benchmarks/quads.c181
1 files changed, 181 insertions, 0 deletions
diff --git a/libguile/whippet/benchmarks/quads.c b/libguile/whippet/benchmarks/quads.c
new file mode 100644
index 000000000..6fa19f452
--- /dev/null
+++ b/libguile/whippet/benchmarks/quads.c
@@ -0,0 +1,181 @@
+#include <stdio.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <sys/time.h>
+
+#include "assert.h"
+#include "gc-api.h"
+#include "gc-basic-stats.h"
+#include "simple-roots-api.h"
+#include "quads-types.h"
+#include "simple-allocator.h"
+
+typedef HANDLE_TO(Quad) QuadHandle;
+
+static Quad* allocate_quad(struct gc_mutator *mut) {
+ // memset to 0 by the collector.
+ return gc_allocate_with_kind(mut, ALLOC_KIND_QUAD, sizeof (Quad));
+}
+
+/* Get the current time in microseconds */
+static unsigned long current_time(void)
+{
+ struct timeval t;
+ if (gettimeofday(&t, NULL) == -1)
+ return 0;
+ return t.tv_sec * 1000 * 1000 + t.tv_usec;
+}
+
+struct thread {
+ struct gc_mutator *mut;
+ struct gc_mutator_roots roots;
+ size_t counter;
+};
+
+// Build tree bottom-up
+static Quad* make_tree(struct thread *t, int depth) {
+ if (depth<=0) {
+ return allocate_quad(t->mut);
+ } else {
+ QuadHandle kids[4] = { { NULL }, };
+ for (size_t i = 0; i < 4; i++) {
+ HANDLE_SET(kids[i], make_tree(t, depth-1));
+ PUSH_HANDLE(t, kids[i]);
+ }
+
+ Quad *result = allocate_quad(t->mut);
+ for (size_t i = 0; i < 4; i++)
+ result->kids[i] = HANDLE_REF(kids[i]);
+
+ for (size_t i = 0; i < 4; i++)
+ POP_HANDLE(t);
+
+ return result;
+ }
+}
+
+static void validate_tree(Quad *tree, int depth) {
+ for (size_t i = 0; i < 4; i++) {
+ if (depth == 0) {
+ if (tree->kids[i])
+ abort();
+ } else {
+ if (!tree->kids[i])
+ abort();
+ validate_tree(tree->kids[i], depth - 1);
+ }
+ }
+}
+
+static void print_elapsed(const char *what, unsigned long start) {
+ unsigned long end = current_time();
+ unsigned long msec = (end - start) / 1000;
+ unsigned long usec = (end - start) % 1000;
+ printf("Completed %s in %lu.%.3lu msec\n", what, msec, usec);
+}
+
+static size_t parse_size(char *arg, const char *what) {
+ long val = atol(arg);
+ if (val <= 0) {
+ fprintf(stderr, "Failed to parse %s '%s'\n", what, arg);
+ exit(1);
+ }
+ return val;
+}
+
+static size_t tree_size(size_t depth) {
+ size_t nquads = 0;
+ size_t leaf_count = 1;
+ for (size_t i = 0; i <= depth; i++) {
+ if (nquads > ((size_t)-1) - leaf_count) {
+ fprintf(stderr,
+ "error: address space too small for quad tree of depth %zu\n",
+ depth);
+ exit(1);
+ }
+ nquads += leaf_count;
+ leaf_count *= 4;
+ }
+ return nquads;
+}
+
+#define MAX_THREAD_COUNT 256
+
+int main(int argc, char *argv[]) {
+ if (argc < 3 || 4 < argc) {
+ fprintf(stderr, "usage: %s DEPTH MULTIPLIER [GC-OPTIONS]\n", argv[0]);
+ return 1;
+ }
+
+ size_t depth = parse_size(argv[1], "depth");
+ double multiplier = atof(argv[2]);
+
+ if (!(1.0 < multiplier && multiplier < 100)) {
+ fprintf(stderr, "Failed to parse heap multiplier '%s'\n", argv[2]);
+ return 1;
+ }
+
+ size_t nquads = tree_size(depth);
+ size_t tree_bytes = nquads * sizeof(Quad);
+ size_t heap_size = tree_bytes * multiplier;
+
+ printf("Allocating heap of %.3fGB (%.2f multiplier of live data).\n",
+ heap_size / 1e9, multiplier);
+
+ struct gc_options *options = gc_allocate_options();
+ gc_options_set_int(options, GC_OPTION_HEAP_SIZE_POLICY, GC_HEAP_SIZE_FIXED);
+ gc_options_set_size(options, GC_OPTION_HEAP_SIZE, heap_size);
+ if (argc == 4) {
+ if (!gc_options_parse_and_set_many(options, argv[3])) {
+ fprintf(stderr, "Failed to set GC options: '%s'\n", argv[3]);
+ return 1;
+ }
+ }
+
+ struct gc_heap *heap;
+ struct gc_mutator *mut;
+ struct gc_basic_stats stats;
+ if (!gc_init(options, NULL, &heap, &mut, GC_BASIC_STATS, &stats)) {
+ fprintf(stderr, "Failed to initialize GC with heap size %zu bytes\n",
+ heap_size);
+ return 1;
+ }
+ struct thread t = { mut, };
+ gc_mutator_set_roots(mut, &t.roots);
+
+ QuadHandle quad = { NULL };
+
+ PUSH_HANDLE(&t, quad);
+
+ printf("Making quad tree of depth %zu (%zu nodes). Total size %.3fGB.\n",
+ depth, nquads, (nquads * sizeof(Quad)) / 1e9);
+ unsigned long start = current_time();
+ HANDLE_SET(quad, make_tree(&t, depth));
+ print_elapsed("construction", start);
+
+ validate_tree(HANDLE_REF(quad), depth);
+
+ size_t garbage_step = heap_size / 7.5;
+ printf("Allocating %.3f GB of garbage, 20 times, validating live tree each time.\n",
+ garbage_step / 1e9);
+ unsigned long garbage_start = current_time();
+ for (size_t i = 0; i < 20; i++) {
+ size_t garbage_depth = 3;
+ start = current_time();
+ for (size_t i = garbage_step/(tree_size(garbage_depth)*4*sizeof(Quad*)); i; i--)
+ make_tree(&t, garbage_depth);
+ print_elapsed("allocating garbage", start);
+
+ start = current_time();
+ validate_tree(HANDLE_REF(quad), depth);
+ }
+ print_elapsed("allocation loop", garbage_start);
+
+ gc_basic_stats_finish(&stats);
+ fputs("\n", stdout);
+ gc_basic_stats_print(&stats, stdout);
+
+ POP_HANDLE(&t);
+ return 0;
+}
+