diff options
Diffstat (limited to 'regressions/ck_hs/benchmark/serial.c')
| -rw-r--r-- | regressions/ck_hs/benchmark/serial.c | 517 |
1 files changed, 0 insertions, 517 deletions
diff --git a/regressions/ck_hs/benchmark/serial.c b/regressions/ck_hs/benchmark/serial.c deleted file mode 100644 index ac4caff241b6..000000000000 --- a/regressions/ck_hs/benchmark/serial.c +++ /dev/null @@ -1,517 +0,0 @@ -/* - * 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 <ck_hs.h> - -#include <assert.h> -#include <ck_malloc.h> -#include <errno.h> -#include <inttypes.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <time.h> - -#include "../../common.h" -#include "../../../src/ck_ht_hash.h" - -static ck_hs_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_hs_destroy(&hs); - return; -} - -static void -set_init(unsigned int size, unsigned int mode) -{ - - if (ck_hs_init(&hs, CK_HS_MODE_OBJECT | CK_HS_MODE_SPMC | mode, hs_hash, hs_compare, - &my_allocator, size, global_seed) == false) { - perror("ck_hs_init"); - exit(EXIT_FAILURE); - } - - return; -} - -static bool -set_remove(const char *value) -{ - unsigned long h; - - h = CK_HS_HASH(&hs, hs_hash, value); - return ck_hs_remove(&hs, h, value) != NULL; -} - -static bool -set_swap(const char *value) -{ - unsigned long h; - void *previous; - - h = CK_HS_HASH(&hs, hs_hash, value); - return ck_hs_fas(&hs, h, value, &previous); -} - -static bool -set_replace(const char *value) -{ - unsigned long h; - void *previous; - - h = CK_HS_HASH(&hs, hs_hash, value); - ck_hs_set(&hs, h, value, &previous); - return previous == value; -} - -static void * -set_get(const char *value) -{ - unsigned long h; - void *v; - - h = CK_HS_HASH(&hs, hs_hash, value); - v = ck_hs_get(&hs, h, value); - return v; -} - -static bool -set_insert(const char *value) -{ - unsigned long h; - - h = CK_HS_HASH(&hs, hs_hash, value); - return ck_hs_put(&hs, h, value); -} - -static bool -set_insert_unique(const char *value) -{ - unsigned long h; - - h = CK_HS_HASH(&hs, hs_hash, value); - return ck_hs_put_unique(&hs, h, value); -} - -static size_t -set_count(void) -{ - - return ck_hs_count(&hs); -} - -static bool -set_reset(void) -{ - - return ck_hs_reset(&hs); -} - -static void -set_gc(void) -{ - - ck_hs_gc(&hs, 0, 0); - return; -} - -static void -set_rebuild(void) -{ - - ck_hs_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_hs_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_hs_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_hs <dictionary> [<repetitions> <initial size>]\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_HS_MODE_DELETE); - 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; -} - |