1 files changed, 85 insertions, 0 deletions
diff --git a/tests/bench/trees.c b/tests/bench/trees.c
new file mode 100644
index 0000000..df46447
--- /dev/null
+++ b/tests/bench/trees.c
@@ -0,0 +1,85 @@
+/* a full binary tree of depth D. checksum is the node count, 8191.
+   malloc: one malloc per node, then a recursive free. same shape as new().
+   arena: one buffer, a bump pointer, no allocator inside the loop.
+   usage: trees malloc|arena REPS */
+#include <stdio.h>
+#include <stdlib.h>
+
+enum { D = 12, EXPECT = 8191 };
+
+typedef struct node {
+	struct node *left, *right;
+} node;
+
+static node *make(int d)
+{
+	node *n = (node *)malloc(sizeof *n);
+	if (d > 0) {
+		n->left = make(d - 1);
+		n->right = make(d - 1);
+	} else
+		n->left = n->right = 0;
+	return n;
+}
+
+static int check(const node *n)
+{
+	if (!n->left) return 1;
+	return 1 + check(n->left) + check(n->right);
+}
+
+static void destroy(node *n)
+{
+	if (!n) return;
+	destroy(n->left);
+	destroy(n->right);
+	free(n);
+}
+
+static node *bump;
+
+static node *make_at(int d)
+{
+	node *n = bump++;
+	if (d > 0) {
+		n->left = make_at(d - 1);
+		n->right = make_at(d - 1);
+	} else
+		n->left = n->right = 0;
+	return n;
+}
+
+int main(int argc, char **argv)
+{
+	int reps, r = 0, k, arena, nodes;
+	node *buf = 0;
+	if (argc != 3) return 2;
+	arena = argv[1][0] == 'a';
+	reps = atoi(argv[2]);
+	nodes = (1 << (D + 1)) - 1;
+	if (arena) {
+		buf = malloc((size_t)nodes * sizeof *buf);
+		if (!buf) return 3;
+	}
+	for (k = 0; k < reps; k++) {
+		if (arena) {
+			node *root;
+			bump = buf;
+			root = make_at(D);
+			r = check(root);
+			__asm__ __volatile__("" : "+r"(r) : "r"(root) : "memory");
+		} else {
+			node *root = make(D);
+			r = check(root);
+			__asm__ __volatile__("" : "+r"(r) : "r"(root) : "memory");
+			destroy(root);
+		}
+	}
+	if (r != EXPECT) {
+		fprintf(stderr, "bad %d\n", r);
+		return 1;
+	}
+	printf("%d\n", r);
+	free(buf);
+	return 0;
+}