1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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;
}
|
