tests/bench/qtree-bench.c

   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 }