summaryrefslogtreecommitdiff
path: root/libguile/whippet/benchmarks/mt-gcbench.c
diff options
context:
space:
mode:
Diffstat (limited to 'libguile/whippet/benchmarks/mt-gcbench.c')
-rw-r--r--libguile/whippet/benchmarks/mt-gcbench.c402
1 files changed, 402 insertions, 0 deletions
diff --git a/libguile/whippet/benchmarks/mt-gcbench.c b/libguile/whippet/benchmarks/mt-gcbench.c
new file mode 100644
index 000000000..9b2521043
--- /dev/null
+++ b/libguile/whippet/benchmarks/mt-gcbench.c
@@ -0,0 +1,402 @@
+// This is adapted from a benchmark written by John Ellis and Pete Kovac
+// of Post Communications.
+// It was modified by Hans Boehm of Silicon Graphics.
+// Translated to C++ 30 May 1997 by William D Clinger of Northeastern Univ.
+// Translated to C 15 March 2000 by Hans Boehm, now at HP Labs.
+//
+// This is no substitute for real applications. No actual application
+// is likely to behave in exactly this way. However, this benchmark was
+// designed to be more representative of real applications than other
+// Java GC benchmarks of which we are aware.
+// It attempts to model those properties of allocation requests that
+// are important to current GC techniques.
+// It is designed to be used either to obtain a single overall performance
+// number, or to give a more detailed estimate of how collector
+// performance varies with object lifetimes. It prints the time
+// required to allocate and collect balanced binary trees of various
+// sizes. Smaller trees result in shorter object lifetimes. Each cycle
+// allocates roughly the same amount of memory.
+// Two data structures are kept around during the entire process, so
+// that the measured performance is representative of applications
+// that maintain some live in-memory data. One of these is a tree
+// containing many pointers. The other is a large array containing
+// double precision floating point numbers. Both should be of comparable
+// size.
+//
+// The results are only really meaningful together with a specification
+// of how much memory was used. It is possible to trade memory for
+// better time performance. This benchmark should be run in a 32 MB
+// heap, though we don't currently know how to enforce that uniformly.
+//
+// Unlike the original Ellis and Kovac benchmark, we do not attempt
+// measure pause times. This facility should eventually be added back
+// in. There are several reasons for omitting it for now. The original
+// implementation depended on assumptions about the thread scheduler
+// that don't hold uniformly. The results really measure both the
+// scheduler and GC. Pause time measurements tend to not fit well with
+// current benchmark suites. As far as we know, none of the current
+// commercial Java implementations seriously attempt to minimize GC pause
+// times.
+
+#include <errno.h>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+
+#include "assert.h"
+#include "gc-api.h"
+#include "gc-basic-stats.h"
+#include "mt-gcbench-types.h"
+#include "simple-roots-api.h"
+#include "simple-allocator.h"
+
+#define MAX_THREAD_COUNT 256
+
+static const int long_lived_tree_depth = 16; // about 4Mb
+static const int array_size = 500000; // about 4Mb
+static const int min_tree_depth = 4;
+static const int max_tree_depth = 16;
+
+typedef HANDLE_TO(Node) NodeHandle;
+typedef HANDLE_TO(DoubleArray) DoubleArrayHandle;
+
+static Node* allocate_node(struct gc_mutator *mut) {
+ // memset to 0 by the collector.
+ return gc_allocate_with_kind(mut, ALLOC_KIND_NODE, sizeof (Node));
+}
+
+static DoubleArray* allocate_double_array(struct gc_mutator *mut,
+ size_t size) {
+ // May be uninitialized.
+ size_t bytes = sizeof(DoubleArray) + sizeof (double) * size;
+ DoubleArray *ret =
+ gc_allocate_pointerless_with_kind(mut, ALLOC_KIND_DOUBLE_ARRAY, bytes);
+ ret->length = size;
+ return ret;
+}
+
+static Hole* allocate_hole(struct gc_mutator *mut, size_t size) {
+ size_t bytes = sizeof(Hole) + sizeof (uintptr_t) * size;
+ Hole *ret = gc_allocate_with_kind(mut, ALLOC_KIND_HOLE, bytes);
+ ret->length = size;
+ return ret;
+}
+
+static unsigned long current_time(void) {
+ struct timeval t = { 0 };
+ gettimeofday(&t, NULL);
+ return t.tv_sec * 1000 * 1000 + t.tv_usec;
+}
+
+static double elapsed_millis(unsigned long start) {
+ return (current_time() - start) * 1e-3;
+}
+
+// Nodes used by a tree of a given size
+static int tree_size(int i) {
+ return ((1 << (i + 1)) - 1);
+}
+
+// Number of iterations to use for a given tree depth
+static int compute_num_iters(int i) {
+ return 2 * tree_size(max_tree_depth + 2) / tree_size(i);
+}
+
+// A power-law distribution. Each integer was selected by starting at 0, taking
+// a random number in [0,1), and then accepting the integer if the random number
+// was less than 0.15, or trying again with the next integer otherwise. Useful
+// for modelling allocation sizes or number of garbage objects to allocate
+// between live allocations.
+static const uint8_t power_law_distribution[256] = {
+ 1, 15, 3, 12, 2, 8, 4, 0, 18, 7, 9, 8, 15, 2, 36, 5,
+ 1, 9, 6, 11, 9, 19, 2, 0, 0, 3, 9, 6, 3, 2, 1, 1,
+ 6, 1, 8, 4, 2, 0, 5, 3, 7, 0, 0, 3, 0, 4, 1, 7,
+ 1, 8, 2, 2, 2, 14, 0, 7, 8, 0, 2, 1, 4, 12, 7, 5,
+ 0, 3, 4, 13, 10, 2, 3, 7, 0, 8, 0, 23, 0, 16, 1, 1,
+ 6, 28, 1, 18, 0, 3, 6, 5, 8, 6, 14, 5, 2, 5, 0, 11,
+ 0, 18, 4, 16, 1, 4, 3, 13, 3, 23, 7, 4, 10, 5, 3, 13,
+ 0, 14, 5, 5, 2, 5, 0, 16, 2, 0, 1, 1, 0, 0, 4, 2,
+ 7, 7, 0, 5, 7, 2, 1, 24, 27, 3, 7, 1, 0, 8, 1, 4,
+ 0, 3, 0, 7, 7, 3, 9, 2, 9, 2, 5, 10, 1, 1, 12, 6,
+ 2, 9, 5, 0, 4, 6, 0, 7, 2, 1, 5, 4, 1, 0, 1, 15,
+ 4, 0, 15, 4, 0, 0, 32, 18, 2, 2, 1, 7, 8, 3, 11, 1,
+ 2, 7, 11, 1, 9, 1, 2, 6, 11, 17, 1, 2, 5, 1, 14, 3,
+ 6, 1, 1, 15, 3, 1, 0, 6, 10, 8, 1, 3, 2, 7, 0, 1,
+ 0, 11, 3, 3, 5, 8, 2, 0, 0, 7, 12, 2, 5, 20, 3, 7,
+ 4, 4, 5, 22, 1, 5, 2, 7, 15, 2, 4, 6, 11, 8, 12, 1
+};
+
+static size_t power_law(size_t *counter) {
+ return power_law_distribution[(*counter)++ & 0xff];
+}
+
+struct thread {
+ struct gc_mutator *mut;
+ struct gc_mutator_roots roots;
+ size_t counter;
+};
+
+static void allocate_garbage(struct thread *t) {
+ size_t hole = power_law(&t->counter);
+ if (hole) {
+ allocate_hole(t->mut, hole);
+ }
+}
+
+static inline void set_field(struct gc_mutator *mut, Node *obj,
+ Node **field, Node *val) {
+ gc_write_barrier(mut, gc_ref_from_heap_object(obj), sizeof(Node),
+ gc_edge(field),
+ gc_ref_from_heap_object(val));
+ *field = val;
+}
+
+// Build tree top down, assigning to older objects.
+static void populate(struct thread *t, int depth, Node *node) {
+ struct gc_mutator *mut = t->mut;
+ if (depth <= 0)
+ return;
+
+ NodeHandle self = { node };
+ PUSH_HANDLE(t, self);
+ allocate_garbage(t);
+ NodeHandle l = { allocate_node(mut) };
+ PUSH_HANDLE(t, l);
+ allocate_garbage(t);
+ NodeHandle r = { allocate_node(mut) };
+ PUSH_HANDLE(t, r);
+
+ set_field(mut, HANDLE_REF(self), &HANDLE_REF(self)->left, HANDLE_REF(l));
+ set_field(mut, HANDLE_REF(self), &HANDLE_REF(self)->right, HANDLE_REF(r));
+ // i is 0 because the memory is zeroed.
+ HANDLE_REF(self)->j = depth;
+
+ populate(t, depth-1, HANDLE_REF(self)->left);
+ populate(t, depth-1, HANDLE_REF(self)->right);
+
+ POP_HANDLE(t);
+ POP_HANDLE(t);
+ POP_HANDLE(t);
+}
+
+// Build tree bottom-up
+static Node* make_tree(struct thread *t, int depth) {
+ struct gc_mutator *mut = t->mut;
+ if (depth <= 0)
+ return allocate_node(mut);
+
+ NodeHandle left = { make_tree(t, depth-1) };
+ PUSH_HANDLE(t, left);
+ NodeHandle right = { make_tree(t, depth-1) };
+ PUSH_HANDLE(t, right);
+
+ allocate_garbage(t);
+ Node *result = allocate_node(mut);
+ result->left = HANDLE_REF(left);
+ result->right = HANDLE_REF(right);
+ // i is 0 because the memory is zeroed.
+ result->j = depth;
+
+ POP_HANDLE(t);
+ POP_HANDLE(t);
+
+ return result;
+}
+
+static void validate_tree(Node *tree, int depth) {
+#ifndef NDEBUG
+ GC_ASSERT_EQ(tree->i, 0);
+ GC_ASSERT_EQ(tree->j, depth);
+ if (depth == 0) {
+ GC_ASSERT(!tree->left);
+ GC_ASSERT(!tree->right);
+ } else {
+ GC_ASSERT(tree->left);
+ GC_ASSERT(tree->right);
+ validate_tree(tree->left, depth - 1);
+ validate_tree(tree->right, depth - 1);
+ }
+#endif
+}
+
+static void time_construction(struct thread *t, int depth) {
+ struct gc_mutator *mut = t->mut;
+ int num_iters = compute_num_iters(depth);
+ NodeHandle temp_tree = { NULL };
+ PUSH_HANDLE(t, temp_tree);
+
+ printf("Creating %d trees of depth %d\n", num_iters, depth);
+
+ {
+ unsigned long start = current_time();
+ for (int i = 0; i < num_iters; ++i) {
+ HANDLE_SET(temp_tree, allocate_node(mut));
+ populate(t, depth, HANDLE_REF(temp_tree));
+ validate_tree(HANDLE_REF(temp_tree), depth);
+ HANDLE_SET(temp_tree, NULL);
+ }
+ printf("\tTop down construction took %.3f msec\n",
+ elapsed_millis(start));
+ }
+
+ {
+ long start = current_time();
+ for (int i = 0; i < num_iters; ++i) {
+ HANDLE_SET(temp_tree, make_tree(t, depth));
+ validate_tree(HANDLE_REF(temp_tree), depth);
+ HANDLE_SET(temp_tree, NULL);
+ }
+ printf("\tBottom up construction took %.3f msec\n",
+ elapsed_millis(start));
+ }
+
+ POP_HANDLE(t);
+}
+
+struct call_with_gc_data {
+ void* (*f)(struct thread *);
+ struct gc_heap *heap;
+};
+static void* call_with_gc_inner(struct gc_stack_addr *addr, void *arg) {
+ struct call_with_gc_data *data = arg;
+ struct gc_mutator *mut = gc_init_for_thread(addr, data->heap);
+ struct thread t = { mut, };
+ gc_mutator_set_roots(mut, &t.roots);
+ void *ret = data->f(&t);
+ gc_finish_for_thread(mut);
+ return ret;
+}
+static void* call_with_gc(void* (*f)(struct thread *),
+ struct gc_heap *heap) {
+ struct call_with_gc_data data = { f, heap };
+ return gc_call_with_stack_addr(call_with_gc_inner, &data);
+}
+
+static void* run_one_test(struct thread *t) {
+ NodeHandle long_lived_tree = { NULL };
+ NodeHandle temp_tree = { NULL };
+ DoubleArrayHandle array = { NULL };
+
+ PUSH_HANDLE(t, long_lived_tree);
+ PUSH_HANDLE(t, temp_tree);
+ PUSH_HANDLE(t, array);
+
+ // Create a long lived object
+ printf(" Creating a long-lived binary tree of depth %d\n",
+ long_lived_tree_depth);
+ HANDLE_SET(long_lived_tree, allocate_node(t->mut));
+ populate(t, long_lived_tree_depth, HANDLE_REF(long_lived_tree));
+
+ // Create long-lived array, filling half of it
+ printf(" Creating a long-lived array of %d doubles\n", array_size);
+ HANDLE_SET(array, allocate_double_array(t->mut, array_size));
+ for (int i = 0; i < array_size/2; ++i) {
+ HANDLE_REF(array)->values[i] = 1.0/i;
+ }
+
+ for (int d = min_tree_depth; d <= max_tree_depth; d += 2) {
+ time_construction(t, d);
+ }
+
+ validate_tree(HANDLE_REF(long_lived_tree), long_lived_tree_depth);
+
+ // Fake reference to LongLivedTree and array to keep them from being optimized
+ // away.
+ if (HANDLE_REF(long_lived_tree)->i != 0
+ || HANDLE_REF(array)->values[1000] != 1.0/1000)
+ fprintf(stderr, "Failed\n");
+
+ POP_HANDLE(t);
+ POP_HANDLE(t);
+ POP_HANDLE(t);
+ return NULL;
+}
+
+static void* run_one_test_in_thread(void *arg) {
+ struct gc_heap *heap = arg;
+ return call_with_gc(run_one_test, heap);
+}
+
+struct join_data { int status; pthread_t thread; };
+static void *join_thread(void *data) {
+ struct join_data *join_data = data;
+ void *ret;
+ join_data->status = pthread_join(join_data->thread, &ret);
+ return ret;
+}
+
+int main(int argc, char *argv[]) {
+ size_t heap_max_live =
+ tree_size(long_lived_tree_depth) * sizeof(Node) +
+ tree_size(max_tree_depth) * sizeof(Node) +
+ sizeof(DoubleArray) + sizeof(double) * array_size;
+ if (argc < 3 || argc > 4) {
+ fprintf(stderr, "usage: %s MULTIPLIER NTHREADS [GC-OPTIONS]\n", argv[0]);
+ return 1;
+ }
+
+ double multiplier = atof(argv[1]);
+ size_t nthreads = atol(argv[2]);
+
+ if (!(0.1 < multiplier && multiplier < 100)) {
+ fprintf(stderr, "Failed to parse heap multiplier '%s'\n", argv[1]);
+ return 1;
+ }
+ if (nthreads < 1 || nthreads > MAX_THREAD_COUNT) {
+ fprintf(stderr, "Expected integer between 1 and %d for thread count, got '%s'\n",
+ (int)MAX_THREAD_COUNT, argv[2]);
+ return 1;
+ }
+
+ size_t heap_size = heap_max_live * multiplier * nthreads;
+
+ 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 main_thread = { mut, };
+ gc_mutator_set_roots(mut, &main_thread.roots);
+
+ printf("Garbage Collector Test\n");
+ printf(" Live storage will peak at %zd bytes.\n\n", heap_max_live);
+
+ pthread_t threads[MAX_THREAD_COUNT];
+ // Run one of the threads in the main thread.
+ for (size_t i = 1; i < nthreads; i++) {
+ int status = pthread_create(&threads[i], NULL, run_one_test_in_thread, heap);
+ if (status) {
+ errno = status;
+ perror("Failed to create thread");
+ return 1;
+ }
+ }
+ run_one_test(&main_thread);
+ for (size_t i = 1; i < nthreads; i++) {
+ struct join_data data = { 0, threads[i] };
+ gc_call_without_gc(mut, join_thread, &data);
+ if (data.status) {
+ errno = data.status;
+ perror("Failed to join thread");
+ return 1;
+ }
+ }
+
+ gc_basic_stats_finish(&stats);
+ fputs("\n", stdout);
+ gc_basic_stats_print(&stats, stdout);
+}