diff options
Diffstat (limited to 'test/tree_bench.c')
| -rw-r--r-- | test/tree_bench.c | 411 |
1 files changed, 0 insertions, 411 deletions
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 <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; -} |