From b5896fff67d150e6ba96cea7d3679f9958b787ea Mon Sep 17 00:00:00 2001 From: David Robillard Date: Mon, 22 Sep 2014 07:36:26 +0000 Subject: Add ZixBTree. git-svn-id: http://svn.drobilla.net/zix/trunk@84 df6676b4-ccc9-40e5-b5d6-7c4628a128e3 --- test/bench.h | 6 +- test/tree_bench.c | 200 ++++++++++++++++++++++++++++++++++++++---------------- test/tree_test.c | 10 +-- 3 files changed, 149 insertions(+), 67 deletions(-) (limited to 'test') diff --git a/test/bench.h b/test/bench.h index 4227e2d..93d4002 100644 --- a/test/bench.h +++ b/test/bench.h @@ -27,10 +27,10 @@ elapsed_s(const struct timespec* start, const struct timespec* end) } static inline struct timespec -bench_start() +bench_start(void) { struct timespec start_t; - clock_gettime(CLOCK_REALTIME, &start_t); + clock_gettime(CLOCK_MONOTONIC, &start_t); return start_t; } @@ -38,7 +38,7 @@ static inline double bench_end(const struct timespec* start_t) { struct timespec end_t; - clock_gettime(CLOCK_REALTIME, &end_t); + clock_gettime(CLOCK_MONOTONIC, &end_t); return elapsed_s(start_t, &end_t); } diff --git a/test/tree_bench.c b/test/tree_bench.c index ff6bd5e..f4bcb0b 100644 --- a/test/tree_bench.c +++ b/test/tree_bench.c @@ -17,31 +17,46 @@ #include "bench.h" #include +#include #include #include #include -#include #include #include "zix/zix.h" -const unsigned seed = 1; +// #define BENCH_SORTED_ARRAY 1 -static int -int_cmp(const void* a, const void* b, void* user_data) +// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates +static uint32_t +unique_rand(uint32_t i) { - const intptr_t ia = (intptr_t)a; - const intptr_t ib = (intptr_t)b; - return ia - ib; + i ^= 0x5CA1AB1E; // Juggle bits to avoid linear clumps + + // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4) + static const uint32_t prime = 4294967291; + if (i >= prime) { + return i; // Values >= prime are mapped to themselves + } else { + const uint32_t residue = ((uint64_t)i * i) % prime; + return (i <= prime / 2) ? residue : prime - residue; + } } static int -int_ptr_cmp(const void* a, const void* b, void* user_data) +int_cmp(const void* a, const void* b, void* user_data) { - const intptr_t ia = *(intptr_t*)a; - const intptr_t ib = *(intptr_t*)b; - return ia - ib; + 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 @@ -55,21 +70,26 @@ test_fail(const char* fmt, ...) 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) { - intptr_t r; - ZixTreeIter* ti; - - ZixTree* t = zix_tree_new(true, int_cmp, NULL, NULL); + start_test("ZixTree"); - srand(seed); + 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 = rand(); + r = unique_rand(i); int status = zix_tree_insert(t, (void*)r, &ti); if (status) { return test_fail("Failed to insert %zu\n", r); @@ -77,12 +97,10 @@ bench_zix_tree(size_t n_elems, } fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - srand(seed); - // Search for all elements struct timespec search_start = bench_start(); for (size_t i = 0; i < n_elems; i++) { - r = rand(); + r = unique_rand(i); if (zix_tree_find(t, (void*)r, &ti)) { return test_fail("Failed to find %zu\n", r); } @@ -92,8 +110,6 @@ bench_zix_tree(size_t n_elems, } fprintf(search_dat, "\t%lf", bench_end(&search_start)); - srand(seed); - // Iterate over all elements struct timespec iter_start = bench_start(); for (ZixTreeIter* iter = zix_tree_begin(t); @@ -103,14 +119,11 @@ bench_zix_tree(size_t n_elems, } fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - srand(seed); - // Delete all elements struct timespec del_start = bench_start(); for (size_t i = 0; i < n_elems; i++) { - r = rand(); - ZixTreeIter* - item; + r = unique_rand(i); + ZixTreeIter* item; if (zix_tree_find(t, (void*)r, &item)) { return test_fail("Failed to find %zu to delete\n", r); } @@ -125,21 +138,90 @@ bench_zix_tree(size_t n_elems, 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 %zu\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 %zu\n", r); + } + if ((intptr_t)zix_btree_get(ti) != r) { + return test_fail("Failed to get %zu\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); + if (zix_btree_remove(t, (void*)r)) { + return test_fail("Failed to remove %zu\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) { - intptr_t r; - ZixSortedArrayIter ti; - - ZixSortedArray* t = zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t)); + start_test("ZixSortedArray"); - srand(seed); + 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 = rand(); + r = unique_rand(i); int status = zix_sorted_array_insert(t, &r, &ti); if (status) { return test_fail("Insert failed\n"); @@ -151,12 +233,10 @@ bench_zix_sorted_array(size_t n_elems, } fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - srand(seed); - // Search for all elements struct timespec search_start = bench_start(); for (size_t i = 0; i < n_elems; ++i) { - r = rand(); + r = unique_rand(i); if (zix_sorted_array_find(t, &r, &ti)) { return test_fail("Find failed\n"); } @@ -167,8 +247,6 @@ bench_zix_sorted_array(size_t n_elems, } fprintf(search_dat, "\t%lf", bench_end(&search_start)); - srand(seed); - // Iterate over all elements struct timespec iter_start = bench_start(); size_t i = 0; @@ -176,7 +254,7 @@ bench_zix_sorted_array(size_t n_elems, 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 = rand(); + 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", @@ -186,12 +264,10 @@ bench_zix_sorted_array(size_t n_elems, } fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - srand(seed); - // Delete all elements struct timespec del_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = rand(); + 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"); @@ -212,19 +288,21 @@ bench_zix_sorted_array(size_t n_elems, } +#endif // BENCH_SORTED_ARRAY + static int bench_glib(size_t n_elems, FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) { - intptr_t r; - GSequence* t = g_sequence_new(NULL); + start_test("GSequence"); - srand(seed); + 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 = rand(); + r = unique_rand(i); GSequenceIter* iter = g_sequence_insert_sorted(t, (void*)r, int_cmp, NULL); if (!iter || g_sequence_iter_is_end(iter)) { return test_fail("Failed to insert %zu\n", r); @@ -232,12 +310,10 @@ bench_glib(size_t n_elems, } fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - srand(seed); - // Search for all elements struct timespec search_start = bench_start(); for (size_t i = 0; i < n_elems; ++i) { - r = rand(); + r = unique_rand(i); GSequenceIter* iter = g_sequence_lookup(t, (void*)r, int_cmp, NULL); if (!iter || g_sequence_iter_is_end(iter)) { return test_fail("Failed to find %zu\n", r); @@ -245,8 +321,6 @@ bench_glib(size_t n_elems, } fprintf(search_dat, "\t%lf", bench_end(&search_start)); - srand(seed); - // Iterate over all elements struct timespec iter_start = bench_start(); for (GSequenceIter* iter = g_sequence_get_begin_iter(t); @@ -256,12 +330,10 @@ bench_glib(size_t n_elems, } fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - srand(seed); - // Delete all elements struct timespec del_start = bench_start(); for (size_t i = 0; i < n_elems; ++i) { - r = rand(); + r = unique_rand(i); GSequenceIter* iter = g_sequence_lookup(t, (void*)r, int_cmp, NULL); if (!iter || g_sequence_iter_is_end(iter)) { return test_fail("Failed to remove %zu\n", r); @@ -288,21 +360,27 @@ main(int argc, char** argv) fprintf(stderr, "Benchmarking %zu .. %zu elements\n", min_n, max_n); +#define HEADER "# n\tZixTree\tZixBTree\tGSequence\n" + FILE* insert_dat = fopen("insert.dat", "w"); FILE* search_dat = fopen("search.dat", "w"); FILE* iter_dat = fopen("iterate.dat", "w"); - FILE* del_dat = fopen("del.dat", "w"); - fprintf(insert_dat, "# n\tZixTree\tZixSortedArray\tGSequence\n"); - fprintf(search_dat, "# n\tZixTree\tZixSortedArray\tGSequence\n"); - fprintf(iter_dat, "# n\tZixTree\tZixSortedArray\tGSequence\n"); - fprintf(del_dat, "# n\tZixTree\tZixSortedArray\tGSequence\n"); + FILE* del_dat = fopen("delete.dat", "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"); @@ -314,5 +392,7 @@ main(int argc, char** argv) fclose(iter_dat); fclose(del_dat); + fprintf(stderr, "Wrote insert.dat search.dat iterate.dat del.dat\n"); + return EXIT_SUCCESS; } diff --git a/test/tree_test.c b/test/tree_test.c index 5eb5a11..b806acd 100644 --- a/test/tree_test.c +++ b/test/tree_test.c @@ -108,12 +108,11 @@ stress(int test_num, size_t n_elems) srand(seed); // Iterate over all elements - size_t i = 0; + size_t i = 0; intptr_t last = -1; for (ZixTreeIter* iter = zix_tree_begin(t); !zix_tree_iter_is_end(iter); iter = zix_tree_iter_next(iter), ++i) { - r = ith_elem(test_num, n_elems, i); const intptr_t iter_data = (intptr_t)zix_tree_get(iter); if (iter_data < last) { fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", @@ -122,6 +121,10 @@ stress(int test_num, size_t n_elems) } last = iter_data; } + if (i != n_elems) { + fprintf(stderr, "Iteration stopped at %zu/%zu elements\n", i, n_elems); + return test_fail(); + } srand(seed); @@ -131,7 +134,6 @@ stress(int test_num, size_t n_elems) for (ZixTreeIter* iter = zix_tree_rbegin(t); !zix_tree_iter_is_rend(iter); iter = zix_tree_iter_prev(iter), ++i) { - r = ith_elem(test_num, n_elems, i); const intptr_t iter_data = (intptr_t)zix_tree_get(iter); if (iter_data > last) { fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", @@ -197,7 +199,7 @@ main(int argc, char** argv) unsigned n_elems = 0; if (argc == 1) { - n_elems = 4096; + n_elems = 100000; } else { n_elems = atol(argv[1]); if (argc > 2) { -- cgit v1.2.1