diff options
Diffstat (limited to 'benchmark/tree_bench.c')
| -rw-r--r-- | benchmark/tree_bench.c | 411 |
1 files changed, 411 insertions, 0 deletions
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 <http://drobilla.net> + + 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 <glib.h> + +#include <inttypes.h> +#include <stdarg.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> + +// #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; +} |