Automatic benchmarking with 'waf bench'.

git-svn-id: http://svn.drobilla.net/zix/trunk@94 df6676b4-ccc9-40e5-b5d6-7c4628a128e3

7 files changed, 81 insertions, 368 deletions

diff --git a/plot.py b/plot.py
index 4eab800..b5068b5 100755
--- a/plot.py
+++ b/plot.py
@@ -34,7 +34,8 @@ class SensibleScalarFormatter(matplotlib.ticker.ScalarFormatter):
 
         self.set_scientific(True)
 
-n_plots = len(sys.argv) - 2
+file_prefix = os.path.commonprefix(sys.argv[1:])
+n_plots     = len(sys.argv) - 2
 for i in range(n_plots):
     filename = sys.argv[i+2]
     file = open(filename, 'r')
@@ -80,7 +81,7 @@ for i in range(n_plots):
                   labelspacing=0.10, columnspacing=0,
                   framealpha=0.90)
 
-    pyplot.title(os.path.splitext(os.path.basename(filename))[0].title())
+    pyplot.title(os.path.splitext(filename[len(file_prefix):])[0].title())
 
     # out = filename.replace('.dat', '.png')
     # print('Writing %s' % out)
diff --git a/test/patree_bench.c b/test/dict_bench.c
index 3c13154..d7407d3 100644
--- a/test/patree_bench.c
+++ b/test/dict_bench.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2011 David Robillard <http://drobilla.net>
+  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
@@ -16,6 +16,7 @@
 
 #include "bench.h"
 
+#include <ctype.h>
 #include <stdarg.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -24,7 +25,6 @@
 #include <glib.h>
 
 #include "zix/chunk.h"
-#include "zix/fat_patree.h"
 #include "zix/hash.h"
 #include "zix/patree.h"
 
@@ -54,7 +54,7 @@ main(int argc, char** argv)
 		return test_fail("Failed to open file %s\n", file);
 	}
 
-	size_t max_n_strings = 10000000;
+	size_t max_n_strings = 100000000;
 
 	/* Read input strings */
 	char**  strings      = NULL;
@@ -64,7 +64,7 @@ main(int argc, char** argv)
 	size_t  buf_len      = 1;
 	size_t  this_str_len = 0;
 	for (char c; (c = fgetc(fd)) != EOF;) {
-		if (c == '\n') {
+		if (isspace(c)) {
 			if (this_str_len == 0) {
 				continue;
 			}
@@ -90,19 +90,18 @@ main(int argc, char** argv)
 
 	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");
+	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 = 1; n <= n_strings; n *= 2) {
+	for (size_t n = n_strings / 16; 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));
+		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);
 
@@ -134,18 +133,6 @@ main(int argc, char** argv)
 				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
@@ -193,27 +180,9 @@ main(int argc, char** argv)
 				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);
 	}
@@ -221,5 +190,7 @@ main(int argc, char** argv)
 	fclose(insert_dat);
 	fclose(search_dat);
 
+	fprintf(stderr, "Wrote dict_insert.txt dict_search.txt\n");
+
 	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;
 }
diff --git a/wscript b/wscript
index f3e350d..75c885c 100644
--- a/wscript
+++ b/wscript
@@ -34,6 +34,8 @@ def options(opt):
                    help='Build unit tests')
     opt.add_option('--bench', action='store_true', dest='build_bench',
                    help='Build benchmarks')
+    opt.add_option('--static', action='store_true', dest='static',
+                   help='Build static library')
 
 def configure(conf):
     conf.load('compiler_c')
@@ -41,8 +43,9 @@ def configure(conf):
     autowaf.set_c99_mode(conf)
     autowaf.display_header('Zix Configuration')
 
