// 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
