variant_benchmark.cc
Go to the documentation of this file.
1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 // Unit tests for the variant template. The 'is' and 'IsEmpty' methods
16 // of variant are not explicitly tested because they are used repeatedly
17 // in building other tests. All other public variant methods should have
18 // explicit tests.
19 
20 #include "absl/types/variant.h"
21 
22 #include <cstddef>
23 #include <cstdlib>
24 #include <string>
25 #include <tuple>
26 
27 #include "benchmark/benchmark.h"
28 #include "absl/utility/utility.h"
29 
30 namespace absl {
31 namespace {
32 
33 template <std::size_t I>
34 struct VariantAlternative {
35  char member;
36 };
37 
38 template <class Indices>
39 struct VariantOfAlternativesImpl;
40 
41 template <std::size_t... Indices>
42 struct VariantOfAlternativesImpl<absl::index_sequence<Indices...>> {
44 };
45 
46 template <std::size_t NumAlternatives>
47 using VariantOfAlternatives = typename VariantOfAlternativesImpl<
49 
50 struct Empty {};
51 
52 template <class... T>
53 void Ignore(T...) noexcept {}
54 
55 template <class T>
56 Empty DoNotOptimizeAndReturnEmpty(T&& arg) noexcept {
57  benchmark::DoNotOptimize(arg);
58  return {};
59 }
60 
61 struct VisitorApplier {
62  struct Visitor {
63  template <class... T>
64  void operator()(T&&... args) const noexcept {
65  Ignore(DoNotOptimizeAndReturnEmpty(args)...);
66  }
67  };
68 
69  template <class... Vars>
70  void operator()(const Vars&... vars) const noexcept {
71  absl::visit(Visitor(), vars...);
72  }
73 };
74 
75 template <std::size_t NumIndices, std::size_t CurrIndex = NumIndices - 1>
76 struct MakeWithIndex {
77  using Variant = VariantOfAlternatives<NumIndices>;
78 
79  static Variant Run(std::size_t index) {
80  return index == CurrIndex
82  : MakeWithIndex<NumIndices, CurrIndex - 1>::Run(index);
83  }
84 };
85 
86 template <std::size_t NumIndices>
87 struct MakeWithIndex<NumIndices, 0> {
88  using Variant = VariantOfAlternatives<NumIndices>;
89 
90  static Variant Run(std::size_t /*index*/) { return Variant(); }
91 };
92 
93 template <std::size_t NumIndices, class Dimensions>
94 struct MakeVariantTuple;
95 
96 template <class T, std::size_t /*I*/>
97 using always_t = T;
98 
99 template <std::size_t NumIndices>
100 VariantOfAlternatives<NumIndices> MakeVariant(std::size_t dimension,
101  std::size_t index) {
102  return dimension == 0
103  ? MakeWithIndex<NumIndices>::Run(index % NumIndices)
104  : MakeVariant<NumIndices>(dimension - 1, index / NumIndices);
105 }
106 
107 template <std::size_t NumIndices, std::size_t... Dimensions>
108 struct MakeVariantTuple<NumIndices, absl::index_sequence<Dimensions...>> {
109  using VariantTuple =
110  std::tuple<always_t<VariantOfAlternatives<NumIndices>, Dimensions>...>;
111 
112  static VariantTuple Run(int index) {
113  return std::make_tuple(MakeVariant<NumIndices>(Dimensions, index)...);
114  }
115 };
116 
117 constexpr std::size_t integral_pow(std::size_t base, std::size_t power) {
118  return power == 0 ? 1 : base * integral_pow(base, power - 1);
119 }
120 
121 template <std::size_t End, std::size_t I = 0>
122 struct VisitTestBody {
123  template <class Vars, class State>
124  static bool Run(Vars& vars, State& state) {
125  if (state.KeepRunning()) {
126  absl::apply(VisitorApplier(), vars[I]);
127  return VisitTestBody<End, I + 1>::Run(vars, state);
128  }
129  return false;
130  }
131 };
132 
133 template <std::size_t End>
134 struct VisitTestBody<End, End> {
135  template <class Vars, class State>
136  static bool Run(Vars& /*vars*/, State& /*state*/) {
137  return true;
138  }
139 };
140 
141 // Visit operations where branch prediction is likely to give a boost.
142 template <std::size_t NumIndices, std::size_t NumDimensions = 1>
143 void BM_RedundantVisit(benchmark::State& state) {
144  auto vars =
145  MakeVariantTuple<NumIndices, absl::make_index_sequence<NumDimensions>>::
146  Run(static_cast<std::size_t>(state.range(0)));
147 
148  for (auto _ : state) { // NOLINT
149  benchmark::DoNotOptimize(vars);
150  absl::apply(VisitorApplier(), vars);
151  }
152 }
153 
154 // Visit operations where branch prediction is unlikely to give a boost.
155 template <std::size_t NumIndices, std::size_t NumDimensions = 1>
156 void BM_Visit(benchmark::State& state) {
157  constexpr std::size_t num_possibilities =
158  integral_pow(NumIndices, NumDimensions);
159 
160  using VariantTupleMaker =
161  MakeVariantTuple<NumIndices, absl::make_index_sequence<NumDimensions>>;
162  using Tuple = typename VariantTupleMaker::VariantTuple;
163 
164  Tuple vars[num_possibilities];
165  for (std::size_t i = 0; i < num_possibilities; ++i)
166  vars[i] = VariantTupleMaker::Run(i);
167 
168  while (VisitTestBody<num_possibilities>::Run(vars, state)) {
169  }
170 }
171 
172 // Visitation
173 // Each visit is on a different variant with a different active alternative)
174 
175 // Unary visit
176 BENCHMARK_TEMPLATE(BM_Visit, 1);
177 BENCHMARK_TEMPLATE(BM_Visit, 2);
178 BENCHMARK_TEMPLATE(BM_Visit, 3);
179 BENCHMARK_TEMPLATE(BM_Visit, 4);
180 BENCHMARK_TEMPLATE(BM_Visit, 5);
181 BENCHMARK_TEMPLATE(BM_Visit, 6);
182 BENCHMARK_TEMPLATE(BM_Visit, 7);
183 BENCHMARK_TEMPLATE(BM_Visit, 8);
184 BENCHMARK_TEMPLATE(BM_Visit, 16);
185 BENCHMARK_TEMPLATE(BM_Visit, 32);
186 BENCHMARK_TEMPLATE(BM_Visit, 64);
187 
188 // Binary visit
189 BENCHMARK_TEMPLATE(BM_Visit, 1, 2);
190 BENCHMARK_TEMPLATE(BM_Visit, 2, 2);
191 BENCHMARK_TEMPLATE(BM_Visit, 3, 2);
192 BENCHMARK_TEMPLATE(BM_Visit, 4, 2);
193 BENCHMARK_TEMPLATE(BM_Visit, 5, 2);
194 
195 // Ternary visit
196 BENCHMARK_TEMPLATE(BM_Visit, 1, 3);
197 BENCHMARK_TEMPLATE(BM_Visit, 2, 3);
198 BENCHMARK_TEMPLATE(BM_Visit, 3, 3);
199 
200 // Quaternary visit
201 BENCHMARK_TEMPLATE(BM_Visit, 1, 4);
202 BENCHMARK_TEMPLATE(BM_Visit, 2, 4);
203 
204 // Redundant Visitation
205 // Each visit consistently has the same alternative active
206 
207 // Unary visit
208 BENCHMARK_TEMPLATE(BM_RedundantVisit, 1)->Arg(0);
209 BENCHMARK_TEMPLATE(BM_RedundantVisit, 2)->DenseRange(0, 1);
210 BENCHMARK_TEMPLATE(BM_RedundantVisit, 8)->DenseRange(0, 7);
211 
212 // Binary visit
213 BENCHMARK_TEMPLATE(BM_RedundantVisit, 1, 2)->Arg(0);
214 BENCHMARK_TEMPLATE(BM_RedundantVisit, 2, 2)
215  ->DenseRange(0, integral_pow(2, 2) - 1);
216 BENCHMARK_TEMPLATE(BM_RedundantVisit, 4, 2)
217  ->DenseRange(0, integral_pow(4, 2) - 1);
218 
219 } // namespace
220 } // namespace absl
int power
make_integer_sequence< size_t, N > make_index_sequence
Definition: utility.h:148
Definition: algorithm.h:29
char member
integer_sequence< size_t, Ints... > index_sequence
Definition: utility.h:85
auto apply(Functor &&functor, Tuple &&t) -> decltype(utility_internal::apply_helper(absl::forward< Functor >(functor), absl::forward< Tuple >(t), absl::make_index_sequence< std::tuple_size< typename std::remove_reference< Tuple >::type >::value >
Definition: utility.h:287
void(*)(utility_internal::InPlaceIndexTag< I >) in_place_index_t
Definition: utility.h:206
void * arg
Definition: mutex.cc:292
variant_internal::VisitResult< Visitor, Variants... > visit(Visitor &&vis, Variants &&...vars)
Definition: variant.h:427


abseil_cpp
Author(s):
autogenerated on Tue Jun 18 2019 19:44:38