diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -165,10 +165,41 @@ #============================================================================== # Register Benchmark tests #============================================================================== -file(GLOB BENCHMARK_TESTS "*.bench.cpp") +set(BENCHMARK_TESTS + algorithms/make_heap_then_sort_heap.bench.cpp + algorithms/make_heap.bench.cpp + algorithms/min_max_element.bench.cpp + algorithms/pop_heap.bench.cpp + algorithms/push_heap.bench.cpp + algorithms/sort_heap.bench.cpp + algorithms/stable_sort.bench.cpp + algorithms.partition_point.bench.cpp + allocation.bench.cpp + deque.bench.cpp + filesystem.bench.cpp + function.bench.cpp + map.bench.cpp + ordered_set.bench.cpp + string.bench.cpp + stringstream.bench.cpp + to_chars.bench.cpp + unordered_set_operations.bench.cpp + util_smartptr.bench.cpp + variant_visit_1.bench.cpp + variant_visit_2.bench.cpp + variant_visit_3.bench.cpp + vector_operations.bench.cpp + ) -if (NOT LIBCXX_ENABLE_INCOMPLETE_FEATURES) - list(FILTER BENCHMARK_TESTS EXCLUDE REGEX "(format_to_n|format_to|format|formatted_size|formatter_float|std_format_spec_string_unicode).bench.cpp") +if (LIBCXX_ENABLE_INCOMPLETE_FEATURES) + set(BENCHMARK_TESTS + ${BENCHMARK_TESTS} + format_to_n.bench.cpp + format_to.bench.cpp + format.bench.cpp + formatted_size.bench.cpp + formatter_float.bench.cpp + std_format_spec_string_unicode.bench.cpp) endif() foreach(test_path ${BENCHMARK_TESTS}) @@ -179,7 +210,7 @@ # Only report the adding of the benchmark once. set(${test_name}_REPORTED ON CACHE INTERNAL "") endif() - add_benchmark_test(${test_name} ${test_file}) + add_benchmark_test(${test_name} ${test_path}) endforeach() if (LIBCXX_INCLUDE_TESTS) diff --git a/libcxx/benchmarks/algorithms.bench.cpp b/libcxx/benchmarks/algorithms/common.h rename from libcxx/benchmarks/algorithms.bench.cpp rename to libcxx/benchmarks/algorithms/common.h --- a/libcxx/benchmarks/algorithms.bench.cpp +++ b/libcxx/benchmarks/algorithms/common.h @@ -1,18 +1,21 @@ +//===----------------------------------------------------------------------===// +// +// 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 LIBCXX_ALGORITHMS_COMMON_H +#define LIBCXX_ALGORITHMS_COMMON_H #include -#include -#include -#include -#include -#include +#include +#include #include -#include "CartesianBenchmarks.h" -#include "GenerateInput.h" -#include "benchmark/benchmark.h" -#include "test_macros.h" - -namespace { +#include "../CartesianBenchmarks.h" +#include "../GenerateInput.h" enum class ValueType { Uint32, Uint64, Pair, Tuple, String, Float }; struct AllValueTypes : EnumValuesAsTuple { @@ -54,9 +57,9 @@ assert(N > 0); // If an element is equal to gas, it indicates that the value of the element // is still to be decided and may change over the course of time. - const int gas = N - 1; + const unsigned int gas = N - 1; V.resize(N); - for (int i = 0; i < N; ++i) { + for (unsigned int i = 0; i < N; ++i) { V[i] = gas; } // Candidate for the pivot position. @@ -134,7 +137,7 @@ } } -void fillValues(std::vector& V, size_t N, Order O) { +inline void fillValues(std::vector& V, size_t N, Order O) { if (O == Order::SingleElement) { V.resize(N, getRandomString(64)); } else { @@ -228,169 +231,24 @@ } } -template -struct Sort { - size_t Quantity; - - void run(benchmark::State& state) const { - runOpOnCopies( - state, Quantity, Order(), BatchSize::CountElements, - [](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 -struct StableSort { - size_t Quantity; - - void run(benchmark::State& state) const { - runOpOnCopies( - state, Quantity, Order(), BatchSize::CountElements, - [](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 -struct MakeHeap { - size_t Quantity; - - void run(benchmark::State& state) const { - runOpOnCopies( - state, Quantity, Order(), BatchSize::CountElements, - [](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 -struct SortHeap { - size_t Quantity; - - void run(benchmark::State& state) const { - runOpOnCopies( - state, Quantity, Order::Heap, BatchSize::CountElements, - [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); }); - } - - std::string name() const { - return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity); - }; -}; - -template -struct MakeThenSortHeap { - size_t Quantity; - - void run(benchmark::State& state) const { - runOpOnCopies(state, Quantity, Order(), BatchSize::CountElements, - [](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 -struct PushHeap { - size_t Quantity; - - void run(benchmark::State& state) const { - runOpOnCopies( - state, Quantity, Order(), BatchSize::CountElements, [](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 -struct PopHeap { - size_t Quantity; - - void run(benchmark::State& state) const { - runOpOnCopies( - state, Quantity, Order(), BatchSize::CountElements, [](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); - }; -}; -template -struct MinMaxElement { - size_t Quantity; - - void run(benchmark::State& state) const { - runOpOnCopies(state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) { - benchmark::DoNotOptimize(std::minmax_element(Copy.begin(), Copy.end())); - }); - } - - std::string name() const { - return "BM_MinMaxElement" + ValueType::name() + Order::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 Quantities = {1 << 0, 1 << 2, 1 << 4, 1 << 6, - 1 << 8, 1 << 10, 1 << 14, +const std::vector 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 + 1 << 18 #endif - }; - makeCartesianProductBenchmark(Quantities); - makeCartesianProductBenchmark( - Quantities); - makeCartesianProductBenchmark(Quantities); - makeCartesianProductBenchmark(Quantities); - makeCartesianProductBenchmark( - Quantities); - makeCartesianProductBenchmark(Quantities); - makeCartesianProductBenchmark(Quantities); - makeCartesianProductBenchmark(Quantities); - benchmark::RunSpecifiedBenchmarks(); -} +}; + +#define LIBCPP_ALGORITHMS_BENCHMARK_MAIN(...) \ + int main(int argc, char** argv) { \ + benchmark::Initialize(&argc, argv); \ + if (benchmark::ReportUnrecognizedArguments(argc, argv)) \ + return 1; \ + \ + makeCartesianProductBenchmark<__VA_ARGS__>(Quantities); \ + benchmark::RunSpecifiedBenchmarks(); \ + } + +#endif // LIBCXX_ALGORITHMS_COMMON_H diff --git a/libcxx/benchmarks/algorithms/make_heap.bench.cpp b/libcxx/benchmarks/algorithms/make_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/make_heap.bench.cpp @@ -0,0 +1,32 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "common.h" + +namespace { +template +struct MakeHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, + [](auto& Copy) { std::make_heap(Copy.begin(), Copy.end()); }); + } + + std::string name() const { + return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; +} // namespace + + +LIBCPP_ALGORITHMS_BENCHMARK_MAIN(MakeHeap, AllValueTypes, AllOrders) diff --git a/libcxx/benchmarks/algorithms/make_heap_then_sort_heap.bench.cpp b/libcxx/benchmarks/algorithms/make_heap_then_sort_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/make_heap_then_sort_heap.bench.cpp @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "common.h" + +namespace { +template +struct MakeThenSortHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies(state, Quantity, Order(), BatchSize::CountElements, + [](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); + }; +}; +} // namespace + + +LIBCPP_ALGORITHMS_BENCHMARK_MAIN(MakeThenSortHeap, AllValueTypes, AllOrders) diff --git a/libcxx/benchmarks/algorithms/min_max_element.bench.cpp b/libcxx/benchmarks/algorithms/min_max_element.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/min_max_element.bench.cpp @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "common.h" + +namespace { +template +struct MinMaxElement { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies(state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) { + benchmark::DoNotOptimize(std::minmax_element(Copy.begin(), Copy.end())); + }); + } + + std::string name() const { + return "BM_MinMaxElement" + ValueType::name() + Order::name() + "_" + std::to_string(Quantity); + } +}; +} // namespace + + +LIBCPP_ALGORITHMS_BENCHMARK_MAIN(MinMaxElement, AllValueTypes, AllOrders) diff --git a/libcxx/benchmarks/algorithms/pop_heap.bench.cpp b/libcxx/benchmarks/algorithms/pop_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/pop_heap.bench.cpp @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "common.h" + +namespace { +template +struct PopHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, [](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 + + +LIBCPP_ALGORITHMS_BENCHMARK_MAIN(PopHeap, AllValueTypes) diff --git a/libcxx/benchmarks/algorithms/push_heap.bench.cpp b/libcxx/benchmarks/algorithms/push_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/push_heap.bench.cpp @@ -0,0 +1,37 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "common.h" + +namespace { +template +struct PushHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, [](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); + }; +}; +} // namespace + + +LIBCPP_ALGORITHMS_BENCHMARK_MAIN(PushHeap, AllValueTypes, AllOrders) diff --git a/libcxx/benchmarks/algorithms/sort.bench.cpp b/libcxx/benchmarks/algorithms/sort.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/sort.bench.cpp @@ -0,0 +1,33 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "common.h" + +namespace { +template +struct Sort { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, + [](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); + }; +}; +} // namespace + +LIBCPP_ALGORITHMS_BENCHMARK_MAIN(Sort, AllValueTypes, AllOrders) diff --git a/libcxx/benchmarks/algorithms/sort_heap.bench.cpp b/libcxx/benchmarks/algorithms/sort_heap.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/sort_heap.bench.cpp @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "common.h" + +namespace { +template +struct SortHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order::Heap, BatchSize::CountElements, + [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); }); + } + + std::string name() const { + return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity); + }; +}; +} // namespace + + +LIBCPP_ALGORITHMS_BENCHMARK_MAIN(SortHeap, AllValueTypes) diff --git a/libcxx/benchmarks/algorithms/stable_sort.bench.cpp b/libcxx/benchmarks/algorithms/stable_sort.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/stable_sort.bench.cpp @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "common.h" + +namespace { +template +struct StableSort { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, + [](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); + }; +}; +} // namespace + + +LIBCPP_ALGORITHMS_BENCHMARK_MAIN(StableSort, AllValueTypes, AllOrders)