From dee23c2058fd33e14610ceda277c11e4d8ce768b Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 1 Oct 2014 03:10:53 +0000 Subject: Automatic benchmarking with 'waf bench'. git-svn-id: http://svn.drobilla.net/zix/trunk@94 df6676b4-ccc9-40e5-b5d6-7c4628a128e3 --- test/dict_bench.c | 196 +++++++++++++++++++++++++++++++++++++++++++++ test/patree_bench.c | 225 ---------------------------------------------------- test/tree_bench.c | 10 +-- 3 files changed, 201 insertions(+), 230 deletions(-) create mode 100644 test/dict_bench.c delete mode 100644 test/patree_bench.c (limited to 'test') diff --git a/test/dict_bench.c b/test/dict_bench.c new file mode 100644 index 0000000..d7407d3 --- /dev/null +++ b/test/dict_bench.c @@ -0,0 +1,196 @@ +/* + Copyright 2011-2014 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 "bench.h" + +#include +#include +#include +#include +#include + +#include + +#include "zix/chunk.h" +#include "zix/hash.h" +#include "zix/patree.h" + +const unsigned seed = 1; + +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 1; +} + +int +main(int argc, char** argv) +{ + if (argc != 2) { + return test_fail("Usage: %s INPUT_FILE\n", argv[0]); + } + + const char* file = argv[1]; + FILE* fd = fopen(file, "r"); + if (!fd) { + return test_fail("Failed to open file %s\n", file); + } + + size_t max_n_strings = 100000000; + + /* Read input strings */ + char** strings = NULL; + size_t* lengths = NULL; + size_t n_strings = 0; + char* buf = calloc(1, 1); + size_t buf_len = 1; + size_t this_str_len = 0; + for (char c; (c = fgetc(fd)) != EOF;) { + if (isspace(c)) { + if (this_str_len == 0) { + continue; + } + strings = realloc(strings, (n_strings + 1) * sizeof(char*)); + lengths = realloc(lengths, (n_strings + 1) * sizeof(size_t)); + strings[n_strings] = malloc(buf_len); + lengths[n_strings] = this_str_len; + memcpy(strings[n_strings], buf, buf_len); + this_str_len = 0; + if (++n_strings == max_n_strings) { + break; + } + } else { + ++this_str_len; + if (buf_len < this_str_len + 1) { + buf_len = this_str_len + 1; + buf = realloc(buf, buf_len); + } + buf[this_str_len - 1] = c; + buf[this_str_len] = '\0'; + } + } + + fclose(fd); + + FILE* insert_dat = fopen("dict_insert.txt", "w"); + FILE* search_dat = fopen("dict_search.txt", "w"); + fprintf(insert_dat, "# n\tGHashTable\tZixHash\tZixPatree\n"); + fprintf(search_dat, "# n\tGHashTable\tZixHash\tZixPatree\n"); + + for (size_t n = n_strings / 16; n <= n_strings; n *= 2) { + printf("Benchmarking n = %zu\n", n); + ZixPatree* patree = zix_patree_new(); + GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal); + ZixHash* zhash = zix_hash_new((ZixHashFunc)zix_chunk_hash, + (ZixEqualFunc)zix_chunk_equal, + sizeof(ZixChunk)); + fprintf(insert_dat, "%zu", n); + fprintf(search_dat, "%zu", n); + + // Benchmark insertion + + // GHashTable + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + g_hash_table_insert(hash, strings[i], strings[i]); + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // ZixHash + insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const ZixChunk chunk = { strings[i], lengths[i] + 1 }; + ZixStatus st = zix_hash_insert(zhash, &chunk, NULL); + if (st && st != ZIX_STATUS_EXISTS) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // ZixPatree + insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + ZixStatus st = zix_patree_insert(patree, strings[i]); + if (st && st != ZIX_STATUS_EXISTS) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + fprintf(insert_dat, "\t%lf\n", bench_end(&insert_start)); + + // Benchmark search + + // GHashTable + srand(seed); + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + char* match = g_hash_table_lookup(hash, strings[index]); + if (strcmp(match, strings[index])) { + return test_fail("Bad match for `%s'\n", strings[index]); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // ZixHash + srand(seed); + search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + const ZixChunk key = { strings[index], lengths[index] + 1 }; + const ZixChunk* match = NULL; + if (!(match = zix_hash_find(zhash, &key))) { + return test_fail("Hash: Failed to find `%s'\n", strings[index]); + } + if (strcmp(match->buf, strings[index])) { + return test_fail("Hash: Bad match %p for `%s': `%s'\n", + (void*)match, strings[index], match->buf); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // ZixPatree + srand(seed); + search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + const char* match = NULL; + if (zix_patree_find(patree, strings[index], &match)) { + return test_fail("Patree: Failed to find `%s'\n", strings[index]); + } + if (strcmp(match, strings[index])) { + + return test_fail("Patree: Bad match for `%s'\n", strings[index]); + } + } + fprintf(search_dat, "\t%lf\n", bench_end(&search_start)); + + zix_patree_free(patree); + zix_hash_free(zhash); + g_hash_table_unref(hash); + } + + fclose(insert_dat); + fclose(search_dat); + + fprintf(stderr, "Wrote dict_insert.txt dict_search.txt\n"); + + return 0; +} diff --git a/test/patree_bench.c b/test/patree_bench.c deleted file mode 100644 index 3c13154..0000000 --- a/test/patree_bench.c +++ /dev/null @@ -1,225 +0,0 @@ -/* - 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 "bench.h" - -#include -#include -#include -#include - -#include - -#include "zix/chunk.h" -#include "zix/fat_patree.h" -#include "zix/hash.h" -#include "zix/patree.h" - -const unsigned seed = 1; - -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 1; -} - -int -main(int argc, char** argv) -{ - if (argc != 2) { - return test_fail("Usage: %s INPUT_FILE\n", argv[0]); - } - - const char* file = argv[1]; - FILE* fd = fopen(file, "r"); - if (!fd) { - return test_fail("Failed to open file %s\n", file); - } - - size_t max_n_strings = 10000000; - - /* Read input strings */ - char** strings = NULL; - size_t* lengths = NULL; - size_t n_strings = 0; - char* buf = calloc(1, 1); - size_t buf_len = 1; - size_t this_str_len = 0; - for (char c; (c = fgetc(fd)) != EOF;) { - if (c == '\n') { - if (this_str_len == 0) { - continue; - } - strings = realloc(strings, (n_strings + 1) * sizeof(char*)); - lengths = realloc(lengths, (n_strings + 1) * sizeof(size_t)); - strings[n_strings] = malloc(buf_len); - lengths[n_strings] = this_str_len; - memcpy(strings[n_strings], buf, buf_len); - this_str_len = 0; - if (++n_strings == max_n_strings) { - break; - } - } else { - ++this_str_len; - if (buf_len < this_str_len + 1) { - buf_len = this_str_len + 1; - buf = realloc(buf, buf_len); - } - buf[this_str_len - 1] = c; - buf[this_str_len] = '\0'; - } - } - - fclose(fd); - - FILE* insert_dat = fopen("insert.dat", "w"); - FILE* search_dat = fopen("search.dat", "w"); - fprintf(insert_dat, "# n\tGHashTable\tZixHash\tZixPatree\tZixFatPatree\n"); - fprintf(search_dat, "# n\tGHashTable\tZixHash\tZixPatree\tZixFatPatree\n"); - - for (size_t n = 1; n <= n_strings; n *= 2) { - printf("Benchmarking n = %zu\n", n); - ZixPatree* patree = zix_patree_new(); - ZixFatPatree* fat_patree = zix_fat_patree_new(); - GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal); - ZixHash* zhash = zix_hash_new((ZixHashFunc)zix_chunk_hash, - (ZixEqualFunc)zix_chunk_equal, - sizeof(ZixChunk)); - fprintf(insert_dat, "%zu", n); - fprintf(search_dat, "%zu", n); - - // Benchmark insertion - - // GHashTable - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - g_hash_table_insert(hash, strings[i], strings[i]); - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // ZixHash - insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const ZixChunk chunk = { strings[i], lengths[i] + 1 }; - ZixStatus st = zix_hash_insert(zhash, &chunk, NULL); - if (st && st != ZIX_STATUS_EXISTS) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // ZixPatree - insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - ZixStatus st = zix_patree_insert(patree, strings[i]); - if (st && st != ZIX_STATUS_EXISTS) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // ZixFatPatree - insert_start = bench_start(); - /* - for (size_t i = 0; i < n; ++i) { - ZixStatus st = zix_fat_patree_insert(fat_patree, strings[i]); - if (st && st != ZIX_STATUS_EXISTS) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - */ - fprintf(insert_dat, "\t%lf\n", bench_end(&insert_start)); - - // Benchmark search - - // GHashTable - srand(seed); - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - char* match = g_hash_table_lookup(hash, strings[index]); - if (strcmp(match, strings[index])) { - return test_fail("Bad match for `%s'\n", strings[index]); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // ZixHash - srand(seed); - search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - const ZixChunk key = { strings[index], lengths[index] + 1 }; - const ZixChunk* match = NULL; - if (!(match = zix_hash_find(zhash, &key))) { - return test_fail("Hash: Failed to find `%s'\n", strings[index]); - } - if (strcmp(match->buf, strings[index])) { - return test_fail("Hash: Bad match %p for `%s': `%s'\n", - (void*)match, strings[index], match->buf); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // ZixPatree - srand(seed); - search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - const char* match = NULL; - if (zix_patree_find(patree, strings[index], &match)) { - return test_fail("Patree: Failed to find `%s'\n", strings[index]); - } - if (strcmp(match, strings[index])) { - - return test_fail("Patree: Bad match for `%s'\n", strings[index]); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // ZixFatPatree - srand(seed); - search_start = bench_start(); - /* - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - char* match = NULL; - if (zix_fat_patree_find(fat_patree, strings[index], &match)) { - return test_fail("FatPatree: Failed to find `%s'\n", strings[index]); - } - if (strcmp(match, strings[index])) { - return test_fail("FatPatree: Bad match for `%s'\n", strings[index]); - } - } - */ - fprintf(search_dat, "\t%lf\n", bench_end(&search_start)); - - zix_patree_free(patree); - zix_fat_patree_free(fat_patree); - zix_hash_free(zhash); - g_hash_table_unref(hash); - } - - fclose(insert_dat); - fclose(search_dat); - - return 0; -} diff --git a/test/tree_bench.c b/test/tree_bench.c index d459268..adb395f 100644 --- a/test/tree_bench.c +++ b/test/tree_bench.c @@ -363,10 +363,10 @@ main(int argc, char** argv) #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("delete.dat", "w"); + 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); @@ -393,7 +393,7 @@ main(int argc, char** argv) fclose(iter_dat); fclose(del_dat); - fprintf(stderr, "Wrote insert.dat search.dat iterate.dat del.dat\n"); + fprintf(stderr, "Wrote tree_insert.txt tree_search.txt tree_iterate.txt tree_del.txt\n"); return EXIT_SUCCESS; } -- cgit v1.2.1