tests/qht-bench.c

   1 /*
   2  * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
   3  *
   4  * License: GNU GPL, version 2 or later.
   5  *   See the COPYING file in the top-level directory.
   6  */
   7 #include "qemu/osdep.h"
   8 #include <glib.h>
   9 #include "qemu/processor.h"
  10 #include "qemu/atomic.h"
  11 #include "qemu/qht.h"
  12 #include "qemu/rcu.h"
  13 #include "exec/tb-hash-xx.h"
  14
  15 struct thread_stats {
  16     size_t rd;
  17     size_t not_rd;
  18     size_t in;
  19     size_t not_in;
  20     size_t rm;
  21     size_t not_rm;
  22     size_t rz;
  23     size_t not_rz;
  24 };
  25
  26 struct thread_info {
  27     void (*func)(struct thread_info *);
  28     struct thread_stats stats;
  29     uint64_t r;
  30     bool write_op; /* writes alternate between insertions and removals */
  31     bool resize_down;
  32 } QEMU_ALIGNED(64); /* avoid false sharing among threads */
  33
  34 static struct qht ht;
  35 static QemuThread *rw_threads;
  36
  37 #define DEFAULT_RANGE (4096)
  38 #define DEFAULT_QHT_N_ELEMS DEFAULT_RANGE
  39
  40 static unsigned int duration = 1;
  41 static unsigned int n_rw_threads = 1;
  42 static unsigned long lookup_range = DEFAULT_RANGE;
  43 static unsigned long update_range = DEFAULT_RANGE;
  44 static size_t init_range = DEFAULT_RANGE;
  45 static size_t init_size = DEFAULT_RANGE;
  46 static size_t n_ready_threads;
  47 static long populate_offset;
  48 static long *keys;
  49
  50 static size_t resize_min;
  51 static size_t resize_max;
  52 static struct thread_info *rz_info;
  53 static unsigned long resize_delay = 1000;
  54 static double resize_rate; /* 0.0 to 1.0 */
  55 static unsigned int n_rz_threads = 1;
  56 static QemuThread *rz_threads;
  57
  58 static double update_rate; /* 0.0 to 1.0 */
  59 static uint64_t update_threshold;
  60 static uint64_t resize_threshold;
  61
  62 static size_t qht_n_elems = DEFAULT_QHT_N_ELEMS;
  63 static int qht_mode;
  64
  65 static bool test_start;
  66 static bool test_stop;
  67
  68 static struct thread_info *rw_info;
  69
  70 static const char commands_string[] =
  71     " -d = duration, in seconds\n"
  72     " -n = number of threads\n"
  73     "\n"
  74     " -o = offset at which keys start\n"
  75     "\n"
  76     " -g = set -s,-k,-K,-l,-r to the same value\n"
  77     " -s = initial size hint\n"
  78     " -k = initial number of keys\n"
  79     " -K = initial range of keys (will be rounded up to pow2)\n"
  80     " -l = lookup range of keys (will be rounded up to pow2)\n"
  81     " -r = update range of keys (will be rounded up to pow2)\n"
  82     "\n"
  83     " -u = update rate (0.0 to 100.0), 50/50 split of insertions/removals\n"
  84     "\n"
  85     " -R = enable auto-resize\n"
  86     " -S = resize rate (0.0 to 100.0)\n"
  87     " -D = delay (in us) between potential resizes\n"
  88     " -N = number of resize threads";
  89
  90 static void usage_complete(int argc, char *argv[])
  91 {
  92     fprintf(stderr, "Usage: %s [options]\n", argv[0]);
  93     fprintf(stderr, "options:\n%s\n", commands_string);
  94     exit(-1);
  95 }
  96
  97 static bool is_equal(const void *obj, const void *userp)
  98 {
  99     const long *a = obj;
 100     const long *b = userp;
 101
 102     return *a == *b;
 103 }
 104
 105 static inline uint32_t h(unsigned long v)
 106 {
 107     return tb_hash_func5(v, 0, 0);
 108 }
 109
 110 /*
 111  * From: https://en.wikipedia.org/wiki/Xorshift
 112  * This is faster than rand_r(), and gives us a wider range (RAND_MAX is only
 113  * guaranteed to be >= INT_MAX).
 114  */
 115 static uint64_t xorshift64star(uint64_t x)
 116 {
 117     x ^= x >> 12; /* a */
 118     x ^= x << 25; /* b */
 119     x ^= x >> 27; /* c */
 120     return x * UINT64_C(2685821657736338717);
 121 }
 122
 123 static void do_rz(struct thread_info *info)
 124 {
 125     struct thread_stats *stats = &info->stats;
 126
 127     if (info->r < resize_threshold) {
 128         size_t size = info->resize_down ? resize_min : resize_max;
 129         bool resized;
 130
 131         resized = qht_resize(&ht, size);
 132         info->resize_down = !info->resize_down;
 133
 134         if (resized) {
 135             stats->rz++;
 136         } else {
 137             stats->not_rz++;
 138         }
 139     }
 140     g_usleep(resize_delay);
 141 }
 142
 143 static void do_rw(struct thread_info *info)
 144 {
 145     struct thread_stats *stats = &info->stats;
 146     uint32_t hash;
 147     long *p;
 148
 149     if (info->r >= update_threshold) {
 150         bool read;
 151
 152         p = &keys[info->r & (lookup_range - 1)];
 153         hash = h(*p);
 154         read = qht_lookup(&ht, is_equal, p, hash);
 155         if (read) {
 156             stats->rd++;
 157         } else {
 158             stats->not_rd++;
 159         }
 160     } else {
 161         p = &keys[info->r & (update_range - 1)];
 162         hash = h(*p);
 163         if (info->write_op) {
 164             bool written = false;
 165
 166             if (qht_lookup(&ht, is_equal, p, hash) == NULL) {
 167                 written = qht_insert(&ht, p, hash);
 168             }
 169             if (written) {
 170                 stats->in++;
 171             } else {
 172                 stats->not_in++;
 173             }
 174         } else {
 175             bool removed = false;
 176
 177             if (qht_lookup(&ht, is_equal, p, hash)) {
 178                 removed = qht_remove(&ht, p, hash);
 179             }
 180             if (removed) {
 181                 stats->rm++;
 182             } else {
 183                 stats->not_rm++;
 184             }
 185         }
 186         info->write_op = !info->write_op;
 187     }
 188 }
 189
 190 static void *thread_func(void *p)
 191 {
 192     struct thread_info *info = p;
 193
 194     rcu_register_thread();
 195
 196     atomic_inc(&n_ready_threads);
 197     while (!atomic_mb_read(&test_start)) {
 198         cpu_relax();
 199     }
 200
 201     rcu_read_lock();
 202     while (!atomic_read(&test_stop)) {
 203         info->r = xorshift64star(info->r);
 204         info->func(info);
 205     }
 206     rcu_read_unlock();
 207
 208     rcu_unregister_thread();
 209     return NULL;
 210 }
 211
 212 /* sets everything except info->func */
 213 static void prepare_thread_info(struct thread_info *info, int i)
 214 {
 215     /* seed for the RNG; each thread should have a different one */
 216     info->r = (i + 1) ^ time(NULL);
 217     /* the first update will be a write */
 218     info->write_op = true;
 219     /* the first resize will be down */
 220     info->resize_down = true;
 221
 222     memset(&info->stats, 0, sizeof(info->stats));
 223 }
 224
 225 static void
 226 th_create_n(QemuThread **threads, struct thread_info **infos, const char *name,
 227             void (*func)(struct thread_info *), int offset, int n)
 228 {
 229     struct thread_info *info;
 230     QemuThread *th;
 231     int i;
 232
 233     th = g_malloc(sizeof(*th) * n);
 234     *threads = th;
 235
 236     info = qemu_memalign(64, sizeof(*info) * n);
 237     *infos = info;
 238
 239     for (i = 0; i < n; i++) {
 240         prepare_thread_info(&info[i], offset + i);
 241         info[i].func = func;
 242         qemu_thread_create(&th[i], name, thread_func, &info[i],
 243                            QEMU_THREAD_JOINABLE);
 244     }
 245 }
 246
 247 static void create_threads(void)
 248 {
 249     th_create_n(&rw_threads, &rw_info, "rw", do_rw, 0, n_rw_threads);
 250     th_create_n(&rz_threads, &rz_info, "rz", do_rz, n_rw_threads, n_rz_threads);
 251 }
 252
 253 static void pr_params(void)
 254 {
 255     printf("Parameters:\n");
 256     printf(" duration:          %d s\n", duration);
 257     printf(" # of threads:      %u\n", n_rw_threads);
 258     printf(" initial # of keys: %zu\n", init_size);
 259     printf(" initial size hint: %zu\n", qht_n_elems);
 260     printf(" auto-resize:       %s\n",
 261            qht_mode & QHT_MODE_AUTO_RESIZE ? "on" : "off");
 262     if (resize_rate) {
 263         printf(" resize_rate:       %f%%\n", resize_rate * 100.0);
 264         printf(" resize range:      %zu-%zu\n", resize_min, resize_max);
 265         printf(" # resize threads   %u\n", n_rz_threads);
 266     }
 267     printf(" update rate:       %f%%\n", update_rate * 100.0);
 268     printf(" offset:            %ld\n", populate_offset);
 269     printf(" initial key range: %zu\n", init_range);
 270     printf(" lookup range:      %lu\n", lookup_range);
 271     printf(" update range:      %lu\n", update_range);
 272 }
 273
 274 static void do_threshold(double rate, uint64_t *threshold)
 275 {
 276     if (rate == 1.0) {
 277         *threshold = UINT64_MAX;
 278     } else {
 279         *threshold = rate * UINT64_MAX;
 280     }
 281 }
 282
 283 static void htable_init(void)
 284 {
 285     unsigned long n = MAX(init_range, update_range);
 286     uint64_t r = time(NULL);
 287     size_t retries = 0;
 288     size_t i;
 289
 290     /* avoid allocating memory later by allocating all the keys now */
 291     keys = g_malloc(sizeof(*keys) * n);
 292     for (i = 0; i < n; i++) {
 293         keys[i] = populate_offset + i;
 294     }
 295
 296     /* some sanity checks */
 297     g_assert_cmpuint(lookup_range, <=, n);
 298
 299     /* compute thresholds */
 300     do_threshold(update_rate, &update_threshold);
 301     do_threshold(resize_rate, &resize_threshold);
 302
 303     if (resize_rate) {
 304         resize_min = n / 2;
 305         resize_max = n;
 306         assert(resize_min < resize_max);
 307     } else {
 308         n_rz_threads = 0;
 309     }
 310
 311     /* initialize the hash table */
 312     qht_init(&ht, qht_n_elems, qht_mode);
 313     assert(init_size <= init_range);
 314
 315     pr_params();
 316
 317     fprintf(stderr, "Initialization: populating %zu items...", init_size);
 318     for (i = 0; i < init_size; i++) {
 319         for (;;) {
 320             uint32_t hash;
 321             long *p;
 322
 323             r = xorshift64star(r);
 324             p = &keys[r & (init_range - 1)];
 325             hash = h(*p);
 326             if (qht_insert(&ht, p, hash)) {
 327                 break;
 328             }
 329             retries++;
 330         }
 331     }
 332     fprintf(stderr, " populated after %zu retries\n", retries);
 333 }
 334
 335 static void add_stats(struct thread_stats *s, struct thread_info *info, int n)
 336 {
 337     int i;
 338
 339     for (i = 0; i < n; i++) {
 340         struct thread_stats *stats = &info[i].stats;
 341
 342         s->rd += stats->rd;
 343         s->not_rd += stats->not_rd;
 344
 345         s->in += stats->in;
 346         s->not_in += stats->not_in;
 347
 348         s->rm += stats->rm;
 349         s->not_rm += stats->not_rm;
 350
 351         s->rz += stats->rz;
 352         s->not_rz += stats->not_rz;
 353     }
 354 }
 355
 356 static void pr_stats(void)
 357 {
 358     struct thread_stats s = {};
 359     double tx;
 360
 361     add_stats(&s, rw_info, n_rw_threads);
 362     add_stats(&s, rz_info, n_rz_threads);
 363
 364     printf("Results:\n");
 365
 366     if (resize_rate) {
 367         printf(" Resizes:           %zu (%.2f%% of %zu)\n",
 368                s.rz, (double)s.rz / (s.rz + s.not_rz) * 100, s.rz + s.not_rz);
 369     }
 370
 371     printf(" Read:              %.2f M (%.2f%% of %.2fM)\n",
 372            (double)s.rd / 1e6,
 373            (double)s.rd / (s.rd + s.not_rd) * 100,
 374            (double)(s.rd + s.not_rd) / 1e6);
 375     printf(" Inserted:          %.2f M (%.2f%% of %.2fM)\n",
 376            (double)s.in / 1e6,
 377            (double)s.in / (s.in + s.not_in) * 100,
 378            (double)(s.in + s.not_in) / 1e6);
 379     printf(" Removed:           %.2f M (%.2f%% of %.2fM)\n",
 380            (double)s.rm / 1e6,
 381            (double)s.rm / (s.rm + s.not_rm) * 100,
 382            (double)(s.rm + s.not_rm) / 1e6);
 383
 384     tx = (s.rd + s.not_rd + s.in + s.not_in + s.rm + s.not_rm) / 1e6 / duration;
 385     printf(" Throughput:        %.2f MT/s\n", tx);
 386     printf(" Throughput/thread: %.2f MT/s/thread\n", tx / n_rw_threads);
 387 }
 388
 389 static void run_test(void)
 390 {
 391     unsigned int remaining;
 392     int i;
 393
 394     while (atomic_read(&n_ready_threads) != n_rw_threads + n_rz_threads) {
 395         cpu_relax();
 396     }
 397     atomic_mb_set(&test_start, true);
 398     do {
 399         remaining = sleep(duration);
 400     } while (remaining);
 401     atomic_mb_set(&test_stop, true);
 402
 403     for (i = 0; i < n_rw_threads; i++) {
 404         qemu_thread_join(&rw_threads[i]);
 405     }
 406     for (i = 0; i < n_rz_threads; i++) {
 407         qemu_thread_join(&rz_threads[i]);
 408     }
 409 }
 410
 411 static void parse_args(int argc, char *argv[])
 412 {
 413     int c;
 414
 415     for (;;) {
 416         c = getopt(argc, argv, "d:D:g:k:K:l:hn:N:o:r:Rs:S:u:");
 417         if (c < 0) {
 418             break;
 419         }
 420         switch (c) {
 421         case 'd':
 422             duration = atoi(optarg);
 423             break;
 424         case 'D':
 425             resize_delay = atol(optarg);
 426             break;
 427         case 'g':
 428             init_range = pow2ceil(atol(optarg));
 429             lookup_range = pow2ceil(atol(optarg));
 430             update_range = pow2ceil(atol(optarg));
 431             qht_n_elems = atol(optarg);
 432             init_size = atol(optarg);
 433             break;
 434         case 'h':
 435             usage_complete(argc, argv);
 436             exit(0);
 437         case 'k':
 438             init_size = atol(optarg);
 439             break;
 440         case 'K':
 441             init_range = pow2ceil(atol(optarg));
 442             break;
 443         case 'l':
 444             lookup_range = pow2ceil(atol(optarg));
 445             break;
 446         case 'n':
 447             n_rw_threads = atoi(optarg);
 448             break;
 449         case 'N':
 450             n_rz_threads = atoi(optarg);
 451             break;
 452         case 'o':
 453             populate_offset = atol(optarg);
 454             break;
 455         case 'r':
 456             update_range = pow2ceil(atol(optarg));
 457             break;
 458         case 'R':
 459             qht_mode |= QHT_MODE_AUTO_RESIZE;
 460             break;
 461         case 's':
 462             qht_n_elems = atol(optarg);
 463             break;
 464         case 'S':
 465             resize_rate = atof(optarg) / 100.0;
 466             if (resize_rate > 1.0) {
 467                 resize_rate = 1.0;
 468             }
 469             break;
 470         case 'u':
 471             update_rate = atof(optarg) / 100.0;
 472             if (update_rate > 1.0) {
 473                 update_rate = 1.0;
 474             }
 475             break;
 476         }
 477     }
 478 }
 479
 480 int main(int argc, char *argv[])
 481 {
 482     parse_args(argc, argv);
 483     htable_init();
 484     create_threads();
 485     run_test();
 486     pr_stats();
 487     return 0;
 488 }