1
2#include "qemu/osdep.h"
3#include "qemu/qtree.h"
4#include "qemu/timer.h"
5
6enum tree_op {
7 OP_LOOKUP,
8 OP_INSERT,
9 OP_REMOVE,
10 OP_REMOVE_ALL,
11 OP_TRAVERSE,
12};
13
14struct benchmark {
15 const char * const name;
16 enum tree_op op;
17 bool fill_on_init;
18};
19
20enum impl_type {
21 IMPL_GTREE,
22 IMPL_QTREE,
23};
24
25struct tree_implementation {
26 const char * const name;
27 enum impl_type type;
28};
29
30static const struct benchmark benchmarks[] = {
31 {
32 .name = "Lookup",
33 .op = OP_LOOKUP,
34 .fill_on_init = true,
35 },
36 {
37 .name = "Insert",
38 .op = OP_INSERT,
39 .fill_on_init = false,
40 },
41 {
42 .name = "Remove",
43 .op = OP_REMOVE,
44 .fill_on_init = true,
45 },
46 {
47 .name = "RemoveAll",
48 .op = OP_REMOVE_ALL,
49 .fill_on_init = true,
50 },
51 {
52 .name = "Traverse",
53 .op = OP_TRAVERSE,
54 .fill_on_init = true,
55 },
56};
57
58static const struct tree_implementation impls[] = {
59 {
60 .name = "GTree",
61 .type = IMPL_GTREE,
62 },
63 {
64 .name = "QTree",
65 .type = IMPL_QTREE,
66 },
67};
68
69static int compare_func(const void *ap, const void *bp)
70{
71 const size_t *a = ap;
72 const size_t *b = bp;
73
74 return *a - *b;
75}
76
77static void init_empty_tree_and_keys(enum impl_type impl,
78 void **ret_tree, size_t **ret_keys,
79 size_t n_elems)
80{
81 size_t *keys = g_malloc_n(n_elems, sizeof(*keys));
82 for (size_t i = 0; i < n_elems; i++) {
83 keys[i] = i;
84 }
85
86 void *tree;
87 switch (impl) {
88 case IMPL_GTREE:
89 tree = g_tree_new(compare_func);
90 break;
91 case IMPL_QTREE:
92 tree = q_tree_new(compare_func);
93 break;
94 default:
95 g_assert_not_reached();
96 }
97
98 *ret_tree = tree;
99 *ret_keys = keys;
100}
101
102static gboolean traverse_func(gpointer key, gpointer value, gpointer data)
103{
104 return FALSE;
105}
106
107static inline void remove_all(void *tree, enum impl_type impl)
108{
109 switch (impl) {
110 case IMPL_GTREE:
111 g_tree_destroy(tree);
112 break;
113 case IMPL_QTREE:
114 q_tree_destroy(tree);
115 break;
116 default:
117 g_assert_not_reached();
118 }
119}
120
121static int64_t run_benchmark(const struct benchmark *bench,
122 enum impl_type impl,
123 size_t n_elems)
124{
125 void *tree;
126 size_t *keys;
127
128 init_empty_tree_and_keys(impl, &tree, &keys, n_elems);
129 if (bench->fill_on_init) {
130 for (size_t i = 0; i < n_elems; i++) {
131 switch (impl) {
132 case IMPL_GTREE:
133 g_tree_insert(tree, &keys[i], &keys[i]);
134 break;
135 case IMPL_QTREE:
136 q_tree_insert(tree, &keys[i], &keys[i]);
137 break;
138 default:
139 g_assert_not_reached();
140 }
141 }
142 }
143
144 int64_t start_ns = get_clock();
145 switch (bench->op) {
146 case OP_LOOKUP:
147 for (size_t i = 0; i < n_elems; i++) {
148 void *value;
149 switch (impl) {
150 case IMPL_GTREE:
151 value = g_tree_lookup(tree, &keys[i]);
152 break;
153 case IMPL_QTREE:
154 value = q_tree_lookup(tree, &keys[i]);
155 break;
156 default:
157 g_assert_not_reached();
158 }
159 (void)value;
160 }
161 break;
162 case OP_INSERT:
163 for (size_t i = 0; i < n_elems; i++) {
164 switch (impl) {
165 case IMPL_GTREE:
166 g_tree_insert(tree, &keys[i], &keys[i]);
167 break;
168 case IMPL_QTREE:
169 q_tree_insert(tree, &keys[i], &keys[i]);
170 break;
171 default:
172 g_assert_not_reached();
173 }
174 }
175 break;
176 case OP_REMOVE:
177 for (size_t i = 0; i < n_elems; i++) {
178 switch (impl) {
179 case IMPL_GTREE:
180 g_tree_remove(tree, &keys[i]);
181 break;
182 case IMPL_QTREE:
183 q_tree_remove(tree, &keys[i]);
184 break;
185 default:
186 g_assert_not_reached();
187 }
188 }
189 break;
190 case OP_REMOVE_ALL:
191 remove_all(tree, impl);
192 break;
193 case OP_TRAVERSE:
194 switch (impl) {
195 case IMPL_GTREE:
196 g_tree_foreach(tree, traverse_func, NULL);
197 break;
198 case IMPL_QTREE:
199 q_tree_foreach(tree, traverse_func, NULL);
200 break;
201 default:
202 g_assert_not_reached();
203 }
204 break;
205 default:
206 g_assert_not_reached();
207 }
208 int64_t ns = get_clock() - start_ns;
209
210 if (bench->op != OP_REMOVE_ALL) {
211 remove_all(tree, impl);
212 }
213 g_free(keys);
214
215 return ns;
216}
217
218int main(int argc, char *argv[])
219{
220 size_t sizes[] = {
221 32,
222 1024,
223 1024 * 4,
224 1024 * 128,
225 1024 * 1024,
226 };
227
228 double res[ARRAY_SIZE(benchmarks)][ARRAY_SIZE(impls)][ARRAY_SIZE(sizes)];
229 for (int i = 0; i < ARRAY_SIZE(sizes); i++) {
230 size_t size = sizes[i];
231 for (int j = 0; j < ARRAY_SIZE(impls); j++) {
232 const struct tree_implementation *impl = &impls[j];
233 for (int k = 0; k < ARRAY_SIZE(benchmarks); k++) {
234 const struct benchmark *bench = &benchmarks[k];
235
236
237 run_benchmark(bench, impl->type, size);
238
239 int64_t total_ns = 0;
240 int64_t n_runs = 0;
241 while (total_ns < 2e8 || n_runs < 5) {
242 total_ns += run_benchmark(bench, impl->type, size);
243 n_runs++;
244 }
245 double ns_per_run = (double)total_ns / n_runs;
246
247
248 res[k][j][i] = size / ns_per_run * 1e3;
249 }
250 }
251 }
252
253 printf("# Results' breakdown: Tree, Op and #Elements. Units: Mops/s\n");
254 printf("%5s %10s ", "Tree", "Op");
255 for (int i = 0; i < ARRAY_SIZE(sizes); i++) {
256 printf("%7zu ", sizes[i]);
257 }
258 printf("\n");
259 char separator[97];
260 for (int i = 0; i < ARRAY_SIZE(separator) - 1; i++) {
261 separator[i] = '-';
262 }
263 separator[ARRAY_SIZE(separator) - 1] = '\0';
264 printf("%s\n", separator);
265 for (int i = 0; i < ARRAY_SIZE(benchmarks); i++) {
266 for (int j = 0; j < ARRAY_SIZE(impls); j++) {
267 printf("%5s %10s ", impls[j].name, benchmarks[i].name);
268 for (int k = 0; k < ARRAY_SIZE(sizes); k++) {
269 printf("%7.2f ", res[i][j][k]);
270 if (j == 0) {
271 printf(" ");
272 } else {
273 if (res[i][0][k] != 0) {
274 double speedup = res[i][j][k] / res[i][0][k];
275 printf("(%4.2fx) ", speedup);
276 } else {
277 printf("( ) ");
278 }
279 }
280 }
281 printf("\n");
282 }
283 }
284 printf("%s\n", separator);
285 return 0;
286}
287
