diff options
author | Abseil Team <absl-team@google.com> | 2018-06-13 11:44:15 -0700 |
---|---|---|
committer | Gennadiy Rozental <rogeeff@google.com> | 2018-06-13 15:04:15 -0400 |
commit | eb686c069f8a6aa87bd6f1ac344a330f361fe9ec (patch) | |
tree | 0820933ad638229d33eff67da21764f63bac5ed2 /absl/types/variant_benchmark.cc | |
parent | e5be80532b5d998813f9db952d2cc5401b1532df (diff) |
- b9a479321581cd0293f124041bf5c06f456afec1 Adds exception safety tests for absl::make_unique<T>(...) by Abseil Team <absl-team@google.com>
- 78c61364007f6ab66155c151d0061bbec89c3dbd Update variadic visitation to use a switch statement when... by Matt Calabrese <calabrese@google.com>
- b62eb9546087e0001307a741fcdf023b2d156966 Merge GitHub PR #130 - Add MIPS support to GetProgramCoun... by Derek Mauro <dmauro@google.com>
- 09ab5739de33c8f1bebab2bb70bf7d4331348f05 Update ABSL_ASSERT to silence clang-tidy warnings about c... by Matt Calabrese <calabrese@google.com>
- e73ee389ce8fe1a90738973c219ebbb19bb389f3 Update unary visitation to use a switch statement when th... by Matt Calabrese <calabrese@google.com>
- c8734ccf475b856c95220f21a5ec4f44302cb5ce Work around a MSVC bug for absl::variant, by making `Acce... by Xiaoyi Zhang <zhangxy@google.com>
GitOrigin-RevId: b9a479321581cd0293f124041bf5c06f456afec1
Change-Id: Idb6fc906087c0a4e6fc5c75a391c7f73101c613e
Diffstat (limited to 'absl/types/variant_benchmark.cc')
-rw-r--r-- | absl/types/variant_benchmark.cc | 220 |
1 files changed, 220 insertions, 0 deletions
diff --git a/absl/types/variant_benchmark.cc b/absl/types/variant_benchmark.cc new file mode 100644 index 00000000..99658ac7 --- /dev/null +++ b/absl/types/variant_benchmark.cc @@ -0,0 +1,220 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// Unit tests for the variant template. The 'is' and 'IsEmpty' methods +// of variant are not explicitly tested because they are used repeatedly +// in building other tests. All other public variant methods should have +// explicit tests. + +#include "absl/types/variant.h" + +#include <cstddef> +#include <cstdlib> +#include <string> +#include <tuple> + +#include "benchmark/benchmark.h" +#include "absl/utility/utility.h" + +namespace absl { +namespace { + +template <std::size_t I> +struct VariantAlternative { + char member; +}; + +template <class Indices> +struct VariantOfAlternativesImpl; + +template <std::size_t... Indices> +struct VariantOfAlternativesImpl<absl::index_sequence<Indices...>> { + using type = absl::variant<VariantAlternative<Indices>...>; +}; + +template <std::size_t NumAlternatives> +using VariantOfAlternatives = typename VariantOfAlternativesImpl< + absl::make_index_sequence<NumAlternatives>>::type; + +struct Empty {}; + +template <class... T> +void Ignore(T...) noexcept {} + +template <class T> +Empty DoNotOptimizeAndReturnEmpty(T&& arg) noexcept { + benchmark::DoNotOptimize(arg); + return {}; +} + +struct VisitorApplier { + struct Visitor { + template <class... T> + void operator()(T&&... args) const noexcept { + Ignore(DoNotOptimizeAndReturnEmpty(args)...); + } + }; + + template <class... Vars> + void operator()(const Vars&... vars) const noexcept { + absl::visit(Visitor(), vars...); + } +}; + +template <std::size_t NumIndices, std::size_t CurrIndex = NumIndices - 1> +struct MakeWithIndex { + using Variant = VariantOfAlternatives<NumIndices>; + + static Variant Run(std::size_t index) { + return index == CurrIndex + ? Variant(absl::in_place_index_t<CurrIndex>()) + : MakeWithIndex<NumIndices, CurrIndex - 1>::Run(index); + } +}; + +template <std::size_t NumIndices> +struct MakeWithIndex<NumIndices, 0> { + using Variant = VariantOfAlternatives<NumIndices>; + + static Variant Run(std::size_t /*index*/) { return Variant(); } +}; + +template <std::size_t NumIndices, class Dimensions> +struct MakeVariantTuple; + +template <class T, std::size_t /*I*/> +using always_t = T; + +template <std::size_t NumIndices> +VariantOfAlternatives<NumIndices> MakeVariant(std::size_t dimension, + std::size_t index) { + return dimension == 0 + ? MakeWithIndex<NumIndices>::Run(index % NumIndices) + : MakeVariant<NumIndices>(dimension - 1, index / NumIndices); +} + +template <std::size_t NumIndices, std::size_t... Dimensions> +struct MakeVariantTuple<NumIndices, absl::index_sequence<Dimensions...>> { + using VariantTuple = + std::tuple<always_t<VariantOfAlternatives<NumIndices>, Dimensions>...>; + + static VariantTuple Run(int index) { + return std::make_tuple(MakeVariant<NumIndices>(Dimensions, index)...); + } +}; + +constexpr std::size_t integral_pow(std::size_t base, std::size_t power) { + return power == 0 ? 1 : base * integral_pow(base, power - 1); +} + +template <std::size_t End, std::size_t I = 0> +struct VisitTestBody { + template <class Vars, class State> + static bool Run(Vars& vars, State& state) { + if (state.KeepRunning()) { + absl::apply(VisitorApplier(), vars[I]); + return VisitTestBody<End, I + 1>::Run(vars, state); + } + return false; + } +}; + +template <std::size_t End> +struct VisitTestBody<End, End> { + template <class Vars, class State> + static bool Run(Vars& /*vars*/, State& /*state*/) { + return true; + } +}; + +// Visit operations where branch prediction is likely to give a boost. +template <std::size_t NumIndices, std::size_t NumDimensions = 1> +void BM_RedundantVisit(benchmark::State& state) { + auto vars = + MakeVariantTuple<NumIndices, absl::make_index_sequence<NumDimensions>>:: + Run(static_cast<std::size_t>(state.range(0))); + + for (auto _ : state) { // NOLINT + benchmark::DoNotOptimize(vars); + absl::apply(VisitorApplier(), vars); + } +} + +// Visit operations where branch prediction is unlikely to give a boost. +template <std::size_t NumIndices, std::size_t NumDimensions = 1> +void BM_Visit(benchmark::State& state) { + constexpr std::size_t num_possibilities = + integral_pow(NumIndices, NumDimensions); + + using VariantTupleMaker = + MakeVariantTuple<NumIndices, absl::make_index_sequence<NumDimensions>>; + using Tuple = typename VariantTupleMaker::VariantTuple; + + Tuple vars[num_possibilities]; + for (std::size_t i = 0; i < num_possibilities; ++i) + vars[i] = VariantTupleMaker::Run(i); + + while (VisitTestBody<num_possibilities>::Run(vars, state)) { + } +} + +// Visitation +// Each visit is on a different variant with a different active alternative) + +// Unary visit +BENCHMARK_TEMPLATE(BM_Visit, 1); +BENCHMARK_TEMPLATE(BM_Visit, 2); +BENCHMARK_TEMPLATE(BM_Visit, 3); +BENCHMARK_TEMPLATE(BM_Visit, 4); +BENCHMARK_TEMPLATE(BM_Visit, 5); +BENCHMARK_TEMPLATE(BM_Visit, 6); +BENCHMARK_TEMPLATE(BM_Visit, 7); +BENCHMARK_TEMPLATE(BM_Visit, 8); +BENCHMARK_TEMPLATE(BM_Visit, 16); +BENCHMARK_TEMPLATE(BM_Visit, 32); +BENCHMARK_TEMPLATE(BM_Visit, 64); + +// Binary visit +BENCHMARK_TEMPLATE(BM_Visit, 1, 2); +BENCHMARK_TEMPLATE(BM_Visit, 2, 2); +BENCHMARK_TEMPLATE(BM_Visit, 3, 2); +BENCHMARK_TEMPLATE(BM_Visit, 4, 2); +BENCHMARK_TEMPLATE(BM_Visit, 5, 2); + +// Ternary visit +BENCHMARK_TEMPLATE(BM_Visit, 1, 3); +BENCHMARK_TEMPLATE(BM_Visit, 2, 3); +BENCHMARK_TEMPLATE(BM_Visit, 3, 3); + +// Quaternary visit +BENCHMARK_TEMPLATE(BM_Visit, 1, 4); +BENCHMARK_TEMPLATE(BM_Visit, 2, 4); + +// Redundant Visitation +// Each visit consistently has the same alternative active + +// Unary visit +BENCHMARK_TEMPLATE(BM_RedundantVisit, 1)->Arg(0); +BENCHMARK_TEMPLATE(BM_RedundantVisit, 2)->DenseRange(0, 1); +BENCHMARK_TEMPLATE(BM_RedundantVisit, 8)->DenseRange(0, 7); + +// Binary visit +BENCHMARK_TEMPLATE(BM_RedundantVisit, 1, 2)->Arg(0); +BENCHMARK_TEMPLATE(BM_RedundantVisit, 2, 2) + ->DenseRange(0, integral_pow(2, 2) - 1); +BENCHMARK_TEMPLATE(BM_RedundantVisit, 4, 2) + ->DenseRange(0, integral_pow(4, 2) - 1); + +} // namespace +} // namespace absl |