xref: /openbmc/qemu/tests/bench/qtree-bench.c (revision e3feb2cc)
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 #include "qemu/osdep.h"
3 #include "qemu/qtree.h"
4 #include "qemu/timer.h"
5 
6 enum tree_op {
7     OP_LOOKUP,
8     OP_INSERT,
9     OP_REMOVE,
10     OP_REMOVE_ALL,
11     OP_TRAVERSE,
12 };
13 
14 struct benchmark {
15     const char * const name;
16     enum tree_op op;
17     bool fill_on_init;
18 };
19 
20 enum impl_type {
21     IMPL_GTREE,
22     IMPL_QTREE,
23 };
24 
25 struct tree_implementation {
26     const char * const name;
27     enum impl_type type;
28 };
29 
30 static 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 
58 static 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 
compare_func(const void * ap,const void * bp)69 static 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 
init_empty_tree_and_keys(enum impl_type impl,void ** ret_tree,size_t ** ret_keys,size_t n_elems)77 static 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 
traverse_func(gpointer key,gpointer value,gpointer data)102 static gboolean traverse_func(gpointer key, gpointer value, gpointer data)
103 {
104     return FALSE;
105 }
106 
remove_all(void * tree,enum impl_type impl)107 static 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 
run_benchmark(const struct benchmark * bench,enum impl_type impl,size_t n_elems)121 static 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 
main(int argc,char * argv[])218 int 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                 /* warm-up run */
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                 /* Throughput, in Mops/s */
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