1 files changed, 222 insertions, 0 deletions
diff --git a/third_party/abseil_cpp/absl/types/variant_benchmark.cc b/third_party/abseil_cpp/absl/types/variant_benchmark.cc
new file mode 100644
index 0000000000..350b175364
--- /dev/null
+++ b/third_party/abseil_cpp/absl/types/variant_benchmark.cc
@@ -0,0 +1,222 @@
+// 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