[libgee] Introduce benchmarks
- From: Didier 'Ptitjes' Villevalois <dvillevalois src gnome org>
- To: svn-commits-list gnome org
- Cc:
- Subject: [libgee] Introduce benchmarks
- Date: Wed, 9 Sep 2009 20:31:35 +0000 (UTC)
commit 71cd9e344d99c55b61d12a6659f862832bede2f5
Author: Didier 'Ptitjes <ptitjes free fr>
Date: Wed Sep 9 22:06:26 2009 +0200
Introduce benchmarks
.gitignore | 5 +-
Makefile.am | 7 ++
benchmark/Makefile.am | 31 ++++++
benchmark/benchmark.vala | 235 +++++++++++++++++++++++++++++++++++++++++
benchmark/benchmarksorts.vala | 73 +++++++++++++
benchmark/mergesort.vala | 110 +++++++++++++++++++
configure.ac | 5 +-
gee/Makefile.am | 9 ++-
8 files changed, 471 insertions(+), 4 deletions(-)
---
diff --git a/.gitignore b/.gitignore
index bd301c2..5c4ffb5 100644
--- a/.gitignore
+++ b/.gitignore
@@ -25,9 +25,10 @@ compile
stamp-h1
*.pc
gee/gee-1.0.vapi
-tests/testarraylist
+gee/gee-internals-1.0.vapi
+benchmark/benchmarks
+tests/tests
tests/testhashmap
tests/testhashset
-tests/testlinkedlist
tests/testtreemap
tests/testtreeset
diff --git a/Makefile.am b/Makefile.am
index 610b9ba..4b3717d 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -7,10 +7,17 @@ DOC_SUBDIR = \
$(NULL)
endif
+if ENABLE_BENCHMARK
+BENCHMARK_SUBDIR = \
+ benchmark \
+ $(NULL)
+endif
+
SUBDIRS = \
gee \
tests \
$(DOC_SUBDIR) \
+ $(BENCHMARK_SUBDIR) \
$(NULL)
pkgconfigdir = $(libdir)/pkgconfig
diff --git a/benchmark/Makefile.am b/benchmark/Makefile.am
new file mode 100644
index 0000000..a226285
--- /dev/null
+++ b/benchmark/Makefile.am
@@ -0,0 +1,31 @@
+include $(top_srcdir)/Makefile.decl
+
+NULL =
+
+AM_CPPFLAGS = \
+ -I$(top_srcdir)/gee \
+ $(GLIB_CFLAGS) \
+ $(NULL)
+
+AM_LDFLAGS = \
+ -lm
+ $(NULL)
+
+noinst_PROGRAMS = benchmarks
+
+progs_ldadd = $(GLIB_LIBS) ../gee/libgee.la
+
+BUILT_SOURCES = benchmarks.vala.stamp
+
+benchmarks_VALASOURCES = \
+ benchmark.vala \
+ benchmarksorts.vala \
+ mergesort.vala \
+ $(NULL)
+
+benchmarks_SOURCES = benchmarks.vala.stamp $(benchmarks_VALASOURCES:.vala=.c)
+benchmarks.vala.stamp: $(benchmarks_VALASOURCES)
+ $(VALAC) -C --basedir $(top_srcdir) --vapidir $(top_srcdir)/gee --pkg gee-internals-1.0 $^
+ touch $@
+benchmarks_LDADD = $(progs_ldadd)
+EXTRA_DIST += $(benchmarks_VALASOURCES)
diff --git a/benchmark/benchmark.vala b/benchmark/benchmark.vala
new file mode 100644
index 0000000..b0e12d6
--- /dev/null
+++ b/benchmark/benchmark.vala
@@ -0,0 +1,235 @@
+/* benchmark.vala
+ *
+ * Copyright (C) 2008 Jürg Billeter
+ * Copyright (C) 2009 Didier Villevalois
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library 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
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Didier 'Ptitjes Villevalois <ptitjes free fr>
+ */
+
+using Gee;
+
+namespace Gee.Benchmark {
+
+ public interface Factory<G> : Object {
+
+ public abstract Collection<G> create ();
+
+ public abstract Collection<G> copy (Collection<G> collection);
+ }
+
+ public interface Generator<G> : Object {
+
+ public abstract string name { get; }
+
+ public abstract void generate_collection (int size, Collection<G> collection);
+ }
+
+ public interface Algorithm<G> : Object {
+
+ public abstract string name { get; }
+
+ public abstract void process_collection (Collection<G> collection);
+ }
+
+ public class RandomInt32 : Object, Generator<int32> {
+
+ public string name { get { return "FullRandom"; } }
+
+ public void generate_collection (int size, Collection<int32> collection) {
+ for (int i = 0; i < size; i++) {
+ collection.add (GLib.Random.int_range (0, size - 1));
+ }
+ }
+ }
+
+ public class FixedVarianceInt32 : Object, Generator<int32> {
+
+ public string name { get { return "FixedVariance"; } }
+
+ public void generate_collection (int size, Collection<int32> collection) {
+ int variance = (int) Math.sqrt (size);
+ for(int i = 0; i < size; i++) {
+ collection.add (i + GLib.Random.int_range (0, variance) - variance / 2);
+ }
+ }
+ }
+
+ public class MountsInt32 : Object, Generator<int32> {
+
+ public string name { get { return "Mounts"; } }
+
+ public void generate_collection (int size, Collection<int32> collection) {
+ int index = 0;
+ int last = 0;
+ int variance = (int) Math.sqrt (size);
+ while (index < size) {
+ int width = GLib.Random.int_range (0, variance);
+ int height = GLib.Random.int_range (- variance / 2, variance / 2);
+ for(int i = 0; i < width; i++) {
+ collection.add (last + height / width);
+ }
+ index += width;
+ last += height;
+ }
+ }
+ }
+
+ public class ReverseSortedInt32 : Object, Generator<int32> {
+
+ public string name { get { return "ReverseSorted"; } }
+
+ public void generate_collection (int size, Collection<int32> collection) {
+ for(int i = 0; i < size; i++) {
+ collection.add (size - i - 1);
+ }
+ }
+ }
+
+ public class SortedInt32 : Object, Generator<int32> {
+
+ public string name { get { return "Sorted"; } }
+
+ public void generate_collection (int size, Collection<int32> collection) {
+ for(int i = 0; i < size; i++) {
+ collection.add (i);
+ }
+ }
+ }
+
+ public class ArrayListFactory<G> : Object, Factory<G> {
+
+ public Collection<G> create () {
+ return new ArrayList<G> ();
+ }
+
+ public Collection<G> copy (Collection<G> collection) {
+ ArrayList<G> copy = new ArrayList<G> ();
+ foreach (G item in collection) {
+ copy.add (item);
+ }
+ return copy;
+ }
+ }
+
+ public class Benchmark<G> : Object {
+
+ public Benchmark (Factory<G> factory,
+ Gee.List<Algorithm<G>> algorithms,
+ Gee.List<Generator<G>> generators,
+ int[] sizes,
+ int iteration_count) {
+ this.factory = factory;
+ this.algorithms = algorithms;
+ this.sizes = sizes;
+ this.generators = generators;
+ this.iteration_count = iteration_count;
+ }
+
+ private Factory<G> factory;
+ private int[] sizes;
+ private Gee.List<Generator<G>> generators;
+ private Gee.List<Algorithm<G>> algorithms;
+ private int iteration_count;
+ private double[,,] results_sum;
+ private double[,,] results_squared_sum;
+
+ public void run () {
+ results_sum = new double[sizes.length,
+ generators.size,
+ algorithms.size];
+ results_squared_sum = new double[sizes.length,
+ generators.size,
+ algorithms.size];
+
+ for (int i = 0; i < sizes.length; i++) {
+ for (int j = 0; j < generators.size; j++) {
+ for (int k = 0; k < algorithms.size; k++) {
+ results_sum[i,j,k] = 0;
+ results_squared_sum[i,j,k] = 0;
+ }
+ }
+ }
+
+ Timer timer = new Timer ();
+
+ for (int iteration = 1; iteration <= iteration_count; iteration++) {
+ for (int i = 0; i < sizes.length; i++) {
+ int size = sizes[i];
+ for (int j = 0; j < generators.size; j++) {
+ Collection<G> collection = factory.create();
+ generators[j].generate_collection (size, collection);
+
+ for (int k = 0; k < algorithms.size; k++) {
+ Collection<G> copy = factory.copy (collection);
+
+ timer.reset ();
+ timer.start ();
+ algorithms[k].process_collection (copy);
+ timer.stop ();
+
+ double elapsed = timer.elapsed ();
+ results_sum[i,j,k] += elapsed;
+ results_squared_sum[i,j,k] += Math.pow (elapsed, 2);
+ }
+ }
+ }
+
+ if (iteration % 10 == 0) {
+ stdout.printf ("|");
+ } else {
+ stdout.printf ("*");
+ }
+ stdout.flush ();
+ if (iteration % 100 == 0) {
+ stdout.printf ("\n\n");
+ display_results (iteration);
+ }
+ }
+ }
+
+ public void display_results (int iteration) {
+ stdout.printf ("After %d iterations: (average [sample standard deviation] in seconds)\n\n", iteration);
+
+ for (int i = 0; i < sizes.length; i++) {
+ stdout.printf ("%d elements:\n", sizes[i]);
+
+ stdout.printf ("%20s\t", "");
+ for (int k = 0; k < algorithms.size; k++) {
+ stdout.printf ("%-20s\t", algorithms[k].name);
+ }
+ stdout.printf ("\n");
+
+ for (int j = 0; j < generators.size; j++) {
+ stdout.printf ("%20s\t", generators[j].name);
+ for (int k = 0; k < algorithms.size; k++) {
+ double average = results_sum[i,j,k] / iteration;
+ double squared_deviation =
+ (results_squared_sum[i,j,k]
+ - ((double) iteration) * Math.pow (average, 2))
+ / (iteration - 1);
+ double deviation = Math.sqrt (squared_deviation);
+ stdout.printf ("%8f [%8f] \t", average, deviation);
+ }
+ stdout.printf ("\n");
+ }
+ stdout.printf ("\n");
+ }
+ stdout.printf ("\n\n");
+ }
+ }
+}
diff --git a/benchmark/benchmarksorts.vala b/benchmark/benchmarksorts.vala
new file mode 100644
index 0000000..f02e1c2
--- /dev/null
+++ b/benchmark/benchmarksorts.vala
@@ -0,0 +1,73 @@
+/* benchmarksorts.vala
+ *
+ * Copyright (C) 2008 Jürg Billeter
+ * Copyright (C) 2009 Didier Villevalois
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library 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
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Didier 'Ptitjes Villevalois <ptitjes free fr>
+ */
+
+using Gee;
+
+namespace Gee.Benchmark {
+
+ public class TimSort<G> : Object, Algorithm<G> {
+
+ public string name { get { return "TimSort"; } }
+
+ public void process_collection (Collection<G> collection) {
+ ((Gee.List<G>) collection).sort ();
+ }
+ }
+
+ public class MergeSort<G> : Object, Algorithm<G> {
+
+ public string name { get { return "MergeSort"; } }
+
+ public void process_collection (Collection<G> collection) {
+ CompareFunc compare = Functions.get_compare_func_for (typeof (G));
+ Gee.MergeSort<G>.sort ((Gee.List<G>) collection, compare);
+ }
+ }
+
+ void main (string[] args) {
+ var algorithms = new ArrayList<Algorithm<int32>> ();
+ algorithms.add (new TimSort<int32> ());
+ algorithms.add (new MergeSort<int32> ());
+
+ var generators = new ArrayList<Generator<int32>> ();
+ generators.add (new RandomInt32 ());
+ generators.add (new FixedVarianceInt32 ());
+ generators.add (new MountsInt32 ());
+ generators.add (new ReverseSortedInt32 ());
+ generators.add (new SortedInt32 ());
+
+ Benchmark<int32> benchmark =
+ new Benchmark<int32> (new ArrayListFactory<int32> (),
+ algorithms,
+ generators,
+ new int[] { 10,
+ 100,
+ 1000,
+ 10000,
+ 100000,
+ 1000000
+ },
+ 1000);
+ benchmark.run ();
+ }
+}
diff --git a/benchmark/mergesort.vala b/benchmark/mergesort.vala
new file mode 100644
index 0000000..988c9d3
--- /dev/null
+++ b/benchmark/mergesort.vala
@@ -0,0 +1,110 @@
+/* mergesort.vala
+ *
+ * Copyright (C) 2009 Didier Villevalois
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library 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
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Will <tcosprojects gmail com>
+ */
+
+internal class Gee.MergeSort<G> {
+
+ public static void sort (List<G> list, CompareFunc compare) {
+ if (list is ArrayList) {
+ MergeSort<G>.sort_arraylist ((ArrayList<G>) list, compare);
+ } else {
+ MergeSort<G>.sort_list (list, compare);
+ }
+ }
+
+ public static void sort_list (List<G> list, CompareFunc compare) {
+ MergeSort<G> helper = new MergeSort<G> ();
+
+ helper.list_collection = list;
+ helper.array = list.to_array ();
+ helper.list = helper.array;
+ helper.index = 0;
+ helper.size = list.size;
+ helper.compare = compare;
+
+ helper.do_sort ();
+
+ // TODO Use a list iterator and use iter.set(item)
+ list.clear ();
+ foreach (G item in helper.array) {
+ list.add (item);
+ }
+ }
+
+ public static void sort_arraylist (ArrayList<G> list, CompareFunc compare) {
+ MergeSort<G> helper = new MergeSort<G> ();
+
+ helper.list_collection = list;
+ helper.list = list._items;
+ helper.index = 0;
+ helper.size = list._size;
+ helper.compare = compare;
+
+ helper.do_sort ();
+ }
+
+ private List<G> list_collection;
+ private G[] array;
+ private unowned G[] list;
+ private int index;
+ private int size;
+ private CompareFunc compare;
+
+ private void do_sort () {
+ if (this.size <= 1) {
+ return;
+ }
+
+ var work_area = new G[this.size];
+
+ merge_sort_aux (index, this.size, work_area);
+ }
+
+ private void merge_sort_aux (int left, int right, G[] work_area) {
+ if (right == left + 1) {
+ return;
+ } else {
+ int size = right - left;
+ int middle = size / 2;
+ int lbegin = left;
+ int rbegin = left + middle;
+
+ merge_sort_aux (left, left + middle, work_area);
+ merge_sort_aux (left + middle, right, work_area);
+
+ for (int i = 0; i < size; i++) {
+ if (lbegin < left + middle && (rbegin == right ||
+ compare (list[lbegin], list[rbegin]) <= 0)) {
+
+ work_area[i] = list[lbegin];
+ lbegin++;
+ } else {
+ work_area[i] = list[rbegin];
+ rbegin++;
+ }
+ }
+
+ for (int i = left; i < right; i++) {
+ list[i] = work_area[i - left];
+ }
+ }
+ }
+}
diff --git a/configure.ac b/configure.ac
index 404a3f6..95a30e7 100644
--- a/configure.ac
+++ b/configure.ac
@@ -25,6 +25,9 @@ AS_IF([test "x$enable_doc" != xno],
AS_IF([test "$VALADOC" = :],
[AC_MSG_ERROR([valadoc not found])])])
+AC_ARG_ENABLE(benchmark, AS_HELP_STRING([--enable-benchmark], [Enable benchmark]), enable_benchmark=$enableval, enable_benchmark=no)
+AM_CONDITIONAL(ENABLE_BENCHMARK, test x$enable_benchmark = xyes)
+
GLIB_REQUIRED=2.12.0
PKG_CHECK_MODULES(GLIB, glib-2.0 >= $GLIB_REQUIRED gobject-2.0 >= $GLIB_REQUIRED)
@@ -33,8 +36,8 @@ AC_SUBST(GLIB_LIBS)
AC_CONFIG_FILES([Makefile
gee-1.0.pc
+ benchmark/Makefile
doc/Makefile
gee/Makefile
tests/Makefile])
-
AC_OUTPUT
diff --git a/gee/Makefile.am b/gee/Makefile.am
index d218923..656d710 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -51,8 +51,15 @@ geeinclude_HEADERS = \
gee.h \
$(NULL)
+VALAFLAGS = \
+ -H gee.h --vapi gee-1.0.vapi \
+ -h gee-internals.h \
+ --internal-vapi gee-internals-1.0.vapi \
+ --gir Gee-1.0.gir \
+ $(NULL)
+
gee-1.0.vapi gee.vala.stamp: $(libgee_la_VALASOURCES)
- $(VALAC) -C -H gee.h --library gee-1.0 --gir Gee-1.0.gir $^
+ $(VALAC) -C $(VALAFLAGS) $^
touch $@
libgee_la_LIBADD = \
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
