aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile15
-rwxr-xr-xbenchmarks/plot.py155
-rw-r--r--test/bench_bitvec.cpp339
-rw-r--r--test/bench_hilbert.cpp111
-rw-r--r--test/bench_utils.hpp64
5 files changed, 681 insertions, 3 deletions
diff --git a/Makefile b/Makefile
index e397515..ed93b0a 100644
--- a/Makefile
+++ b/Makefile
@@ -40,6 +40,7 @@ endif # DEBUG
HEADERS = $(wildcard chilbert/*.hpp) $(wildcard chilbert/*.ipp)
DETAIL_HEADERS = $(wildcard chilbert/detail/*.hpp)
TESTS = test/test_bitvec test/test_gray_code_rank test/test_hilbert
+BENCHMARKS = test/bench_bitvec test/bench_hilbert
PROGS = bin/chilbert_obj bin/chilbert_svg
ALL_HEADERS = $(HEADERS) $(DETAIL_HEADERS)
@@ -49,6 +50,8 @@ all: $(PROGS)
tests: $(TESTS)
+benchmarks: $(BENCHMARKS)
+
test/%: test/%.cpp $(ALL_HEADERS)
$(CXX) $(CXXFLAGS) -o $@ $@.cpp
@@ -66,12 +69,18 @@ bin/%: bin/%.cpp $(ALL_HEADERS)
FORCE:
clean:
- rm -f $(TESTS) $(PROGS)
+ rm -f $(PROGS) $(TESTS) $(BENCHMARKS)
-%.run: tests
+%.run:
$*
-test: $(addsuffix .run, $(TESTS)) FORCE
+test: tests $(addsuffix .run, $(TESTS)) FORCE
+
+bench: $(BENCHMARKS)
+ mkdir -p benchmarks
+ cd benchmarks && ../test/bench_bitvec
+ cd benchmarks && ../test/bench_hilbert
+ cd benchmarks && ./plot.py
install: FORCE
install -d $(DESTDIR)$(includedir)/chilbert/
diff --git a/benchmarks/plot.py b/benchmarks/plot.py
new file mode 100755
index 0000000..b329ed4
--- /dev/null
+++ b/benchmarks/plot.py
@@ -0,0 +1,155 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+import csv
+import glob
+import itertools
+import math
+import matplotlib.pyplot as plt
+import sys
+
+
+def get_dashes():
+ """Generator for plot line dash patterns."""
+ dash = 2.0
+ space = dot = 0.75
+
+ yield [] # Solid
+ yield [dash, space] # Dashed
+ yield [dot, space] # Dotted
+
+ # Dash-dots, with increasing number of dots for each line
+ for i in itertools.count(2):
+ yield [dash, space] + [dot, space] * (i - 1)
+
+
+def plot(in_file, out_filename, x_label, y_max=None):
+ fig_height = 4.0
+ dashes = get_dashes()
+ markers = itertools.cycle(
+ ['o', 's', 'v', 'D', '*', 'p', 'P', 'h', 'X', '+', 'x'])
+
+ reader = csv.reader(in_file, delimiter='\t')
+ header = next(reader)
+ cols = [x for x in zip(*list(reader))]
+
+ plt.clf()
+ fig = plt.figure(figsize=(fig_height * math.sqrt(2), fig_height))
+ ax = fig.add_subplot(111)
+
+ ax.set_xlabel(x_label)
+
+ ax.set_ylabel(u'Time (μs)')
+ if y_max is not None:
+ ax.set_ylim([0.0, y_max])
+
+ ax.grid(linewidth=0.25, linestyle=':', color='0', dashes=[0.2, 1.6])
+ ax.tick_params(axis='both', width=0.75)
+
+ x = cols[0]
+ for i, y in enumerate(cols[1::]):
+ ax.plot(x,
+ list(map(float, y)),
+ label=header[i + 1],
+ marker=next(markers),
+ dashes=next(dashes),
+ markersize=3.0,
+ linewidth=1.0)
+
+ plt.legend(loc='upper left')
+ plt.savefig(out_filename, bbox_inches='tight', pad_inches=0.025)
+ plt.close()
+ sys.stderr.write('wrote {}\n'.format(out_filename))
+
+
+def plot_section(x_label, plots):
+ # Get maximum value for all Y axes
+ y_max = 0.0
+ for p in plots:
+ name = p[0]
+ filename = name + '.txt'
+
+ with open(filename, 'r') as in_file:
+ reader = csv.reader(in_file, delimiter='\t')
+ next(reader)
+ for row in reader:
+ y_max = max(y_max, *map(float, row[1::]))
+
+ html = ''
+ for p in plots:
+ name = p[0]
+ caption = p[1]
+ filename = name + '.txt'
+ out_filename = filename.replace('.txt', '.svg')
+
+ with open(filename, 'r') as in_file:
+ plot(in_file, filename.replace('.txt', '.svg'), x_label, y_max)
+
+ html += ''.join([' <figure>',
+ '<img src="{}"/>'.format(out_filename),
+ '<figcaption>{}</figcaption>'.format(caption),
+ '</figure>\n'])
+
+ return html
+
+
+if __name__ == '__main__':
+ files = glob.glob('*.txt')
+
+ html = '''<html>
+<head>
+ <title>Hilbert Benchmarks</title>
+ <style type="text/css">
+ figure {
+ display: inline-block;
+ }
+
+ figure img {
+ width: 100%;
+ }
+
+ figcaption {
+ padding-top: 1ex;
+ text-align: center;
+ }
+ </style>
+</head>
+<body>
+ <h1>CHilbert Benchmarks</h1>
+'''
+
+ html += ' <h2>Bit Vector Operations</h2>'
+ html += plot_section(
+ 'Bits',
+ [('bitvec_and', 'Bitwise AND'),
+ ('bitvec_or', 'Bitwise OR'),
+ ('bitvec_xor', 'Bitwise XOR'),
+ ('bitvec_none', 'Zero test'),
+ ('bitvec_set_one', 'Set bit'),
+ ('bitvec_set_all', 'Set all'),
+ ('bitvec_reset_one', 'Reset bit'),
+ ('bitvec_reset_all', 'Reset all'),
+ ('bitvec_flip_one', 'Flip bit'),
+ ('bitvec_flip_all', 'Flip all'),
+ ('bitvec_count', 'Count'),
+ ('bitvec_find_first', 'Find first'),
+ ('bitvec_left_shift', 'Left shift'),
+ ('bitvec_right_shift', 'Right shift'),
+ ('bitvec_left_rotate', 'Left rotate'),
+ ('bitvec_right_rotate', 'Right rotate'),
+ ('bitvec_gray_code', 'Gray code'),
+ ('bitvec_gray_code_inv', 'Gray code inverse'),
+ ('bitvec_comparison', 'Comparison'),
+ ('bitvec_iteration', 'Iteration')])
+
+ html += ' <h2>Hilbert Mapping</h2>\n'
+ html += plot_section(
+ 'Dimensions',
+ [('hilbert_coords_to_index', 'Coordinates to index'),
+ ('hilbert_index_to_coords', 'Index to coordinates')])
+
+ html += '</body>\n</html>\n'
+ with open('benchmarks.html', 'w') as index_file:
+ index_file.write(html)
+
+ sys.stderr.write('wrote benchmarks.html\n')
diff --git a/test/bench_bitvec.cpp b/test/bench_bitvec.cpp
new file mode 100644
index 0000000..741b2d2
--- /dev/null
+++ b/test/bench_bitvec.cpp
@@ -0,0 +1,339 @@
+/*
+ Copyright (C) 2018 David Robillard <d@drobilla.net>
+
+ This program 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 2 of the License, or (at your option) any later
+ version.
+
+ This program 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 <https://www.gnu.org/licenses/>.
+*/
+
+#include "bench_utils.hpp"
+
+#include "chilbert/BoundedBitVec.hpp"
+#include "chilbert/DynamicBitVec.hpp"
+#include "chilbert/SmallBitVec.hpp"
+#include "chilbert/StaticBitVec.hpp"
+
+#include <fstream>
+
+template <class T, size_t N>
+struct BenchAnd
+{
+ Duration operator()(Context& ctx)
+ {
+ const T v = make_random_bitvec<T, N>(ctx);
+ T r = make_random_bitvec<T, N>(ctx);
+
+ return run_bench([&](auto) { r &= v; });
+ }
+};
+
+template <class T, size_t N>
+struct BenchOr
+{
+ Duration operator()(Context& ctx)
+ {
+ const T v = make_random_bitvec<T, N>(ctx);
+ T r = make_random_bitvec<T, N>(ctx);
+
+ return run_bench([&](auto) { r |= v; });
+ }
+};
+
+template <class T, size_t N>
+struct BenchXor
+{
+ Duration operator()(Context& ctx)
+ {
+ const T v = make_random_bitvec<T, N>(ctx);
+ T r = make_random_bitvec<T, N>(ctx);
+
+ return run_bench([&](auto) { r ^= v; });
+ }
+};
+
+template <class T, size_t N>
+struct BenchSetOne
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ return run_bench([&](const auto i) { v.set(i % N); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchSetAll
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ return run_bench([&](auto) { v.set(); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchResetOne
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ return run_bench([&](const auto i) { v.reset(i % N); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchResetAll
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ return run_bench([&](auto) { v.reset(); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchFlipOne
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ return run_bench([&](const auto i) { v.flip(i % N); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchFlipAll
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ return run_bench([&](auto) { v.flip(); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchNone
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ bool r = false;
+ return run_bench([&](auto) { r = v.none(); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchCount
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ volatile size_t r = 0;
+ return run_bench([&](auto) { r = v.count(); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchLeftShift
+{
+ Duration operator()(Context& ctx)
+ {
+ const T v = make_random_bitvec<T, N>(ctx);
+ T r = v;
+ return run_bench([&](const auto i) { r <<= (i % N); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchRightShift
+{
+ Duration operator()(Context& ctx)
+ {
+ const T v = make_random_bitvec<T, N>(ctx);
+ T r = v;
+ return run_bench([&](const auto i) { r >>= (i % N); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchLeftRotate
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ return run_bench([&](const auto i) { v.rotl(i % N); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchRightRotate
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ volatile bool r = false;
+ return run_bench([&](const auto i) {
+ v.rotr(i % N);
+ r = v.test(0);
+ });
+ }
+};
+
+template <class T, size_t N>
+struct BenchFindFirst
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ volatile size_t r = 0;
+ return run_bench([&](auto) { r = v.find_first(); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchGrayCode
+{
+ Duration operator()(Context& ctx)
+ {
+ const T v = make_random_bitvec<T, N>(ctx);
+ T r = v;
+
+ return run_bench([&](auto) { chilbert::detail::gray_code(r); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchGrayCodeInv
+{
+ Duration operator()(Context& ctx)
+ {
+ const T v = make_random_bitvec<T, N>(ctx);
+ T r = v;
+
+ return run_bench([&](auto) { chilbert::detail::gray_code_inv(r); });
+ }
+};
+
+template <class T, size_t N>
+struct BenchComparison
+{
+ Duration operator()(Context& ctx)
+ {
+ std::vector<T> vecs;
+ for (size_t i = 0; i < 32; ++i) {
+ vecs.emplace_back(make_random_bitvec<T, N>(ctx));
+ }
+
+ volatile bool r = false;
+
+ return run_bench([&](const auto i) {
+ r |= vecs[i % vecs.size()] < vecs[(i + 1) % vecs.size()];
+ });
+ }
+};
+
+template <class T, size_t N>
+struct BenchIteration
+{
+ Duration operator()(Context& ctx)
+ {
+ T v = make_random_bitvec<T, N>(ctx);
+ auto i = v.begin();
+ volatile bool r = false;
+ return run_bench([&](const auto) {
+ r = (++i == v.end());
+ if (r) {
+ i = v.begin();
+ }
+ });
+ }
+};
+
+/// Run benchmark for size N
+template <template <class U, size_t M> class Bench, size_t N>
+void
+bench_row(Context& ctx, std::ostream& os)
+{
+ std::array<Duration, 4> results = {
+ ((N <= chilbert::SmallBitVec::bits_per_rack)
+ ? Bench<chilbert::SmallBitVec, N>{}(ctx)
+ : Duration{}),
+ Bench<chilbert::StaticBitVec<N>, N>{}(ctx),
+ Bench<chilbert::BoundedBitVec<N>, N>{}(ctx),
+ Bench<chilbert::DynamicBitVec, N>{}(ctx),
+ };
+
+ write_row(os, N, results);
+}
+
+/// Terminate recursion
+template <template <class U, size_t M> class Bench>
+void
+bench_rec(Context&, std::ostream&)
+{
+}
+
+/// Run benchmark for sizes N, Ns... (recursive helper)
+template <template <class U, size_t M> class Bench, size_t N, size_t... Ns>
+void
+bench_rec(Context& ctx, std::ostream& os)
+{
+ bench_row<Bench, N>(ctx, os);
+ bench_rec<Bench, Ns...>(ctx, os);
+}
+
+/// Run benchmark
+template <template <class U, size_t M> class Bench>
+void
+bench(Context& ctx, const std::string& name)
+{
+ std::ofstream out("bitvec_" + name + ".txt");
+ out << "n\tsmall\tstatic\tbounded\tdynamic\n";
+ bench_rec<Bench, 16, 32, 64, 128, 256, 512>(ctx, out);
+}
+
+int
+main()
+{
+ Context ctx;
+
+ bench<BenchAnd>(ctx, "and");
+ bench<BenchOr>(ctx, "or");
+ bench<BenchXor>(ctx, "xor");
+ bench<BenchNone>(ctx, "none");
+
+ bench<BenchSetOne>(ctx, "set_one");
+ bench<BenchSetAll>(ctx, "set_all");
+
+ bench<BenchResetOne>(ctx, "reset_one");
+ bench<BenchResetAll>(ctx, "reset_all");
+
+ bench<BenchFlipOne>(ctx, "flip_one");
+ bench<BenchFlipAll>(ctx, "flip_all");
+
+ bench<BenchCount>(ctx, "count");
+ bench<BenchFindFirst>(ctx, "find_first");
+
+ bench<BenchLeftShift>(ctx, "left_shift");
+ bench<BenchRightShift>(ctx, "right_shift");
+
+ bench<BenchLeftRotate>(ctx, "left_rotate");
+ bench<BenchRightRotate>(ctx, "right_rotate");
+
+ bench<BenchGrayCode>(ctx, "gray_code");
+ bench<BenchGrayCodeInv>(ctx, "gray_code_inv");
+
+ bench<BenchComparison>(ctx, "comparison");
+ bench<BenchIteration>(ctx, "iteration");
+
+ return 0;
+}
diff --git a/test/bench_hilbert.cpp b/test/bench_hilbert.cpp
new file mode 100644
index 0000000..c5f1ad9
--- /dev/null
+++ b/test/bench_hilbert.cpp
@@ -0,0 +1,111 @@
+/*
+ Copyright (C) 2018 David Robillard <d@drobilla.net>
+
+ This program 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 2 of the License, or (at your option) any later
+ version.
+
+ This program 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 <https://www.gnu.org/licenses/>.
+*/
+
+#include "bench_utils.hpp"
+
+#include "chilbert/BoundedBitVec.hpp"
+#include "chilbert/DynamicBitVec.hpp"
+#include "chilbert/SmallBitVec.hpp"
+#include "chilbert/StaticBitVec.hpp"
+#include "chilbert/chilbert.hpp"
+
+#include <fstream>
+
+template <class H, size_t M, size_t D>
+struct BenchCoordsToIndex
+{
+ Duration operator()(Context& ctx)
+ {
+ const auto p = make_random_point<M, D>(ctx);
+ H ha = make_zero_bitvec<H, D * M>();
+
+ return run_bench(
+ [&](auto) { chilbert::coords_to_index(p.data(), M, D, ha); });
+ }
+};
+
+template <class H, size_t M, size_t D>
+struct BenchIndexToCoords
+{
+ Duration operator()(Context& ctx)
+ {
+ auto p = make_random_point<M, D>(ctx);
+ const H ha = make_random_bitvec<H, D * M>(ctx);
+
+ return run_bench(
+ [&](auto) { chilbert::index_to_coords(p.data(), M, D, ha); });
+ }
+};
+
+/// Run benchmark for size N
+template <template <class H, size_t M, size_t D> class Bench,
+ size_t M,
+ size_t D>
+void
+bench_row(Context& ctx, std::ostream& os)
+{
+ std::array<Duration, 4> results = {
+ ((M * D <= chilbert::SmallBitVec::bits_per_rack)
+ ? Bench<chilbert::SmallBitVec, M, D>{}(ctx)
+ : Duration{}),
+ Bench<chilbert::StaticBitVec<M * D>, M, D>{}(ctx),
+ Bench<chilbert::BoundedBitVec<M * D>, M, D>{}(ctx),
+ Bench<chilbert::DynamicBitVec, M, D>{}(ctx),
+ };
+
+ write_row(os, D, results);
+}
+
+/// Terminate recursion
+template <template <class H, size_t M, size_t D> class Bench, size_t M>
+void
+bench_rec(Context&, std::ostream&)
+{
+}
+
+/// Run benchmark for sizes N, Ns... (recursive helper)
+template <template <class H, size_t M, size_t D> class Bench,
+ size_t M,
+ size_t D,
+ size_t... Ds>
+void
+bench_rec(Context& ctx, std::ostream& os)
+{
+ bench_row<Bench, M, D>(ctx, os);
+ bench_rec<Bench, M, Ds...>(ctx, os);
+}
+
+/// Run benchmark
+template <template <class H, size_t M, size_t D> class Bench>
+void
+bench(Context& ctx, const std::string& name)
+{
+ std::ofstream out("hilbert_" + name + ".txt");
+ out << "d\tsmall\tstatic\tbounded\tdynamic\n";
+ bench_rec<Bench, 8, 2, 4, 8, 16, 32, 64>(ctx, out);
+}
+
+int
+main()
+{
+ Context ctx;
+
+ bench<BenchCoordsToIndex>(ctx, "coords_to_index");
+ bench<BenchIndexToCoords>(ctx, "index_to_coords");
+
+ return 0;
+}
diff --git a/test/bench_utils.hpp b/test/bench_utils.hpp
new file mode 100644
index 0000000..a3f7f81
--- /dev/null
+++ b/test/bench_utils.hpp
@@ -0,0 +1,64 @@
+/*
+ Copyright (C) 2018 David Robillard <d@drobilla.net>
+
+ This program 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 2 of the License, or (at your option) any later
+ version.
+
+ This program 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 <https://www.gnu.org/licenses/>.
+*/
+
+#ifndef BENCH_UTILS_HPP
+#define BENCH_UTILS_HPP
+
+#include "test_utils.hpp"
+
+#include <array>
+#include <chrono>
+#include <cstddef>
+#include <iostream>
+
+using Duration = std::chrono::duration<double, std::micro>;
+
+/// Write a TSV row to `os` with `n` as the first column followed by `results`
+template <class T, size_t M>
+void
+write_row(std::ostream& os, const size_t n, const std::array<T, M>& results)
+{
+ os << n;
+ for (const auto t : results) {
+ if (t == Duration::zero()) {
+ os << "\tNaN";
+ } else {
+ os << '\t' << t.count();
+ }
+ }
+ os << std::endl;
+}
+
+/// Repeatedly run an operation and return the average time
+template <class Operation>
+Duration
+run_bench(const Operation& op)
+{
+ static constexpr auto bench_duration = std::chrono::milliseconds{10};
+
+ const auto t_start = std::chrono::steady_clock{}.now();
+ auto t_now = t_start;
+ size_t count = 0;
+ for (; t_now < t_start + bench_duration; ++count) {
+ op(count);
+ t_now = std::chrono::steady_clock{}.now();
+ }
+
+ return (t_now - t_start) / count;
+}
+
+#endif
generated by cgit v1.2.1 (git 2.18.0) at 2025-01-04 23:18:17 +0000