| Message ID | 1464138802-23503-13-git-send-email-cota@braap.org |
|---|---|
| State | New |
| Headers | show |
On 25/05/16 04:13, Emilio G. Cota wrote: > 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 @@ (snip) > +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); The previous two lines are common for the both "if" branches. Lets move it above the "if". > + 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(); Shouldn't we do this before checking for 'test_start'? > + > + rcu_read_lock(); Why don't we do rcu_read_lock()/rcu_read_unlock() inside the loop? > + 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) 'offset' is not used in this function. > +{ > + 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); > + } > +} > + (snip) > + > +static void run_test(void) > +{ > + unsigned int remaining; > + int i; > + Are we sure all the threads are ready at this point? Otherwise why bother with 'test_start' flag? > + 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]); > + } > +} > + > Kind regards, Sergey
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
On Tue, May 31, 2016 at 16:12:32 +0100, Alex Bennée wrote: > 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. ./qht-bench -d $duration -n $n -u $u -k $range -K $range -l $range -r $range -s $range where $duration is in seconds, $n is the number of threads, $u is the update rate (0.0 to 100.0), and $range is the number of keys. Most people will want to set all of -k,K,l,r,s to the same value, so it might be a good idea to add another parameter to set them all at once. E.
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; +}
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. 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