// 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 // // https://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 { ABSL_NAMESPACE_BEGIN 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 ABSL_NAMESPACE_END } // namespace absl