Re: [Qemu-devel] [PATCH v6 12/15] qht: add qht-bench, a performance benchmark

["Alex Bennée" <alex.bennee@linaro.org>]

Emilio G. Cota <cota@braap.org> writes:

> This serves as a performance benchmark as well as a stress test
> for QHT. We can tweak quite a number of things, including the
> number of resize threads and how frequently resizes are triggered.
>
> A performance comparison of QHT vs CLHT[1] and ck_hs[2] using
> this same benchmark program can be found here:
>   http://imgur.com/a/0Bms4
>
> The tests are run on a 64-core AMD Opteron 6376.

It would be useful to include the template of the command line arguments
for these plots here. For example when I run it without any arguments I
get:


Results:
 Read:              34.21 M (100.00% of 34.21M)
 Inserted:          0.00 M (-nan% of 0.00M)
 Removed:           0.00 M (-nan% of 0.00M)
 Throughput:        34.21 MT/s
 Throughput/thread: 34.21 MT/s/thread

Looking at the graph it says 200k keys, so:

$ ./tests/qht-bench -k 200000
qht-bench: tests/qht-bench.c:309: htable_init: Assertion `init_size <= init_range `

So I'm a little confused on how I'm running this benchmark.

>
> Note that ck_hs's performance drops significantly as writes go
> up, since it requires an external lock (I used a ck_spinlock)
> around every write.
>
> Also, note that CLHT instead of using a seqlock, relies on an
> allocator that does not ever return the same address during the
> same read-critical section. This gives it a slight performance
> advantage over QHT on read-heavy workloads, since the seqlock
> writes aren't there.
>
> [1] CLHT: https://github.com/LPD-EPFL/CLHT
>           https://infoscience.epfl.ch/record/207109/files/ascy_asplos15.pdf
>
> [2] ck_hs: http://concurrencykit.org/
>            http://backtrace.io/blog/blog/2015/03/13/workload-specialization/
>
> A few of those plots are shown in text here, since that site
> might not be online forever. Throughput is on Mops/s on the Y axis.
>
>                              200K keys, 0 % updates
>
>   450 ++--+------+------+-------+-------+-------+-------+------+-------+--++
>       |   +      +      +       +       +       +       +      +      +N+  |
>   400 ++                                                           ---+E+ ++
>       |                                                       +++----      |
>   350 ++          9 ++------+------++                       --+E+    -+H+ ++
>       |             |      +H+-     |                 -+N+----   ---- +++  |
>   300 ++          8 ++     +E+     ++             -----+E+  --+H+         ++
>       |             |      +++      |         -+N+-----+H+--               |
>   250 ++          7 ++------+------++  +++-----+E+----                    ++
>   200 ++                    1         -+E+-----+H+                        ++
>       |                           ----                     qht +-E--+      |
>   150 ++                      -+E+                        clht +-H--+     ++
>       |                   ----                              ck +-N--+      |
>   100 ++               +E+                                                ++
>       |            ----                                                    |
>    50 ++       -+E+                                                       ++
>       |   +E+E+  +      +       +       +       +       +      +       +   |
>     0 ++--E------+------+-------+-------+-------+-------+------+-------+--++
>           1      8      16      24      32      40      48     56      64
>                                 Number of threads
>
>                              200K keys, 1 % updates
>
>   350 ++--+------+------+-------+-------+-------+-------+------+-------+--++
>       |   +      +      +       +       +       +       +      +     -+E+  |
>   300 ++                                                         -----+H+ ++
>       |                                                       +E+--        |
>       |           9 ++------+------++                  +++----             |
>   250 ++            |      +E+   -- |                 -+E+                ++
>       |           8 ++         --  ++             ----                     |
>   200 ++            |      +++-     |  +++  ---+E+                        ++
>       |           7 ++------N------++ -+E+--               qht +-E--+      |
>       |                     1  +++----                    clht +-H--+      |
>   150 ++                      -+E+                          ck +-N--+     ++
>       |                   ----                                             |
>   100 ++               +E+                                                ++
>       |            ----                                                    |
>       |        -+E+                                                        |
>    50 ++    +H+-+N+----+N+-----+N+------                                  ++
>       |   +E+E+  +      +       +      +N+-----+N+-----+N+----+N+-----+N+  |
>     0 ++--E------+------+-------+-------+-------+-------+------+-------+--++
>           1      8      16      24      32      40      48     56      64
>                                 Number of threads
>
>                              200K keys, 20 % updates
>
>   300 ++--+------+------+-------+-------+-------+-------+------+-------+--++
>       |   +      +      +       +       +       +       +      +       +   |
>       |                                                              -+H+  |
>   250 ++                                                         ----     ++
>       |           9 ++------+------++                       --+H+  ---+E+  |
>       |           8 ++     +H+--   ++                 -+H+----+E+--        |
>   200 ++            |      +E+    --|             -----+E+--  +++         ++
>       |           7 ++      + ---- ++       ---+H+---- +++ qht +-E--+      |
>   150 ++          6 ++------N------++ -+H+-----+E+        clht +-H--+     ++
>       |                     1     -----+E+--                ck +-N--+      |
>       |                       -+H+----                                     |
>   100 ++                  -----+E+                                        ++
>       |                +E+--                                               |
>       |            ----+++                                                 |
>    50 ++       -+E+                                                       ++
>       |     +E+ +++                                                        |
>       |   +E+N+-+N+-----+       +       +       +       +      +       +   |
>     0 ++--E------+------N-------N-------N-------N-------N------N-------N--++
>           1      8      16      24      32      40      48     56      64
>                                 Number of threads
>
>                             200K keys, 100 % updates       qht +-E--+
>                                                           clht +-H--+
>   160 ++--+------+------+-------+-------+-------+-------+---ck-+-N-----+--++
>       |   +      +      +       +       +       +       +      +   ----H   |
>   140 ++                                                      +H+--  -+E+ ++
>       |                                                +++----   ----      |
>   120 ++          8 ++------+------++                 -+H+    +E+         ++
>       |           7 ++     +H+---- ++             ---- +++----             |
>   100 ++            |      +E+      |  +++  ---+H+    -+E+                ++
>       |           6 ++     +++     ++ -+H+--   +++----                     |
>    80 ++          5 ++------N----------+E+-----+E+                        ++
>       |                     1 -+H+---- +++                                 |
>       |                   -----+E+                                         |
>    60 ++               +H+---- +++                                        ++
>       |            ----+E+                                                 |
>    40 ++        +H+----                                                   ++
>       |       --+E+                                                        |
>    20 ++    +E+                                                           ++
>       |  +EE+    +      +       +       +       +       +      +       +   |
>     0 ++--+N-N---N------N-------N-------N-------N-------N------N-------N--++
>           1      8      16      24      32      40      48     56      64
>                                 Number of threads
>
> Signed-off-by: Emilio G. Cota <cota@braap.org>
> ---
>  tests/.gitignore  |   1 +
>  tests/Makefile    |   3 +-
>  tests/qht-bench.c | 474 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 477 insertions(+), 1 deletion(-)
>  create mode 100644 tests/qht-bench.c
>
> diff --git a/tests/.gitignore b/tests/.gitignore
> index ffde5d2..d19023e 100644
> --- a/tests/.gitignore
> +++ b/tests/.gitignore
> @@ -7,6 +7,7 @@ check-qnull
>  check-qstring
>  check-qom-interface
>  check-qom-proplist
> +qht-bench
>  rcutorture
>  test-aio
>  test-base64
> diff --git a/tests/Makefile b/tests/Makefile
> index 8589b11..176bbd8 100644
> --- a/tests/Makefile
> +++ b/tests/Makefile
> @@ -398,7 +398,7 @@ test-obj-y = tests/check-qint.o tests/check-qstring.o tests/check-qdict.o \
>  	tests/test-opts-visitor.o tests/test-qmp-event.o \
>  	tests/rcutorture.o tests/test-rcu-list.o \
>  	tests/test-qdist.o \
> -	tests/test-qht.o
> +	tests/test-qht.o tests/qht-bench.o
>
>  $(test-obj-y): QEMU_INCLUDES += -Itests
>  QEMU_CFLAGS += -I$(SRC_PATH)/tests
> @@ -439,6 +439,7 @@ tests/rcutorture$(EXESUF): tests/rcutorture.o $(test-util-obj-y)
>  tests/test-rcu-list$(EXESUF): tests/test-rcu-list.o $(test-util-obj-y)
>  tests/test-qdist$(EXESUF): tests/test-qdist.o $(test-util-obj-y)
>  tests/test-qht$(EXESUF): tests/test-qht.o $(test-util-obj-y)
> +tests/qht-bench$(EXESUF): tests/qht-bench.o $(test-util-obj-y)
>
>  tests/test-qdev-global-props$(EXESUF): tests/test-qdev-global-props.o \
>  	hw/core/qdev.o hw/core/qdev-properties.o hw/core/hotplug.o\
> diff --git a/tests/qht-bench.c b/tests/qht-bench.c
> new file mode 100644
> index 0000000..30d27c8
> --- /dev/null
> +++ b/tests/qht-bench.c
> @@ -0,0 +1,474 @@
> +/*
> + * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
> + *
> + * License: GNU GPL, version 2 or later.
> + *   See the COPYING file in the top-level directory.
> + */
> +#include "qemu/osdep.h"
> +#include <glib.h>
> +#include "qemu/processor.h"
> +#include "qemu/atomic.h"
> +#include "qemu/qht.h"
> +#include "qemu/rcu.h"
> +#include "exec/tb-hash-xx.h"
> +
> +struct thread_stats {
> +    size_t rd;
> +    size_t not_rd;
> +    size_t in;
> +    size_t not_in;
> +    size_t rm;
> +    size_t not_rm;
> +    size_t rz;
> +    size_t not_rz;
> +};
> +
> +struct thread_info {
> +    void (*func)(struct thread_info *);
> +    struct thread_stats stats;
> +    uint64_t r;
> +    bool write_op; /* writes alternate between insertions and removals */
> +    bool resize_down;
> +} QEMU_ALIGNED(64); /* avoid false sharing among threads */
> +
> +static struct qht ht;
> +static QemuThread *rw_threads;
> +
> +#define DEFAULT_RANGE (4096)
> +#define DEFAULT_QHT_N_ELEMS DEFAULT_RANGE
> +
> +static unsigned int duration = 1;
> +static unsigned int n_rw_threads = 1;
> +static unsigned long lookup_range = DEFAULT_RANGE;
> +static unsigned long update_range = DEFAULT_RANGE;
> +static size_t init_range = DEFAULT_RANGE;
> +static size_t init_size = DEFAULT_RANGE;
> +static long populate_offset;
> +static long *keys;
> +
> +static size_t resize_min;
> +static size_t resize_max;
> +static struct thread_info *rz_info;
> +static unsigned long resize_delay = 1000;
> +static double resize_rate; /* 0.0 to 1.0 */
> +static unsigned int n_rz_threads = 1;
> +static QemuThread *rz_threads;
> +
> +static double update_rate; /* 0.0 to 1.0 */
> +static uint64_t update_threshold;
> +static uint64_t resize_threshold;
> +
> +static size_t qht_n_elems = DEFAULT_QHT_N_ELEMS;
> +static int qht_mode;
> +
> +static bool test_start;
> +static bool test_stop;
> +
> +static struct thread_info *rw_info;
> +
> +static const char commands_string[] =
> +    " -d = duration, in seconds\n"
> +    " -n = number of threads\n"
> +    "\n"
> +    " -k = initial number of keys\n"
> +    " -o = offset at which keys start\n"
> +    " -K = initial range of keys (will be rounded up to pow2)\n"
> +    " -l = lookup range of keys (will be rounded up to pow2)\n"
> +    " -r = update range of keys (will be rounded up to pow2)\n"
> +    "\n"
> +    " -u = update rate (0.0 to 100.0), 50/50 split of insertions/removals\n"
> +    "\n"
> +    " -s = initial size hint\n"
> +    " -R = enable auto-resize\n"
> +    " -S = resize rate (0.0 to 100.0)\n"
> +    " -D = delay (in us) between potential resizes\n"
> +    " -N = number of resize threads";
> +
> +static void usage_complete(int argc, char *argv[])
> +{
> +    fprintf(stderr, "Usage: %s [options]\n", argv[0]);
> +    fprintf(stderr, "options:\n%s\n", commands_string);
> +    exit(-1);
> +}
> +
> +static bool is_equal(const void *obj, const void *userp)
> +{
> +    const long *a = obj;
> +    const long *b = userp;
> +
> +    return *a == *b;
> +}
> +
> +static inline uint32_t h(unsigned long v)
> +{
> +    return tb_hash_func5(v, 0, 0);
> +}
> +
> +/*
> + * From: https://en.wikipedia.org/wiki/Xorshift
> + * This is faster than rand_r(), and gives us a wider range (RAND_MAX is only
> + * guaranteed to be >= INT_MAX).
> + */
> +static uint64_t xorshift64star(uint64_t x)
> +{
> +    x ^= x >> 12; /* a */
> +    x ^= x << 25; /* b */
> +    x ^= x >> 27; /* c */
> +    return x * UINT64_C(2685821657736338717);
> +}
> +
> +static void do_rz(struct thread_info *info)
> +{
> +    struct thread_stats *stats = &info->stats;
> +
> +    if (info->r < resize_threshold) {
> +        size_t size = info->resize_down ? resize_min : resize_max;
> +        bool resized;
> +
> +        resized = qht_resize(&ht, size);
> +        info->resize_down = !info->resize_down;
> +
> +        if (resized) {
> +            stats->rz++;
> +        } else {
> +            stats->not_rz++;
> +        }
> +    }
> +    g_usleep(resize_delay);
> +}
> +
> +static void do_rw(struct thread_info *info)
> +{
> +    struct thread_stats *stats = &info->stats;
> +    uint32_t hash;
> +    long *p;
> +
> +    if (info->r >= update_threshold) {
> +        bool read;
> +
> +        p = &keys[info->r & (lookup_range - 1)];
> +        hash = h(*p);
> +        read = qht_lookup(&ht, is_equal, p, hash);
> +        if (read) {
> +            stats->rd++;
> +        } else {
> +            stats->not_rd++;
> +        }
> +    } else {
> +        p = &keys[info->r & (update_range - 1)];
> +        hash = h(*p);
> +        if (info->write_op) {
> +            bool written = false;
> +
> +            if (qht_lookup(&ht, is_equal, p, hash) == NULL) {
> +                written = qht_insert(&ht, p, hash);
> +            }
> +            if (written) {
> +                stats->in++;
> +            } else {
> +                stats->not_in++;
> +            }
> +        } else {
> +            bool removed = false;
> +
> +            if (qht_lookup(&ht, is_equal, p, hash)) {
> +                removed = qht_remove(&ht, p, hash);
> +            }
> +            if (removed) {
> +                stats->rm++;
> +            } else {
> +                stats->not_rm++;
> +            }
> +        }
> +        info->write_op = !info->write_op;
> +    }
> +}
> +
> +static void *thread_func(void *p)
> +{
> +    struct thread_info *info = p;
> +
> +    while (!atomic_mb_read(&test_start)) {
> +        cpu_relax();
> +    }
> +
> +    rcu_register_thread();
> +
> +    rcu_read_lock();
> +    while (!atomic_read(&test_stop)) {
> +        info->r = xorshift64star(info->r);
> +        info->func(info);
> +    }
> +    rcu_read_unlock();
> +
> +    rcu_unregister_thread();
> +    return NULL;
> +}
> +
> +/* sets everything except info->func */
> +static void prepare_thread_info(struct thread_info *info, int i)
> +{
> +    /* seed for the RNG; each thread should have a different one */
> +    info->r = (i + 1) ^ time(NULL);
> +    /* the first update will be a write */
> +    info->write_op = true;
> +    /* the first resize will be down */
> +    info->resize_down = true;
> +
> +    memset(&info->stats, 0, sizeof(info->stats));
> +}
> +
> +static void
> +th_create_n(QemuThread **threads, struct thread_info **infos, const char *name,
> +            void (*func)(struct thread_info *), int offset, int n)
> +{
> +    struct thread_info *info;
> +    QemuThread *th;
> +    int i;
> +
> +    th = g_malloc(sizeof(*th) * n);
> +    *threads = th;
> +
> +    info = qemu_memalign(64, sizeof(*info) * n);
> +    *infos = info;
> +
> +    for (i = 0; i < n; i++) {
> +        prepare_thread_info(&info[i], i);
> +        info[i].func = func;
> +        qemu_thread_create(&th[i], name, thread_func, &info[i],
> +                           QEMU_THREAD_JOINABLE);
> +    }
> +}
> +
> +static void create_threads(void)
> +{
> +    th_create_n(&rw_threads, &rw_info, "rw", do_rw, 0, n_rw_threads);
> +    th_create_n(&rz_threads, &rz_info, "rz", do_rz, n_rw_threads, n_rz_threads);
> +}
> +
> +static void pr_params(void)
> +{
> +    printf("Parameters:\n");
> +    printf(" duration:          %d s\n", duration);
> +    printf(" # of threads:      %u\n", n_rw_threads);
> +    printf(" initial # of keys: %zu\n", init_size);
> +    printf(" initial size hint: %zu\n", qht_n_elems);
> +    printf(" auto-resize:       %s\n",
> +           qht_mode & QHT_MODE_AUTO_RESIZE ? "on" : "off");
> +    if (resize_rate) {
> +        printf(" resize_rate:       %f%%\n", resize_rate * 100.0);
> +        printf(" resize range:      %zu-%zu\n", resize_min, resize_max);
> +        printf(" # resize threads   %u\n", n_rz_threads);
> +    }
> +    printf(" update rate:       %f%%\n", update_rate * 100.0);
> +    printf(" offset:            %ld\n", populate_offset);
> +    printf(" initial key range: %zu\n", init_range);
> +    printf(" lookup range:      %zu\n", lookup_range);
> +    printf(" update range:      %zu\n", update_range);
> +}
> +
> +static void do_threshold(double rate, uint64_t *threshold)
> +{
> +    if (rate == 1.0) {
> +        *threshold = UINT64_MAX;
> +    } else {
> +        *threshold = rate * UINT64_MAX;
> +    }
> +}
> +
> +static void htable_init(void)
> +{
> +    unsigned long n = MAX(init_range, update_range);
> +    uint64_t r = time(NULL);
> +    size_t retries = 0;
> +    size_t i;
> +
> +    /* avoid allocating memory later by allocating all the keys now */
> +    keys = g_malloc(sizeof(*keys) * n);
> +    for (i = 0; i < n; i++) {
> +        keys[i] = populate_offset + i;
> +    }
> +
> +    /* some sanity checks */
> +    g_assert_cmpuint(lookup_range, <=, n);
> +
> +    /* compute thresholds */
> +    do_threshold(update_rate, &update_threshold);
> +    do_threshold(resize_rate, &resize_threshold);
> +
> +    if (resize_rate) {
> +        resize_min = n / 2;
> +        resize_max = n;
> +        assert(resize_min < resize_max);
> +    } else {
> +        n_rz_threads = 0;
> +    }
> +
> +    /* initialize the hash table */
> +    qht_init(&ht, qht_n_elems, qht_mode);
> +    assert(init_size <= init_range);
> +
> +    pr_params();
> +
> +    fprintf(stderr, "Initialization: populating %zu items...", init_size);
> +    for (i = 0; i < init_size; i++) {
> +        for (;;) {
> +            uint32_t hash;
> +            long *p;
> +
> +            r = xorshift64star(r);
> +            p = &keys[r & (init_range - 1)];
> +            hash = h(*p);
> +            if (qht_insert(&ht, p, hash)) {
> +                break;
> +            }
> +            retries++;
> +        }
> +    }
> +    fprintf(stderr, " populated after %zu retries\n", retries);
> +}
> +
> +static void add_stats(struct thread_stats *s, struct thread_info *info, int n)
> +{
> +    int i;
> +
> +    for (i = 0; i < n; i++) {
> +        struct thread_stats *stats = &info[i].stats;
> +
> +        s->rd += stats->rd;
> +        s->not_rd += stats->not_rd;
> +
> +        s->in += stats->in;
> +        s->not_in += stats->not_in;
> +
> +        s->rm += stats->rm;
> +        s->not_rm += stats->not_rm;
> +
> +        s->rz += stats->rz;
> +        s->not_rz += stats->not_rz;
> +    }
> +}
> +
> +static void pr_stats(void)
> +{
> +    struct thread_stats s = {};
> +    double tx;
> +
> +    add_stats(&s, rw_info, n_rw_threads);
> +    add_stats(&s, rz_info, n_rz_threads);
> +
> +    printf("Results:\n");
> +
> +    if (resize_rate) {
> +        printf(" Resizes:           %zu (%.2f%% of %zu)\n",
> +               s.rz, (double)s.rz / (s.rz + s.not_rz) * 100, s.rz + s.not_rz);
> +    }
> +
> +    printf(" Read:              %.2f M (%.2f%% of %.2fM)\n",
> +           (double)s.rd / 1e6,
> +           (double)s.rd / (s.rd + s.not_rd) * 100,
> +           (double)(s.rd + s.not_rd) / 1e6);
> +    printf(" Inserted:          %.2f M (%.2f%% of %.2fM)\n",
> +           (double)s.in / 1e6,
> +           (double)s.in / (s.in + s.not_in) * 100,
> +           (double)(s.in + s.not_in) / 1e6);
> +    printf(" Removed:           %.2f M (%.2f%% of %.2fM)\n",
> +           (double)s.rm / 1e6,
> +           (double)s.rm / (s.rm + s.not_rm) * 100,
> +           (double)(s.rm + s.not_rm) / 1e6);
> +
> +    tx = (s.rd + s.not_rd + s.in + s.not_in + s.rm + s.not_rm) / 1e6 / duration;
> +    printf(" Throughput:        %.2f MT/s\n", tx);
> +    printf(" Throughput/thread: %.2f MT/s/thread\n", tx / n_rw_threads);
> +}
> +
> +static void run_test(void)
> +{
> +    unsigned int remaining;
> +    int i;
> +
> +    atomic_mb_set(&test_start, true);
> +    do {
> +        remaining = sleep(duration);
> +    } while (remaining);
> +    atomic_mb_set(&test_stop, true);
> +
> +    for (i = 0; i < n_rw_threads; i++) {
> +        qemu_thread_join(&rw_threads[i]);
> +    }
> +    for (i = 0; i < n_rz_threads; i++) {
> +        qemu_thread_join(&rz_threads[i]);
> +    }
> +}
> +
> +static void parse_args(int argc, char *argv[])
> +{
> +    int c;
> +
> +    for (;;) {
> +        c = getopt(argc, argv, "d:D:k:K:l:hn:N:o:r:Rs:S:u:");
> +        if (c < 0) {
> +            break;
> +        }
> +        switch (c) {
> +        case 'd':
> +            duration = atoi(optarg);
> +            break;
> +        case 'D':
> +            resize_delay = atol(optarg);
> +            break;
> +        case 'h':
> +            usage_complete(argc, argv);
> +            exit(0);
> +        case 'k':
> +            init_size = atol(optarg);
> +            break;
> +        case 'K':
> +            init_range = pow2ceil(atol(optarg));
> +            break;
> +        case 'l':
> +            lookup_range = pow2ceil(atol(optarg));
> +            break;
> +        case 'n':
> +            n_rw_threads = atoi(optarg);
> +            break;
> +        case 'N':
> +            n_rz_threads = atoi(optarg);
> +            break;
> +        case 'o':
> +            populate_offset = atol(optarg);
> +            break;
> +        case 'r':
> +            update_range = pow2ceil(atol(optarg));
> +            break;
> +        case 'R':
> +            qht_mode |= QHT_MODE_AUTO_RESIZE;
> +            break;
> +        case 's':
> +            qht_n_elems = atol(optarg);
> +            break;
> +        case 'S':
> +            resize_rate = atof(optarg) / 100.0;
> +            if (resize_rate > 1.0) {
> +                resize_rate = 1.0;
> +            }
> +            break;
> +        case 'u':
> +            update_rate = atof(optarg) / 100.0;
> +            if (update_rate > 1.0) {
> +                update_rate = 1.0;
> +            }
> +            break;
> +        }
> +    }
> +}
> +
> +int main(int argc, char *argv[])
> +{
> +    parse_args(argc, argv);
> +    htable_init();
> +    create_threads();
> +    run_test();
> +    pr_stats();
> +    return 0;
> +}


--
Alex Bennée