a

1 files changed, 92 insertions, 0 deletions

diff --git a/tests/bench/trees.zc b/tests/bench/trees.zc
new file mode 100644
index 0000000..c8f46ef
--- /dev/null
+++ b/tests/bench/trees.zc
@@ -0,0 +1,92 @@
+// a full binary tree of depth D. checksum is the node count, 8191.
+// each node is two pointers. new() rounds that plus the 5-word header up
+// to 8 words (a 4-word block cannot hold the header). free of the owned
+// root recycles the tree onto the size-class lists.
+//   a  plain new / own / free
+//   b  the same, marked o3 (calls and new still leave the region)
+//   c  one array, used as an arena of pairs. no allocator in the loop.
+// the same shapes are tests/bench/trees.c.
+const int D = 12;
+const int WORDS = 16382; // two words for each of the 8191 nodes
+
+struct node { node* left, right; };
+int* heap;
+int used;
+
+node*.u make(int depth) {
+	node* n = new(node);
+	if (depth > 0) {
+		n.left = make(depth - 1);
+		n.right = make(depth - 1);
+	} else {
+		n.left = 0;
+		n.right = 0;
+	}
+	return u*n;
+}
+o3 node*.u make3(int depth) {
+	node* n = new(node);
+	if (depth > 0) {
+		n.left = make3(depth - 1);
+		n.right = make3(depth - 1);
+	} else {
+		n.left = 0;
+		n.right = 0;
+	}
+	return u*n;
+}
+int check(node* n) {
+	if (!n.left) return 1;
+	return 1 + check(n.left) + check(n.right);
+}
+o3 int check3(node* n) {
+	if (!n.left) return 1;
+	return 1 + check3(n.left) + check3(n.right);
+}
+
+// a node id is its word index plus one, so 0 can mean "no child"
+o3 int build(int depth) {
+	int i = used;
+	used = used + 2;
+	if (depth > 0) {
+		heap[i] = build(depth - 1);
+		heap[i + 1] = build(depth - 1);
+	} else {
+		heap[i] = 0;
+		heap[i + 1] = 0;
+	}
+	return i + 1;
+}
+o3 int ck(int id) {
+	int i, l;
+	if (id == 0) return 0;
+	i = id - 1;
+	l = heap[i];
+	if (l == 0) return 1;
+	return 1 + ck(l) + ck(heap[i + 1]);
+}
+
+int main() {
+	int which = get_c(), reps = 0, ch = get_c(), r = 0;
+	while (ch >= '0' && ch <= '9') { reps = reps * 10 + ch - '0'; ch = get_c(); }
+	if (which == 'c') {
+		heap = new(int, WORDS);
+		while (reps > 0) { used = 0; r = ck(build(D)); reps--; }
+		put_n(r); put_c(10);
+		return 0;
+	}
+	while (reps > 0) {
+		if (which == 'b') {
+			node* root = make3(D);
+			r = check3(root);
+			free(d*root);
+		} else {
+			node* root = make(D);
+			r = check(root);
+			free(d*root);
+		}
+		reps--;
+	}
+	put_n(r); put_c(10);
+	return 0;
+}