From e36b37583bebd229102f46c4ed7d2f6fad8697d4 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 23 Jul 2021 13:24:09 +0200 Subject: Adding upstream version 0.6.0. Signed-off-by: Daniel Baumann --- regressions/ck_rhs/benchmark/Makefile | 17 + regressions/ck_rhs/benchmark/parallel_bytestring.c | 599 +++++++++++++++++++++ regressions/ck_rhs/benchmark/serial.c | 517 ++++++++++++++++++ 3 files changed, 1133 insertions(+) create mode 100644 regressions/ck_rhs/benchmark/Makefile create mode 100644 regressions/ck_rhs/benchmark/parallel_bytestring.c create mode 100644 regressions/ck_rhs/benchmark/serial.c (limited to 'regressions/ck_rhs/benchmark') diff --git a/regressions/ck_rhs/benchmark/Makefile b/regressions/ck_rhs/benchmark/Makefile new file mode 100644 index 0000000..e997993 --- /dev/null +++ b/regressions/ck_rhs/benchmark/Makefile @@ -0,0 +1,17 @@ +.PHONY: clean distribution + +OBJECTS=serial parallel_bytestring + +all: $(OBJECTS) + +serial: serial.c ../../../include/ck_rhs.h ../../../src/ck_rhs.c + $(CC) $(CFLAGS) -o serial serial.c ../../../src/ck_rhs.c + +parallel_bytestring: parallel_bytestring.c ../../../include/ck_rhs.h ../../../src/ck_rhs.c ../../../src/ck_epoch.c + $(CC) $(PTHREAD_CFLAGS) $(CFLAGS) -o parallel_bytestring parallel_bytestring.c ../../../src/ck_rhs.c ../../../src/ck_epoch.c + +clean: + rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe + +include ../../../build/regressions.build +CFLAGS+=-D_GNU_SOURCE diff --git a/regressions/ck_rhs/benchmark/parallel_bytestring.c b/regressions/ck_rhs/benchmark/parallel_bytestring.c new file mode 100644 index 0000000..a95d940 --- /dev/null +++ b/regressions/ck_rhs/benchmark/parallel_bytestring.c @@ -0,0 +1,599 @@ +/* + * Copyright 2012 Samy Al Bahra. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyrighs + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyrighs + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ +#include "../../common.h" +#include +#include "../../../src/ck_ht_hash.h" +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +static ck_rhs_t hs CK_CC_CACHELINE; +static char **keys; +static size_t keys_length = 0; +static size_t keys_capacity = 128; +static ck_epoch_t epoch_hs; +static ck_epoch_record_t epoch_wr; +static int n_threads; +static bool next_stage; + +enum state { + HS_STATE_STOP = 0, + HS_STATE_GET, + HS_STATE_STRICT_REPLACEMENT, + HS_STATE_DELETION, + HS_STATE_REPLACEMENT, + HS_STATE_COUNT +}; + +static ck_spinlock_t mtx = CK_SPINLOCK_INITIALIZER; +static struct affinity affinerator = AFFINITY_INITIALIZER; +static uint64_t accumulator[HS_STATE_COUNT]; +static int barrier[HS_STATE_COUNT]; +static int state; + +struct hs_epoch { + ck_epoch_entry_t epoch_entry; +}; + +COMMON_ALARM_DECLARE_GLOBAL(hs_alarm, alarm_event, next_stage) + +static void +alarm_handler(int s) +{ + + (void)s; + next_stage = true; + return; +} + +static unsigned long +hs_hash(const void *object, unsigned long seed) +{ + const char *c = object; + unsigned long h; + + h = (unsigned long)MurmurHash64A(c, strlen(c), seed); + return h; +} + +static bool +hs_compare(const void *previous, const void *compare) +{ + + return strcmp(previous, compare) == 0; +} + +static void +hs_destroy(ck_epoch_entry_t *e) +{ + + free(e); + return; +} + +static void * +hs_malloc(size_t r) +{ + ck_epoch_entry_t *b; + + b = malloc(sizeof(*b) + r); + return b + 1; +} + +static void +hs_free(void *p, size_t b, bool r) +{ + struct hs_epoch *e = p; + + (void)b; + + if (r == true) { + /* Destruction requires safe memory reclamation. */ + ck_epoch_call(&epoch_wr, &(--e)->epoch_entry, hs_destroy); + } else { + free(--e); + } + + return; +} + +static struct ck_malloc my_allocator = { + .malloc = hs_malloc, + .free = hs_free +}; + +static void +set_init(void) +{ + unsigned int mode = CK_RHS_MODE_OBJECT | CK_RHS_MODE_SPMC; + + + ck_epoch_init(&epoch_hs); + ck_epoch_register(&epoch_hs, &epoch_wr); + common_srand48((long int)time(NULL)); + if (ck_rhs_init(&hs, mode, hs_hash, hs_compare, &my_allocator, 65536, common_lrand48()) == false) { + perror("ck_rhs_init"); + exit(EXIT_FAILURE); + } + + return; +} + +static bool +set_remove(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return (bool)ck_rhs_remove(&hs, h, value); +} + +static bool +set_replace(const char *value) +{ + unsigned long h; + void *previous; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_set(&hs, h, value, &previous); +} + +static bool +set_swap(const char *value) +{ + unsigned long h; + void *previous; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_fas(&hs, h, value, &previous); +} + +static void * +set_get(const char *value) +{ + unsigned long h; + void *v; + + h = CK_RHS_HASH(&hs, hs_hash, value); + v = ck_rhs_get(&hs, h, value); + return v; +} + +static bool +set_insert(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_put(&hs, h, value); +} + +static size_t +set_count(void) +{ + + return ck_rhs_count(&hs); +} + +static bool +set_reset(void) +{ + + return ck_rhs_reset(&hs); +} + +static void * +reader(void *unused) +{ + size_t i; + ck_epoch_record_t epoch_record; + int state_previous = HS_STATE_STOP; + int n_state = 0; + uint64_t s, j, a; + + (void)unused; + if (aff_iterate(&affinerator) != 0) + perror("WARNING: Failed to affine thread"); + + s = j = a = 0; + ck_epoch_register(&epoch_hs, &epoch_record); + for (;;) { + j++; + ck_epoch_begin(&epoch_record, NULL); + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + char *r; + + r = set_get(keys[i]); + if (r == NULL) { + if (n_state == HS_STATE_STRICT_REPLACEMENT) { + ck_error("ERROR: Did not find during replacement: %s\n", keys[i]); + } + + continue; + } + + if (strcmp(r, keys[i]) == 0) + continue; + + ck_error("ERROR: Found invalid value: [%s] but expected [%s]\n", (char *)r, keys[i]); + } + a += rdtsc() - s; + ck_epoch_end(&epoch_record, NULL); + + n_state = ck_pr_load_int(&state); + if (n_state != state_previous) { + ck_spinlock_lock(&mtx); + accumulator[state_previous] += a / (j * keys_length); + ck_spinlock_unlock(&mtx); + + ck_pr_inc_int(&barrier[state_previous]); + while (ck_pr_load_int(&barrier[state_previous]) != n_threads + 1) + ck_pr_stall(); + + state_previous = n_state; + s = j = a = 0; + } + } + + return NULL; +} + +static uint64_t +acc(size_t i) +{ + uint64_t r; + + ck_spinlock_lock(&mtx); + r = accumulator[i]; + ck_spinlock_unlock(&mtx); + + return r; +} + +int +main(int argc, char *argv[]) +{ + FILE *fp; + char buffer[512]; + size_t i, j, r; + unsigned int d = 0; + uint64_t s, e, a, repeated; + char **t; + pthread_t *readers; + double p_r, p_d; + + COMMON_ALARM_DECLARE_LOCAL(hs_alarm, alarm_event) + + r = 20; + s = 8; + p_d = 0.5; + p_r = 0.5; + n_threads = CORES - 1; + + if (argc < 2) { + ck_error("Usage: parallel [ \n" + " ]\n"); + } + + if (argc >= 3) + r = atoi(argv[2]); + + if (argc >= 4) + s = (uint64_t)atoi(argv[3]); + + if (argc >= 5) { + n_threads = atoi(argv[4]); + if (n_threads < 1) { + ck_error("ERROR: Number of readers must be >= 1.\n"); + } + } + + if (argc >= 6) { + p_r = atof(argv[5]) / 100.00; + if (p_r < 0) { + ck_error("ERROR: Probability of replacement must be >= 0 and <= 100.\n"); + } + } + + if (argc >= 7) { + p_d = atof(argv[6]) / 100.00; + if (p_d < 0) { + ck_error("ERROR: Probability of deletion must be >= 0 and <= 100.\n"); + } + } + + COMMON_ALARM_INIT(hs_alarm, alarm_event, r) + + affinerator.delta = 1; + readers = malloc(sizeof(pthread_t) * n_threads); + assert(readers != NULL); + + keys = malloc(sizeof(char *) * keys_capacity); + assert(keys != NULL); + + fp = fopen(argv[1], "r"); + assert(fp != NULL); + + while (fgets(buffer, sizeof(buffer), fp) != NULL) { + buffer[strlen(buffer) - 1] = '\0'; + keys[keys_length++] = strdup(buffer); + assert(keys[keys_length - 1] != NULL); + + if (keys_length == keys_capacity) { + t = realloc(keys, sizeof(char *) * (keys_capacity *= 2)); + assert(t != NULL); + keys = t; + } + } + + t = realloc(keys, sizeof(char *) * keys_length); + assert(t != NULL); + keys = t; + + set_init(); + + for (i = 0; i < (size_t)n_threads; i++) { + if (pthread_create(&readers[i], NULL, reader, NULL) != 0) { + ck_error("ERROR: Failed to create thread %zu.\n", i); + } + } + + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + + fprintf(stderr, " [S] %d readers, 1 writer.\n", n_threads); + fprintf(stderr, " [S] %zu entries stored and %u duplicates.\n\n", + set_count(), d); + + fprintf(stderr, " ,- BASIC TEST\n"); + fprintf(stderr, " | Executing SMR test..."); + a = 0; + for (j = 0; j < r; j++) { + if (set_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + e = rdtsc(); + a += e - s; + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + fprintf(stderr, " | Executing replacement test..."); + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_replace(keys[i]); + e = rdtsc(); + a += e - s; + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + fprintf(stderr, " | Executing get test..."); + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + if (set_get(keys[i]) == NULL) { + ck_error("ERROR: Unexpected NULL value.\n"); + } + } + e = rdtsc(); + a += e - s; + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + a = 0; + fprintf(stderr, " | Executing removal test..."); + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + fprintf(stderr, " | Executing negative look-up test..."); + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + set_get("\x50\x03\x04\x05\x06\x10"); + } + e = rdtsc(); + a += e - s; + } + fprintf(stderr, "done (%" PRIu64 " ticks)\n", a / (r * keys_length)); + + ck_epoch_record_t epoch_temporary = epoch_wr; + ck_epoch_synchronize(&epoch_wr); + + fprintf(stderr, " '- Summary: %u pending, %u peak, %lu reclamations -> " + "%u pending, %u peak, %lu reclamations\n\n", + epoch_temporary.n_pending, epoch_temporary.n_peak, epoch_temporary.n_dispatch, + epoch_wr.n_pending, epoch_wr.n_peak, epoch_wr.n_dispatch); + + fprintf(stderr, " ,- READER CONCURRENCY\n"); + fprintf(stderr, " | Executing reader test..."); + + ck_pr_store_int(&state, HS_STATE_GET); + while (ck_pr_load_int(&barrier[HS_STATE_STOP]) != n_threads) + ck_pr_stall(); + ck_pr_inc_int(&barrier[HS_STATE_STOP]); + common_sleep(r); + ck_pr_store_int(&state, HS_STATE_STRICT_REPLACEMENT); + while (ck_pr_load_int(&barrier[HS_STATE_GET]) != n_threads) + ck_pr_stall(); + + fprintf(stderr, "done (reader = %" PRIu64 " ticks)\n", + acc(HS_STATE_GET) / n_threads); + + fprintf(stderr, " | Executing strict replacement test..."); + + a = repeated = 0; + common_alarm(alarm_handler, &alarm_event, r); + + ck_pr_inc_int(&barrier[HS_STATE_GET]); + for (;;) { + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + if (i & 1) { + set_replace(keys[i]); + } else { + set_swap(keys[i]); + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + + ck_pr_store_int(&state, HS_STATE_DELETION); + while (ck_pr_load_int(&barrier[HS_STATE_STRICT_REPLACEMENT]) != n_threads) + ck_pr_stall(); + set_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), acc(HS_STATE_STRICT_REPLACEMENT) / n_threads); + + common_alarm(alarm_handler, &alarm_event, r); + + fprintf(stderr, " | Executing deletion test (%.2f)...", p_d * 100); + a = repeated = 0; + ck_pr_inc_int(&barrier[HS_STATE_STRICT_REPLACEMENT]); + for (;;) { + double delete; + + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + set_insert(keys[i]); + if (p_d != 0.0) { + delete = common_drand48(); + if (delete <= p_d) + set_remove(keys[i]); + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + ck_pr_store_int(&state, HS_STATE_REPLACEMENT); + while (ck_pr_load_int(&barrier[HS_STATE_DELETION]) != n_threads) + ck_pr_stall(); + + set_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), acc(HS_STATE_DELETION) / n_threads); + + common_alarm(alarm_handler, &alarm_event, r); + + fprintf(stderr, " | Executing replacement test (%.2f)...", p_r * 100); + a = repeated = 0; + ck_pr_inc_int(&barrier[HS_STATE_DELETION]); + for (;;) { + double delete, replace; + + repeated++; + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + set_insert(keys[i]); + if (p_d != 0.0) { + delete = common_drand48(); + if (delete <= p_d) + set_remove(keys[i]); + } else { + delete = 0.0; + } + + if (p_r != 0.0) { + replace = common_drand48(); + if (replace <= p_r) { + if ((i & 1) || (delete <= p_d)) { + set_replace(keys[i]); + } else { + set_swap(keys[i]); + } + } + } + } + e = rdtsc(); + a += e - s; + + if (next_stage == true) { + next_stage = false; + break; + } + } + ck_pr_store_int(&state, HS_STATE_STOP); + while (ck_pr_load_int(&barrier[HS_STATE_REPLACEMENT]) != n_threads) + ck_pr_stall(); + set_reset(); + ck_epoch_synchronize(&epoch_wr); + fprintf(stderr, "done (writer = %" PRIu64 " ticks, reader = %" PRIu64 " ticks)\n", + a / (repeated * keys_length), acc(HS_STATE_REPLACEMENT) / n_threads); + + ck_pr_inc_int(&barrier[HS_STATE_REPLACEMENT]); + epoch_temporary = epoch_wr; + ck_epoch_synchronize(&epoch_wr); + + fprintf(stderr, " '- Summary: %u pending, %u peak, %lu reclamations -> " + "%u pending, %u peak, %lu reclamations\n\n", + epoch_temporary.n_pending, epoch_temporary.n_peak, epoch_temporary.n_dispatch, + epoch_wr.n_pending, epoch_wr.n_peak, epoch_wr.n_dispatch); + return 0; +} + diff --git a/regressions/ck_rhs/benchmark/serial.c b/regressions/ck_rhs/benchmark/serial.c new file mode 100644 index 0000000..18fa892 --- /dev/null +++ b/regressions/ck_rhs/benchmark/serial.c @@ -0,0 +1,517 @@ +/* + * Copyright 2012 Samy Al Bahra. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyrighs + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyrighs + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "../../common.h" +#include "../../../src/ck_ht_hash.h" + +static ck_rhs_t hs; +static char **keys; +static size_t keys_length = 0; +static size_t keys_capacity = 128; +static unsigned long global_seed; + +static void * +hs_malloc(size_t r) +{ + + return malloc(r); +} + +static void +hs_free(void *p, size_t b, bool r) +{ + + (void)b; + (void)r; + + free(p); + + return; +} + +static struct ck_malloc my_allocator = { + .malloc = hs_malloc, + .free = hs_free +}; + +static unsigned long +hs_hash(const void *object, unsigned long seed) +{ + const char *c = object; + unsigned long h; + + h = (unsigned long)MurmurHash64A(c, strlen(c), seed); + return h; +} + +static bool +hs_compare(const void *previous, const void *compare) +{ + + return strcmp(previous, compare) == 0; +} + +static void +set_destroy(void) +{ + + ck_rhs_destroy(&hs); + return; +} + +static void +set_init(unsigned int size, unsigned int mode) +{ + + if (ck_rhs_init(&hs, CK_RHS_MODE_OBJECT | CK_RHS_MODE_SPMC | mode, hs_hash, hs_compare, + &my_allocator, size, global_seed) == false) { + perror("ck_rhs_init"); + exit(EXIT_FAILURE); + } + + return; +} + +static bool +set_remove(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_remove(&hs, h, value) != NULL; +} + +static bool +set_swap(const char *value) +{ + unsigned long h; + void *previous; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_fas(&hs, h, value, &previous); +} + +static bool +set_replace(const char *value) +{ + unsigned long h; + void *previous; + + h = CK_RHS_HASH(&hs, hs_hash, value); + ck_rhs_set(&hs, h, value, &previous); + return previous != NULL; +} + +static void * +set_get(const char *value) +{ + unsigned long h; + void *v; + + h = CK_RHS_HASH(&hs, hs_hash, value); + v = ck_rhs_get(&hs, h, value); + return v; +} + +static bool +set_insert(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_put(&hs, h, value); +} + +static bool +set_insert_unique(const char *value) +{ + unsigned long h; + + h = CK_RHS_HASH(&hs, hs_hash, value); + return ck_rhs_put_unique(&hs, h, value); +} + +static size_t +set_count(void) +{ + + return ck_rhs_count(&hs); +} + +static bool +set_reset(void) +{ + + return ck_rhs_reset(&hs); +} + +static void +set_gc(void) +{ + + ck_rhs_gc(&hs); + return; +} + +static void +set_rebuild(void) +{ + + ck_rhs_rebuild(&hs); + return; +} + +static void +keys_shuffle(char **k) +{ + size_t i, j; + char *t; + + for (i = keys_length; i > 1; i--) { + j = rand() % (i - 1); + + if (j != i - 1) { + t = k[i - 1]; + k[i - 1] = k[j]; + k[j] = t; + } + } + + return; +} + +static void +run_test(const char *file, size_t r, unsigned int size, unsigned int mode) +{ + FILE *fp; + char buffer[512]; + size_t i, j; + unsigned int d = 0; + uint64_t s, e, a, ri, si, ai, sr, rg, sg, ag, sd, ng, ss, sts, su, sgc, sb; + struct ck_rhs_stat st; + char **t; + + keys = malloc(sizeof(char *) * keys_capacity); + assert(keys != NULL); + + fp = fopen(file, "r"); + assert(fp != NULL); + + while (fgets(buffer, sizeof(buffer), fp) != NULL) { + buffer[strlen(buffer) - 1] = '\0'; + keys[keys_length++] = strdup(buffer); + assert(keys[keys_length - 1] != NULL); + + if (keys_length == keys_capacity) { + t = realloc(keys, sizeof(char *) * (keys_capacity *= 2)); + assert(t != NULL); + keys = t; + } + } + + t = realloc(keys, sizeof(char *) * keys_length); + assert(t != NULL); + keys = t; + + set_init(size, mode); + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + ck_rhs_stat(&hs, &st); + + fprintf(stderr, "# %zu entries stored, %u duplicates, %u probe.\n", + set_count(), d, st.probe_maximum); + + a = 0; + for (j = 0; j < r; j++) { + if (set_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = keys_length; i > 0; i--) + d += set_insert(keys[i - 1]) == false; + e = rdtsc(); + a += e - s; + } + ri = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + if (set_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + e = rdtsc(); + a += e - s; + } + si = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + keys_shuffle(keys); + + if (set_reset() == false) { + ck_error("ERROR: Failed to reset hash table.\n"); + } + + s = rdtsc(); + for (i = 0; i < keys_length; i++) + d += set_insert(keys[i]) == false; + e = rdtsc(); + a += e - s; + } + ai = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_swap(keys[i]); + e = rdtsc(); + a += e - s; + } + ss = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_replace(keys[i]); + e = rdtsc(); + a += e - s; + } + sr = a / (r * keys_length); + + set_reset(); + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = keys_length; i > 0; i--) { + if (set_get(keys[i - 1]) == NULL) { + ck_error("ERROR: Unexpected NULL value.\n"); + } + } + e = rdtsc(); + a += e - s; + } + rg = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + if (set_get(keys[i]) == NULL) { + ck_error("ERROR: Unexpected NULL value.\n"); + } + } + e = rdtsc(); + a += e - s; + } + sg = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + keys_shuffle(keys); + + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + if (set_get(keys[i]) == NULL) { + ck_error("ERROR: Unexpected NULL value.\n"); + } + } + e = rdtsc(); + a += e - s; + } + ag = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + } + sd = a / (r * keys_length); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) { + set_get("\x50\x03\x04\x05\x06\x10"); + } + e = rdtsc(); + a += e - s; + } + ng = a / (r * keys_length); + + set_reset(); + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_insert(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + } + sts = a / (r * keys_length); + + set_reset(); + + /* Prune duplicates. */ + for (i = 0; i < keys_length; i++) { + if (set_insert(keys[i]) == true) + continue; + + free(keys[i]); + keys[i] = keys[--keys_length]; + } + + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + for (i = 0; i < keys_length; i++) + set_insert_unique(keys[i]); + e = rdtsc(); + a += e - s; + + for (i = 0; i < keys_length; i++) + set_remove(keys[i]); + } + su = a / (r * keys_length); + + for (i = 0; i < keys_length; i++) + set_insert_unique(keys[i]); + + for (i = 0; i < keys_length / 2; i++) + set_remove(keys[i]); + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + set_gc(); + e = rdtsc(); + a += e - s; + } + sgc = a / r; + + a = 0; + for (j = 0; j < r; j++) { + s = rdtsc(); + set_rebuild(); + e = rdtsc(); + a += e - s; + } + sb = a / r; + + printf("%zu " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 " " + "%" PRIu64 "\n", + keys_length, ri, si, ai, ss, sr, rg, sg, ag, sd, ng, sts, su, sgc, sb); + + fclose(fp); + + for (i = 0; i < keys_length; i++) { + free(keys[i]); + } + + free(keys); + keys_length = 0; + set_destroy(); + return; +} + +int +main(int argc, char *argv[]) +{ + unsigned int r, size; + + common_srand48((long int)time(NULL)); + if (argc < 2) { + ck_error("Usage: ck_rhs [ ]\n"); + } + + r = 16; + if (argc >= 3) + r = atoi(argv[2]); + + size = 8; + if (argc >= 4) + size = atoi(argv[3]); + + global_seed = common_lrand48(); + run_test(argv[1], r, size, 0); + run_test(argv[1], r, size, CK_RHS_MODE_READ_MOSTLY); + fprintf(stderr, "# reverse_insertion serial_insertion random_insertion serial_swap " + "serial_replace reverse_get serial_get random_get serial_remove negative_get tombstone " + "set_unique gc rebuild\n\n"); + + return 0; +} + -- cgit v1.2.3