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