From adae13963a67d85d39ca990b262688a729a98edc Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 13 Aug 2020 17:25:50 +0200 Subject: Move benchmarks to a separate directory --- benchmark/bench.h | 44 ++++++ benchmark/dict_bench.c | 258 +++++++++++++++++++++++++++++++ benchmark/tree_bench.c | 411 +++++++++++++++++++++++++++++++++++++++++++++++++ test/bench.h | 44 ------ test/dict_bench.c | 258 ------------------------------- test/tree_bench.c | 411 ------------------------------------------------- wscript | 8 +- 7 files changed, 717 insertions(+), 717 deletions(-) create mode 100644 benchmark/bench.h create mode 100644 benchmark/dict_bench.c create mode 100644 benchmark/tree_bench.c delete mode 100644 test/bench.h delete mode 100644 test/dict_bench.c delete mode 100644 test/tree_bench.c diff --git a/benchmark/bench.h b/benchmark/bench.h new file mode 100644 index 0000000..716601b --- /dev/null +++ b/benchmark/bench.h @@ -0,0 +1,44 @@ +/* + Copyright 2011 David Robillard + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#define _POSIX_C_SOURCE 199309L + +#include +#include + +static inline double +elapsed_s(const struct timespec* start, const struct timespec* end) +{ + return ( (double)(end->tv_sec - start->tv_sec) + + ((double)(end->tv_nsec - start->tv_nsec) * 0.000000001) ); +} + +static inline struct timespec +bench_start(void) +{ + struct timespec start_t; + clock_gettime(CLOCK_MONOTONIC, &start_t); + return start_t; +} + +static inline double +bench_end(const struct timespec* start_t) +{ + struct timespec end_t; + clock_gettime(CLOCK_MONOTONIC, &end_t); + return elapsed_s(start_t, &end_t); +} + diff --git a/benchmark/dict_bench.c b/benchmark/dict_bench.c new file mode 100644 index 0000000..e26f88a --- /dev/null +++ b/benchmark/dict_bench.c @@ -0,0 +1,258 @@ +/* + Copyright 2011-2014 David Robillard + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include "bench.h" + +#include "zix/ampatree.h" +#include "zix/chunk.h" +#include "zix/common.h" +#include "zix/hash.h" +#include "zix/patree.h" +#include "zix/trie.h" + +#include + +#include +#include +#include +#include +#include +#include + +static const unsigned seed = 1; + +ZIX_LOG_FUNC(1, 2) +static int +test_fail(const char* fmt, ...) +{ + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return 1; +} + +int +main(int argc, char** argv) +{ + if (argc != 2) { + return test_fail("Usage: %s INPUT_FILE\n", argv[0]); + } + + const char* file = argv[1]; + FILE* fd = fopen(file, "r"); + if (!fd) { + return test_fail("Failed to open file %s\n", file); + } + + size_t max_n_strings = 100000000; + + /* Read input strings */ + char** strings = NULL; + size_t* lengths = NULL; + size_t n_strings = 0; + char* buf = (char*)calloc(1, 1); + size_t buf_len = 1; + size_t this_str_len = 0; + for (int c; (c = fgetc(fd)) != EOF;) { + if (isspace(c)) { + if (this_str_len == 0) { + continue; + } + strings = (char**)realloc(strings, (n_strings + 1) * sizeof(char*)); + lengths = (size_t*)realloc(lengths, (n_strings + 1) * sizeof(size_t)); + strings[n_strings] = (char*)malloc(buf_len); + lengths[n_strings] = this_str_len; + memcpy(strings[n_strings], buf, buf_len); + this_str_len = 0; + if (++n_strings == max_n_strings) { + break; + } + } else { + ++this_str_len; + if (buf_len < this_str_len + 1) { + buf_len = this_str_len + 1; + buf = (char*)realloc(buf, buf_len); + } + buf[this_str_len - 1] = (char)c; + buf[this_str_len] = '\0'; + } + } + + fclose(fd); + + FILE* insert_dat = fopen("dict_insert.txt", "w"); + FILE* search_dat = fopen("dict_search.txt", "w"); + fprintf(insert_dat, "# n\tGHashTable\tZixHash\tZixPatree\tZixTrie\tZixAMPatree\n"); + fprintf(search_dat, "# n\tGHashTable\tZixHash\tZixPatree\tZixTrie\tZixAMPatree\n"); + + for (size_t n = n_strings / 16; n <= n_strings; n *= 2) { + printf("Benchmarking n = %zu\n", n); + ZixPatree* patree = zix_patree_new(); + ZixAMPatree* ampatree = zix_ampatree_new(); + ZixTrie* trie = zix_trie_new(); + GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal); + ZixHash* zhash = zix_hash_new((ZixHashFunc)zix_chunk_hash, + (ZixEqualFunc)zix_chunk_equal, + sizeof(ZixChunk)); + fprintf(insert_dat, "%zu", n); + fprintf(search_dat, "%zu", n); + + // Benchmark insertion + + // GHashTable + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + g_hash_table_insert(hash, strings[i], strings[i]); + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // ZixHash + insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const ZixChunk chunk = { strings[i], lengths[i] + 1 }; + ZixStatus st = zix_hash_insert(zhash, &chunk, NULL); + if (st && st != ZIX_STATUS_EXISTS) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // ZixPatree + insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + ZixStatus st = zix_patree_insert(patree, strings[i], lengths[i]); + if (st && st != ZIX_STATUS_EXISTS) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // ZixTrie + insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + ZixStatus st = zix_trie_insert(trie, strings[i], lengths[i]); + if (st && st != ZIX_STATUS_EXISTS) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // ZixAMPatree + insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + ZixStatus st = zix_ampatree_insert(ampatree, strings[i], lengths[i]); + if (st && st != ZIX_STATUS_EXISTS) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + fprintf(insert_dat, "\t%lf\n", bench_end(&insert_start)); + + // Benchmark search + + // GHashTable + srand(seed); + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + char* match = (char*)g_hash_table_lookup(hash, strings[index]); + if (strcmp(match, strings[index])) { + return test_fail("Bad match for `%s'\n", strings[index]); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // ZixHash + srand(seed); + search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + const ZixChunk key = { strings[index], lengths[index] + 1 }; + const ZixChunk* match = NULL; + if (!(match = (const ZixChunk*)zix_hash_find(zhash, &key))) { + return test_fail("Hash: Failed to find `%s'\n", strings[index]); + } + if (strcmp((const char*)match->buf, strings[index])) { + return test_fail("Hash: Bad match %p for `%s': `%s'\n", + (const void*)match, + strings[index], + (const char*)match->buf); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // ZixPatree + srand(seed); + search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + const char* match = NULL; + if (zix_patree_find(patree, strings[index], &match)) { + return test_fail("Patree: Failed to find `%s'\n", strings[index]); + } + if (strcmp(match, strings[index])) { + return test_fail("Patree: Bad match for `%s'\n", strings[index]); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // ZixTrie + srand(seed); + search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + const char* match = NULL; + if (zix_trie_find(trie, strings[index], &match)) { + return test_fail("Trie: Failed to find `%s'\n", strings[index]); + } + if (strcmp(match, strings[index])) { + return test_fail("Trie: Bad match `%s' for `%s'\n", + match, strings[index]); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // ZixAMPatree + srand(seed); + search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + const char* match = NULL; + if (zix_ampatree_find(ampatree, strings[index], &match)) { + return test_fail("AMPatree: Failed to find `%s'\n", strings[index]); + } + if (strcmp(match, strings[index])) { + return test_fail("AMPatree: Bad match `%s' for `%s'\n", + match, strings[index]); + } + } + fprintf(search_dat, "\t%lf\n", bench_end(&search_start)); + + zix_patree_free(patree); + zix_ampatree_free(ampatree); + zix_trie_free(trie); + zix_hash_free(zhash); + g_hash_table_unref(hash); + } + + fclose(insert_dat); + fclose(search_dat); + + fprintf(stderr, "Wrote dict_insert.txt dict_search.txt\n"); + + return 0; +} diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c new file mode 100644 index 0000000..f87af78 --- /dev/null +++ b/benchmark/tree_bench.c @@ -0,0 +1,411 @@ +/* + Copyright 2011-2014 David Robillard + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include "bench.h" + +#include "zix/btree.h" +#include "zix/common.h" +#include "zix/tree.h" + +#include + +#include +#include +#include +#include +#include +#include +#include + +// #define BENCH_SORTED_ARRAY 1 + +// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates +static size_t +unique_rand(size_t i) +{ + i ^= 0x5CA1AB1E; // Juggle bits to avoid linear clumps + + // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4) + static const size_t prime = 4294967291; + if (i >= prime) { + return i; // Values >= prime are mapped to themselves + } else { + const size_t residue = ((uint64_t)i * i) % prime; + return (i <= prime / 2) ? residue : prime - residue; + } +} + +static int +int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) +{ + const intptr_t ia = (intptr_t)a; + const intptr_t ib = (intptr_t)b; + // note the (ia - ib) trick here would overflow + if (ia == ib) { + return 0; + } else if (ia < ib) { + return -1; + } else { + return 1; + } +} + +static int +g_int_cmp(const void* a, const void* b, void* user_data) +{ + return int_cmp(a, b, user_data); +} + +ZIX_LOG_FUNC(1, 2) +static int +test_fail(const char* fmt, ...) +{ + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return EXIT_FAILURE; +} + +static void +start_test(const char* name) +{ + fprintf(stderr, "Benchmarking %s\n", name); +} + +static int +bench_zix_tree(size_t n_elems, + FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) +{ + start_test("ZixTree"); + + intptr_t r = 0; + ZixTreeIter* ti = NULL; + ZixTree* t = zix_tree_new(false, int_cmp, NULL, NULL); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status) { + return test_fail("Failed to insert %" PRIdPTR "\n", r); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + if (zix_tree_find(t, (void*)r, &ti)) { + return test_fail("Failed to find %" PRIdPTR "\n", r); + } + if ((intptr_t)zix_tree_get(ti) != r) { + return test_fail("Failed to get %" PRIdPTR "\n", r); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // Iterate over all elements + struct timespec iter_start = bench_start(); + for (ZixTreeIter* iter = zix_tree_begin(t); + !zix_tree_iter_is_end(iter); + iter = zix_tree_iter_next(iter)) { + zix_tree_get(iter); + } + fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); + + // Delete all elements + struct timespec del_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + ZixTreeIter* item; + if (zix_tree_find(t, (void*)r, &item)) { + return test_fail("Failed to find %" PRIdPTR " to delete\n", r); + } + if (zix_tree_remove(t, item)) { + return test_fail("Failed to remove %" PRIdPTR "\n", r); + } + } + fprintf(del_dat, "\t%lf", bench_end(&del_start)); + + zix_tree_free(t); + + return EXIT_SUCCESS; +} + +static int +bench_zix_btree(size_t n_elems, + FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) +{ + start_test("ZixBTree"); + + intptr_t r = 0; + ZixBTreeIter* ti = NULL; + ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + int status = zix_btree_insert(t, (void*)r); + if (status) { + return test_fail("Failed to insert %" PRIdPTR "\n", r); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + if (zix_btree_find(t, (void*)r, &ti)) { + return test_fail("Failed to find %" PRIdPTR "\n", r); + } + if ((intptr_t)zix_btree_get(ti) != r) { + return test_fail("Failed to get %" PRIdPTR "\n", r); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // Iterate over all elements + struct timespec iter_start = bench_start(); + ZixBTreeIter* iter = zix_btree_begin(t); + for (; + !zix_btree_iter_is_end(iter); + zix_btree_iter_increment(iter)) { + zix_btree_get(iter); + } + zix_btree_iter_free(iter); + fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); + + // Delete all elements + struct timespec del_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + void* removed; + if (zix_btree_remove(t, (void*)r, &removed, NULL)) { + return test_fail("Failed to remove %" PRIdPTR "\n", r); + } + } + fprintf(del_dat, "\t%lf", bench_end(&del_start)); + + zix_btree_free(t); + + return EXIT_SUCCESS; +} + +#ifdef BENCH_SORTED_ARRAY + +static int +int_ptr_cmp(const void* a, const void* b, void* user_data) +{ + const intptr_t ia = *(const intptr_t*)a; + const intptr_t ib = *(const intptr_t*)b; + return ia - ib; +} + +static int +bench_zix_sorted_array(size_t n_elems, + FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) +{ + start_test("ZixSortedArray"); + + intptr_t r = 0; + ZixSortedArrayIter ti = NULL; + ZixSortedArray* t = zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t)); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + int status = zix_sorted_array_insert(t, &r, &ti); + if (status) { + return test_fail("Insert failed\n"); + } + if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { + return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + *(intptr_t*)zix_sorted_array_get_data(ti), r); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + if (zix_sorted_array_find(t, &r, &ti)) { + return test_fail("Find failed\n"); + } + if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { + return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + *(intptr_t*)zix_sorted_array_get_data(ti), r); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // Iterate over all elements + struct timespec iter_start = bench_start(); + size_t i = 0; + intptr_t last = -1; + for (ZixSortedArrayIter iter = zix_sorted_array_begin(t); + !zix_sorted_array_iter_is_end(t, iter); + iter = zix_sorted_array_iter_next(t, iter), ++i) { + r = unique_rand(i); + const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter); + if (iter_data < last) { + return test_fail("Iter corrupt (%" PRIdPTR " < %zu)\n", + iter_data, last); + } + last = iter_data; + } + fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); + + // Delete all elements + struct timespec del_start = bench_start(); + for (i = 0; i < n_elems; i++) { + r = unique_rand(i); + ZixSortedArrayIter item; + if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) { + return test_fail("Failed to find item to remove\n"); + } + if (zix_sorted_array_remove(t, item)) { + return test_fail("Error removing item\n"); + } + } + fprintf(del_dat, "\t%lf", bench_end(&del_start)); + + if (zix_sorted_array_size(t) != 0) { + return test_fail("Array is not empty after removing all items\n"); + } + + zix_sorted_array_free(t); + + return EXIT_SUCCESS; + +} + +#endif // BENCH_SORTED_ARRAY + +static int +bench_glib(size_t n_elems, + FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) +{ + start_test("GSequence"); + + intptr_t r = 0; + GSequence* t = g_sequence_new(NULL); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + GSequenceIter* iter = g_sequence_insert_sorted(t, (void*)r, g_int_cmp, NULL); + if (!iter || g_sequence_iter_is_end(iter)) { + return test_fail("Failed to insert %" PRIdPTR "\n", r); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + GSequenceIter* iter = g_sequence_lookup(t, (void*)r, g_int_cmp, NULL); + if (!iter || g_sequence_iter_is_end(iter)) { + return test_fail("Failed to find %" PRIdPTR "\n", r); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // Iterate over all elements + struct timespec iter_start = bench_start(); + for (GSequenceIter* iter = g_sequence_get_begin_iter(t); + !g_sequence_iter_is_end(iter); + iter = g_sequence_iter_next(iter)) { + g_sequence_get(iter); + } + fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); + + // Delete all elements + struct timespec del_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + GSequenceIter* iter = + g_sequence_lookup(t, (void*)r, g_int_cmp, NULL); + if (!iter || g_sequence_iter_is_end(iter)) { + return test_fail("Failed to remove %" PRIdPTR "\n", r); + } + g_sequence_remove(iter); + } + fprintf(del_dat, "\t%lf", bench_end(&del_start)); + + g_sequence_free(t); + + return EXIT_SUCCESS; +} + +int +main(int argc, char** argv) +{ + if (argc != 3) { + fprintf(stderr, "USAGE: %s MIN_N MAX_N\n", argv[0]); + return 1; + } + + const size_t min_n = atol(argv[1]); + const size_t max_n = atol(argv[2]); + + fprintf(stderr, "Benchmarking %zu .. %zu elements\n", min_n, max_n); + +#define HEADER "# n\tZixTree\tZixBTree\tGSequence\n" + + FILE* insert_dat = fopen("tree_insert.txt", "w"); + FILE* search_dat = fopen("tree_search.txt", "w"); + FILE* iter_dat = fopen("tree_iterate.txt", "w"); + FILE* del_dat = fopen("tree_delete.txt", "w"); + fprintf(insert_dat, HEADER); + fprintf(search_dat, HEADER); + fprintf(iter_dat, HEADER); + fprintf(del_dat, HEADER); + for (size_t n = min_n; n <= max_n; n *= 2) { + fprintf(stderr, "n = %zu\n", n); + fprintf(insert_dat, "%zu", n); + fprintf(search_dat, "%zu", n); + fprintf(iter_dat, "%zu", n); + fprintf(del_dat, "%zu", n); + bench_zix_tree(n, insert_dat, search_dat, iter_dat, del_dat); +#ifdef BENCH_SORTED_ARRAY + bench_zix_sorted_array(n, insert_dat, search_dat, iter_dat, del_dat); +#endif + bench_zix_btree(n, insert_dat, search_dat, iter_dat, del_dat); + bench_glib(n, insert_dat, search_dat, iter_dat, del_dat); + fprintf(insert_dat, "\n"); + fprintf(search_dat, "\n"); + fprintf(iter_dat, "\n"); + fprintf(del_dat, "\n"); + } + fclose(insert_dat); + fclose(search_dat); + fclose(iter_dat); + fclose(del_dat); + + fprintf(stderr, "Wrote tree_insert.txt tree_search.txt tree_iterate.txt tree_del.txt\n"); + + return EXIT_SUCCESS; +} diff --git a/test/bench.h b/test/bench.h deleted file mode 100644 index 716601b..0000000 --- a/test/bench.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - Copyright 2011 David Robillard - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#define _POSIX_C_SOURCE 199309L - -#include -#include - -static inline double -elapsed_s(const struct timespec* start, const struct timespec* end) -{ - return ( (double)(end->tv_sec - start->tv_sec) - + ((double)(end->tv_nsec - start->tv_nsec) * 0.000000001) ); -} - -static inline struct timespec -bench_start(void) -{ - struct timespec start_t; - clock_gettime(CLOCK_MONOTONIC, &start_t); - return start_t; -} - -static inline double -bench_end(const struct timespec* start_t) -{ - struct timespec end_t; - clock_gettime(CLOCK_MONOTONIC, &end_t); - return elapsed_s(start_t, &end_t); -} - diff --git a/test/dict_bench.c b/test/dict_bench.c deleted file mode 100644 index e26f88a..0000000 --- a/test/dict_bench.c +++ /dev/null @@ -1,258 +0,0 @@ -/* - Copyright 2011-2014 David Robillard - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include "bench.h" - -#include "zix/ampatree.h" -#include "zix/chunk.h" -#include "zix/common.h" -#include "zix/hash.h" -#include "zix/patree.h" -#include "zix/trie.h" - -#include - -#include -#include -#include -#include -#include -#include - -static const unsigned seed = 1; - -ZIX_LOG_FUNC(1, 2) -static int -test_fail(const char* fmt, ...) -{ - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return 1; -} - -int -main(int argc, char** argv) -{ - if (argc != 2) { - return test_fail("Usage: %s INPUT_FILE\n", argv[0]); - } - - const char* file = argv[1]; - FILE* fd = fopen(file, "r"); - if (!fd) { - return test_fail("Failed to open file %s\n", file); - } - - size_t max_n_strings = 100000000; - - /* Read input strings */ - char** strings = NULL; - size_t* lengths = NULL; - size_t n_strings = 0; - char* buf = (char*)calloc(1, 1); - size_t buf_len = 1; - size_t this_str_len = 0; - for (int c; (c = fgetc(fd)) != EOF;) { - if (isspace(c)) { - if (this_str_len == 0) { - continue; - } - strings = (char**)realloc(strings, (n_strings + 1) * sizeof(char*)); - lengths = (size_t*)realloc(lengths, (n_strings + 1) * sizeof(size_t)); - strings[n_strings] = (char*)malloc(buf_len); - lengths[n_strings] = this_str_len; - memcpy(strings[n_strings], buf, buf_len); - this_str_len = 0; - if (++n_strings == max_n_strings) { - break; - } - } else { - ++this_str_len; - if (buf_len < this_str_len + 1) { - buf_len = this_str_len + 1; - buf = (char*)realloc(buf, buf_len); - } - buf[this_str_len - 1] = (char)c; - buf[this_str_len] = '\0'; - } - } - - fclose(fd); - - FILE* insert_dat = fopen("dict_insert.txt", "w"); - FILE* search_dat = fopen("dict_search.txt", "w"); - fprintf(insert_dat, "# n\tGHashTable\tZixHash\tZixPatree\tZixTrie\tZixAMPatree\n"); - fprintf(search_dat, "# n\tGHashTable\tZixHash\tZixPatree\tZixTrie\tZixAMPatree\n"); - - for (size_t n = n_strings / 16; n <= n_strings; n *= 2) { - printf("Benchmarking n = %zu\n", n); - ZixPatree* patree = zix_patree_new(); - ZixAMPatree* ampatree = zix_ampatree_new(); - ZixTrie* trie = zix_trie_new(); - GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal); - ZixHash* zhash = zix_hash_new((ZixHashFunc)zix_chunk_hash, - (ZixEqualFunc)zix_chunk_equal, - sizeof(ZixChunk)); - fprintf(insert_dat, "%zu", n); - fprintf(search_dat, "%zu", n); - - // Benchmark insertion - - // GHashTable - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - g_hash_table_insert(hash, strings[i], strings[i]); - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // ZixHash - insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const ZixChunk chunk = { strings[i], lengths[i] + 1 }; - ZixStatus st = zix_hash_insert(zhash, &chunk, NULL); - if (st && st != ZIX_STATUS_EXISTS) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // ZixPatree - insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - ZixStatus st = zix_patree_insert(patree, strings[i], lengths[i]); - if (st && st != ZIX_STATUS_EXISTS) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // ZixTrie - insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - ZixStatus st = zix_trie_insert(trie, strings[i], lengths[i]); - if (st && st != ZIX_STATUS_EXISTS) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // ZixAMPatree - insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - ZixStatus st = zix_ampatree_insert(ampatree, strings[i], lengths[i]); - if (st && st != ZIX_STATUS_EXISTS) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - fprintf(insert_dat, "\t%lf\n", bench_end(&insert_start)); - - // Benchmark search - - // GHashTable - srand(seed); - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - char* match = (char*)g_hash_table_lookup(hash, strings[index]); - if (strcmp(match, strings[index])) { - return test_fail("Bad match for `%s'\n", strings[index]); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // ZixHash - srand(seed); - search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - const ZixChunk key = { strings[index], lengths[index] + 1 }; - const ZixChunk* match = NULL; - if (!(match = (const ZixChunk*)zix_hash_find(zhash, &key))) { - return test_fail("Hash: Failed to find `%s'\n", strings[index]); - } - if (strcmp((const char*)match->buf, strings[index])) { - return test_fail("Hash: Bad match %p for `%s': `%s'\n", - (const void*)match, - strings[index], - (const char*)match->buf); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // ZixPatree - srand(seed); - search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - const char* match = NULL; - if (zix_patree_find(patree, strings[index], &match)) { - return test_fail("Patree: Failed to find `%s'\n", strings[index]); - } - if (strcmp(match, strings[index])) { - return test_fail("Patree: Bad match for `%s'\n", strings[index]); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // ZixTrie - srand(seed); - search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - const char* match = NULL; - if (zix_trie_find(trie, strings[index], &match)) { - return test_fail("Trie: Failed to find `%s'\n", strings[index]); - } - if (strcmp(match, strings[index])) { - return test_fail("Trie: Bad match `%s' for `%s'\n", - match, strings[index]); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // ZixAMPatree - srand(seed); - search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - const char* match = NULL; - if (zix_ampatree_find(ampatree, strings[index], &match)) { - return test_fail("AMPatree: Failed to find `%s'\n", strings[index]); - } - if (strcmp(match, strings[index])) { - return test_fail("AMPatree: Bad match `%s' for `%s'\n", - match, strings[index]); - } - } - fprintf(search_dat, "\t%lf\n", bench_end(&search_start)); - - zix_patree_free(patree); - zix_ampatree_free(ampatree); - zix_trie_free(trie); - zix_hash_free(zhash); - g_hash_table_unref(hash); - } - - fclose(insert_dat); - fclose(search_dat); - - fprintf(stderr, "Wrote dict_insert.txt dict_search.txt\n"); - - return 0; -} diff --git a/test/tree_bench.c b/test/tree_bench.c deleted file mode 100644 index f87af78..0000000 --- a/test/tree_bench.c +++ /dev/null @@ -1,411 +0,0 @@ -/* - Copyright 2011-2014 David Robillard - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include "bench.h" - -#include "zix/btree.h" -#include "zix/common.h" -#include "zix/tree.h" - -#include - -#include -#include -#include -#include -#include -#include -#include - -// #define BENCH_SORTED_ARRAY 1 - -// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates -static size_t -unique_rand(size_t i) -{ - i ^= 0x5CA1AB1E; // Juggle bits to avoid linear clumps - - // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4) - static const size_t prime = 4294967291; - if (i >= prime) { - return i; // Values >= prime are mapped to themselves - } else { - const size_t residue = ((uint64_t)i * i) % prime; - return (i <= prime / 2) ? residue : prime - residue; - } -} - -static int -int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) -{ - const intptr_t ia = (intptr_t)a; - const intptr_t ib = (intptr_t)b; - // note the (ia - ib) trick here would overflow - if (ia == ib) { - return 0; - } else if (ia < ib) { - return -1; - } else { - return 1; - } -} - -static int -g_int_cmp(const void* a, const void* b, void* user_data) -{ - return int_cmp(a, b, user_data); -} - -ZIX_LOG_FUNC(1, 2) -static int -test_fail(const char* fmt, ...) -{ - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return EXIT_FAILURE; -} - -static void -start_test(const char* name) -{ - fprintf(stderr, "Benchmarking %s\n", name); -} - -static int -bench_zix_tree(size_t n_elems, - FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) -{ - start_test("ZixTree"); - - intptr_t r = 0; - ZixTreeIter* ti = NULL; - ZixTree* t = zix_tree_new(false, int_cmp, NULL, NULL); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - int status = zix_tree_insert(t, (void*)r, &ti); - if (status) { - return test_fail("Failed to insert %" PRIdPTR "\n", r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - if (zix_tree_find(t, (void*)r, &ti)) { - return test_fail("Failed to find %" PRIdPTR "\n", r); - } - if ((intptr_t)zix_tree_get(ti) != r) { - return test_fail("Failed to get %" PRIdPTR "\n", r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - for (ZixTreeIter* iter = zix_tree_begin(t); - !zix_tree_iter_is_end(iter); - iter = zix_tree_iter_next(iter)) { - zix_tree_get(iter); - } - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - ZixTreeIter* item; - if (zix_tree_find(t, (void*)r, &item)) { - return test_fail("Failed to find %" PRIdPTR " to delete\n", r); - } - if (zix_tree_remove(t, item)) { - return test_fail("Failed to remove %" PRIdPTR "\n", r); - } - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - zix_tree_free(t); - - return EXIT_SUCCESS; -} - -static int -bench_zix_btree(size_t n_elems, - FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) -{ - start_test("ZixBTree"); - - intptr_t r = 0; - ZixBTreeIter* ti = NULL; - ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - int status = zix_btree_insert(t, (void*)r); - if (status) { - return test_fail("Failed to insert %" PRIdPTR "\n", r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - if (zix_btree_find(t, (void*)r, &ti)) { - return test_fail("Failed to find %" PRIdPTR "\n", r); - } - if ((intptr_t)zix_btree_get(ti) != r) { - return test_fail("Failed to get %" PRIdPTR "\n", r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - ZixBTreeIter* iter = zix_btree_begin(t); - for (; - !zix_btree_iter_is_end(iter); - zix_btree_iter_increment(iter)) { - zix_btree_get(iter); - } - zix_btree_iter_free(iter); - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - void* removed; - if (zix_btree_remove(t, (void*)r, &removed, NULL)) { - return test_fail("Failed to remove %" PRIdPTR "\n", r); - } - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - zix_btree_free(t); - - return EXIT_SUCCESS; -} - -#ifdef BENCH_SORTED_ARRAY - -static int -int_ptr_cmp(const void* a, const void* b, void* user_data) -{ - const intptr_t ia = *(const intptr_t*)a; - const intptr_t ib = *(const intptr_t*)b; - return ia - ib; -} - -static int -bench_zix_sorted_array(size_t n_elems, - FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) -{ - start_test("ZixSortedArray"); - - intptr_t r = 0; - ZixSortedArrayIter ti = NULL; - ZixSortedArray* t = zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t)); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - int status = zix_sorted_array_insert(t, &r, &ti); - if (status) { - return test_fail("Insert failed\n"); - } - if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { - return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", - *(intptr_t*)zix_sorted_array_get_data(ti), r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - if (zix_sorted_array_find(t, &r, &ti)) { - return test_fail("Find failed\n"); - } - if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { - return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", - *(intptr_t*)zix_sorted_array_get_data(ti), r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - size_t i = 0; - intptr_t last = -1; - for (ZixSortedArrayIter iter = zix_sorted_array_begin(t); - !zix_sorted_array_iter_is_end(t, iter); - iter = zix_sorted_array_iter_next(t, iter), ++i) { - r = unique_rand(i); - const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter); - if (iter_data < last) { - return test_fail("Iter corrupt (%" PRIdPTR " < %zu)\n", - iter_data, last); - } - last = iter_data; - } - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (i = 0; i < n_elems; i++) { - r = unique_rand(i); - ZixSortedArrayIter item; - if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) { - return test_fail("Failed to find item to remove\n"); - } - if (zix_sorted_array_remove(t, item)) { - return test_fail("Error removing item\n"); - } - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - if (zix_sorted_array_size(t) != 0) { - return test_fail("Array is not empty after removing all items\n"); - } - - zix_sorted_array_free(t); - - return EXIT_SUCCESS; - -} - -#endif // BENCH_SORTED_ARRAY - -static int -bench_glib(size_t n_elems, - FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) -{ - start_test("GSequence"); - - intptr_t r = 0; - GSequence* t = g_sequence_new(NULL); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - GSequenceIter* iter = g_sequence_insert_sorted(t, (void*)r, g_int_cmp, NULL); - if (!iter || g_sequence_iter_is_end(iter)) { - return test_fail("Failed to insert %" PRIdPTR "\n", r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - GSequenceIter* iter = g_sequence_lookup(t, (void*)r, g_int_cmp, NULL); - if (!iter || g_sequence_iter_is_end(iter)) { - return test_fail("Failed to find %" PRIdPTR "\n", r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - for (GSequenceIter* iter = g_sequence_get_begin_iter(t); - !g_sequence_iter_is_end(iter); - iter = g_sequence_iter_next(iter)) { - g_sequence_get(iter); - } - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - GSequenceIter* iter = - g_sequence_lookup(t, (void*)r, g_int_cmp, NULL); - if (!iter || g_sequence_iter_is_end(iter)) { - return test_fail("Failed to remove %" PRIdPTR "\n", r); - } - g_sequence_remove(iter); - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - g_sequence_free(t); - - return EXIT_SUCCESS; -} - -int -main(int argc, char** argv) -{ - if (argc != 3) { - fprintf(stderr, "USAGE: %s MIN_N MAX_N\n", argv[0]); - return 1; - } - - const size_t min_n = atol(argv[1]); - const size_t max_n = atol(argv[2]); - - fprintf(stderr, "Benchmarking %zu .. %zu elements\n", min_n, max_n); - -#define HEADER "# n\tZixTree\tZixBTree\tGSequence\n" - - FILE* insert_dat = fopen("tree_insert.txt", "w"); - FILE* search_dat = fopen("tree_search.txt", "w"); - FILE* iter_dat = fopen("tree_iterate.txt", "w"); - FILE* del_dat = fopen("tree_delete.txt", "w"); - fprintf(insert_dat, HEADER); - fprintf(search_dat, HEADER); - fprintf(iter_dat, HEADER); - fprintf(del_dat, HEADER); - for (size_t n = min_n; n <= max_n; n *= 2) { - fprintf(stderr, "n = %zu\n", n); - fprintf(insert_dat, "%zu", n); - fprintf(search_dat, "%zu", n); - fprintf(iter_dat, "%zu", n); - fprintf(del_dat, "%zu", n); - bench_zix_tree(n, insert_dat, search_dat, iter_dat, del_dat); -#ifdef BENCH_SORTED_ARRAY - bench_zix_sorted_array(n, insert_dat, search_dat, iter_dat, del_dat); -#endif - bench_zix_btree(n, insert_dat, search_dat, iter_dat, del_dat); - bench_glib(n, insert_dat, search_dat, iter_dat, del_dat); - fprintf(insert_dat, "\n"); - fprintf(search_dat, "\n"); - fprintf(iter_dat, "\n"); - fprintf(del_dat, "\n"); - } - fclose(insert_dat); - fclose(search_dat); - fclose(iter_dat); - fclose(del_dat); - - fprintf(stderr, "Wrote tree_insert.txt tree_search.txt tree_iterate.txt tree_del.txt\n"); - - return EXIT_SUCCESS; -} diff --git a/wscript b/wscript index 170f911..f0eb85e 100644 --- a/wscript +++ b/wscript @@ -219,12 +219,12 @@ def build(bld): # Benchmark programs for i in ['tree_bench', 'dict_bench']: bld(features = 'c cprogram', - source = 'test/%s.c' % i, + source = 'benchmark/%s.c' % i, includes = ['.'], use = 'libzix_static', uselib = 'GLIB', lib = ['rt'], - target = 'test/%s' % i, + target = 'benchmark/%s' % i, framework = framework, install_path = '') @@ -275,7 +275,7 @@ def bench(ctx): # Benchmark trees - subprocess.call(['test/tree_bench', '400000', '6400000']) + subprocess.call(['benchmark/tree_bench', '400000', '6400000']) subprocess.call(['../plot.py', 'tree_bench.svg', 'tree_insert.txt', 'tree_search.txt', @@ -298,6 +298,6 @@ def bench(ctx): out.write(word + ' ') out.close() - subprocess.call(['test/dict_bench', 'gibberish.txt']) + subprocess.call(['benchmark/dict_bench', 'gibberish.txt']) subprocess.call(['../plot.py', 'dict_bench.svg', 'dict_insert.txt', 'dict_search.txt']) -- cgit v1.2.1