Switch to meson build system

3 files changed, 529 insertions, 0 deletions

diff --git a/benchmark/bench_bitvec.cpp b/benchmark/bench_bitvec.cpp
new file mode 100644
index 0000000..6580af9
--- /dev/null
+++ b/benchmark/bench_bitvec.cpp
@@ -0,0 +1,352 @@
+/*
+  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 "test_utils.hpp"
+
+#include "chilbert/BoundedBitVec.hpp" // IWYU pragma: keep
+#include "chilbert/DynamicBitVec.hpp" // IWYU pragma: keep
+#include "chilbert/SmallBitVec.hpp"
+#include "chilbert/StaticBitVec.hpp" // IWYU pragma: keep
+
+#include <array>
+#include <cstddef>
+#include <fstream>
+#include <string>
+#include <vector>
+
+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;
+		(void)r;
+
+		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;
+		(void)r;
+
+		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;
+		(void)r;
+
+		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;
+		(void)r;
+
+		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/benchmark/bench_hilbert.cpp b/benchmark/bench_hilbert.cpp
new file mode 100644
index 0000000..52c12dc
--- /dev/null
+++ b/benchmark/bench_hilbert.cpp
@@ -0,0 +1,113 @@
+/*
+  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 "test_utils.hpp"
+
+#include "chilbert/BoundedBitVec.hpp" // IWYU pragma: keep
+#include "chilbert/DynamicBitVec.hpp" // IWYU pragma: keep
+#include "chilbert/SmallBitVec.hpp"
+#include "chilbert/StaticBitVec.hpp" // IWYU pragma: keep
+#include "chilbert/chilbert.hpp"
+
+#include <array>
+#include <cstddef>
+#include <fstream>
+#include <string>
+
+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, 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, 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/benchmark/bench_utils.hpp b/benchmark/bench_utils.hpp
new file mode 100644
index 0000000..a3f7f81
--- /dev/null
+++ b/benchmark/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