| 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 | |
| 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 | |
| 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 | |
| 102 | static gboolean traverse_func(gpointer key, gpointer value, gpointer data) |
| 103 | { |
| 104 | return FALSE; |
| 105 | } |
| 106 | |
| 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 | |
| 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 | |
| 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 | } |