diff options
Diffstat (limited to 'gnu/llvm/libcxx/benchmarks')
19 files changed, 2929 insertions, 0 deletions
diff --git a/gnu/llvm/libcxx/benchmarks/CMakeLists.txt b/gnu/llvm/libcxx/benchmarks/CMakeLists.txt new file mode 100644 index 00000000000..bd38de97d7a --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/CMakeLists.txt @@ -0,0 +1,219 @@ +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} + ${SANITIZER_FLAGS} + ) +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() +if (LIBCXX_NEEDS_SITE_CONFIG) + list(APPEND BENCHMARK_LIBCXX_COMPILE_FLAGS -include "${LIBCXX_BINARY_DIR}/__config_site") +endif() +split_list(BENCHMARK_LIBCXX_COMPILE_FLAGS) + +ExternalProject_Add(google-benchmark-libcxx + EXCLUDE_FROM_ALL ON + DEPENDS cxx cxx-headers + 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) + +check_flag_supported("-std=c++17") +mangle_name("LIBCXX_SUPPORTS_STD_EQ_c++17_FLAG" BENCHMARK_SUPPORTS_STD_CXX17_FLAG) +if (${BENCHMARK_SUPPORTS_STD_CXX17_FLAG}) + set(BENCHMARK_DIALECT_FLAG "-std=c++17") +else() + # If the compiler doesn't support -std=c++17, attempt to fall back to -std=c++1z while still + # requiring C++17 language features. + set(BENCHMARK_DIALECT_FLAG "-std=c++1z") +endif() + +set(BENCHMARK_TEST_COMPILE_FLAGS + ${BENCHMARK_DIALECT_FLAG} -O2 + -fsized-deallocation + -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} + ${SANITIZER_FLAGS} + -Wno-user-defined-literals +) + +set(BENCHMARK_TEST_LIBCXX_LINK_FLAGS + -nodefaultlibs + -L${BENCHMARK_LIBCXX_INSTALL}/lib/ + ${SANITIZER_FLAGS} +) +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) + +if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++") + find_library(LIBSTDCXX_FILESYSTEM_TEST stdc++fs + PATHS ${LIBCXX_BENCHMARK_NATIVE_GCC_TOOLCHAIN} + PATH_SUFFIXES lib lib64 + DOC "The libstdc++ filesystem library used by the benchmarks" + ) + if (NOT "${LIBSTDCXX_FILESYSTEM_TEST}" STREQUAL "LIBSTDCXX_FILESYSTEM_TEST-NOTFOUND") + set(LIBSTDCXX_FILESYSTEM_LIB "stdc++fs") + endif() +endif() + +set(libcxx_benchmark_targets) + +function(add_benchmark_test name source_file) + set(libcxx_target ${name}_libcxx) + list(APPEND libcxx_benchmark_targets ${libcxx_target}) + add_executable(${libcxx_target} EXCLUDE_FROM_ALL ${source_file}) + add_dependencies(${libcxx_target} cxx cxx-headers google-benchmark-libcxx) + add_dependencies(cxx-benchmarks ${libcxx_target}) + if (LIBCXX_ENABLE_SHARED) + target_link_libraries(${libcxx_target} PRIVATE cxx_shared) + else() + target_link_libraries(${libcxx_target} PRIVATE cxx_static) + endif() + if (TARGET cxx_experimental) + target_link_libraries(${libcxx_target} PRIVATE cxx_experimental) + endif() + target_link_libraries(${libcxx_target} PRIVATE -lbenchmark) + if (LLVM_USE_SANITIZER) + target_link_libraries(${libcxx_target} PRIVATE -ldl) + endif() + 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}") + cxx_link_system_libraries(${libcxx_target}) + if (LIBCXX_BENCHMARK_NATIVE_STDLIB) + if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++" AND NOT DEFINED LIBSTDCXX_FILESYSTEM_LIB + AND "${name}" STREQUAL "filesystem") + return() + endif() + 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} PRIVATE -lbenchmark) + if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++") + target_link_libraries(${native_target} PRIVATE ${LIBSTDCXX_FILESYSTEM_LIB}) + elseif (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libc++") + target_link_libraries(${native_target} PRIVATE -lc++fs -lc++experimental) + endif() + if (LIBCXX_HAS_PTHREAD_LIB) + target_link_libraries(${native_target} PRIVATE -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() +endfunction() + + +#============================================================================== +# 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() + +if (LIBCXX_INCLUDE_TESTS) + include(AddLLVM) + + if (NOT DEFINED LIBCXX_TEST_DEPS) + message(FATAL_ERROR "Expected LIBCXX_TEST_DEPS to be defined") + endif() + + configure_lit_site_cfg( + ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.py.in + ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg.py) + + set(BENCHMARK_LIT_ARGS "--show-all --show-xfail --show-unsupported ${LIT_ARGS_DEFAULT}") + + add_lit_target(check-cxx-benchmarks + "Running libcxx benchmarks tests" + ${CMAKE_CURRENT_BINARY_DIR} + DEPENDS cxx-benchmarks ${LIBCXX_TEST_DEPS} + ARGS ${BENCHMARK_LIT_ARGS}) +endif() diff --git a/gnu/llvm/libcxx/benchmarks/CartesianBenchmarks.h b/gnu/llvm/libcxx/benchmarks/CartesianBenchmarks.h new file mode 100644 index 00000000000..2eea1568193 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/CartesianBenchmarks.h @@ -0,0 +1,133 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + + +#include <string> +#include <tuple> +#include <type_traits> +#include <vector> + +#include "benchmark/benchmark.h" +#include "test_macros.h" + +namespace internal { + +template <class D, class E, size_t I> +struct EnumValue : std::integral_constant<E, static_cast<E>(I)> { + static std::string name() { return std::string("_") + D::Names[I]; } +}; + +template <class D, class E, size_t ...Idxs> +constexpr auto makeEnumValueTuple(std::index_sequence<Idxs...>) { + return std::make_tuple(EnumValue<D, E, Idxs>{}...); +} + +template <class B> +static auto skip(const B& Bench, int) -> decltype(Bench.skip()) { + return Bench.skip(); +} +template <class B> +static auto skip(const B& Bench, char) { + return false; +} + +template <class B, class Args, size_t... Is> +void makeBenchmarkFromValuesImpl(const Args& A, std::index_sequence<Is...>) { + for (auto& V : A) { + B Bench{std::get<Is>(V)...}; + if (!internal::skip(Bench, 0)) { + benchmark::RegisterBenchmark(Bench.name().c_str(), + [=](benchmark::State& S) { Bench.run(S); }); + } + } +} + +template <class B, class... Args> +void makeBenchmarkFromValues(const std::vector<std::tuple<Args...> >& A) { + makeBenchmarkFromValuesImpl<B>(A, std::index_sequence_for<Args...>()); +} + +template <template <class...> class B, class Args, class... U> +void makeBenchmarkImpl(const Args& A, std::tuple<U...> t) { + makeBenchmarkFromValues<B<U...> >(A); +} + +template <template <class...> class B, class Args, class... U, + class... T, class... Tuples> +void makeBenchmarkImpl(const Args& A, std::tuple<U...>, std::tuple<T...>, + Tuples... rest) { + (internal::makeBenchmarkImpl<B>(A, std::tuple<U..., T>(), rest...), ...); +} + +template <class R, class T> +void allValueCombinations(R& Result, const T& Final) { + return Result.push_back(Final); +} + +template <class R, class T, class V, class... Vs> +void allValueCombinations(R& Result, const T& Prev, const V& Value, + const Vs&... Values) { + for (const auto& E : Value) { + allValueCombinations(Result, std::tuple_cat(Prev, std::make_tuple(E)), + Values...); + } +} + +} // namespace internal + +// CRTP class that enables using enum types as a dimension for +// makeCartesianProductBenchmark below. +// The type passed to `B` will be a std::integral_constant<E, e>, with the +// additional static function `name()` that returns the stringified name of the +// label. +// +// Eg: +// enum class MyEnum { A, B }; +// struct AllMyEnum : EnumValuesAsTuple<AllMyEnum, MyEnum, 2> { +// static constexpr absl::string_view Names[] = {"A", "B"}; +// }; +template <class Derived, class EnumType, size_t NumLabels> +using EnumValuesAsTuple = + decltype(internal::makeEnumValueTuple<Derived, EnumType>( + std::make_index_sequence<NumLabels>{})); + +// Instantiates B<T0, T1, ..., TN> where <Ti...> are the combinations in the +// cartesian product of `Tuples...`, and pass (arg0, ..., argN) as constructor +// arguments where `(argi...)` are the combination in the cartesian product of +// the runtime values of `A...`. +// B<T...> requires: +// - std::string name(args...): The name of the benchmark. +// - void run(benchmark::State&, args...): The body of the benchmark. +// It can also optionally provide: +// - bool skip(args...): When `true`, skips the combination. Default is false. +// +// Returns int to facilitate registration. The return value is unspecified. +template <template <class...> class B, class... Tuples, class... Args> +int makeCartesianProductBenchmark(const Args&... A) { + std::vector<std::tuple<typename Args::value_type...> > V; + internal::allValueCombinations(V, std::tuple<>(), A...); + internal::makeBenchmarkImpl<B>(V, std::tuple<>(), Tuples()...); + return 0; +} + +template <class B, class... Args> +int makeCartesianProductBenchmark(const Args&... A) { + std::vector<std::tuple<typename Args::value_type...> > V; + internal::allValueCombinations(V, std::tuple<>(), A...); + internal::makeBenchmarkFromValues<B>(V); + return 0; +} + +// When `opaque` is true, this function hides the runtime state of `value` from +// the optimizer. +// It returns `value`. +template <class T> +TEST_ALWAYS_INLINE inline T maybeOpaque(T value, bool opaque) { + if (opaque) benchmark::DoNotOptimize(value); + return value; +} diff --git a/gnu/llvm/libcxx/benchmarks/ContainerBenchmarks.h b/gnu/llvm/libcxx/benchmarks/ContainerBenchmarks.h new file mode 100644 index 00000000000..d2061f28853 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/ContainerBenchmarks.h @@ -0,0 +1,140 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef BENCHMARK_CONTAINER_BENCHMARKS_H +#define BENCHMARK_CONTAINER_BENCHMARKS_H + +#include <cassert> + +#include "Utilities.h" +#include "benchmark/benchmark.h" + +namespace ContainerBenchmarks { + +template <class Container> +void BM_ConstructSize(benchmark::State& st, Container) { + auto size = st.range(0); + for (auto _ : st) { + Container c(size); + DoNotOptimizeData(c); + } +} + +template <class Container> +void BM_ConstructSizeValue(benchmark::State& st, Container, typename Container::value_type const& val) { + const auto size = st.range(0); + for (auto _ : st) { + Container c(size, val); + DoNotOptimizeData(c); + } +} + +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); + DoNotOptimizeData(c); + } +} + +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_H diff --git a/gnu/llvm/libcxx/benchmarks/GenerateInput.h b/gnu/llvm/libcxx/benchmarks/GenerateInput.h new file mode 100644 index 00000000000..e4f131c628f --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/GenerateInput.h @@ -0,0 +1,144 @@ +#ifndef BENCHMARK_GENERATE_INPUT_H +#define BENCHMARK_GENERATE_INPUT_H + +#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(IntT Min = 0, + IntT Max = std::numeric_limits<IntT>::max()) { + std::uniform_int_distribution<IntT> dist(Min, Max); + 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_H diff --git a/gnu/llvm/libcxx/benchmarks/Utilities.h b/gnu/llvm/libcxx/benchmarks/Utilities.h new file mode 100644 index 00000000000..9ad2a58796e --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/Utilities.h @@ -0,0 +1,33 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef BENCHMARK_UTILITIES_H +#define BENCHMARK_UTILITIES_H + +#include <cassert> +#include <type_traits> + +#include "benchmark/benchmark.h" + +namespace UtilitiesInternal { + template <class Container> + auto HaveDataImpl(int) -> decltype((std::declval<Container&>().data(), std::true_type{})); + template <class Container> + auto HaveDataImpl(long) -> std::false_type; + template <class T> + using HasData = decltype(HaveDataImpl<T>(0)); +} // namespace UtilitiesInternal + +template <class Container, std::enable_if_t<UtilitiesInternal::HasData<Container>::value>* = nullptr> +void DoNotOptimizeData(Container &c) { benchmark::DoNotOptimize(c.data()); } +template <class Container, std::enable_if_t<!UtilitiesInternal::HasData<Container>::value>* = nullptr> +void DoNotOptimizeData(Container &c) { benchmark::DoNotOptimize(&c); } + + +#endif // BENCHMARK_UTILITIES_H diff --git a/gnu/llvm/libcxx/benchmarks/algorithms.bench.cpp b/gnu/llvm/libcxx/benchmarks/algorithms.bench.cpp new file mode 100644 index 00000000000..b259d476457 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/algorithms.bench.cpp @@ -0,0 +1,276 @@ + +#include <algorithm> +#include <cstdint> +#include <map> +#include <random> +#include <string> +#include <utility> +#include <vector> + +#include "CartesianBenchmarks.h" +#include "GenerateInput.h" +#include "benchmark/benchmark.h" +#include "test_macros.h" + +namespace { + +enum class ValueType { Uint32, String }; +struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> { + static constexpr const char* Names[] = {"uint32", "string"}; +}; + +template <class V> +using Value = + std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>; + +enum class Order { + Random, + Ascending, + Descending, + SingleElement, + PipeOrgan, + Heap +}; +struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> { + static constexpr const char* Names[] = {"Random", "Ascending", + "Descending", "SingleElement", + "PipeOrgan", "Heap"}; +}; + +void fillValues(std::vector<uint32_t>& V, size_t N, Order O) { + if (O == Order::SingleElement) { + V.resize(N, 0); + } else { + while (V.size() < N) + V.push_back(V.size()); + } +} + +void fillValues(std::vector<std::string>& V, size_t N, Order O) { + + if (O == Order::SingleElement) { + V.resize(N, getRandomString(1024)); + } else { + while (V.size() < N) + V.push_back(getRandomString(1024)); + } +} + +template <class T> +void sortValues(T& V, Order O) { + assert(std::is_sorted(V.begin(), V.end())); + switch (O) { + case Order::Random: { + std::random_device R; + std::mt19937 M(R()); + std::shuffle(V.begin(), V.end(), M); + break; + } + case Order::Ascending: + std::sort(V.begin(), V.end()); + break; + case Order::Descending: + std::sort(V.begin(), V.end(), std::greater<>()); + break; + case Order::SingleElement: + // Nothing to do + break; + case Order::PipeOrgan: + std::sort(V.begin(), V.end()); + std::reverse(V.begin() + V.size() / 2, V.end()); + break; + case Order::Heap: + std::make_heap(V.begin(), V.end()); + break; + } +} + +template <class ValueType> +std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N, + Order O) { + // Let's make sure that all random sequences of the same size are the same. + // That way we can compare the different algorithms with the same input. + static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > > + Cached; + + auto& Values = Cached[{N, O}]; + if (Values.empty()) { + fillValues(Values, N, O); + sortValues(Values, O); + }; + const size_t NumCopies = std::max(size_t{1}, 1000 / N); + return { NumCopies, Values }; +} + +template <class T, class U> +TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies, + U& Orig) { + state.PauseTiming(); + for (auto& Copy : Copies) + Copy = Orig; + state.ResumeTiming(); +} + +template <class ValueType, class F> +void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O, + bool CountElements, F f) { + auto Copies = makeOrderedValues<ValueType>(Quantity, O); + const auto Orig = Copies[0]; + + const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size(); + while (state.KeepRunningBatch(Batch)) { + for (auto& Copy : Copies) { + f(Copy); + benchmark::DoNotOptimize(Copy); + } + resetCopies(state, Copies, Orig); + } +} + +template <class ValueType, class Order> +struct Sort { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { + std::sort(Copy.begin(), Copy.end()); + }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_Sort" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; + +template <class ValueType, class Order> +struct StableSort { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { + std::stable_sort(Copy.begin(), Copy.end()); + }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_StableSort" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; + +template <class ValueType, class Order> +struct MakeHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { + std::make_heap(Copy.begin(), Copy.end()); + }); + } + + std::string name() const { + return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; + +template <class ValueType> +struct SortHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>( + state, Quantity, Order::Heap, false, + [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); }); + } + + std::string name() const { + return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity); + }; +}; + +template <class ValueType, class Order> +struct MakeThenSortHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { + std::make_heap(Copy.begin(), Copy.end()); + std::sort_heap(Copy.begin(), Copy.end()); + }); + } + + std::string name() const { + return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; + +template <class ValueType, class Order> +struct PushHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) { + for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) { + std::push_heap(Copy.begin(), I + 1); + } + }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_PushHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; + +template <class ValueType> +struct PopHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) { + for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) { + std::pop_heap(B, I); + } + }); + } + + std::string name() const { + return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity); + }; +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + const std::vector<size_t> Quantities = {1 << 0, 1 << 2, 1 << 4, 1 << 6, + 1 << 8, 1 << 10, 1 << 14, + // Running each benchmark in parallel consumes too much memory with MSAN + // and can lead to the test process being killed. +#if !TEST_HAS_FEATURE(memory_sanitizer) + 1 << 18 +#endif + }; + makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities); + makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>( + Quantities); + makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities); + makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities); + makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>( + Quantities); + makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities); + makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/gnu/llvm/libcxx/benchmarks/algorithms.partition_point.bench.cpp b/gnu/llvm/libcxx/benchmarks/algorithms.partition_point.bench.cpp new file mode 100644 index 00000000000..840cf0391ee --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/algorithms.partition_point.bench.cpp @@ -0,0 +1,124 @@ +#include <array> +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <tuple> +#include <vector> + +#include "benchmark/benchmark.h" + +#include "CartesianBenchmarks.h" +#include "GenerateInput.h" + +namespace { + +template <typename I, typename N> +std::array<I, 10> every_10th_percentile_N(I first, N n) { + N step = n / 10; + std::array<I, 10> res; + + for (size_t i = 0; i < 10; ++i) { + res[i] = first; + std::advance(first, step); + } + + return res; +} + +template <class IntT> +struct TestIntBase { + static std::vector<IntT> generateInput(size_t size) { + std::vector<IntT> Res(size); + std::generate(Res.begin(), Res.end(), + [] { return getRandomInteger<IntT>(); }); + return Res; + } +}; + +struct TestInt32 : TestIntBase<std::int32_t> { + static constexpr const char* Name = "TestInt32"; +}; + +struct TestInt64 : TestIntBase<std::int64_t> { + static constexpr const char* Name = "TestInt64"; +}; + +struct TestUint32 : TestIntBase<std::uint32_t> { + static constexpr const char* Name = "TestUint32"; +}; + +struct TestMediumString { + static constexpr const char* Name = "TestMediumString"; + static constexpr size_t StringSize = 32; + + static std::vector<std::string> generateInput(size_t size) { + std::vector<std::string> Res(size); + std::generate(Res.begin(), Res.end(), [] { return getRandomString(StringSize); }); + return Res; + } +}; + +using AllTestTypes = std::tuple<TestInt32, TestInt64, TestUint32, TestMediumString>; + +struct LowerBoundAlg { + template <class I, class V> + I operator()(I first, I last, const V& value) const { + return std::lower_bound(first, last, value); + } + + static constexpr const char* Name = "LowerBoundAlg"; +}; + +struct UpperBoundAlg { + template <class I, class V> + I operator()(I first, I last, const V& value) const { + return std::upper_bound(first, last, value); + } + + static constexpr const char* Name = "UpperBoundAlg"; +}; + +struct EqualRangeAlg { + template <class I, class V> + std::pair<I, I> operator()(I first, I last, const V& value) const { + return std::equal_range(first, last, value); + } + + static constexpr const char* Name = "EqualRangeAlg"; +}; + +using AllAlgs = std::tuple<LowerBoundAlg, UpperBoundAlg, EqualRangeAlg>; + +template <class Alg, class TestType> +struct PartitionPointBench { + size_t Quantity; + + std::string name() const { + return std::string("PartitionPointBench_") + Alg::Name + "_" + + TestType::Name + '/' + std::to_string(Quantity); + } + + void run(benchmark::State& state) const { + auto Data = TestType::generateInput(Quantity); + std::sort(Data.begin(), Data.end()); + auto Every10Percentile = every_10th_percentile_N(Data.begin(), Data.size()); + + for (auto _ : state) { + for (auto Test : Every10Percentile) + benchmark::DoNotOptimize(Alg{}(Data.begin(), Data.end(), *Test)); + } + } +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + const std::vector<size_t> Quantities = {1 << 8, 1 << 10, 1 << 20}; + makeCartesianProductBenchmark<PartitionPointBench, AllAlgs, AllTestTypes>( + Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/gnu/llvm/libcxx/benchmarks/allocation.bench.cpp b/gnu/llvm/libcxx/benchmarks/allocation.bench.cpp new file mode 100644 index 00000000000..236e74044a5 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/allocation.bench.cpp @@ -0,0 +1,136 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "benchmark/benchmark.h" + +#include <new> +#include <vector> +#include <cassert> + +struct PointerList { + PointerList* Next = nullptr; +}; + +struct MallocWrapper { + __attribute__((always_inline)) + static void* Allocate(size_t N) { + return std::malloc(N); + } + __attribute__((always_inline)) + static void Deallocate(void* P, size_t) { + std::free(P); + } +}; + +struct NewWrapper { + __attribute__((always_inline)) + static void* Allocate(size_t N) { + return ::operator new(N); + } + __attribute__((always_inline)) + static void Deallocate(void* P, size_t) { + ::operator delete(P); + } +}; + +struct BuiltinNewWrapper { + __attribute__((always_inline)) + static void* Allocate(size_t N) { + return __builtin_operator_new(N); + } + __attribute__((always_inline)) + static void Deallocate(void* P, size_t) { + __builtin_operator_delete(P); + } +}; + +struct BuiltinSizedNewWrapper { + __attribute__((always_inline)) + static void* Allocate(size_t N) { + return __builtin_operator_new(N); + } + __attribute__((always_inline)) + static void Deallocate(void* P, size_t N) { + __builtin_operator_delete(P, N); + } +}; + + +template <class AllocWrapper> +static void BM_AllocateAndDeallocate(benchmark::State& st) { + const size_t alloc_size = st.range(0); + while (st.KeepRunning()) { + void* p = AllocWrapper::Allocate(alloc_size); + benchmark::DoNotOptimize(p); + AllocWrapper::Deallocate(p, alloc_size); + } +} + + +template <class AllocWrapper> +static void BM_AllocateOnly(benchmark::State& st) { + const size_t alloc_size = st.range(0); + PointerList *Start = nullptr; + + while (st.KeepRunning()) { + PointerList* p = (PointerList*)AllocWrapper::Allocate(alloc_size); + benchmark::DoNotOptimize(p); + p->Next = Start; + Start = p; + } + + PointerList *Next = Start; + while (Next) { + PointerList *Tmp = Next; + Next = Tmp->Next; + AllocWrapper::Deallocate(Tmp, alloc_size); + } +} + +template <class AllocWrapper> +static void BM_DeallocateOnly(benchmark::State& st) { + const size_t alloc_size = st.range(0); + const auto NumAllocs = st.max_iterations; + + using PtrT = void*; + std::vector<void*> Pointers(NumAllocs); + for (auto& p : Pointers) { + p = AllocWrapper::Allocate(alloc_size); + } + + void** Data = Pointers.data(); + void** const End = Pointers.data() + Pointers.size(); + while (st.KeepRunning()) { + AllocWrapper::Deallocate(*Data, alloc_size); + Data += 1; + } + assert(Data == End); +} + +static int RegisterAllocBenchmarks() { + using FnType = void(*)(benchmark::State&); + struct { + const char* name; + FnType func; + } TestCases[] = { + {"BM_Malloc", &BM_AllocateAndDeallocate<MallocWrapper>}, + {"BM_New", &BM_AllocateAndDeallocate<NewWrapper>}, + {"BM_BuiltinNewDelete", BM_AllocateAndDeallocate<BuiltinNewWrapper>}, + {"BM_BuiltinSizedNewDelete", BM_AllocateAndDeallocate<BuiltinSizedNewWrapper>}, + {"BM_BuiltinNewAllocateOnly", BM_AllocateOnly<BuiltinSizedNewWrapper>}, + {"BM_BuiltinNewSizedDeallocateOnly", BM_DeallocateOnly<BuiltinSizedNewWrapper>}, + + }; + for (auto TC : TestCases) { + benchmark::RegisterBenchmark(TC.name, TC.func)->Range(16, 4096 * 2); + } + return 0; +} +int Sink = RegisterAllocBenchmarks(); + +BENCHMARK_MAIN(); diff --git a/gnu/llvm/libcxx/benchmarks/deque.bench.cpp b/gnu/llvm/libcxx/benchmarks/deque.bench.cpp new file mode 100644 index 00000000000..0025a335ccf --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/deque.bench.cpp @@ -0,0 +1,47 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include <deque> + +#include "benchmark/benchmark.h" + +#include "ContainerBenchmarks.h" +#include "GenerateInput.h" + +using namespace ContainerBenchmarks; + +constexpr std::size_t TestNumInputs = 1024; + +BENCHMARK_CAPTURE(BM_ConstructSize, + deque_byte, + std::deque<unsigned char>{})->Arg(5140480); + +BENCHMARK_CAPTURE(BM_ConstructSizeValue, + deque_byte, + std::deque<unsigned char>{}, 0)->Arg(5140480); + +BENCHMARK_CAPTURE(BM_ConstructIterIter, + deque_char, + std::deque<char>{}, + getRandomIntegerInputs<char>)->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_ConstructIterIter, + deque_size_t, + std::deque<size_t>{}, + getRandomIntegerInputs<size_t>)->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_ConstructIterIter, + deque_string, + std::deque<std::string>{}, + getRandomStringInputs)->Arg(TestNumInputs); + + + + +BENCHMARK_MAIN(); diff --git a/gnu/llvm/libcxx/benchmarks/filesystem.bench.cpp b/gnu/llvm/libcxx/benchmarks/filesystem.bench.cpp new file mode 100644 index 00000000000..64314ac5ab0 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/filesystem.bench.cpp @@ -0,0 +1,163 @@ +#include "benchmark/benchmark.h" +#include "GenerateInput.h" +#include "test_iterators.h" +#include "filesystem_include.h" + +static const size_t TestNumInputs = 1024; + + +template <class GenInputs> +void BM_PathConstructString(benchmark::State &st, GenInputs gen) { + using fs::path; + 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()); + } + st.SetComplexityN(st.range(0)); +} +BENCHMARK_CAPTURE(BM_PathConstructString, large_string, + getRandomStringInputs)->Range(8, TestNumInputs)->Complexity(); + + +template <class GenInputs> +void BM_PathConstructCStr(benchmark::State &st, GenInputs gen) { + using fs::path; + 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 fs::path; + 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()); + } + st.SetComplexityN(st.range(0)); +} +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)->Range(8, TestNumInputs)->Complexity(); +BENCHMARK_CAPTURE(BM_PathConstructForwardIter, large_string, + getRandomStringInputs)->Range(8, TestNumInputs)->Complexity(); + + +template <class GenInputs> +void BM_PathIterateMultipleTimes(benchmark::State &st, GenInputs gen) { + using fs::path; + 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(); + } + st.SetComplexityN(st.range(0)); +} +BENCHMARK_CAPTURE(BM_PathIterateMultipleTimes, iterate_elements, + getRandomStringInputs)->Range(8, TestNumInputs)->Complexity(); + + +template <class GenInputs> +void BM_PathIterateOnce(benchmark::State &st, GenInputs gen) { + using fs::path; + 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(); + } + st.SetComplexityN(st.range(0)); +} +BENCHMARK_CAPTURE(BM_PathIterateOnce, iterate_elements, + getRandomStringInputs)->Range(8, TestNumInputs)->Complexity(); + +template <class GenInputs> +void BM_PathIterateOnceBackwards(benchmark::State &st, GenInputs gen) { + using fs::path; + 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); + +static fs::path getRandomPaths(int NumParts, int PathLen) { + fs::path Result; + while (NumParts--) { + std::string Part = getRandomString(PathLen); + Result /= Part; + } + return Result; +} + +template <class GenInput> +void BM_LexicallyNormal(benchmark::State &st, GenInput gen, size_t PathLen) { + using fs::path; + auto In = gen(st.range(0), PathLen); + benchmark::DoNotOptimize(&In); + while (st.KeepRunning()) { + benchmark::DoNotOptimize(In.lexically_normal()); + } + st.SetComplexityN(st.range(0)); +} +BENCHMARK_CAPTURE(BM_LexicallyNormal, small_path, + getRandomPaths, /*PathLen*/5)->RangeMultiplier(2)->Range(2, 256)->Complexity(); +BENCHMARK_CAPTURE(BM_LexicallyNormal, large_path, + getRandomPaths, /*PathLen*/32)->RangeMultiplier(2)->Range(2, 256)->Complexity(); + +BENCHMARK_MAIN(); diff --git a/gnu/llvm/libcxx/benchmarks/function.bench.cpp b/gnu/llvm/libcxx/benchmarks/function.bench.cpp new file mode 100644 index 00000000000..7fabc937dd9 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/function.bench.cpp @@ -0,0 +1,231 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include <cstdint> +#include <functional> +#include <memory> +#include <string> + +#include "CartesianBenchmarks.h" +#include "benchmark/benchmark.h" +#include "test_macros.h" + +namespace { + +enum class FunctionType { + Null, + FunctionPointer, + MemberFunctionPointer, + MemberPointer, + SmallTrivialFunctor, + SmallNonTrivialFunctor, + LargeTrivialFunctor, + LargeNonTrivialFunctor +}; + +struct AllFunctionTypes : EnumValuesAsTuple<AllFunctionTypes, FunctionType, 8> { + static constexpr const char* Names[] = {"Null", + "FuncPtr", + "MemFuncPtr", + "MemPtr", + "SmallTrivialFunctor", + "SmallNonTrivialFunctor", + "LargeTrivialFunctor", + "LargeNonTrivialFunctor"}; +}; + +enum class Opacity { kOpaque, kTransparent }; + +struct AllOpacity : EnumValuesAsTuple<AllOpacity, Opacity, 2> { + static constexpr const char* Names[] = {"Opaque", "Transparent"}; +}; + +struct S { + int function() const { return 0; } + int field = 0; +}; + +int FunctionWithS(const S*) { return 0; } + +struct SmallTrivialFunctor { + int operator()(const S*) const { return 0; } +}; +struct SmallNonTrivialFunctor { + SmallNonTrivialFunctor() {} + SmallNonTrivialFunctor(const SmallNonTrivialFunctor&) {} + ~SmallNonTrivialFunctor() {} + int operator()(const S*) const { return 0; } +}; +struct LargeTrivialFunctor { + LargeTrivialFunctor() { + // Do not spend time initializing the padding. + } + int padding[16]; + int operator()(const S*) const { return 0; } +}; +struct LargeNonTrivialFunctor { + int padding[16]; + LargeNonTrivialFunctor() { + // Do not spend time initializing the padding. + } + LargeNonTrivialFunctor(const LargeNonTrivialFunctor&) {} + ~LargeNonTrivialFunctor() {} + int operator()(const S*) const { return 0; } +}; + +using Function = std::function<int(const S*)>; + +TEST_ALWAYS_INLINE +inline Function MakeFunction(FunctionType type, bool opaque = false) { + switch (type) { + case FunctionType::Null: + return nullptr; + case FunctionType::FunctionPointer: + return maybeOpaque(FunctionWithS, opaque); + case FunctionType::MemberFunctionPointer: + return maybeOpaque(&S::function, opaque); + case FunctionType::MemberPointer: + return maybeOpaque(&S::field, opaque); + case FunctionType::SmallTrivialFunctor: + return maybeOpaque(SmallTrivialFunctor{}, opaque); + case FunctionType::SmallNonTrivialFunctor: + return maybeOpaque(SmallNonTrivialFunctor{}, opaque); + case FunctionType::LargeTrivialFunctor: + return maybeOpaque(LargeTrivialFunctor{}, opaque); + case FunctionType::LargeNonTrivialFunctor: + return maybeOpaque(LargeNonTrivialFunctor{}, opaque); + } +} + +template <class Opacity, class FunctionType> +struct ConstructAndDestroy { + static void run(benchmark::State& state) { + for (auto _ : state) { + if (Opacity() == ::Opacity::kOpaque) { + benchmark::DoNotOptimize(MakeFunction(FunctionType(), true)); + } else { + MakeFunction(FunctionType()); + } + } + } + + static std::string name() { + return "BM_ConstructAndDestroy" + FunctionType::name() + Opacity::name(); + } +}; + +template <class FunctionType> +struct Copy { + static void run(benchmark::State& state) { + auto value = MakeFunction(FunctionType()); + for (auto _ : state) { + benchmark::DoNotOptimize(value); + auto copy = value; // NOLINT + benchmark::DoNotOptimize(copy); + } + } + + static std::string name() { return "BM_Copy" + FunctionType::name(); } +}; + +template <class FunctionType> +struct Move { + static void run(benchmark::State& state) { + Function values[2] = {MakeFunction(FunctionType())}; + int i = 0; + for (auto _ : state) { + benchmark::DoNotOptimize(values); + benchmark::DoNotOptimize(values[i ^ 1] = std::move(values[i])); + i ^= 1; + } + } + + static std::string name() { + return "BM_Move" + FunctionType::name(); + } +}; + +template <class Function1, class Function2> +struct Swap { + static void run(benchmark::State& state) { + Function values[2] = {MakeFunction(Function1()), MakeFunction(Function2())}; + for (auto _ : state) { + benchmark::DoNotOptimize(values); + values[0].swap(values[1]); + } + } + + static bool skip() { return Function1() > Function2(); } + + static std::string name() { + return "BM_Swap" + Function1::name() + Function2::name(); + } +}; + +template <class FunctionType> +struct OperatorBool { + static void run(benchmark::State& state) { + auto f = MakeFunction(FunctionType()); + for (auto _ : state) { + benchmark::DoNotOptimize(f); + benchmark::DoNotOptimize(static_cast<bool>(f)); + } + } + + static std::string name() { return "BM_OperatorBool" + FunctionType::name(); } +}; + +template <class FunctionType> +struct Invoke { + static void run(benchmark::State& state) { + S s; + const auto value = MakeFunction(FunctionType()); + for (auto _ : state) { + benchmark::DoNotOptimize(value); + benchmark::DoNotOptimize(value(&s)); + } + } + + static bool skip() { return FunctionType() == ::FunctionType::Null; } + + static std::string name() { return "BM_Invoke" + FunctionType::name(); } +}; + +template <class FunctionType> +struct InvokeInlined { + static void run(benchmark::State& state) { + S s; + for (auto _ : state) { + MakeFunction(FunctionType())(&s); + } + } + + static bool skip() { return FunctionType() == ::FunctionType::Null; } + + static std::string name() { + return "BM_InvokeInlined" + FunctionType::name(); + } +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + makeCartesianProductBenchmark<ConstructAndDestroy, AllOpacity, + AllFunctionTypes>(); + makeCartesianProductBenchmark<Copy, AllFunctionTypes>(); + makeCartesianProductBenchmark<Move, AllFunctionTypes>(); + makeCartesianProductBenchmark<Swap, AllFunctionTypes, AllFunctionTypes>(); + makeCartesianProductBenchmark<OperatorBool, AllFunctionTypes>(); + makeCartesianProductBenchmark<Invoke, AllFunctionTypes>(); + makeCartesianProductBenchmark<InvokeInlined, AllFunctionTypes>(); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/gnu/llvm/libcxx/benchmarks/lit.cfg.py b/gnu/llvm/libcxx/benchmarks/lit.cfg.py new file mode 100644 index 00000000000..84857d570d7 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/lit.cfg.py @@ -0,0 +1,23 @@ +# -*- Python -*- vim: set ft=python ts=4 sw=4 expandtab tw=79: +# Configuration file for the 'lit' test runner. +import os +import site + +site.addsitedir(os.path.join(os.path.dirname(os.path.dirname(__file__)), 'utils')) +from libcxx.test.googlebenchmark import GoogleBenchmark + +# Tell pylint that we know config and lit_config exist somewhere. +if 'PYLINT_IMPORT' in os.environ: + config = object() + lit_config = object() + +# name: The name of this test suite. +config.name = 'libc++ benchmarks' +config.suffixes = [] + +config.test_exec_root = os.path.join(config.libcxx_obj_root, 'benchmarks') +config.test_source_root = config.test_exec_root + +config.test_format = GoogleBenchmark(test_sub_dirs='.', + test_suffix='.libcxx.out', + benchmark_args=config.benchmark_args)
\ No newline at end of file diff --git a/gnu/llvm/libcxx/benchmarks/lit.site.cfg.py.in b/gnu/llvm/libcxx/benchmarks/lit.site.cfg.py.in new file mode 100644 index 00000000000..e3ce8b22263 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/lit.site.cfg.py.in @@ -0,0 +1,10 @@ +@LIT_SITE_CFG_IN_HEADER@ + +import sys + +config.libcxx_src_root = "@LIBCXX_SOURCE_DIR@" +config.libcxx_obj_root = "@LIBCXX_BINARY_DIR@" +config.benchmark_args = "@LIBCXX_BENCHMARK_TEST_ARGS@".split(';') + +# Let the main config do the real work. +lit_config.load_config(config, "@LIBCXX_SOURCE_DIR@/benchmarks/lit.cfg.py")
\ No newline at end of file diff --git a/gnu/llvm/libcxx/benchmarks/ordered_set.bench.cpp b/gnu/llvm/libcxx/benchmarks/ordered_set.bench.cpp new file mode 100644 index 00000000000..a9d9c929ac6 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/ordered_set.bench.cpp @@ -0,0 +1,248 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include <algorithm> +#include <cstdint> +#include <memory> +#include <random> +#include <set> +#include <string> +#include <vector> + +#include "CartesianBenchmarks.h" +#include "benchmark/benchmark.h" +#include "test_macros.h" + +namespace { + +enum class HitType { Hit, Miss }; + +struct AllHitTypes : EnumValuesAsTuple<AllHitTypes, HitType, 2> { + static constexpr const char* Names[] = {"Hit", "Miss"}; +}; + +enum class AccessPattern { Ordered, Random }; + +struct AllAccessPattern + : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> { + static constexpr const char* Names[] = {"Ordered", "Random"}; +}; + +void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) { + if (AP == AccessPattern::Random) { + std::random_device R; + std::mt19937 M(R()); + std::shuffle(std::begin(Keys), std::end(Keys), M); + } +} + +struct TestSets { + std::vector<std::set<uint64_t> > Sets; + std::vector<uint64_t> Keys; +}; + +TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit, + AccessPattern Access) { + TestSets R; + R.Sets.resize(1); + + for (uint64_t I = 0; I < TableSize; ++I) { + R.Sets[0].insert(2 * I); + R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1); + } + R.Sets.resize(NumTables, R.Sets[0]); + sortKeysBy(R.Keys, Access); + + return R; +} + +struct Base { + size_t TableSize; + size_t NumTables; + Base(size_t T, size_t N) : TableSize(T), NumTables(N) {} + + bool skip() const { + size_t Total = TableSize * NumTables; + return Total < 100 || Total > 1000000; + } + + std::string baseName() const { + return "_TableSize" + std::to_string(TableSize) + "_NumTables" + + std::to_string(NumTables); + } +}; + +template <class Access> +struct Create : Base { + using Base::Base; + + void run(benchmark::State& State) const { + std::vector<uint64_t> Keys(TableSize); + std::iota(Keys.begin(), Keys.end(), uint64_t{0}); + sortKeysBy(Keys, Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + std::vector<std::set<uint64_t>> Sets(NumTables); + for (auto K : Keys) { + for (auto& Set : Sets) { + benchmark::DoNotOptimize(Set.insert(K)); + } + } + } + } + + std::string name() const { + return "BM_Create" + Access::name() + baseName(); + } +}; + +template <class Hit, class Access> +struct Find : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto K : Data.Keys) { + for (auto& Set : Data.Sets) { + benchmark::DoNotOptimize(Set.find(K)); + } + } + } + } + + std::string name() const { + return "BM_Find" + Hit::name() + Access::name() + baseName(); + } +}; + +template <class Hit, class Access> +struct FindNeEnd : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto K : Data.Keys) { + for (auto& Set : Data.Sets) { + benchmark::DoNotOptimize(Set.find(K) != Set.end()); + } + } + } + } + + std::string name() const { + return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName(); + } +}; + +template <class Access> +struct InsertHit : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto K : Data.Keys) { + for (auto& Set : Data.Sets) { + benchmark::DoNotOptimize(Set.insert(K)); + } + } + } + } + + std::string name() const { + return "BM_InsertHit" + Access::name() + baseName(); + } +}; + +template <class Access> +struct InsertMissAndErase : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto K : Data.Keys) { + for (auto& Set : Data.Sets) { + benchmark::DoNotOptimize(Set.erase(Set.insert(K).first)); + } + } + } + } + + std::string name() const { + return "BM_InsertMissAndErase" + Access::name() + baseName(); + } +}; + +struct IterateRangeFor : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, + AccessPattern::Ordered); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto& Set : Data.Sets) { + for (auto& V : Set) { + benchmark::DoNotOptimize(V); + } + } + } + } + + std::string name() const { return "BM_IterateRangeFor" + baseName(); } +}; + +struct IterateBeginEnd : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, + AccessPattern::Ordered); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto& Set : Data.Sets) { + for (auto it = Set.begin(); it != Set.end(); ++it) { + benchmark::DoNotOptimize(*it); + } + } + } + } + + std::string name() const { return "BM_IterateBeginEnd" + baseName(); } +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000}; + const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000}; + + makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables); + makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>( + TableSize, NumTables); + makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>( + TableSize, NumTables); + makeCartesianProductBenchmark<InsertHit, AllAccessPattern>( + TableSize, NumTables); + makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>( + TableSize, NumTables); + makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables); + makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/gnu/llvm/libcxx/benchmarks/string.bench.cpp b/gnu/llvm/libcxx/benchmarks/string.bench.cpp new file mode 100644 index 00000000000..fe8a1c533d9 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/string.bench.cpp @@ -0,0 +1,574 @@ + +#include <cstdint> +#include <new> +#include <vector> + +#include "CartesianBenchmarks.h" +#include "GenerateInput.h" +#include "benchmark/benchmark.h" +#include "test_macros.h" + +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, '*'); + for (auto _ : state) + 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), '-'); + for (auto _ : state) + 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), '-'); + for (auto _ : state) + 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), '-'); + for (auto _ : state) + benchmark::DoNotOptimize(s1.find(s2)); +} +BENCHMARK(BM_StringFindMatch2)->Range(1, MAX_STRING_LEN / 4); + +static void BM_StringCtorDefault(benchmark::State &state) { + for (auto _ : state) { + std::string Default; + benchmark::DoNotOptimize(Default); + } +} +BENCHMARK(BM_StringCtorDefault); + +enum class Length { Empty, Small, Large, Huge }; +struct AllLengths : EnumValuesAsTuple<AllLengths, Length, 4> { + static constexpr const char* Names[] = {"Empty", "Small", "Large", "Huge"}; +}; + +enum class Opacity { Opaque, Transparent }; +struct AllOpacity : EnumValuesAsTuple<AllOpacity, Opacity, 2> { + static constexpr const char* Names[] = {"Opaque", "Transparent"}; +}; + +enum class DiffType { Control, ChangeFirst, ChangeMiddle, ChangeLast }; +struct AllDiffTypes : EnumValuesAsTuple<AllDiffTypes, DiffType, 4> { + static constexpr const char* Names[] = {"Control", "ChangeFirst", + "ChangeMiddle", "ChangeLast"}; +}; + +static constexpr char SmallStringLiteral[] = "012345678"; + +TEST_ALWAYS_INLINE const char* getSmallString(DiffType D) { + switch (D) { + case DiffType::Control: + return SmallStringLiteral; + case DiffType::ChangeFirst: + return "-12345678"; + case DiffType::ChangeMiddle: + return "0123-5678"; + case DiffType::ChangeLast: + return "01234567-"; + } +} + +static constexpr char LargeStringLiteral[] = + "012345678901234567890123456789012345678901234567890123456789012"; + +TEST_ALWAYS_INLINE const char* getLargeString(DiffType D) { +#define LARGE_STRING_FIRST "123456789012345678901234567890" +#define LARGE_STRING_SECOND "234567890123456789012345678901" + switch (D) { + case DiffType::Control: + return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2"; + case DiffType::ChangeFirst: + return "-" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2"; + case DiffType::ChangeMiddle: + return "0" LARGE_STRING_FIRST "-" LARGE_STRING_SECOND "2"; + case DiffType::ChangeLast: + return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "-"; + } +} + +TEST_ALWAYS_INLINE const char* getHugeString(DiffType D) { +#define HUGE_STRING0 "0123456789" +#define HUGE_STRING1 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0 +#define HUGE_STRING2 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1 +#define HUGE_STRING3 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2 +#define HUGE_STRING4 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3 + switch (D) { + case DiffType::Control: + return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789"; + case DiffType::ChangeFirst: + return "-123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789"; + case DiffType::ChangeMiddle: + return "0123456789" HUGE_STRING4 "01234-6789" HUGE_STRING4 "0123456789"; + case DiffType::ChangeLast: + return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "012345678-"; + } +} + +TEST_ALWAYS_INLINE const char* getString(Length L, + DiffType D = DiffType::Control) { + switch (L) { + case Length::Empty: + return ""; + case Length::Small: + return getSmallString(D); + case Length::Large: + return getLargeString(D); + case Length::Huge: + return getHugeString(D); + } +} + +TEST_ALWAYS_INLINE std::string makeString(Length L, + DiffType D = DiffType::Control, + Opacity O = Opacity::Transparent) { + switch (L) { + case Length::Empty: + return maybeOpaque("", O == Opacity::Opaque); + case Length::Small: + return maybeOpaque(getSmallString(D), O == Opacity::Opaque); + case Length::Large: + return maybeOpaque(getLargeString(D), O == Opacity::Opaque); + case Length::Huge: + return maybeOpaque(getHugeString(D), O == Opacity::Opaque); + } +} + +template <class Length, class Opaque> +struct StringConstructDestroyCStr { + static void run(benchmark::State& state) { + for (auto _ : state) { + benchmark::DoNotOptimize( + makeString(Length(), DiffType::Control, Opaque())); + } + } + + static std::string name() { + return "BM_StringConstructDestroyCStr" + Length::name() + Opaque::name(); + } +}; + +template <class Length, bool MeasureCopy, bool MeasureDestroy> +static void StringCopyAndDestroy(benchmark::State& state) { + static constexpr size_t NumStrings = 1024; + auto Orig = makeString(Length()); + std::aligned_storage<sizeof(std::string)>::type Storage[NumStrings]; + + while (state.KeepRunningBatch(NumStrings)) { + if (!MeasureCopy) + state.PauseTiming(); + for (size_t I = 0; I < NumStrings; ++I) { + ::new (static_cast<void*>(Storage + I)) std::string(Orig); + } + if (!MeasureCopy) + state.ResumeTiming(); + if (!MeasureDestroy) + state.PauseTiming(); + for (size_t I = 0; I < NumStrings; ++I) { + using S = std::string; + reinterpret_cast<S*>(Storage + I)->~S(); + } + if (!MeasureDestroy) + state.ResumeTiming(); + } +} + +template <class Length> +struct StringCopy { + static void run(benchmark::State& state) { + StringCopyAndDestroy<Length, true, false>(state); + } + + static std::string name() { return "BM_StringCopy" + Length::name(); } +}; + +template <class Length> +struct StringDestroy { + static void run(benchmark::State& state) { + StringCopyAndDestroy<Length, false, true>(state); + } + + static std::string name() { return "BM_StringDestroy" + Length::name(); } +}; + +template <class Length> +struct StringMove { + static void run(benchmark::State& state) { + // Keep two object locations and move construct back and forth. + std::aligned_storage<sizeof(std::string), alignof(std::string)>::type Storage[2]; + using S = std::string; + size_t I = 0; + S *newS = new (static_cast<void*>(Storage)) std::string(makeString(Length())); + for (auto _ : state) { + // Switch locations. + I ^= 1; + benchmark::DoNotOptimize(Storage); + // Move construct into the new location, + S *tmpS = new (static_cast<void*>(Storage + I)) S(std::move(*newS)); + // then destroy the old one. + newS->~S(); + newS = tmpS; + } + newS->~S(); + } + + static std::string name() { return "BM_StringMove" + Length::name(); } +}; + +template <class Length, class Opaque> +struct StringResizeDefaultInit { + static void run(benchmark::State& state) { + constexpr bool opaque = Opaque{} == Opacity::Opaque; + constexpr int kNumStrings = 4 << 10; + size_t length = makeString(Length()).size(); + std::string strings[kNumStrings]; + while (state.KeepRunningBatch(kNumStrings)) { + state.PauseTiming(); + for (int i = 0; i < kNumStrings; ++i) { + std::string().swap(strings[i]); + } + benchmark::DoNotOptimize(strings); + state.ResumeTiming(); + for (int i = 0; i < kNumStrings; ++i) { + strings[i].__resize_default_init(maybeOpaque(length, opaque)); + } + } + } + + static std::string name() { + return "BM_StringResizeDefaultInit" + Length::name() + Opaque::name(); + } +}; + +template <class Length, class Opaque> +struct StringAssignStr { + static void run(benchmark::State& state) { + constexpr bool opaque = Opaque{} == Opacity::Opaque; + constexpr int kNumStrings = 4 << 10; + std::string src = makeString(Length()); + std::string strings[kNumStrings]; + while (state.KeepRunningBatch(kNumStrings)) { + state.PauseTiming(); + for (int i = 0; i < kNumStrings; ++i) { + std::string().swap(strings[i]); + } + benchmark::DoNotOptimize(strings); + state.ResumeTiming(); + for (int i = 0; i < kNumStrings; ++i) { + strings[i] = *maybeOpaque(&src, opaque); + } + } + } + + static std::string name() { + return "BM_StringAssignStr" + Length::name() + Opaque::name(); + } +}; + +template <class Length, class Opaque> +struct StringAssignAsciiz { + static void run(benchmark::State& state) { + constexpr bool opaque = Opaque{} == Opacity::Opaque; + constexpr int kNumStrings = 4 << 10; + std::string strings[kNumStrings]; + while (state.KeepRunningBatch(kNumStrings)) { + state.PauseTiming(); + for (int i = 0; i < kNumStrings; ++i) { + std::string().swap(strings[i]); + } + benchmark::DoNotOptimize(strings); + state.ResumeTiming(); + for (int i = 0; i < kNumStrings; ++i) { + strings[i] = maybeOpaque(getString(Length()), opaque); + } + } + } + + static std::string name() { + return "BM_StringAssignAsciiz" + Length::name() + Opaque::name(); + } +}; + +template <class Opaque> +struct StringAssignAsciizMix { + static void run(benchmark::State& state) { + constexpr auto O = Opaque{}; + constexpr auto D = DiffType::Control; + constexpr int kNumStrings = 4 << 10; + std::string strings[kNumStrings]; + while (state.KeepRunningBatch(kNumStrings)) { + state.PauseTiming(); + for (int i = 0; i < kNumStrings; ++i) { + std::string().swap(strings[i]); + } + benchmark::DoNotOptimize(strings); + state.ResumeTiming(); + for (int i = 0; i < kNumStrings - 7; i += 8) { + strings[i + 0] = maybeOpaque(getSmallString(D), O == Opacity::Opaque); + strings[i + 1] = maybeOpaque(getSmallString(D), O == Opacity::Opaque); + strings[i + 2] = maybeOpaque(getLargeString(D), O == Opacity::Opaque); + strings[i + 3] = maybeOpaque(getSmallString(D), O == Opacity::Opaque); + strings[i + 4] = maybeOpaque(getSmallString(D), O == Opacity::Opaque); + strings[i + 5] = maybeOpaque(getSmallString(D), O == Opacity::Opaque); + strings[i + 6] = maybeOpaque(getLargeString(D), O == Opacity::Opaque); + strings[i + 7] = maybeOpaque(getSmallString(D), O == Opacity::Opaque); + } + } + } + + static std::string name() { + return "BM_StringAssignAsciizMix" + Opaque::name(); + } +}; + +enum class Relation { Eq, Less, Compare }; +struct AllRelations : EnumValuesAsTuple<AllRelations, Relation, 3> { + static constexpr const char* Names[] = {"Eq", "Less", "Compare"}; +}; + +template <class Rel, class LHLength, class RHLength, class DiffType> +struct StringRelational { + static void run(benchmark::State& state) { + auto Lhs = makeString(RHLength()); + auto Rhs = makeString(LHLength(), DiffType()); + for (auto _ : state) { + benchmark::DoNotOptimize(Lhs); + benchmark::DoNotOptimize(Rhs); + switch (Rel()) { + case Relation::Eq: + benchmark::DoNotOptimize(Lhs == Rhs); + break; + case Relation::Less: + benchmark::DoNotOptimize(Lhs < Rhs); + break; + case Relation::Compare: + benchmark::DoNotOptimize(Lhs.compare(Rhs)); + break; + } + } + } + + static bool skip() { + // Eq is commutative, so skip half the matrix. + if (Rel() == Relation::Eq && LHLength() > RHLength()) + return true; + // We only care about control when the lengths differ. + if (LHLength() != RHLength() && DiffType() != ::DiffType::Control) + return true; + // For empty, only control matters. + if (LHLength() == Length::Empty && DiffType() != ::DiffType::Control) + return true; + return false; + } + + static std::string name() { + return "BM_StringRelational" + Rel::name() + LHLength::name() + + RHLength::name() + DiffType::name(); + } +}; + +template <class Rel, class LHLength, class RHLength, class DiffType> +struct StringRelationalLiteral { + static void run(benchmark::State& state) { + auto Lhs = makeString(LHLength(), DiffType()); + for (auto _ : state) { + benchmark::DoNotOptimize(Lhs); + constexpr const char* Literal = RHLength::value == Length::Empty + ? "" + : RHLength::value == Length::Small + ? SmallStringLiteral + : LargeStringLiteral; + switch (Rel()) { + case Relation::Eq: + benchmark::DoNotOptimize(Lhs == Literal); + break; + case Relation::Less: + benchmark::DoNotOptimize(Lhs < Literal); + break; + case Relation::Compare: + benchmark::DoNotOptimize(Lhs.compare(Literal)); + break; + } + } + } + + static bool skip() { + // Doesn't matter how they differ if they have different size. + if (LHLength() != RHLength() && DiffType() != ::DiffType::Control) + return true; + // We don't need huge. Doensn't give anything different than Large. + if (LHLength() == Length::Huge || RHLength() == Length::Huge) + return true; + return false; + } + + static std::string name() { + return "BM_StringRelationalLiteral" + Rel::name() + LHLength::name() + + RHLength::name() + DiffType::name(); + } +}; + +enum class Depth { Shallow, Deep }; +struct AllDepths : EnumValuesAsTuple<AllDepths, Depth, 2> { + static constexpr const char* Names[] = {"Shallow", "Deep"}; +}; + +enum class Temperature { Hot, Cold }; +struct AllTemperatures : EnumValuesAsTuple<AllTemperatures, Temperature, 2> { + static constexpr const char* Names[] = {"Hot", "Cold"}; +}; + +template <class Temperature, class Depth, class Length> +struct StringRead { + void run(benchmark::State& state) const { + static constexpr size_t NumStrings = + Temperature() == ::Temperature::Hot + ? 1 << 10 + : /* Enough strings to overflow the cache */ 1 << 20; + static_assert((NumStrings & (NumStrings - 1)) == 0, + "NumStrings should be a power of two to reduce overhead."); + + std::vector<std::string> Values(NumStrings, makeString(Length())); + size_t I = 0; + for (auto _ : state) { + // Jump long enough to defeat cache locality, and use a value that is + // coprime with NumStrings to ensure we visit every element. + I = (I + 17) % NumStrings; + const auto& V = Values[I]; + + // Read everything first. Escaping data() through DoNotOptimize might + // cause the compiler to have to recalculate information about `V` due to + // aliasing. + const char* const Data = V.data(); + const size_t Size = V.size(); + benchmark::DoNotOptimize(Data); + benchmark::DoNotOptimize(Size); + if (Depth() == ::Depth::Deep) { + // Read into the payload. This mainly shows the benefit of SSO when the + // data is cold. + benchmark::DoNotOptimize(*Data); + } + } + } + + static bool skip() { + // Huge does not give us anything that Large doesn't have. Skip it. + if (Length() == ::Length::Huge) { + return true; + } + return false; + } + + std::string name() const { + return "BM_StringRead" + Temperature::name() + Depth::name() + + Length::name(); + } +}; + +void sanityCheckGeneratedStrings() { + for (auto Lhs : {Length::Empty, Length::Small, Length::Large, Length::Huge}) { + const auto LhsString = makeString(Lhs); + for (auto Rhs : + {Length::Empty, Length::Small, Length::Large, Length::Huge}) { + if (Lhs > Rhs) + continue; + const auto RhsString = makeString(Rhs); + + // The smaller one must be a prefix of the larger one. + if (RhsString.find(LhsString) != 0) { + fprintf(stderr, "Invalid autogenerated strings for sizes (%d,%d).\n", + static_cast<int>(Lhs), static_cast<int>(Rhs)); + std::abort(); + } + } + } + // Verify the autogenerated diffs + for (auto L : {Length::Small, Length::Large, Length::Huge}) { + const auto Control = makeString(L); + const auto Verify = [&](std::string Exp, size_t Pos) { + // Only change on the Pos char. + if (Control[Pos] != Exp[Pos]) { + Exp[Pos] = Control[Pos]; + if (Control == Exp) + return; + } + fprintf(stderr, "Invalid autogenerated diff with size %d\n", + static_cast<int>(L)); + std::abort(); + }; + Verify(makeString(L, DiffType::ChangeFirst), 0); + Verify(makeString(L, DiffType::ChangeMiddle), Control.size() / 2); + Verify(makeString(L, DiffType::ChangeLast), Control.size() - 1); + } +} + +// Some small codegen thunks to easily see generated code. +bool StringEqString(const std::string& a, const std::string& b) { + return a == b; +} +bool StringEqCStr(const std::string& a, const char* b) { return a == b; } +bool CStrEqString(const char* a, const std::string& b) { return a == b; } +bool StringEqCStrLiteralEmpty(const std::string& a) { + return a == ""; +} +bool StringEqCStrLiteralSmall(const std::string& a) { + return a == SmallStringLiteral; +} +bool StringEqCStrLiteralLarge(const std::string& a) { + return a == LargeStringLiteral; +} + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + sanityCheckGeneratedStrings(); + + makeCartesianProductBenchmark<StringConstructDestroyCStr, AllLengths, + AllOpacity>(); + + makeCartesianProductBenchmark<StringAssignStr, AllLengths, AllOpacity>(); + makeCartesianProductBenchmark<StringAssignAsciiz, AllLengths, AllOpacity>(); + makeCartesianProductBenchmark<StringAssignAsciizMix, AllOpacity>(); + + makeCartesianProductBenchmark<StringCopy, AllLengths>(); + makeCartesianProductBenchmark<StringMove, AllLengths>(); + makeCartesianProductBenchmark<StringDestroy, AllLengths>(); + makeCartesianProductBenchmark<StringResizeDefaultInit, AllLengths, + AllOpacity>(); + makeCartesianProductBenchmark<StringRelational, AllRelations, AllLengths, + AllLengths, AllDiffTypes>(); + makeCartesianProductBenchmark<StringRelationalLiteral, AllRelations, + AllLengths, AllLengths, AllDiffTypes>(); + makeCartesianProductBenchmark<StringRead, AllTemperatures, AllDepths, + AllLengths>(); + benchmark::RunSpecifiedBenchmarks(); + + if (argc < 0) { + // ODR-use the functions to force them being generated in the binary. + auto functions = std::make_tuple( + StringEqString, StringEqCStr, CStrEqString, StringEqCStrLiteralEmpty, + StringEqCStrLiteralSmall, StringEqCStrLiteralLarge); + printf("%p", &functions); + } +} diff --git a/gnu/llvm/libcxx/benchmarks/stringstream.bench.cpp b/gnu/llvm/libcxx/benchmarks/stringstream.bench.cpp new file mode 100644 index 00000000000..828ef4b405f --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/stringstream.bench.cpp @@ -0,0 +1,40 @@ +#include "benchmark/benchmark.h" +#include "test_macros.h" + +#include <sstream> + +TEST_NOINLINE double 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/gnu/llvm/libcxx/benchmarks/unordered_set_operations.bench.cpp b/gnu/llvm/libcxx/benchmarks/unordered_set_operations.bench.cpp new file mode 100644 index 00000000000..e0030d6c473 --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/unordered_set_operations.bench.cpp @@ -0,0 +1,307 @@ +#include <unordered_set> +#include <vector> +#include <functional> +#include <cstdint> +#include <cstdlib> +#include <cstring> + +#include "benchmark/benchmark.h" + +#include "ContainerBenchmarks.h" +#include "GenerateInput.h" +#include "test_macros.h" + +using namespace ContainerBenchmarks; + +constexpr std::size_t TestNumInputs = 1024; + +template <class _Size> +inline TEST_ALWAYS_INLINE +_Size loadword(const void* __p) { + _Size __r; + std::memcpy(&__r, __p, sizeof(__r)); + return __r; +} + +inline TEST_ALWAYS_INLINE +std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) { + return (__val >> __shift) | (__val << (64 - __shift)); +} + +inline TEST_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 TEST_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 TEST_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 TEST_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 TEST_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 TEST_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 TEST_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.data(); it != end; ++it) { + benchmark::DoNotOptimize(last_hash += fn(*it)); + } + benchmark::ClobberMemory(); + } +} + +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 Ascending // +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/gnu/llvm/libcxx/benchmarks/util_smartptr.bench.cpp b/gnu/llvm/libcxx/benchmarks/util_smartptr.bench.cpp new file mode 100644 index 00000000000..053cbd659be --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/util_smartptr.bench.cpp @@ -0,0 +1,41 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include <memory> + +#include "benchmark/benchmark.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/gnu/llvm/libcxx/benchmarks/vector_operations.bench.cpp b/gnu/llvm/libcxx/benchmarks/vector_operations.bench.cpp new file mode 100644 index 00000000000..70a317df9fb --- /dev/null +++ b/gnu/llvm/libcxx/benchmarks/vector_operations.bench.cpp @@ -0,0 +1,40 @@ +#include <vector> +#include <functional> +#include <cstdint> +#include <cstdlib> +#include <cstring> + +#include "benchmark/benchmark.h" + +#include "ContainerBenchmarks.h" +#include "GenerateInput.h" + +using namespace ContainerBenchmarks; + +constexpr std::size_t TestNumInputs = 1024; + +BENCHMARK_CAPTURE(BM_ConstructSize, + vector_byte, + std::vector<unsigned char>{})->Arg(5140480); + +BENCHMARK_CAPTURE(BM_ConstructSizeValue, + vector_byte, + std::vector<unsigned char>{}, 0)->Arg(5140480); + +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(); |