diff options
Diffstat (limited to 'lib/libcxx/benchmarks')
| -rw-r--r-- | lib/libcxx/benchmarks/CMakeLists.txt | 156 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/ContainerBenchmarks.hpp | 113 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/GenerateInput.hpp | 142 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/algorithms.bench.cpp | 62 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/filesystem.bench.cpp | 138 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/string.bench.cpp | 49 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/stringstream.bench.cpp | 38 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/unordered_set_operations.bench.cpp | 316 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/util_smartptr.bench.cpp | 42 | ||||
| -rw-r--r-- | lib/libcxx/benchmarks/vector_operations.bench.cpp | 32 |
10 files changed, 1061 insertions, 27 deletions
diff --git a/lib/libcxx/benchmarks/CMakeLists.txt b/lib/libcxx/benchmarks/CMakeLists.txt new file mode 100644 index 00000000000..8211ebd009a --- /dev/null +++ b/lib/libcxx/benchmarks/CMakeLists.txt @@ -0,0 +1,156 @@ +include(ExternalProject) +include(CheckCXXCompilerFlag) + +#============================================================================== +# Build Google Benchmark for libc++ +#============================================================================== + +set(BENCHMARK_LIBCXX_COMPILE_FLAGS + -Wno-unused-command-line-argument + -nostdinc++ + -isystem ${LIBCXX_SOURCE_DIR}/include + -L${LIBCXX_LIBRARY_DIR} + -Wl,-rpath,${LIBCXX_LIBRARY_DIR} + ) +if (DEFINED LIBCXX_CXX_ABI_LIBRARY_PATH) + list(APPEND BENCHMARK_LIBCXX_COMPILE_FLAGS + -L${LIBCXX_CXX_ABI_LIBRARY_PATH} + -Wl,-rpath,${LIBCXX_CXX_ABI_LIBRARY_PATH}) +endif() +split_list(BENCHMARK_LIBCXX_COMPILE_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_ARGS + -DCMAKE_C_COMPILER:STRING=${CMAKE_C_COMPILER} + -DCMAKE_CXX_COMPILER:STRING=${CMAKE_CXX_COMPILER} + -DCMAKE_BUILD_TYPE:STRING=RELEASE + -DCMAKE_INSTALL_PREFIX:PATH=<INSTALL_DIR> + -DCMAKE_CXX_FLAGS:STRING=${BENCHMARK_LIBCXX_COMPILE_FLAGS} + -DBENCHMARK_USE_LIBCXX:BOOL=ON + -DBENCHMARK_ENABLE_TESTING:BOOL=OFF) + +#============================================================================== +# Build Google Benchmark for the native stdlib +#============================================================================== +set(BENCHMARK_NATIVE_TARGET_FLAGS) +if (LIBCXX_BENCHMARK_NATIVE_GCC_TOOLCHAIN) + set(BENCHMARK_NATIVE_TARGET_FLAGS + -gcc-toolchain ${LIBCXX_BENCHMARK_NATIVE_GCC_TOOLCHAIN}) +endif() +split_list(BENCHMARK_NATIVE_TARGET_FLAGS) + +if (LIBCXX_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 + -DCMAKE_C_COMPILER:STRING=${CMAKE_C_COMPILER} + -DCMAKE_CXX_COMPILER:STRING=${CMAKE_CXX_COMPILER} + -DCMAKE_CXX_FLAGS:STRING=${BENCHMARK_NATIVE_TARGET_FLAGS} + -DCMAKE_BUILD_TYPE:STRING=RELEASE + -DCMAKE_INSTALL_PREFIX:PATH=<INSTALL_DIR> + -DBENCHMARK_ENABLE_TESTING:BOOL=OFF) +endif() + +#============================================================================== +# Benchmark tests configuration +#============================================================================== +add_custom_target(cxx-benchmarks) +set(BENCHMARK_OUTPUT_DIR ${CMAKE_CURRENT_BINARY_DIR}) +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 + -I${LIBCXX_SOURCE_DIR}/test/support +) +set(BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS + -nostdinc++ + -isystem ${LIBCXX_SOURCE_DIR}/include + ${BENCHMARK_TEST_COMPILE_FLAGS} + -Wno-user-defined-literals +) +set(BENCHMARK_TEST_LIBCXX_LINK_FLAGS + -nodefaultlibs + -L${BENCHMARK_LIBCXX_INSTALL}/lib/ +) +set(BENCHMARK_TEST_NATIVE_COMPILE_FLAGS + ${BENCHMARK_NATIVE_TARGET_FLAGS} + ${BENCHMARK_TEST_COMPILE_FLAGS} +) +set(BENCHMARK_TEST_NATIVE_LINK_FLAGS + ${BENCHMARK_NATIVE_TARGET_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_COMPILE_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(cxx-benchmarks ${libcxx_target}) + if (LIBCXX_ENABLE_SHARED) + target_link_libraries(${libcxx_target} cxx_shared) + else() + target_link_libraries(${libcxx_target} cxx_static) + endif() + if (TARGET cxx_experimental) + target_link_libraries(${libcxx_target} cxx_experimental) + endif() + target_link_libraries(${libcxx_target} -lbenchmark) + set_target_properties(${libcxx_target} + PROPERTIES + OUTPUT_NAME "${name}.libcxx.out" + RUNTIME_OUTPUT_DIRECTORY "${BENCHMARK_OUTPUT_DIR}" + COMPILE_FLAGS "${BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS}" + LINK_FLAGS "${BENCHMARK_TEST_LIBCXX_LINK_FLAGS}") + if (LIBCXX_BENCHMARK_NATIVE_STDLIB) + set(native_target ${name}_native) + add_executable(${native_target} EXCLUDE_FROM_ALL ${source_file}) + add_dependencies(${native_target} google-benchmark-native + google-benchmark-libcxx) + target_link_libraries(${native_target} -lbenchmark) + if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++") + target_link_libraries(${native_target} -lstdc++fs) + elseif (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libc++") + target_link_libraries(${native_target} -lc++experimental) + endif() + if (LIBCXX_HAS_PTHREAD_LIB) + target_link_libraries(${native_target} -pthread) + endif() + add_dependencies(cxx-benchmarks ${native_target}) + set_target_properties(${native_target} + PROPERTIES + OUTPUT_NAME "${name}.native.out" + RUNTIME_OUTPUT_DIRECTORY "${BENCHMARK_OUTPUT_DIR}" + INCLUDE_DIRECTORIES "" + COMPILE_FLAGS "${BENCHMARK_TEST_NATIVE_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) + string(REPLACE ".bench.cpp" "" test_name "${test_file}") + if (NOT DEFINED ${test_name}_REPORTED) + message(STATUS "Adding Benchmark: ${test_file}") + # Only report the adding of the benchmark once. + set(${test_name}_REPORTED ON CACHE INTERNAL "") + endif() + add_benchmark_test(${test_name} ${test_file}) +endforeach() diff --git a/lib/libcxx/benchmarks/ContainerBenchmarks.hpp b/lib/libcxx/benchmarks/ContainerBenchmarks.hpp new file mode 100644 index 00000000000..dc268e7ebca --- /dev/null +++ b/lib/libcxx/benchmarks/ContainerBenchmarks.hpp @@ -0,0 +1,113 @@ +#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_ConstructIterIter(benchmark::State& st, Container, GenInputs gen) { + auto in = gen(st.range(0)); + const auto begin = in.begin(); + const auto end = in.end(); + benchmark::DoNotOptimize(&in); + while (st.KeepRunning()) { + Container c(begin, end); + benchmark::DoNotOptimize(c.data()); + } +} + +template <class Container, class GenInputs> +void BM_InsertValue(benchmark::State& st, Container c, GenInputs gen) { + auto in = gen(st.range(0)); + 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(0)); + 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> +void BM_InsertDuplicate(benchmark::State& st, Container c, GenInputs gen) { + auto in = gen(st.range(0)); + const auto end = in.end(); + c.insert(in.begin(), in.end()); + benchmark::DoNotOptimize(&c); + benchmark::DoNotOptimize(&in); + while (st.KeepRunning()) { + for (auto it = in.begin(); it != end; ++it) { + benchmark::DoNotOptimize(&(*c.insert(*it).first)); + } + benchmark::ClobberMemory(); + } +} + + +template <class Container, class GenInputs> +void BM_EmplaceDuplicate(benchmark::State& st, Container c, GenInputs gen) { + auto in = gen(st.range(0)); + const auto end = in.end(); + c.insert(in.begin(), in.end()); + benchmark::DoNotOptimize(&c); + benchmark::DoNotOptimize(&in); + while (st.KeepRunning()) { + for (auto it = in.begin(); it != end; ++it) { + benchmark::DoNotOptimize(&(*c.emplace(*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(0)); + 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(0)); + 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/lib/libcxx/benchmarks/GenerateInput.hpp b/lib/libcxx/benchmarks/GenerateInput.hpp new file mode 100644 index 00000000000..9d5adac4af4 --- /dev/null +++ b/lib/libcxx/benchmarks/GenerateInput.hpp @@ -0,0 +1,142 @@ +#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 (size_t 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; +} + +inline std::vector<const char*> getRandomCStringInputs(size_t N) { + static std::vector<std::string> inputs = getRandomStringInputs(N); + std::vector<const char*> cinputs; + for (auto const& str : inputs) + cinputs.push_back(str.c_str()); + return cinputs; +} + + +#endif // BENCHMARK_GENERATE_INPUT_HPP diff --git a/lib/libcxx/benchmarks/algorithms.bench.cpp b/lib/libcxx/benchmarks/algorithms.bench.cpp new file mode 100644 index 00000000000..745cc172718 --- /dev/null +++ b/lib/libcxx/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(0)); + 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/lib/libcxx/benchmarks/filesystem.bench.cpp b/lib/libcxx/benchmarks/filesystem.bench.cpp new file mode 100644 index 00000000000..f7949a163a7 --- /dev/null +++ b/lib/libcxx/benchmarks/filesystem.bench.cpp @@ -0,0 +1,138 @@ +#include <experimental/filesystem> + +#include "benchmark/benchmark_api.h" +#include "GenerateInput.hpp" +#include "test_iterators.h" + +namespace fs = std::experimental::filesystem; + +static const size_t TestNumInputs = 1024; + + +template <class GenInputs> +void BM_PathConstructString(benchmark::State &st, GenInputs gen) { + using namespace fs; + const auto in = gen(st.range(0)); + path PP; + for (auto& Part : in) + PP /= Part; + benchmark::DoNotOptimize(PP.native().data()); + while (st.KeepRunning()) { + const path P(PP.native()); + benchmark::DoNotOptimize(P.native().data()); + } +} +BENCHMARK_CAPTURE(BM_PathConstructString, large_string, + getRandomStringInputs)->Arg(TestNumInputs); + + +template <class GenInputs> +void BM_PathConstructCStr(benchmark::State &st, GenInputs gen) { + using namespace fs; + const auto in = gen(st.range(0)); + path PP; + for (auto& Part : in) + PP /= Part; + benchmark::DoNotOptimize(PP.native().data()); + while (st.KeepRunning()) { + const path P(PP.native().c_str()); + benchmark::DoNotOptimize(P.native().data()); + } +} +BENCHMARK_CAPTURE(BM_PathConstructCStr, large_string, + getRandomStringInputs)->Arg(TestNumInputs); + + +template <template <class...> class ItType, class GenInputs> +void BM_PathConstructIter(benchmark::State &st, GenInputs gen) { + using namespace fs; + using Iter = ItType<std::string::const_iterator>; + const auto in = gen(st.range(0)); + path PP; + for (auto& Part : in) + PP /= Part; + auto Start = Iter(PP.native().begin()); + auto End = Iter(PP.native().end()); + benchmark::DoNotOptimize(PP.native().data()); + benchmark::DoNotOptimize(Start); + benchmark::DoNotOptimize(End); + while (st.KeepRunning()) { + const path P(Start, End); + benchmark::DoNotOptimize(P.native().data()); + } +} +template <class GenInputs> +void BM_PathConstructInputIter(benchmark::State &st, GenInputs gen) { + BM_PathConstructIter<input_iterator>(st, gen); +} +template <class GenInputs> +void BM_PathConstructForwardIter(benchmark::State &st, GenInputs gen) { + BM_PathConstructIter<forward_iterator>(st, gen); +} +BENCHMARK_CAPTURE(BM_PathConstructInputIter, large_string, + getRandomStringInputs)->Arg(TestNumInputs); +BENCHMARK_CAPTURE(BM_PathConstructForwardIter, large_string, + getRandomStringInputs)->Arg(TestNumInputs); + + +template <class GenInputs> +void BM_PathIterateMultipleTimes(benchmark::State &st, GenInputs gen) { + using namespace fs; + const auto in = gen(st.range(0)); + path PP; + for (auto& Part : in) + PP /= Part; + benchmark::DoNotOptimize(PP.native().data()); + while (st.KeepRunning()) { + for (auto &E : PP) { + benchmark::DoNotOptimize(E.native().data()); + } + benchmark::ClobberMemory(); + } +} +BENCHMARK_CAPTURE(BM_PathIterateMultipleTimes, iterate_elements, + getRandomStringInputs)->Arg(TestNumInputs); + + +template <class GenInputs> +void BM_PathIterateOnce(benchmark::State &st, GenInputs gen) { + using namespace fs; + const auto in = gen(st.range(0)); + path PP; + for (auto& Part : in) + PP /= Part; + benchmark::DoNotOptimize(PP.native().data()); + while (st.KeepRunning()) { + const path P = PP.native(); + for (auto &E : P) { + benchmark::DoNotOptimize(E.native().data()); + } + benchmark::ClobberMemory(); + } +} +BENCHMARK_CAPTURE(BM_PathIterateOnce, iterate_elements, + getRandomStringInputs)->Arg(TestNumInputs); + +template <class GenInputs> +void BM_PathIterateOnceBackwards(benchmark::State &st, GenInputs gen) { + using namespace fs; + const auto in = gen(st.range(0)); + path PP; + for (auto& Part : in) + PP /= Part; + benchmark::DoNotOptimize(PP.native().data()); + while (st.KeepRunning()) { + const path P = PP.native(); + const auto B = P.begin(); + auto I = P.end(); + while (I != B) { + --I; + benchmark::DoNotOptimize(*I); + } + benchmark::DoNotOptimize(*I); + } +} +BENCHMARK_CAPTURE(BM_PathIterateOnceBackwards, iterate_elements, + getRandomStringInputs)->Arg(TestNumInputs); + +BENCHMARK_MAIN() diff --git a/lib/libcxx/benchmarks/string.bench.cpp b/lib/libcxx/benchmarks/string.bench.cpp new file mode 100644 index 00000000000..ef892391688 --- /dev/null +++ b/lib/libcxx/benchmarks/string.bench.cpp @@ -0,0 +1,49 @@ +#include <unordered_set> +#include <vector> +#include <cstdint> + +#include "benchmark/benchmark_api.h" +#include "GenerateInput.hpp" + +constexpr std::size_t MAX_STRING_LEN = 8 << 14; + +// Benchmark when there is no match. +static void BM_StringFindNoMatch(benchmark::State &state) { + std::string s1(state.range(0), '-'); + std::string s2(8, '*'); + while (state.KeepRunning()) + benchmark::DoNotOptimize(s1.find(s2)); +} +BENCHMARK(BM_StringFindNoMatch)->Range(10, MAX_STRING_LEN); + +// Benchmark when the string matches first time. +static void BM_StringFindAllMatch(benchmark::State &state) { + std::string s1(MAX_STRING_LEN, '-'); + std::string s2(state.range(0), '-'); + while (state.KeepRunning()) + benchmark::DoNotOptimize(s1.find(s2)); +} +BENCHMARK(BM_StringFindAllMatch)->Range(1, MAX_STRING_LEN); + +// Benchmark when the string matches somewhere in the end. +static void BM_StringFindMatch1(benchmark::State &state) { + std::string s1(MAX_STRING_LEN / 2, '*'); + s1 += std::string(state.range(0), '-'); + std::string s2(state.range(0), '-'); + while (state.KeepRunning()) + benchmark::DoNotOptimize(s1.find(s2)); +} +BENCHMARK(BM_StringFindMatch1)->Range(1, MAX_STRING_LEN / 4); + +// Benchmark when the string matches somewhere from middle to the end. +static void BM_StringFindMatch2(benchmark::State &state) { + std::string s1(MAX_STRING_LEN / 2, '*'); + s1 += std::string(state.range(0), '-'); + s1 += std::string(state.range(0), '*'); + std::string s2(state.range(0), '-'); + while (state.KeepRunning()) + benchmark::DoNotOptimize(s1.find(s2)); +} +BENCHMARK(BM_StringFindMatch2)->Range(1, MAX_STRING_LEN / 4); + +BENCHMARK_MAIN() diff --git a/lib/libcxx/benchmarks/stringstream.bench.cpp b/lib/libcxx/benchmarks/stringstream.bench.cpp new file mode 100644 index 00000000000..6023cf775bc --- /dev/null +++ b/lib/libcxx/benchmarks/stringstream.bench.cpp @@ -0,0 +1,38 @@ +#include "benchmark/benchmark_api.h" + +#include <sstream> +double __attribute__((noinline)) istream_numbers(); + +double istream_numbers() { + const char *a[] = { + "-6 69 -71 2.4882e-02 -100 101 -2.00005 5000000 -50000000", + "-25 71 7 -9.3262e+01 -100 101 -2.00005 5000000 -50000000", + "-14 53 46 -6.7026e-02 -100 101 -2.00005 5000000 -50000000" + }; + + int a1, a2, a3, a4, a5, a6, a7; + double f1 = 0.0, f2 = 0.0, q = 0.0; + for (int i=0; i < 3; i++) { + std::istringstream s(a[i]); + s >> a1 + >> a2 + >> a3 + >> f1 + >> a4 + >> a5 + >> f2 + >> a6 + >> a7; + q += (a1 + a2 + a3 + a4 + a5 + a6 + a7 + f1 + f2)/1000000; + } + return q; +} + +static void BM_Istream_numbers(benchmark::State &state) { + double i = 0; + while (state.KeepRunning()) + benchmark::DoNotOptimize(i += istream_numbers()); +} + +BENCHMARK(BM_Istream_numbers)->RangeMultiplier(2)->Range(1024, 4096); +BENCHMARK_MAIN() diff --git a/lib/libcxx/benchmarks/unordered_set_operations.bench.cpp b/lib/libcxx/benchmarks/unordered_set_operations.bench.cpp index c9ee689f69d..e2afdde56dc 100644 --- a/lib/libcxx/benchmarks/unordered_set_operations.bench.cpp +++ b/lib/libcxx/benchmarks/unordered_set_operations.bench.cpp @@ -1,44 +1,306 @@ #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(); - while (st.KeepRunning()) { - c.clear(); - for (auto it = in.begin(); it != end; ++it) { - benchmark::DoNotOptimize(c.insert(*it)); - } - benchmark::DoNotOptimize(c); - } +inline __attribute__((__always_inline__)) +std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) { + return (__val >> __shift) | (__val << (64 - __shift)); } -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(); +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(0)); + const auto end = in.data() + in.size(); + std::size_t last_hash = 0; + benchmark::DoNotOptimize(&last_hash); while (st.KeepRunning()) { - for (auto it = in.begin(); it != end; ++it) { - benchmark::DoNotOptimize(c.find(*it)); + for (auto it = in.data(); it != end; ++it) { + benchmark::DoNotOptimize(last_hash += fn(*it)); } + benchmark::ClobberMemory(); } } -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_CAPTURE(BM_InsertDuplicate, + unordered_set_int, + std::unordered_set<int>{}, + getRandomIntegerInputs<int>)->Arg(TestNumInputs); +BENCHMARK_CAPTURE(BM_InsertDuplicate, + unordered_set_string, + std::unordered_set<std::string>{}, + getRandomStringInputs)->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_EmplaceDuplicate, + unordered_set_int, + std::unordered_set<int>{}, + getRandomIntegerInputs<int>)->Arg(TestNumInputs); +BENCHMARK_CAPTURE(BM_EmplaceDuplicate, + unordered_set_string, + std::unordered_set<std::string>{}, + getRandomStringInputs)->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_InsertDuplicate, + unordered_set_int_insert_arg, + std::unordered_set<int>{}, + getRandomIntegerInputs<int>)->Arg(TestNumInputs); +BENCHMARK_CAPTURE(BM_InsertDuplicate, + unordered_set_string_insert_arg, + std::unordered_set<std::string>{}, + getRandomStringInputs)->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_EmplaceDuplicate, + unordered_set_int_insert_arg, + std::unordered_set<int>{}, + getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_EmplaceDuplicate, + unordered_set_string_arg, + std::unordered_set<std::string>{}, + getRandomCStringInputs)->Arg(TestNumInputs); BENCHMARK_MAIN() diff --git a/lib/libcxx/benchmarks/util_smartptr.bench.cpp b/lib/libcxx/benchmarks/util_smartptr.bench.cpp new file mode 100644 index 00000000000..ad3f03a0448 --- /dev/null +++ b/lib/libcxx/benchmarks/util_smartptr.bench.cpp @@ -0,0 +1,42 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include <memory> + +#include "benchmark/benchmark_api.h" + +static void BM_SharedPtrCreateDestroy(benchmark::State& st) { + while (st.KeepRunning()) { + auto sp = std::make_shared<int>(42); + benchmark::DoNotOptimize(sp.get()); + } +} +BENCHMARK(BM_SharedPtrCreateDestroy); + +static void BM_SharedPtrIncDecRef(benchmark::State& st) { + auto sp = std::make_shared<int>(42); + benchmark::DoNotOptimize(sp.get()); + while (st.KeepRunning()) { + std::shared_ptr<int> sp2(sp); + benchmark::ClobberMemory(); + } +} +BENCHMARK(BM_SharedPtrIncDecRef); + +static void BM_WeakPtrIncDecRef(benchmark::State& st) { + auto sp = std::make_shared<int>(42); + benchmark::DoNotOptimize(sp.get()); + while (st.KeepRunning()) { + std::weak_ptr<int> wp(sp); + benchmark::ClobberMemory(); + } +} +BENCHMARK(BM_WeakPtrIncDecRef); + +BENCHMARK_MAIN() diff --git a/lib/libcxx/benchmarks/vector_operations.bench.cpp b/lib/libcxx/benchmarks/vector_operations.bench.cpp new file mode 100644 index 00000000000..004e801f0be --- /dev/null +++ b/lib/libcxx/benchmarks/vector_operations.bench.cpp @@ -0,0 +1,32 @@ +#include <vector> +#include <functional> +#include <cstdint> +#include <cstdlib> +#include <cstring> + +#include "benchmark/benchmark_api.h" + +#include "ContainerBenchmarks.hpp" +#include "GenerateInput.hpp" + +using namespace ContainerBenchmarks; + +constexpr std::size_t TestNumInputs = 1024; + +BENCHMARK_CAPTURE(BM_ConstructIterIter, + vector_char, + std::vector<char>{}, + getRandomIntegerInputs<char>)->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_ConstructIterIter, + vector_size_t, + std::vector<size_t>{}, + getRandomIntegerInputs<size_t>)->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_ConstructIterIter, + vector_string, + std::vector<std::string>{}, + getRandomStringInputs)->Arg(TestNumInputs); + + +BENCHMARK_MAIN() |