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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
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;
}
|