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 } 287