From a54b3fcd7b73411f9decc82ebf7ddb906e13052b Mon Sep 17 00:00:00 2001 From: David Robillard Date: Mon, 5 Sep 2011 04:31:38 +0000 Subject: Initial import. git-svn-id: http://svn.drobilla.net/zix/trunk@1 df6676b4-ccc9-40e5-b5d6-7c4628a128e3 --- test/tree_bench.c | 205 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ test/tree_test.c | 158 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 363 insertions(+) create mode 100644 test/tree_bench.c create mode 100644 test/tree_test.c (limited to 'test') diff --git a/test/tree_bench.c b/test/tree_bench.c new file mode 100644 index 0000000..48d5935 --- /dev/null +++ b/test/tree_bench.c @@ -0,0 +1,205 @@ +/* + 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 + +#include +#include +#include +#include +#include + +#include + +#include "zix/zix.h" + +const unsigned seed = 1; + +static int +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; +} + +static int +test_fail() +{ + fprintf(stderr, "ERROR\n"); + return EXIT_FAILURE; +} + +static inline double +elapsed_s(const struct timespec* start, const struct timespec* end) +{ + return ( (end->tv_sec - start->tv_sec) + + ((end->tv_nsec - start->tv_nsec) * 0.000000001) ); +} + +static inline struct timespec +bench_start() +{ + struct timespec start_t; + clock_gettime(CLOCK_REALTIME, &start_t); + return start_t; +} + +static inline double +bench_end(const struct timespec* start_t) +{ + struct timespec end_t; + clock_gettime(CLOCK_REALTIME, &end_t); + return elapsed_s(start_t, &end_t); +} + +static int +bench_zix(size_t n_elems, FILE* insert_dat, FILE* search_dat) +{ + intptr_t r; + ZixTreeIter ti; + + ZixTree* t = zix_tree_new(true, int_cmp, NULL); + + srand(seed); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status && status != ZIX_STATUS_EXISTS) { + return test_fail(); + } + } + 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(); + if (zix_tree_find(t, (void*)r, &ti)) { + return test_fail(); + } + if ((intptr_t)zix_tree_get_data(ti) != r) { + return test_fail(); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + srand(seed); + + // Delete all elements + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + ZixTreeIter item; + if (zix_tree_find(t, (void*)r, &item)) { + return test_fail(); + } + if (zix_tree_remove(t, item)) { + return test_fail(); + } + } + + zix_tree_free(t); + + return EXIT_SUCCESS; +} + +static int +bench_glib(size_t n_elems, FILE* insert_dat, FILE* search_dat) +{ + intptr_t r; + GSequence* t = g_sequence_new(NULL); + + srand(seed); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + g_sequence_insert_sorted(t, (void*)r, int_cmp, NULL); + } + 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(); + if (!g_sequence_search(t, (void*)r, int_cmp, NULL)) { + return test_fail(); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + +#if 0 + srand(seed); + + // Delete all elements + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + GSequenceIter item; + if (g_sequence_find(t, (void*)r, &item)) { + return test_fail(); + } + if (g_sequence_remove(t, item)) { + return test_fail(); + } + } +#endif + + 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); + + FILE* insert_dat = fopen("insert.dat", "w"); + FILE* search_dat = fopen("search.dat", "w"); + fprintf(insert_dat, "# n\tZixTree\tGSequence\n"); + fprintf(search_dat, "# n\tZixTree\tGSequence\n"); + for (size_t n = min_n; n <= max_n; n *= 2) { + fprintf(insert_dat, "%zu", n); + fprintf(search_dat, "%zu", n); + bench_zix(n, insert_dat, search_dat); + bench_glib(n, insert_dat, search_dat); + fprintf(insert_dat, "\n"); + fprintf(search_dat, "\n"); + } + fclose(insert_dat); + fclose(search_dat); + + return EXIT_SUCCESS; +} diff --git a/test/tree_test.c b/test/tree_test.c new file mode 100644 index 0000000..d4fb283 --- /dev/null +++ b/test/tree_test.c @@ -0,0 +1,158 @@ +/* + 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. +*/ + +#include +#include +#include +#include +#include + +#include + +#include "zix/zix.h" + +unsigned seed = 1; + +static int +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; +} + +static int +ith_elem(int test_num, size_t n_elems, int i) +{ + switch (test_num % 3) { + case 0: + return i; // Increasing (worst case) + case 1: + return n_elems - i; // Decreasing (worse case) + case 2: + default: + return rand() % 100; // Random + } +} + +static int +test_fail() +{ + return EXIT_FAILURE; +} + +static int +stress(int test_num, size_t n_elems) +{ + intptr_t r; + ZixTreeIter ti; + + ZixTree* t = zix_tree_new(true, int_cmp, NULL); + + srand(seed); + + // Insert n_elems elements + for (size_t i = 0; i < n_elems; i++) { + r = ith_elem(test_num, n_elems, i); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status == ZIX_STATUS_EXISTS) { + continue; + } else if (status != ZIX_STATUS_SUCCESS) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + if ((intptr_t)zix_tree_get_data(ti) != r) { + fprintf(stderr, "Data is corrupted! Saw %" PRIdPTR ", expected %zu\n", + (intptr_t)zix_tree_get_data(ti), i); + return test_fail(); + } + } + + srand(seed); + + // Search for all elements + for (size_t i = 0; i < n_elems; i++) { + r = ith_elem(test_num, n_elems, i); + if (zix_tree_find(t, (void*)r, &ti)) { + fprintf(stderr, "Find failed\n"); + return test_fail(); + } + if ((intptr_t)zix_tree_get_data(ti) != r) { + fprintf(stderr, "Data corrupted (saw %" PRIdPTR ", expected %zu\n", + (intptr_t)zix_tree_get_data(ti), i); + return test_fail(); + } + } + + srand(seed); + + // Delete all elements + for (size_t i = 0; i < n_elems; i++) { + r = ith_elem(test_num, n_elems, i); + ZixTreeIter item; + if (zix_tree_find(t, (void*)r, &item) != ZIX_STATUS_SUCCESS) { + fprintf(stderr, "Failed to find item to remove\n"); + return test_fail(); + } + if (zix_tree_remove(t, item)) { + fprintf(stderr, "Error removing item\n"); + } + } + + zix_tree_free(t); + + return EXIT_SUCCESS; +} + +int +main(int argc, char** argv) +{ + const size_t n_tests = 3; + size_t n_elems = 0; + + struct timeval time; + gettimeofday(&time, NULL); + + if (argc == 1) { + n_elems = 4096; + } else { + n_elems = atol(argv[1]); + if (argc > 2) { + seed = atol(argv[2]); + } else { + seed = time.tv_sec + time.tv_usec; + } + } + + if (n_elems == 0) { + fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); + return 1; + } + + printf("Running %zu tests with %zu elements (seed %d)", + n_tests, n_elems, seed); + + for (size_t i = 0; i < n_tests; ++i) { + printf("."); + fflush(stdout); + if (stress(i, n_elems)) { + fprintf(stderr, "FAIL: Random seed %u\n", seed); + return test_fail(); + } + } + printf("\n"); + return EXIT_SUCCESS; +} -- cgit v1.2.1