-    conf.env.BUILD_BENCH = Options.options.build_bench
-    conf.env.BUILD_TESTS = Options.options.build_tests
+    conf.env.BUILD_BENCH  = Options.options.build_bench
+    conf.env.BUILD_TESTS  = Options.options.build_tests
+    conf.env.BUILD_STATIC = Options.options.static
 
     # Check for mlock
     conf.check(function_name='mlock',
@@ -100,7 +103,6 @@ def build(bld):
     lib_source = '''
         zix/chunk.c
         zix/digest.c
-        zix/fat_patree.c
         zix/hash.c
         zix/patree.c
         zix/ring.c
@@ -123,6 +125,19 @@ def build(bld):
               cflags          = libflags + ['-DZIX_SHARED',
                                             '-DZIX_INTERNAL'])
 
+    if bld.env.BUILD_STATIC or bld.env.BUILD_BENCH:
+        obj = bld(features        = 'c cstlib',
+                  export_includes = ['.'],
+                  source          = lib_source,
+                  includes        = ['.'],
+                  name            = 'libzix_static',
+                  target          = 'zix',
+                  vnum            = ZIX_LIB_VERSION,
+                  install_path    = None,
+                  framework       = framework,
+                  cflags          = libflags + ['-DZIX_SHARED',
+                                                '-DZIX_INTERNAL'])
+
     if bld.env.BUILD_TESTS:
         test_libs   = ['pthread', 'dl']
         test_cflags = []
@@ -132,7 +147,7 @@ def build(bld):
             test_libs   += ['gcov']
             test_cflags += ['-fprofile-arcs', '-ftest-coverage']
 
-        # Static library (for unit test code coverage)
+        # Profiled static library (for unit test code coverage)
         obj = bld(features     = 'c cstlib',
                   source       = lib_source,
                   includes     = ['.'],
@@ -157,11 +172,11 @@ def build(bld):
 
     if bld.env.BUILD_BENCH:
         # Benchmark programs
-        for i in ['tree_bench', 'patree_bench']:
+        for i in ['tree_bench', 'dict_bench']:
             obj = bld(features     = 'c cprogram',
                       source       = 'test/%s.c' % i,
                       includes     = ['.'],
-                      use          = 'libzix',
+                      use          = 'libzix_static',
                       uselib       = 'GLIB',
                       lib          = ['rt'],
                       target       = 'test/%s' % i,
@@ -196,3 +211,35 @@ def test(ctx):
     os.environ['PATH'] = 'test' + os.pathsep + os.getenv('PATH')
     autowaf.run_tests(ctx, APPNAME, tests, dirs=['.', './test'])
     autowaf.post_test(ctx, APPNAME, dirs=['.', './test'])
+
+def bench(ctx):
+    os.chdir('build')
+
+    # Benchmark trees
+
+    subprocess.call(['test/tree_bench', '400000', '6400000'])
+    subprocess.call(['../plot.py', 'tree_bench.svg',
+                     'tree_insert.txt',
+                     'tree_search.txt',
+                     'tree_iterate.txt',
+                     'tree_delete.txt'])
+
+    # Benchmark dictionaries
+
+    filename = 'gibberish.txt'
+    if not os.path.exists(filename):
+        Logs.info('Generating random text %s' % filename)
+        import random
+        out = open(filename, 'w')
+        for i in xrange(1 << 20):
+            wordlen = random.randrange(1, 128)
+            for j in xrange(wordlen):
+                out.write(chr(random.randrange(ord('A'), ord('Z'))))
+            out.write(' ')
+        out.close()
+
+    subprocess.call(['test/dict_bench', 'gibberish.txt'])
+    subprocess.call(['../plot.py', 'dict_bench.svg',
+                     'dict_insert.txt', 'dict_search.txt'])
+    
+                
diff --git a/zix/btree.h b/zix/btree.h
index 3acd3a4..2de5565 100644
--- a/zix/btree.h
+++ b/zix/btree.h
@@ -80,6 +80,10 @@ zix_btree_insert(ZixBTree* t, void* e);
 /**
    Remove the value `e` from `t`.
 
+   @param t Tree to remove from.
+
+   @param e Value to remove.
+
    @param out Set to point to the removed pointer (which may not equal `e`).
 
    @param next If non-NULL, pointed to the value following `e`.  If *next is
diff --git a/zix/fat_patree.c b/zix/fat_patree.c
deleted file mode 100644
index 454cfba..0000000
--- a/zix/fat_patree.c
+++ /dev/null
@@ -1,239 +0,0 @@
-/*
-  Copyright 2011 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.
-*/
-
-#define _XOPEN_SOURCE 500
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/fat_patree.h"
-
-#define N_CHILDREN 256
-
-typedef uint_fast8_t n_edges_t;
-
-typedef struct _ZixFatPatreeNode {
-	char*                     label_first;           /* Start of incoming label */
-	char*                     label_last;            /* End of incoming label */
-	char*                     str;                   /* String stored at this node */
-	struct _ZixFatPatreeNode* children[N_CHILDREN];  /* Children of this node */
-} ZixFatPatreeNode;
-
-struct _ZixFatPatree {
-	ZixFatPatreeNode* root;  /* Root of the tree */
-};
-
-ZIX_API
-ZixFatPatree*
-zix_fat_patree_new(void)
-{
-	ZixFatPatree* t = (ZixFatPatree*)malloc(sizeof(ZixFatPatree));
-	memset(t, '\0', sizeof(struct _ZixFatPatree));
-
-	t->root = (ZixFatPatreeNode*)malloc(sizeof(ZixFatPatreeNode));
-	memset(t->root, '\0', sizeof(ZixFatPatreeNode));
-
-	return t;
-}
-
-static void
-zix_fat_patree_free_rec(ZixFatPatreeNode* n)
-{
-	if (n) {
-		for (int i = 0; i < N_CHILDREN; ++i) {
-			zix_fat_patree_free_rec(n->children[i]);
-		}
-	}
-}
-
-ZIX_API
-void
-zix_fat_patree_free(ZixFatPatree* t)
-{
-	zix_fat_patree_free_rec(t->root);
-	free(t->root);
-	free(t);
-}
-
-static inline bool
-patree_find_edge(ZixFatPatreeNode* n, uint8_t c, n_edges_t* index)
-{
-	if (n->children[c]) {
-		*index = c;
-		return true;
-	}
-	return false;
-}
-
-static void
-patree_add_edge(ZixFatPatreeNode* n,
-                char*             str,
-                char*             first,
-                char*             last)
-{
-	assert(last >= first);
-	const int index = (uint8_t)first[0];
-	assert(!n->children[index]);
-
-	ZixFatPatreeNode* new_node = (ZixFatPatreeNode*)malloc(
-		sizeof(ZixFatPatreeNode));
-	n->children[index] = new_node;
-	n->children[index]->label_first = first;
-	n->children[index]->label_last  = last;
-	n->children[index]->str         = str;
-	for (int i = 0; i < N_CHILDREN; ++i) {
-		n->children[index]->children[i] = NULL;
-	}
-}
-
-/* Split an outgoing edge (to a child) at the given index */
-static void
-patree_split_edge(ZixFatPatreeNode* child,
-                  size_t         index)
-{
-	char* const first = child->label_first + index;
-	char* const last  = child->label_last;
-	assert(last >= first);
-
-	ZixFatPatreeNode* new_node = (ZixFatPatreeNode*)malloc(
-		sizeof(ZixFatPatreeNode));
-	new_node->label_first  = first;
-	new_node->label_last   = last;
-	new_node->str          = child->str;
-	memcpy(new_node->children, child->children,
-	       sizeof(ZixFatPatreeNode*) * N_CHILDREN);
-
-	child->label_last = child->label_first + (index - 1);  // chop end
-	child->str = NULL;
-
-	for (int i = 0; i < N_CHILDREN; ++i) {
-		child->children[i] = NULL;
-	}
-	const int new_node_index = (int)first[0];
-	assert(new_node_index < N_CHILDREN);
-	assert(!child->children[new_node_index]);
-	child->children[new_node_index] = new_node;
-}
-
-static ZixStatus
-patree_insert_internal(ZixFatPatreeNode* n, char* str, char* first, char* last)
-{
-	n_edges_t child_i;
-	assert(first <= last);
-
-	if (patree_find_edge(n, *first, &child_i)) {
-		ZixFatPatreeNode* child       = n->children[child_i];
-		char* const    label_first = child->label_first;
-		char* const    label_last  = child->label_last;
-		size_t         split_i     = 0;
-		const size_t   label_len   = label_last - label_first + 1;
-		const size_t   s_len       = last - first + 1;
-		const size_t   max_len     = (s_len < label_len) ? s_len : label_len;
-
-		while (split_i < max_len && first[split_i] == label_first[split_i]) {
-			++split_i;
-		}
-		child = n->children[child_i];
-
-		if (label_len < s_len) {
-			if (split_i == label_len) {
-				return patree_insert_internal(child, str, first + label_len, last);
-			} else {
-				patree_split_edge(child, split_i);
-				return patree_insert_internal(child, str, first + split_i, last);
-			}
-		} else if (label_len != split_i) {
-			patree_split_edge(child, split_i);
-			if (split_i != s_len) {
-				patree_add_edge(child, str, first + split_i, last);
-			} else {
-				assert(!child->str);
-				child->str = str;
-			}
-			return ZIX_STATUS_SUCCESS;
-		} else if (label_len == s_len && !child->str) {
-			child->str = str;
-		} else {
-			return ZIX_STATUS_EXISTS;
-		}
-
-	} else {
-		patree_add_edge(n, str, first, last);
-	}
-
-	return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_fat_patree_insert(ZixFatPatree* t, const char* str)
-{
-	const size_t len = strlen(str);
-	// FIXME: awful casts
-	return patree_insert_internal(t->root, (char*)str, (char*)str, (char*)str + len - 1);
-}
-
-ZIX_API
-ZixStatus
-zix_fat_patree_find(ZixFatPatree* t, const char* p, char** match)
-{
-	ZixFatPatreeNode* n = t->root;
-	n_edges_t         child_i;
-
-	*match = NULL;
-
-	while (*p != '\0') {
-		if (patree_find_edge(n, p[0], &child_i)) {
-			ZixFatPatreeNode* const child       = n->children[child_i];
-			const char* const    label_first = child->label_first;
-			const char* const    label_last  = child->label_last;
-
-			/* Prefix compare search string and label */
-			const char* l = label_first;
-			while (*p != '\0' && l <= label_last) {
-				if (*l++ != *p++) {
-					return ZIX_STATUS_NOT_FOUND;
-				}
-			}
-
-			if (!*p) {
-				/* Reached end of search string */
-				if (l == label_last + 1) {
-					/* Reached end of label string as well, match */
-					*match = child->str;
-					return *match ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
-				} else {
-					/* Label string is longer, no match (prefix match) */
-					return ZIX_STATUS_NOT_FOUND;
-				}
-			} else {
-				/* Match at this node, continue search downwards.
-				   Possibly we have prematurely hit a leaf, so the next
-				   edge search will fail.
-				*/
-				n  = child;
-			}
-		} else {
-			return ZIX_STATUS_NOT_FOUND;
-		}
-	}
-
-	return ZIX_STATUS_NOT_FOUND;
-}
diff --git a/zix/fat_patree.h b/zix/fat_patree.h
deleted file mode 100644
index 2fb1b4d..0000000
--- a/zix/fat_patree.h
+++ /dev/null
@@ -1,71 +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.
-*/
-
-#ifndef ZIX_FAT_PATREE_H
-#define ZIX_FAT_PATREE_H
-
-#include "zix/common.h"
-
-/**
-   @addtogroup zix
-   @{
-   @name FatPatree
-   @{
-*/
-
-typedef struct _ZixFatPatree ZixFatPatree;
-
-/**
-   Construct a new Patree.
-*/
-ZIX_API
-ZixFatPatree*
-zix_fat_patree_new(void);
-
-/**
-   Destroy `t`.
-*/
-ZIX_API
-void
-zix_fat_patree_free(ZixFatPatree* t);
-
-/**
-   Print a DOT description of `t` to `fd`.
-*/
-ZIX_API
-void
-zix_fat_patree_print_dot(const ZixFatPatree* t, FILE* fd);
-
-/**
-   Insert `str` into `t`.
-*/
-ZIX_API
-ZixStatus
-zix_fat_patree_insert(ZixFatPatree* t, const char* str);
-
-/**
-   Search for `str` in `t`.
-*/
-ZIX_API
-ZixStatus
-zix_fat_patree_find(ZixFatPatree* t, const char* str, char** match);
-
-/**
-   @}
-   @}
-*/
-
-#endif  /* ZIX_FAT_PATREE_H */