aboutsummaryrefslogtreecommitdiffstats
path: root/benchmark
diff options
context:
space:
mode:
Diffstat (limited to 'benchmark')
-rw-r--r--benchmark/bench_bitvec.cpp461
-rw-r--r--benchmark/bench_hilbert.cpp93
-rw-r--r--benchmark/bench_utils.hpp40
3 files changed, 284 insertions, 310 deletions
diff --git a/benchmark/bench_bitvec.cpp b/benchmark/bench_bitvec.cpp
index 6580af9..5c885b1 100644
--- a/benchmark/bench_bitvec.cpp
+++ b/benchmark/bench_bitvec.cpp
@@ -29,324 +29,303 @@
#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 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);
+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; });
- }
+ 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);
+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; });
- }
+ 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 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 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 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 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 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 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 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 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 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 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 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 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 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;
+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); });
- }
+ 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;
+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); });
- }
+ 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 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();
- }
- });
- }
+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>
+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);
+ 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>
+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>
+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);
+ bench_row<Bench, N>(ctx, os);
+ bench_rec<Bench, Ns...>(ctx, os);
}
/// Run benchmark
-template <template <class U, size_t M> class Bench>
+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);
+ 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;
+ Context ctx;
- bench<BenchAnd>(ctx, "and");
- bench<BenchOr>(ctx, "or");
- bench<BenchXor>(ctx, "xor");
- bench<BenchNone>(ctx, "none");
+ 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<BenchSetOne>(ctx, "set_one");
+ bench<BenchSetAll>(ctx, "set_all");
- bench<BenchResetOne>(ctx, "reset_one");
- bench<BenchResetAll>(ctx, "reset_all");
+ bench<BenchResetOne>(ctx, "reset_one");
+ bench<BenchResetAll>(ctx, "reset_all");
- bench<BenchFlipOne>(ctx, "flip_one");
- bench<BenchFlipAll>(ctx, "flip_all");
+ bench<BenchFlipOne>(ctx, "flip_one");
+ bench<BenchFlipAll>(ctx, "flip_all");
- bench<BenchCount>(ctx, "count");
- bench<BenchFindFirst>(ctx, "find_first");
+ bench<BenchCount>(ctx, "count");
+ bench<BenchFindFirst>(ctx, "find_first");
- bench<BenchLeftShift>(ctx, "left_shift");
- bench<BenchRightShift>(ctx, "right_shift");
+ bench<BenchLeftShift>(ctx, "left_shift");
+ bench<BenchRightShift>(ctx, "right_shift");
- bench<BenchLeftRotate>(ctx, "left_rotate");
- bench<BenchRightRotate>(ctx, "right_rotate");
+ bench<BenchLeftRotate>(ctx, "left_rotate");
+ bench<BenchRightRotate>(ctx, "right_rotate");
- bench<BenchGrayCode>(ctx, "gray_code");
- bench<BenchGrayCodeInv>(ctx, "gray_code_inv");
+ bench<BenchGrayCode>(ctx, "gray_code");
+ bench<BenchGrayCodeInv>(ctx, "gray_code_inv");
- bench<BenchComparison>(ctx, "comparison");
- bench<BenchIteration>(ctx, "iteration");
+ bench<BenchComparison>(ctx, "comparison");
+ bench<BenchIteration>(ctx, "iteration");
- return 0;
+ return 0;
}
diff --git a/benchmark/bench_hilbert.cpp b/benchmark/bench_hilbert.cpp
index 52c12dc..5793d29 100644
--- a/benchmark/bench_hilbert.cpp
+++ b/benchmark/bench_hilbert.cpp
@@ -29,85 +29,80 @@
#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 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);
+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); });
- }
+ 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>
+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);
+ 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>
+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>
+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);
+ 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>
+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);
+ 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;
+ Context ctx;
- bench<BenchCoordsToIndex>(ctx, "coords_to_index");
- bench<BenchIndexToCoords>(ctx, "index_to_coords");
+ bench<BenchCoordsToIndex>(ctx, "coords_to_index");
+ bench<BenchIndexToCoords>(ctx, "index_to_coords");
- return 0;
+ return 0;
}
diff --git a/benchmark/bench_utils.hpp b/benchmark/bench_utils.hpp
index a3f7f81..620cb27 100644
--- a/benchmark/bench_utils.hpp
+++ b/benchmark/bench_utils.hpp
@@ -28,37 +28,37 @@
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>
+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;
+ 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>
+template<class Operation>
Duration
run_bench(const Operation& op)
{
- static constexpr auto bench_duration = std::chrono::milliseconds{10};
+ 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();
- }
+ 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;
+ return (t_now - t_start) / count;
}
#endif
generated by cgit v1.2.1 (git 2.18.0) at 2025-01-08 20:06:10 +0000