summaryrefslogtreecommitdiffstats
path: root/test
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2011-09-15 18:58:27 +0000
committerDavid Robillard <d@drobilla.net>2011-09-15 18:58:27 +0000
commita267e6c2f935fcab94e66e0f1c897a9357d5f3a9 (patch)
tree95d06ba174a8c57c06e3959f3ab7cd927e53c581 /test
parent62585c184ed99cb8acc11b025be414752d8b0240 (diff)
downloadzix-a267e6c2f935fcab94e66e0f1c897a9357d5f3a9.tar.gz
zix-a267e6c2f935fcab94e66e0f1c897a9357d5f3a9.tar.bz2
zix-a267e6c2f935fcab94e66e0f1c897a9357d5f3a9.zip
Benchmark sorted array.
git-svn-id: http://svn.drobilla.net/zix/trunk@10 df6676b4-ccc9-40e5-b5d6-7c4628a128e3
Diffstat (limited to 'test')
-rw-r--r--test/tree_bench.c110
1 files changed, 103 insertions, 7 deletions
diff --git a/test/tree_bench.c b/test/tree_bench.c
index 2c8ce97..c428eb0 100644
--- a/test/tree_bench.c
+++ b/test/tree_bench.c
@@ -40,6 +40,14 @@ int_cmp(const void* a, const void* b, void* user_data)
}
static int
+int_ptr_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(const char* fmt, ...)
{
va_list args;
@@ -74,8 +82,8 @@ bench_end(const struct timespec* start_t)
}
static int
-bench_zix(size_t n_elems,
- FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat)
+bench_zix_tree(size_t n_elems,
+ FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat)
{
intptr_t r;
ZixTreeIter ti;
@@ -143,6 +151,93 @@ bench_zix(size_t n_elems,
}
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));
+
+ 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_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));
+
+ 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_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));
+
+ srand(seed);
+
+ // 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 = rand();
+ 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));
+
+ srand(seed);
+
+ // Delete all elements
+ struct timespec del_start = bench_start();
+ for (size_t i = 0; i < n_elems; i++) {
+ r = rand();
+ 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;
+
+}
+
+static int
bench_glib(size_t n_elems,
FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat)
{
@@ -222,16 +317,17 @@ main(int argc, char** argv)
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\tGSequence\n");
- fprintf(search_dat, "# n\tZixTree\tGSequence\n");
- fprintf(iter_dat, "# n\tZixTree\tGSequence\n");
- fprintf(del_dat, "# n\tZixTree\tGSequence\n");
+ 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");
for (size_t n = min_n; n <= max_n; n *= 2) {
fprintf(insert_dat, "%zu", n);
fprintf(search_dat, "%zu", n);
fprintf(iter_dat, "%zu", n);
fprintf(del_dat, "%zu", n);
- bench_zix(n, insert_dat, search_dat, iter_dat, del_dat);
+ bench_zix_tree(n, insert_dat, search_dat, iter_dat, del_dat);
+ bench_zix_sorted_array(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");