[libcxx] Add support for benchmark tests using Google Benchmark.
Summary:
This patch does the following:
1. Checks in a copy of the Google Benchmark library into the libc++ repo under `utils/google-benchmark`.
2. Teaches libc++ how to build Google Benchmark against both (A) in-tree libc++ and (B) the platforms native STL.
3. Allows performance benchmarks to be built as part of the libc++ build.
Building the benchmarks (and Google Benchmark) is off by default. It must be enabled using the CMake option `-DLIBCXX_INCLUDE_BENCHMARKS=ON`. When this option is enabled the tests under `libcxx/benchmarks` can be built using the `libcxx-benchmarks` target.
On Linux platforms where libstdc++ is the default STL the CMake option `-DLIBCXX_BUILD_BENCHMARKS_NATIVE_STDLIB=ON` can be used to build each benchmark test against libstdc++ as well. This is useful for comparing performance between standard libraries.
Support for benchmarks is currently very minimal. They must be manually run by the user and there is no mechanism for detecting performance regressions.
Known Issues:
* `-DLIBCXX_INCLUDE_BENCHMARKS=ON` is only supported for Clang, and not GCC, since the `-stdlib=libc++` option is needed to build Google Benchmark.
Reviewers: danalbert, dberlin, chandlerc, mclow.lists, jroelofs
Subscribers: chandlerc, dberlin, tberghammer, danalbert, srhines, hfinkel
Differential Revision: https://reviews.llvm.org/D22240
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@276049 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/benchmarks/CMakeLists.txt b/benchmarks/CMakeLists.txt
new file mode 100644
index 0000000..e95bfa8
--- /dev/null
+++ b/benchmarks/CMakeLists.txt
@@ -0,0 +1,119 @@
+include(ExternalProject)
+include(CheckCXXCompilerFlag)
+
+#==============================================================================
+# Build Google Benchmark for libc++
+#==============================================================================
+check_cxx_compiler_flag(-stdlib=libc++ LIBCXX_HAS_NO_STDLIB_LIBCXX_FLAG)
+if (NOT LIBCXX_HAS_NO_STDLIB_LIBCXX_FLAG)
+ message(FATAL "Benchmark requires support for the -stdlib=libc++ flag")
+endif()
+
+set(BENCHMARK_LIBCXX_COMPILE_FLAGS
+ -Wno-unused-command-line-argument
+ -nostdinc++
+ -cxx-isystem ${LIBCXX_SOURCE_DIR}/include
+ -stdlib=libc++)
+set(BENCHMARK_LIBCXX_LINK_FLAGS
+ -L${LIBCXX_LIBRARY_DIR}
+ -Wl,-rpath,${LIBCXX_LIBRARY_DIR})
+split_list(BENCHMARK_LIBCXX_COMPILE_FLAGS)
+split_list(BENCHMARK_LIBCXX_LINK_FLAGS)
+
+ExternalProject_Add(google-benchmark-libcxx
+ EXCLUDE_FROM_ALL ON
+ DEPENDS cxx
+ PREFIX benchmark-libcxx
+ SOURCE_DIR ${LIBCXX_SOURCE_DIR}/utils/google-benchmark
+ INSTALL_DIR ${CMAKE_CURRENT_BINARY_DIR}/benchmark-libcxx
+ CMAKE_CACHE_DEFAULT_ARGS
+ -DCMAKE_BUILD_TYPE:STRING=RELEASE
+ -DCMAKE_INSTALL_PREFIX:PATH=<INSTALL_DIR>
+ -DCMAKE_CXX_FLAGS:STRING=${BENCHMARK_LIBCXX_COMPILE_FLAGS}
+ -DCMAKE_SHARED_LINK_FLAGS:STRING=${BENCHMARK_LIBCXX_LINK_FLAGS}
+ -DCMAKE_EXE_LINK_FLAGS:STRING=${BENCHMARK_LIBCXX_LINK_FLAGS}
+ -DBENCHMARK_ENABLE_TESTING:BOOL=OFF)
+
+#==============================================================================
+# Build Google Benchmark for the native stdlib
+#==============================================================================
+if (LIBCXX_BUILD_BENCHMARK_NATIVE_STDLIB)
+ ExternalProject_Add(google-benchmark-native
+ EXCLUDE_FROM_ALL ON
+ PREFIX benchmark-native
+ SOURCE_DIR ${LIBCXX_SOURCE_DIR}/utils/google-benchmark
+ INSTALL_DIR ${CMAKE_CURRENT_BINARY_DIR}/benchmark-native
+ CMAKE_CACHE_ARGS
+ -DBENCHMARK_ENABLE_TESTING:BOOL=OFF
+ CMAKE_CACHE_DEFAULT_ARGS
+ -DCMAKE_BUILD_TYPE:STRING=RELEASE
+ -DCMAKE_INSTALL_PREFIX:PATH=<INSTALL_DIR>)
+endif()
+
+#==============================================================================
+# Benchmark tests configuration
+#==============================================================================
+add_custom_target(libcxx-benchmarks)
+
+set(BENCHMARK_LIBCXX_INSTALL ${CMAKE_CURRENT_BINARY_DIR}/benchmark-libcxx)
+set(BENCHMARK_NATIVE_INSTALL ${CMAKE_CURRENT_BINARY_DIR}/benchmark-native)
+set(BENCHMARK_TEST_COMPILE_FLAGS
+ -std=c++14 -O2
+ -I${BENCHMARK_LIBCXX_INSTALL}/include
+)
+set(BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS
+ -nostdinc++
+ ${BENCHMARK_TEST_COMPILE_FLAGS}
+ -Wno-user-defined-literals
+)
+set(BENCHMARK_TEST_LIBCXX_LINK_FLAGS
+ -nodefaultlibs
+ -L${BENCHMARK_LIBCXX_INSTALL}/lib/
+)
+set(BENCHMARK_TEST_NATIVE_LINK_FLAGS
+ -L${BENCHMARK_NATIVE_INSTALL}/lib/
+)
+split_list(BENCHMARK_TEST_COMPILE_FLAGS)
+split_list(BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS)
+split_list(BENCHMARK_TEST_LIBCXX_LINK_FLAGS)
+split_list(BENCHMARK_TEST_NATIVE_LINK_FLAGS)
+macro(add_benchmark_test name source_file)
+ set(libcxx_target ${name}_libcxx)
+ add_executable(${libcxx_target} EXCLUDE_FROM_ALL ${source_file})
+ add_dependencies(${libcxx_target} cxx google-benchmark-libcxx)
+ add_dependencies(libcxx-benchmarks ${libcxx_target})
+ target_link_libraries(${libcxx_target} cxx -lbenchmark)
+ set_target_properties(${libcxx_target}
+ PROPERTIES
+ OUTPUT_NAME "${name}.libcxx.out"
+ COMPILE_FLAGS "${BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS}"
+ LINK_FLAGS "${BENCHMARK_TEST_LIBCXX_LINK_FLAGS}")
+ if (LIBCXX_BUILD_BENCHMARK_NATIVE_STDLIB)
+ set(native_target ${name}_native)
+ add_executable(${native_target} EXCLUDE_FROM_ALL ${source_file})
+ add_dependencies(${native_target} google-benchmark-native)
+ target_link_libraries(${native_target} -lbenchmark)
+ if (LIBCXX_HAS_PTHREAD_LIB)
+ target_link_libraries(${native_target} -pthread)
+ endif()
+ add_dependencies(libcxx-benchmarks ${native_target})
+ set_target_properties(${native_target}
+ PROPERTIES
+ OUTPUT_NAME "${name}.native.out"
+ INCLUDE_DIRECTORIES ""
+ COMPILE_FLAGS "${BENCHMARK_TEST_COMPILE_FLAGS}"
+ LINK_FLAGS "${BENCHMARK_TEST_NATIVE_LINK_FLAGS}")
+ endif()
+endmacro()
+
+
+#==============================================================================
+# Register Benchmark tests
+#==============================================================================
+file(GLOB BENCHMARK_TESTS "*.bench.cpp")
+foreach(test_path ${BENCHMARK_TESTS})
+ get_filename_component(test_file "${test_path}" NAME)
+ message(STATUS "TEST: ${test_file}")
+ string(REPLACE ".bench.cpp" "" test_name "${test_file}")
+ add_benchmark_test(${test_name} ${test_file})
+endforeach()
diff --git a/benchmarks/ContainerBenchmarks.hpp b/benchmarks/ContainerBenchmarks.hpp
new file mode 100644
index 0000000..d6107f6
--- /dev/null
+++ b/benchmarks/ContainerBenchmarks.hpp
@@ -0,0 +1,69 @@
+#ifndef BENCHMARK_CONTAINER_BENCHMARKS_HPP
+#define BENCHMARK_CONTAINER_BENCHMARKS_HPP
+
+#include <cassert>
+
+#include "benchmark/benchmark_api.h"
+
+namespace ContainerBenchmarks {
+
+template <class Container, class GenInputs>
+void BM_InsertValue(benchmark::State& st, Container c, GenInputs gen) {
+ auto in = gen(st.range_x());
+ const auto end = in.end();
+ while (st.KeepRunning()) {
+ c.clear();
+ for (auto it = in.begin(); it != end; ++it) {
+ benchmark::DoNotOptimize(&(*c.insert(*it).first));
+ }
+ benchmark::ClobberMemory();
+ }
+}
+
+template <class Container, class GenInputs>
+void BM_InsertValueRehash(benchmark::State& st, Container c, GenInputs gen) {
+ auto in = gen(st.range_x());
+ const auto end = in.end();
+ while (st.KeepRunning()) {
+ c.clear();
+ c.rehash(16);
+ for (auto it = in.begin(); it != end; ++it) {
+ benchmark::DoNotOptimize(&(*c.insert(*it).first));
+ }
+ benchmark::ClobberMemory();
+ }
+}
+
+template <class Container, class GenInputs>
+static void BM_Find(benchmark::State& st, Container c, GenInputs gen) {
+ auto in = gen(st.range_x());
+ c.insert(in.begin(), in.end());
+ benchmark::DoNotOptimize(&(*c.begin()));
+ const auto end = in.data() + in.size();
+ while (st.KeepRunning()) {
+ for (auto it = in.data(); it != end; ++it) {
+ benchmark::DoNotOptimize(&(*c.find(*it)));
+ }
+ benchmark::ClobberMemory();
+ }
+}
+
+template <class Container, class GenInputs>
+static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
+ c.rehash(8);
+ auto in = gen(st.range_x());
+ c.insert(in.begin(), in.end());
+ benchmark::DoNotOptimize(&(*c.begin()));
+ const auto end = in.data() + in.size();
+ while (st.KeepRunning()) {
+ for (auto it = in.data(); it != end; ++it) {
+ benchmark::DoNotOptimize(&(*c.find(*it)));
+ }
+ benchmark::ClobberMemory();
+ }
+
+}
+
+} // end namespace ContainerBenchmarks
+
+#endif // BENCHMARK_CONTAINER_BENCHMARKS_HPP
diff --git a/benchmarks/GenerateInput.hpp b/benchmarks/GenerateInput.hpp
new file mode 100644
index 0000000..5ddda76
--- /dev/null
+++ b/benchmarks/GenerateInput.hpp
@@ -0,0 +1,133 @@
+#ifndef BENCHMARK_GENERATE_INPUT_HPP
+#define BENCHMARK_GENERATE_INPUT_HPP
+
+#include <algorithm>
+#include <random>
+#include <vector>
+#include <string>
+#include <climits>
+#include <cstddef>
+
+static const char Letters[] = {
+ '0','1','2','3','4',
+ '5','6','7','8','9',
+ 'A','B','C','D','E','F',
+ 'G','H','I','J','K',
+ 'L','M','N','O','P',
+ 'Q','R','S','T','U',
+ 'V','W','X','Y','Z',
+ 'a','b','c','d','e','f',
+ 'g','h','i','j','k',
+ 'l','m','n','o','p',
+ 'q','r','s','t','u',
+ 'v','w','x','y','z'
+};
+static const std::size_t LettersSize = sizeof(Letters);
+
+inline std::default_random_engine& getRandomEngine() {
+ static std::default_random_engine RandEngine(std::random_device{}());
+ return RandEngine;
+}
+
+inline char getRandomChar() {
+ std::uniform_int_distribution<> LettersDist(0, LettersSize-1);
+ return Letters[LettersDist(getRandomEngine())];
+}
+
+template <class IntT>
+inline IntT getRandomInteger() {
+ std::uniform_int_distribution<IntT> dist;
+ return dist(getRandomEngine());
+}
+
+inline std::string getRandomString(std::size_t Len) {
+ std::string str(Len, 0);
+ std::generate_n(str.begin(), Len, &getRandomChar);
+ return str;
+}
+
+template <class IntT>
+inline std::vector<IntT> getDuplicateIntegerInputs(size_t N) {
+ std::vector<IntT> inputs(N, static_cast<IntT>(-1));
+ return inputs;
+}
+
+template <class IntT>
+inline std::vector<IntT> getSortedIntegerInputs(size_t N) {
+ std::vector<IntT> inputs;
+ for (size_t i=0; i < N; i += 1)
+ inputs.push_back(i);
+ return inputs;
+}
+
+template <class IntT>
+std::vector<IntT> getSortedLargeIntegerInputs(size_t N) {
+ std::vector<IntT> inputs;
+ for (size_t i=0; i < N; ++i) {
+ inputs.push_back(i + N);
+ }
+ return inputs;
+}
+
+template <class IntT>
+std::vector<IntT> getSortedTopBitsIntegerInputs(size_t N) {
+ std::vector<IntT> inputs = getSortedIntegerInputs<IntT>(N);
+ for (auto& E : inputs) E <<= ((sizeof(IntT) / 2) * CHAR_BIT);
+ return inputs;
+}
+
+template <class IntT>
+inline std::vector<IntT> getReverseSortedIntegerInputs(size_t N) {
+ std::vector<IntT> inputs;
+ std::size_t i = N;
+ while (i > 0) {
+ --i;
+ inputs.push_back(i);
+ }
+ return inputs;
+}
+
+template <class IntT>
+std::vector<IntT> getPipeOrganIntegerInputs(size_t N) {
+ std::vector<IntT> v; v.reserve(N);
+ for (size_t i = 0; i < N/2; ++i) v.push_back(i);
+ for (size_t i = N/2; i < N; ++i) v.push_back(N - i);
+ return v;
+}
+
+
+template <class IntT>
+std::vector<IntT> getRandomIntegerInputs(size_t N) {
+ std::vector<IntT> inputs;
+ for (size_t i=0; i < N; ++i) {
+ inputs.push_back(getRandomInteger<IntT>());
+ }
+ return inputs;
+}
+
+inline std::vector<std::string> getDuplicateStringInputs(size_t N) {
+ std::vector<std::string> inputs(N, getRandomString(1024));
+ return inputs;
+}
+
+inline std::vector<std::string> getRandomStringInputs(size_t N) {
+ std::vector<std::string> inputs;
+ for (int i=0; i < N; ++i) {
+ inputs.push_back(getRandomString(1024));
+ }
+ return inputs;
+}
+
+inline std::vector<std::string> getSortedStringInputs(size_t N) {
+ std::vector<std::string> inputs = getRandomStringInputs(N);
+ std::sort(inputs.begin(), inputs.end());
+ return inputs;
+}
+
+inline std::vector<std::string> getReverseSortedStringInputs(size_t N) {
+ std::vector<std::string> inputs = getSortedStringInputs(N);
+ std::reverse(inputs.begin(), inputs.end());
+ return inputs;
+}
+
+#endif // BENCHMARK_GENERATE_INPUT_HPP
diff --git a/benchmarks/algorithms.bench.cpp b/benchmarks/algorithms.bench.cpp
new file mode 100644
index 0000000..82ed992
--- /dev/null
+++ b/benchmarks/algorithms.bench.cpp
@@ -0,0 +1,62 @@
+#include <unordered_set>
+#include <vector>
+#include <cstdint>
+
+#include "benchmark/benchmark_api.h"
+#include "GenerateInput.hpp"
+
+constexpr std::size_t TestNumInputs = 1024;
+
+template <class GenInputs>
+void BM_Sort(benchmark::State& st, GenInputs gen) {
+ using ValueType = typename decltype(gen(0))::value_type;
+ const auto in = gen(st.range_x());
+ std::vector<ValueType> inputs[5];
+ auto reset_inputs = [&]() {
+ for (auto& C : inputs) {
+ C = in;
+ benchmark::DoNotOptimize(C.data());
+ }
+ };
+ reset_inputs();
+ while (st.KeepRunning()) {
+ for (auto& I : inputs) {
+ std::sort(I.data(), I.data() + I.size());
+ benchmark::DoNotOptimize(I.data());
+ }
+ st.PauseTiming();
+ reset_inputs();
+ benchmark::ClobberMemory();
+ st.ResumeTiming();
+ }
+}
+
+BENCHMARK_CAPTURE(BM_Sort, random_uint32,
+ getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Sort, sorted_ascending_uint32,
+ getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Sort, sorted_descending_uint32,
+ getReverseSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Sort, single_element_uint32,
+ getDuplicateIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Sort, pipe_organ_uint32,
+ getPipeOrganIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Sort, random_strings,
+ getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Sort, sorted_ascending_strings,
+ getSortedStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Sort, sorted_descending_strings,
+ getReverseSortedStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Sort, single_element_strings,
+ getDuplicateStringInputs)->Arg(TestNumInputs);
+
+
+BENCHMARK_MAIN()
diff --git a/benchmarks/unordered_set_operations.bench.cpp b/benchmarks/unordered_set_operations.bench.cpp
index c9ee689..ab737c1 100644
--- a/benchmarks/unordered_set_operations.bench.cpp
+++ b/benchmarks/unordered_set_operations.bench.cpp
@@ -1,44 +1,268 @@
#include <unordered_set>
#include <vector>
+#include <functional>
#include <cstdint>
+#include <cstdlib>
+#include <cstring>
#include "benchmark/benchmark_api.h"
-template <class IntT>
-std::vector<IntT> getInputs(size_t N) {
- std::vector<IntT> inputs;
- for (size_t i=0; i < N; ++i) {
- inputs.push_back(i);
- }
- return inputs;
+#include "ContainerBenchmarks.hpp"
+#include "GenerateInput.hpp"
+
+using namespace ContainerBenchmarks;
+
+constexpr std::size_t TestNumInputs = 1024;
+
+template <class _Size>
+inline __attribute__((__always_inline__))
+_Size loadword(const void* __p) {
+ _Size __r;
+ std::memcpy(&__r, __p, sizeof(__r));
+ return __r;
}
-template <class Container, class Inputs>
-void BM_SetInsert(benchmark::State& st, Container c, Inputs const& in) {
- const auto end = in.end();
+inline __attribute__((__always_inline__))
+std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
+ return (__val >> __shift) | (__val << (64 - __shift));
+}
+
+inline __attribute__((__always_inline__))
+std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
+ const std::size_t __mul = 0x9ddfea08eb382d69ULL;
+ std::size_t __a = (__u ^ __v) * __mul;
+ __a ^= (__a >> 47);
+ std::size_t __b = (__v ^ __a) * __mul;
+ __b ^= (__b >> 47);
+ __b *= __mul;
+ return __b;
+}
+
+
+template <std::size_t _Len>
+inline __attribute__((__always_inline__))
+std::size_t hash_len_0_to_8(const char* __s) {
+ static_assert(_Len == 4 || _Len == 8, "");
+ const uint64_t __a = loadword<uint32_t>(__s);
+ const uint64_t __b = loadword<uint32_t>(__s + _Len - 4);
+ return hash_len_16(_Len + (__a << 3), __b);
+}
+
+struct UInt32Hash {
+ UInt32Hash() = default;
+ inline __attribute__((__always_inline__))
+ std::size_t operator()(uint32_t data) const {
+ return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
+ }
+};
+
+struct UInt64Hash {
+ UInt64Hash() = default;
+ inline __attribute__((__always_inline__))
+ std::size_t operator()(uint64_t data) const {
+ return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
+ }
+};
+
+struct UInt128Hash {
+ UInt128Hash() = default;
+ inline __attribute__((__always_inline__))
+ std::size_t operator()(__uint128_t data) const {
+ const __uint128_t __mask = static_cast<std::size_t>(-1);
+ const std::size_t __a = (std::size_t)(data & __mask);
+ const std::size_t __b = (std::size_t)((data & (__mask << 64)) >> 64);
+ return hash_len_16(__a, rotate_by_at_least_1(__b + 16, 16)) ^ __b;
+ }
+};
+
+struct UInt32Hash2 {
+ UInt32Hash2() = default;
+ inline __attribute__((__always_inline__))
+ std::size_t operator()(uint32_t data) const {
+ const uint32_t __m = 0x5bd1e995;
+ const uint32_t __r = 24;
+ uint32_t __h = 4;
+ uint32_t __k = data;
+ __k *= __m;
+ __k ^= __k >> __r;
+ __k *= __m;
+ __h *= __m;
+ __h ^= __k;
+ __h ^= __h >> 13;
+ __h *= __m;
+ __h ^= __h >> 15;
+ return __h;
+ }
+};
+
+struct UInt64Hash2 {
+ UInt64Hash2() = default;
+ inline __attribute__((__always_inline__))
+ std::size_t operator()(uint64_t data) const {
+ return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
+ }
+};
+
+//----------------------------------------------------------------------------//
+// BM_Hash
+// ---------------------------------------------------------------------------//
+
+template <class HashFn, class GenInputs>
+void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
+ auto in = gen(st.range_x());
+ const auto end = in.data() + in.size();
+ std::size_t last_hash = 0;
+ benchmark::DoNotOptimize(&last_hash);
while (st.KeepRunning()) {
- c.clear();
- for (auto it = in.begin(); it != end; ++it) {
- benchmark::DoNotOptimize(c.insert(*it));
+ for (auto it = in.data(); it != end; ++it) {
+ benchmark::DoNotOptimize(last_hash += fn(*it));
}
- benchmark::DoNotOptimize(c);
+ benchmark::ClobberMemory();
}
}
-BENCHMARK_CAPTURE(BM_SetInsert, uint32_insert,
- std::unordered_set<uint32_t>{}, getInputs<uint32_t>(1024));
-template <class Container, class Inputs>
-void BM_SetFind(benchmark::State& st, Container c, Inputs const& in) {
- c.insert(in.begin(), in.end());
- const auto end = in.end();
- while (st.KeepRunning()) {
- for (auto it = in.begin(); it != end; ++it) {
- benchmark::DoNotOptimize(c.find(*it));
- }
- }
-}
-BENCHMARK_CAPTURE(BM_SetFind, uint32_lookup,
- std::unordered_set<uint32_t>{}, getInputs<uint32_t>(1024));
+BENCHMARK_CAPTURE(BM_Hash,
+ uint32_random_std_hash,
+ std::hash<uint32_t>{},
+ getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
+BENCHMARK_CAPTURE(BM_Hash,
+ uint32_random_custom_hash,
+ UInt32Hash{},
+ getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Hash,
+ uint32_top_std_hash,
+ std::hash<uint32_t>{},
+ getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Hash,
+ uint32_top_custom_hash,
+ UInt32Hash{},
+ getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
+
+
+//----------------------------------------------------------------------------//
+// BM_InsertValue
+// ---------------------------------------------------------------------------//
+
+
+// Sorted Assending //
+BENCHMARK_CAPTURE(BM_InsertValue,
+ unordered_set_uint32,
+ std::unordered_set<uint32_t>{},
+ getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_InsertValue,
+ unordered_set_uint32_sorted,
+ std::unordered_set<uint32_t>{},
+ getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+// Top Bytes //
+BENCHMARK_CAPTURE(BM_InsertValue,
+ unordered_set_top_bits_uint32,
+ std::unordered_set<uint32_t>{},
+ getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_InsertValueRehash,
+ unordered_set_top_bits_uint32,
+ std::unordered_set<uint32_t, UInt32Hash>{},
+ getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+// String //
+BENCHMARK_CAPTURE(BM_InsertValue,
+ unordered_set_string,
+ std::unordered_set<std::string>{},
+ getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_InsertValueRehash,
+ unordered_set_string,
+ std::unordered_set<std::string>{},
+ getRandomStringInputs)->Arg(TestNumInputs);
+
+//----------------------------------------------------------------------------//
+// BM_Find
+// ---------------------------------------------------------------------------//
+
+// Random //
+BENCHMARK_CAPTURE(BM_Find,
+ unordered_set_random_uint64,
+ std::unordered_set<uint64_t>{},
+ getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_FindRehash,
+ unordered_set_random_uint64,
+ std::unordered_set<uint64_t, UInt64Hash>{},
+ getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
+
+// Sorted //
+BENCHMARK_CAPTURE(BM_Find,
+ unordered_set_sorted_uint64,
+ std::unordered_set<uint64_t>{},
+ getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_FindRehash,
+ unordered_set_sorted_uint64,
+ std::unordered_set<uint64_t, UInt64Hash>{},
+ getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
+
+
+// Sorted //
+#if 1
+BENCHMARK_CAPTURE(BM_Find,
+ unordered_set_sorted_uint128,
+ std::unordered_set<__uint128_t, UInt128Hash>{},
+ getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_FindRehash,
+ unordered_set_sorted_uint128,
+ std::unordered_set<__uint128_t, UInt128Hash>{},
+ getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
+#endif
+
+// Sorted //
+BENCHMARK_CAPTURE(BM_Find,
+ unordered_set_sorted_uint32,
+ std::unordered_set<uint32_t>{},
+ getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_FindRehash,
+ unordered_set_sorted_uint32,
+ std::unordered_set<uint32_t, UInt32Hash2>{},
+ getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+
+// Sorted Ascending //
+BENCHMARK_CAPTURE(BM_Find,
+ unordered_set_sorted_large_uint64,
+ std::unordered_set<uint64_t>{},
+ getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_FindRehash,
+ unordered_set_sorted_large_uint64,
+ std::unordered_set<uint64_t, UInt64Hash>{},
+ getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
+
+
+// Top Bits //
+BENCHMARK_CAPTURE(BM_Find,
+ unordered_set_top_bits_uint64,
+ std::unordered_set<uint64_t>{},
+ getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_FindRehash,
+ unordered_set_top_bits_uint64,
+ std::unordered_set<uint64_t, UInt64Hash>{},
+ getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
+
+// String //
+BENCHMARK_CAPTURE(BM_Find,
+ unordered_set_string,
+ std::unordered_set<std::string>{},
+ getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_FindRehash,
+ unordered_set_string,
+ std::unordered_set<std::string>{},
+ getRandomStringInputs)->Arg(TestNumInputs);
BENCHMARK_MAIN()