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 ABSL_NAMESPACE_BEGIN
32 namespace {
33
34 template <std::size_t I>
35 struct VariantAlternative {
36 char member;
37 };
38
39 template <class Indices>
40 struct VariantOfAlternativesImpl;
41
42 template <std::size_t... Indices>
43 struct VariantOfAlternativesImpl<absl::index_sequence<Indices...>> {
44 using type = absl::variant<VariantAlternative<Indices>...>;
45 };
46
47 template <std::size_t NumAlternatives>
48 using VariantOfAlternatives = typename VariantOfAlternativesImpl<
49 absl::make_index_sequence<NumAlternatives>>::type;
50
51 struct Empty {};
52
53 template <class... T>
Ignore(T...)54 void Ignore(T...) noexcept {}
55
56 template <class T>
DoNotOptimizeAndReturnEmpty(T && arg)57 Empty DoNotOptimizeAndReturnEmpty(T&& arg) noexcept {
58 benchmark::DoNotOptimize(arg);
59 return {};
60 }
61
62 struct VisitorApplier {
63 struct Visitor {
64 template <class... T>
operator ()absl::__anon12bf4a300111::VisitorApplier::Visitor65 void operator()(T&&... args) const noexcept {
66 Ignore(DoNotOptimizeAndReturnEmpty(args)...);
67 }
68 };
69
70 template <class... Vars>
operator ()absl::__anon12bf4a300111::VisitorApplier71 void operator()(const Vars&... vars) const noexcept {
72 absl::visit(Visitor(), vars...);
73 }
74 };
75
76 template <std::size_t NumIndices, std::size_t CurrIndex = NumIndices - 1>
77 struct MakeWithIndex {
78 using Variant = VariantOfAlternatives<NumIndices>;
79
Runabsl::__anon12bf4a300111::MakeWithIndex80 static Variant Run(std::size_t index) {
81 return index == CurrIndex
82 ? Variant(absl::in_place_index_t<CurrIndex>())
83 : MakeWithIndex<NumIndices, CurrIndex - 1>::Run(index);
84 }
85 };
86
87 template <std::size_t NumIndices>
88 struct MakeWithIndex<NumIndices, 0> {
89 using Variant = VariantOfAlternatives<NumIndices>;
90
Runabsl::__anon12bf4a300111::MakeWithIndex91 static Variant Run(std::size_t /*index*/) { return Variant(); }
92 };
93
94 template <std::size_t NumIndices, class Dimensions>
95 struct MakeVariantTuple;
96
97 template <class T, std::size_t /*I*/>
98 using always_t = T;
99
100 template <std::size_t NumIndices>
MakeVariant(std::size_t dimension,std::size_t index)101 VariantOfAlternatives<NumIndices> MakeVariant(std::size_t dimension,
102 std::size_t index) {
103 return dimension == 0
104 ? MakeWithIndex<NumIndices>::Run(index % NumIndices)
105 : MakeVariant<NumIndices>(dimension - 1, index / NumIndices);
106 }
107
108 template <std::size_t NumIndices, std::size_t... Dimensions>
109 struct MakeVariantTuple<NumIndices, absl::index_sequence<Dimensions...>> {
110 using VariantTuple =
111 std::tuple<always_t<VariantOfAlternatives<NumIndices>, Dimensions>...>;
112
Runabsl::__anon12bf4a300111::MakeVariantTuple113 static VariantTuple Run(int index) {
114 return std::make_tuple(MakeVariant<NumIndices>(Dimensions, index)...);
115 }
116 };
117
integral_pow(std::size_t base,std::size_t power)118 constexpr std::size_t integral_pow(std::size_t base, std::size_t power) {
119 return power == 0 ? 1 : base * integral_pow(base, power - 1);
120 }
121
122 template <std::size_t End, std::size_t I = 0>
123 struct VisitTestBody {
124 template <class Vars, class State>
Runabsl::__anon12bf4a300111::VisitTestBody125 static bool Run(Vars& vars, State& state) {
126 if (state.KeepRunning()) {
127 absl::apply(VisitorApplier(), vars[I]);
128 return VisitTestBody<End, I + 1>::Run(vars, state);
129 }
130 return false;
131 }
132 };
133
134 template <std::size_t End>
135 struct VisitTestBody<End, End> {
136 template <class Vars, class State>
Runabsl::__anon12bf4a300111::VisitTestBody137 static bool Run(Vars& /*vars*/, State& /*state*/) {
138 return true;
139 }
140 };
141
142 // Visit operations where branch prediction is likely to give a boost.
143 template <std::size_t NumIndices, std::size_t NumDimensions = 1>
BM_RedundantVisit(benchmark::State & state)144 void BM_RedundantVisit(benchmark::State& state) {
145 auto vars =
146 MakeVariantTuple<NumIndices, absl::make_index_sequence<NumDimensions>>::
147 Run(static_cast<std::size_t>(state.range(0)));
148
149 for (auto _ : state) { // NOLINT
150 benchmark::DoNotOptimize(vars);
151 absl::apply(VisitorApplier(), vars);
152 }
153 }
154
155 // Visit operations where branch prediction is unlikely to give a boost.
156 template <std::size_t NumIndices, std::size_t NumDimensions = 1>
BM_Visit(benchmark::State & state)157 void BM_Visit(benchmark::State& state) {
158 constexpr std::size_t num_possibilities =
159 integral_pow(NumIndices, NumDimensions);
160
161 using VariantTupleMaker =
162 MakeVariantTuple<NumIndices, absl::make_index_sequence<NumDimensions>>;
163 using Tuple = typename VariantTupleMaker::VariantTuple;
164
165 Tuple vars[num_possibilities];
166 for (std::size_t i = 0; i < num_possibilities; ++i)
167 vars[i] = VariantTupleMaker::Run(i);
168
169 while (VisitTestBody<num_possibilities>::Run(vars, state)) {
170 }
171 }
172
173 // Visitation
174 // Each visit is on a different variant with a different active alternative)
175
176 // Unary visit
177 BENCHMARK_TEMPLATE(BM_Visit, 1);
178 BENCHMARK_TEMPLATE(BM_Visit, 2);
179 BENCHMARK_TEMPLATE(BM_Visit, 3);
180 BENCHMARK_TEMPLATE(BM_Visit, 4);
181 BENCHMARK_TEMPLATE(BM_Visit, 5);
182 BENCHMARK_TEMPLATE(BM_Visit, 6);
183 BENCHMARK_TEMPLATE(BM_Visit, 7);
184 BENCHMARK_TEMPLATE(BM_Visit, 8);
185 BENCHMARK_TEMPLATE(BM_Visit, 16);
186 BENCHMARK_TEMPLATE(BM_Visit, 32);
187 BENCHMARK_TEMPLATE(BM_Visit, 64);
188
189 // Binary visit
190 BENCHMARK_TEMPLATE(BM_Visit, 1, 2);
191 BENCHMARK_TEMPLATE(BM_Visit, 2, 2);
192 BENCHMARK_TEMPLATE(BM_Visit, 3, 2);
193 BENCHMARK_TEMPLATE(BM_Visit, 4, 2);
194 BENCHMARK_TEMPLATE(BM_Visit, 5, 2);
195
196 // Ternary visit
197 BENCHMARK_TEMPLATE(BM_Visit, 1, 3);
198 BENCHMARK_TEMPLATE(BM_Visit, 2, 3);
199 BENCHMARK_TEMPLATE(BM_Visit, 3, 3);
200
201 // Quaternary visit
202 BENCHMARK_TEMPLATE(BM_Visit, 1, 4);
203 BENCHMARK_TEMPLATE(BM_Visit, 2, 4);
204
205 // Redundant Visitation
206 // Each visit consistently has the same alternative active
207
208 // Unary visit
209 BENCHMARK_TEMPLATE(BM_RedundantVisit, 1)->Arg(0);
210 BENCHMARK_TEMPLATE(BM_RedundantVisit, 2)->DenseRange(0, 1);
211 BENCHMARK_TEMPLATE(BM_RedundantVisit, 8)->DenseRange(0, 7);
212
213 // Binary visit
214 BENCHMARK_TEMPLATE(BM_RedundantVisit, 1, 2)->Arg(0);
215 BENCHMARK_TEMPLATE(BM_RedundantVisit, 2, 2)
216 ->DenseRange(0, integral_pow(2, 2) - 1);
217 BENCHMARK_TEMPLATE(BM_RedundantVisit, 4, 2)
218 ->DenseRange(0, integral_pow(4, 2) - 1);
219
220 } // namespace
221 ABSL_NAMESPACE_END
222 } // namespace absl
223