Group tests and benchmarks with the corresponding source code.

5 files changed, 521 insertions, 0 deletions

diff --git a/libdimension/bench/Makefile.am b/libdimension/bench/Makefile.am
new file mode 100644
index 0000000..353acb3
--- /dev/null
+++ b/libdimension/bench/Makefile.am
@@ -0,0 +1,41 @@
+###########################################################################
+## Copyright (C) 2009-2010 Tavian Barnes <tavianator@tavianator.com>     ##
+##                                                                       ##
+## This file is part of The Dimension Build Suite.                       ##
+##                                                                       ##
+## The Dimension Build Suite is free software; you can redistribute it   ##
+## and/or modify it under the terms of the GNU General Public License as ##
+## published by the Free Software Foundation; either version 3 of the    ##
+## License, or (at your option) any later version.                       ##
+##                                                                       ##
+## The Dimension Build Suite is distributed in the hope that it will be  ##
+## useful, but WITHOUT ANY WARRANTY; without even the implied warranty   ##
+## of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  ##
+## General Public License for more details.                              ##
+##                                                                       ##
+## You should have received a copy of the GNU General Public License     ##
+## along with this program.  If not, see <http://www.gnu.org/licenses/>. ##
+###########################################################################
+
+INCLUDES = -I$(top_srcdir)/libdimension
+
+EXTRA_PROGRAMS = bench-array                                                   \
+                 bench-geometry                                                \
+                 bench-polynomial                                              \
+                 bench-prtree
+
+AM_CFLAGS  = $(libsandglass_CFLAGS) -fno-inline
+AM_LDFLAGS = $(libsandglass_LIBS) $(top_builddir)/libdimension/libdimension.la
+
+bench_array_SOURCES = array.c
+bench_geometry_SOURCES = geometry.c
+bench_polynomial_SOURCES = polynomial.c
+bench_prtree_SOURCES = prtree.c
+
+bench: $(EXTRA_PROGRAMS)
+	./bench-array
+	./bench-geometry
+	./bench-polynomial
+	./bench-prtree
+
+.PHONY: bench
diff --git a/libdimension/bench/array.c b/libdimension/bench/array.c
new file mode 100644
index 0000000..3fe0c83
--- /dev/null
+++ b/libdimension/bench/array.c
@@ -0,0 +1,118 @@
+/*************************************************************************
+ * Copyright (C) 2009-2010 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Benchmark Suite.                   *
+ *                                                                       *
+ * The Dimension Benchmark Suite is free software; you can redistribute  *
+ * it and/or modify it under the terms of the GNU General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Benchmark Suite is distributed in the hope that it will *
+ * be useful, but WITHOUT ANY WARRANTY; without even the implied         *
+ * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See *
+ * the GNU General Public License for more details.                      *
+ *                                                                       *
+ * You should have received a copy of the GNU General Public License     *
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+#include "dimension.h"
+#include <sandglass.h>
+#include <stdlib.h>
+#include <stdint.h>
+
+int
+main(void)
+{
+  const unsigned int count = 32;
+  uint32_t object = 1;
+
+  sandglass_t sandglass;
+  if (sandglass_init_monotonic(&sandglass, SANDGLASS_CPUTIME) != 0) {
+    perror("sandglass_create()");
+    return EXIT_FAILURE;
+  }
+
+  /* Benchmark allocation and deallocation */
+  dmnsn_array *array;
+  sandglass_bench_fine(&sandglass, {
+    array = dmnsn_new_array(sizeof(object));
+    dmnsn_delete_array(array);
+  });
+  printf("dmnsn_new_array() + dmnsn_delete_array(): %ld\n", sandglass.grains);
+
+  /* Create our test array */
+  array = dmnsn_new_array(sizeof(object));
+
+  /* dmnsn_array_push() */
+
+  printf("dmnsn_array_push():");
+
+  for (unsigned int i = 0; i < count; ++i) {
+    sandglass_bench_noprecache(&sandglass, dmnsn_array_push(array, &object));
+    printf(" %ld", sandglass.grains);
+  }
+  printf("\n");
+
+  /* dmnsn_array_get() */
+  sandglass_bench_fine(&sandglass, dmnsn_array_get(array, count/2, &object));
+  printf("dmnsn_array_get(): %ld\n", sandglass.grains);
+
+  /* dmnsn_array_set() */
+  sandglass_bench_fine(&sandglass, dmnsn_array_set(array, count/2, &object));
+  printf("dmnsn_array_set(): %ld\n", sandglass.grains);
+
+  /* dmnsn_array_at() */
+  void *ptr;
+  sandglass_bench_fine(&sandglass, ptr = dmnsn_array_at(array, count/2));
+  printf("dmnsn_array_at() = %p: %ld\n", ptr, sandglass.grains);
+
+  /* dmnsn_array_size() */
+  size_t size;
+  sandglass_bench_fine(&sandglass, size = dmnsn_array_size(array));
+  printf("dmnsn_array_size() = %zu: %ld\n", size, sandglass.grains);
+
+  /* dmnsn_array_resize() */
+  dmnsn_array_resize(array, count);
+  sandglass_bench_noprecache(&sandglass, dmnsn_array_resize(array, count * 2));
+  printf("dmnsn_array_resize(): %ld", sandglass.grains);
+
+  sandglass_bench_noprecache(&sandglass, dmnsn_array_resize(array, count));
+  printf(" %ld\n", sandglass.grains);
+
+  /* dmnsn_array_insert() */
+
+  printf("dmnsn_array_insert():");
+
+  for (size_t i = 0; i < count; ++i) {
+    sandglass_bench_noprecache(&sandglass,
+                               dmnsn_array_insert(array, count/2, &object));
+    printf(" %ld", sandglass.grains);
+  }
+  printf("\n");
+
+  /* dmnsn_array_remove() */
+
+  printf("dmnsn_array_remove():");
+
+  for (size_t i = 0; i < count; ++i) {
+    sandglass_bench_noprecache(&sandglass,
+                               dmnsn_array_remove(array, count/2));
+    printf(" %ld", sandglass.grains);
+  }
+  printf("\n");
+
+  /* dmnsn_array_pop() */
+
+  printf("dmnsn_array_pop():");
+
+  for (size_t i = 0; i < count; ++i) {
+    sandglass_bench_noprecache(&sandglass, dmnsn_array_pop(array, &object));
+    printf(" %ld", sandglass.grains);
+  }
+  printf("\n");
+
+  dmnsn_delete_array(array);
+  return EXIT_SUCCESS;
+}
diff --git a/libdimension/bench/geometry.c b/libdimension/bench/geometry.c
new file mode 100644
index 0000000..4b77c9b
--- /dev/null
+++ b/libdimension/bench/geometry.c
@@ -0,0 +1,171 @@
+/*************************************************************************
+ * Copyright (C) 2009-2010 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Benchmark Suite.                   *
+ *                                                                       *
+ * The Dimension Benchmark Suite is free software; you can redistribute  *
+ * it and/or modify it under the terms of the GNU General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Benchmark Suite is distributed in the hope that it will *
+ * be useful, but WITHOUT ANY WARRANTY; without even the implied         *
+ * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See *
+ * the GNU General Public License for more details.                      *
+ *                                                                       *
+ * You should have received a copy of the GNU General Public License     *
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+#include "dimension.h"
+#include <sandglass.h>
+#include <stdlib.h>
+
+int
+main(void)
+{
+  dmnsn_vector vector, vector2;
+  dmnsn_matrix matrix, matrix2;
+  dmnsn_line line;
+  double result;
+
+  sandglass_t sandglass;
+  if (sandglass_init_monotonic(&sandglass, SANDGLASS_CPUTIME) != 0) {
+    perror("sandglass_create()");
+    return EXIT_FAILURE;
+  }
+
+  /* dmnsn_new_vector() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_new_vector(1.0, 2.0, 3.0);
+  });
+  printf("dmnsn_new_vector(): %ld\n", sandglass.grains);
+
+  /* dmnsn_matrix_construct() */
+  sandglass_bench_fine(&sandglass, {
+    matrix = dmnsn_new_matrix(1.0, 1.0, 0.0, 0.0,
+                              1.0, 1.0, 1.0, 0.0,
+                              0.0, 1.0, 1.0, 0.0);
+  });
+  printf("dmnsn_new_matrix(): %ld\n", sandglass.grains);
+
+  /* dmnsn_identity_matrix() */
+  sandglass_bench_fine(&sandglass, {
+    matrix = dmnsn_identity_matrix();
+  });
+  printf("dmnsn_identity_matrix(): %ld\n", sandglass.grains);
+
+  /* dmnsn_scale_matrix() */
+  sandglass_bench_fine(&sandglass, {
+    matrix = dmnsn_scale_matrix(vector);
+  });
+  printf("dmnsn_scale_matrix(): %ld\n", sandglass.grains);
+
+  /* dmnsn_identity_matrix() */
+  sandglass_bench_fine(&sandglass, {
+    matrix = dmnsn_translation_matrix(vector);
+  });
+  printf("dmnsn_translation_matrix(): %ld\n", sandglass.grains);
+
+  /* dmnsn_rotation_matrix() */
+  sandglass_bench_fine(&sandglass, {
+    matrix = dmnsn_rotation_matrix(vector);
+  });
+  printf("dmnsn_rotation_matrix(): %ld\n", sandglass.grains);
+
+  /* dmnsn_new_line() */
+  vector2 = dmnsn_new_vector(3.0, 2.0, 1.0);
+  sandglass_bench_fine(&sandglass, {
+    line = dmnsn_new_line(vector, vector2);
+  });
+  printf("dmnsn_new_line(): %ld\n", sandglass.grains);
+
+  /* dmnsn_vector_add() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_vector_add(vector, vector2);
+  });
+  printf("dmnsn_vector_add(): %ld\n", sandglass.grains);
+
+  /* dmnsn_vector_sub() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_vector_sub(vector, vector2);
+  });
+  printf("dmnsn_vector_sub(): %ld\n", sandglass.grains);
+
+  /* dmnsn_vector_mul() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_vector_mul(2.0, vector);
+  });
+  printf("dmnsn_vector_mul(): %ld\n", sandglass.grains);
+
+  /* dmnsn_vector_div() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_vector_div(vector, 2.0);
+  });
+  printf("dmnsn_vector_div(): %ld\n", sandglass.grains);
+
+  /* dmnsn_vector_cross() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_vector_cross(vector, vector2);
+  });
+  printf("dmnsn_vector_cross(): %ld\n", sandglass.grains);
+
+  /* dmnsn_vector_dot() */
+  sandglass_bench_fine(&sandglass, {
+    result = dmnsn_vector_dot(vector, vector2);
+  });
+  printf("dmnsn_vector_dot(): %ld\n", sandglass.grains);
+
+  /* dmnsn_vector_norm() */
+  sandglass_bench_fine(&sandglass, {
+    result = dmnsn_vector_norm(vector);
+  });
+  printf("dmnsn_vector_norm(): %ld\n", sandglass.grains);
+
+  /* dmnsn_vector_normalize() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_vector_normalize(vector);
+  });
+  printf("dmnsn_vector_normalize(): %ld\n", sandglass.grains);
+
+  /* dmnsn_matrix_inverse() */
+  sandglass_bench_fine(&sandglass, {
+    matrix = dmnsn_matrix_inverse(matrix);
+  });
+  printf("dmnsn_matrix_inverse(): %ld\n", sandglass.grains);
+
+  /* dmnsn_matrix_inverse(HARD) */
+  matrix2 = dmnsn_new_matrix(1.0, 1.0, 0.0, 0.0,
+                             1.0, 1.0, 1.0, 0.0,
+                             0.0, 1.0, 1.0, 0.0);
+  sandglass_bench_fine(&sandglass, {
+    matrix = dmnsn_matrix_inverse(matrix2);
+  });
+  printf("dmnsn_matrix_inverse(HARD): %ld\n", sandglass.grains);
+
+  /* dmnsn_matrix_mul() */
+  sandglass_bench_fine(&sandglass, {
+    matrix = dmnsn_matrix_mul(matrix, matrix2);
+  });
+  printf("dmnsn_matrix_mul(): %ld\n", sandglass.grains);
+
+  /* dmnsn_transform_vector() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_transform_vector(matrix, vector);
+  });
+  printf("dmnsn_transform_vector(): %ld\n", sandglass.grains);
+
+  /* dmnsn_transform_line() */
+  sandglass_bench_fine(&sandglass, {
+    line = dmnsn_transform_line(matrix, line);
+  });
+  printf("dmnsn_transform_line(): %ld\n", sandglass.grains);
+
+  /* dmnsn_line_point() */
+  sandglass_bench_fine(&sandglass, {
+    vector = dmnsn_line_point(line, result);
+  });
+  printf("dmnsn_line_point(): %ld\n", sandglass.grains);
+
+  return EXIT_SUCCESS;
+}
diff --git a/libdimension/bench/polynomial.c b/libdimension/bench/polynomial.c
new file mode 100644
index 0000000..0313060
--- /dev/null
+++ b/libdimension/bench/polynomial.c
@@ -0,0 +1,72 @@
+/*************************************************************************
+ * Copyright (C) 2009-2010 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Benchmark Suite.                   *
+ *                                                                       *
+ * The Dimension Benchmark Suite is free software; you can redistribute  *
+ * it and/or modify it under the terms of the GNU General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Benchmark Suite is distributed in the hope that it will *
+ * be useful, but WITHOUT ANY WARRANTY; without even the implied         *
+ * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See *
+ * the GNU General Public License for more details.                      *
+ *                                                                       *
+ * You should have received a copy of the GNU General Public License     *
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+#include "dimension.h"
+#include <sandglass.h>
+#include <stdlib.h>
+
+int
+main(void)
+{
+#define NPOLY 5
+  double p[NPOLY][NPOLY + 1], x[NPOLY];
+
+  /* p[0][] = x - 0.5; */
+  p[0][1] =  1.0;
+  p[0][0] = -0.5;
+
+  /* p[1][] = (x + 0.5)*(x - 0.5) */
+  p[1][2] =  1.0;
+  p[1][1] =  0.0;
+  p[1][0] = -0.25;
+
+  /* p[2][] = (x + 1)*(x - 1.2345)*(x - 100) */
+  p[2][3] =  1.0;
+  p[2][2] = -100.2345;
+  p[2][1] =  22.2155;
+  p[2][0] =  123.45;
+
+  /* p[3][] = (x + 1)*(x - 1.2345)*(x - 5)*(x - 100) */
+  p[3][4] =  1.0;
+  p[3][3] = -105.2345;
+  p[3][2] =  523.388;
+  p[3][1] =  12.3725;
+  p[3][0] = -617.25;
+
+  /* p[4][] = (x + 1)*(x - 1.2345)*(x - 2.3456)*(x - 5)*(x - 100) */
+  p[4][5] =  1.0;
+  p[4][4] = -107.5801;
+  p[4][3] =  770.2260432;
+  p[4][2] = -1215.2863928;
+  p[4][1] = -646.270936;
+  p[4][0] =  1447.8216;
+
+  sandglass_t sandglass;
+  if (sandglass_init_monotonic(&sandglass, SANDGLASS_CPUTIME) != 0) {
+    perror("sandglass_create()");
+    return EXIT_FAILURE;
+  }
+
+  for (size_t i = 0; i < NPOLY; ++i) {
+    sandglass_bench_fine(&sandglass, dmnsn_solve_polynomial(p[i], i + 1, x));
+    printf("dmnsn_solve_polynomial(x^%zu): %ld\n", i + 1, sandglass.grains);
+  }
+
+  return EXIT_SUCCESS;
+}
diff --git a/libdimension/bench/prtree.c b/libdimension/bench/prtree.c
new file mode 100644
index 0000000..b6f778a
--- /dev/null
+++ b/libdimension/bench/prtree.c
@@ -0,0 +1,119 @@
+/*************************************************************************
+ * Copyright (C) 2009-2011 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Benchmark Suite.                   *
+ *                                                                       *
+ * The Dimension Benchmark Suite is free software; you can redistribute  *
+ * it and/or modify it under the terms of the GNU General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Benchmark Suite is distributed in the hope that it will *
+ * be useful, but WITHOUT ANY WARRANTY; without even the implied         *
+ * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See *
+ * the GNU General Public License for more details.                      *
+ *                                                                       *
+ * You should have received a copy of the GNU General Public License     *
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+#include "dimension-impl.h"
+#include <sandglass.h>
+#include <stdlib.h>
+
+static bool
+dmnsn_fake_intersection_fn(const dmnsn_object *object, dmnsn_line line,
+                           dmnsn_intersection *intersection)
+{
+  intersection->t = (object->bounding_box.min.z - line.x0.z)/line.n.z;
+  intersection->normal = dmnsn_x;
+  return true;
+}
+
+static bool
+dmnsn_fake_inside_fn(const dmnsn_object *object, dmnsn_vector point)
+{
+  return true;
+}
+
+static void
+dmnsn_randomize_bounding_box(dmnsn_object *object)
+{
+  dmnsn_vector a, b;
+
+  a.x = 2.0*((double)rand())/RAND_MAX - 1.0;
+  a.y = 2.0*((double)rand())/RAND_MAX - 1.0;
+  a.z = 2.0*((double)rand())/RAND_MAX - 1.0;
+
+  b.x = 2.0*((double)rand())/RAND_MAX - 1.0;
+  b.y = 2.0*((double)rand())/RAND_MAX - 1.0;
+  b.z = 2.0*((double)rand())/RAND_MAX - 1.0;
+
+  object->bounding_box.min = dmnsn_vector_min(a, b);
+  object->bounding_box.max = dmnsn_vector_max(a, b);
+}
+
+static dmnsn_object *
+dmnsn_new_fake_object(void)
+{
+  dmnsn_object *object = dmnsn_new_object();
+  /* Generate a bounding box in  (-1, -1, -1), (1, 1, 1) */
+  dmnsn_randomize_bounding_box(object);
+  object->intersection_fn = dmnsn_fake_intersection_fn;
+  object->inside_fn       = dmnsn_fake_inside_fn;
+  return object;
+}
+
+int
+main(void)
+{
+  const size_t nobjects = 10000;
+
+  sandglass_t sandglass;
+  if (sandglass_init_monotonic(&sandglass, SANDGLASS_CPUTIME) != 0) {
+    perror("sandglass_create()");
+    return EXIT_FAILURE;
+  }
+
+  dmnsn_array *objects = dmnsn_new_array(sizeof(dmnsn_object *));
+  for (size_t i = 0; i < nobjects; ++i) {
+    dmnsn_object *object = dmnsn_new_fake_object();
+    dmnsn_initialize_object(object);
+    dmnsn_array_push(objects, &object);
+  }
+
+  dmnsn_prtree *tree;
+  sandglass_bench_noprecache(&sandglass, {
+    tree = dmnsn_new_prtree(objects);
+  });
+  printf("dmnsn_new_prtree(): %ld\n", sandglass.grains);
+
+  /* dmnsn_prtree_intersection() */
+  dmnsn_line ray = dmnsn_new_line(
+    dmnsn_new_vector( 1.0,  1.0, -2.0),
+    dmnsn_new_vector(-0.5, -0.5,  1.0)
+  );
+  dmnsn_intersection intersection;
+
+  sandglass_bench_fine(&sandglass, {
+    dmnsn_prtree_intersection(tree, ray, &intersection, true);
+  });
+  printf("dmnsn_prtree_intersection(): %ld\n", sandglass.grains);
+
+  /* dmnsn_prtree_inside() */
+  sandglass_bench_fine(&sandglass, {
+    dmnsn_prtree_inside(tree, dmnsn_zero);
+  });
+  printf("dmnsn_prtree_inside(): %ld\n", sandglass.grains);
+
+  /* Cleanup */
+  dmnsn_delete_prtree(tree);
+  for (size_t i = 0; i < nobjects; ++i) {
+    dmnsn_object *object;
+    dmnsn_array_get(objects, i, &object);
+    dmnsn_delete_object(object);
+  }
+
+  dmnsn_delete_array(objects);
+  return EXIT_SUCCESS;
+}