Improve compile time of variant.

In particular, improve the compile time of the overload set builder
that variant uses to determine which alternative to construct.

Instead of having the __overload type construct itself recursively,
this patch uses a flat construction for the overload set.

git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@366033 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 154 insertions, 31 deletions

diff --git a/include/variant b/include/variant
index 88a625df7..98a62c992 100644
--- a/include/variant
+++ b/include/variant
@@ -1098,59 +1098,64 @@ struct __narrowing_check {
   template <class _Dest>
   static auto __test_impl(_Dest (&&)[1]) -> __identity<_Dest>;
   template <class _Dest, class _Source>
-  using _Apply = decltype(__test_impl<_Dest>({std::declval<_Source>()}));
+  using _Apply _LIBCPP_NODEBUG_TYPE = decltype(__test_impl<_Dest>({std::declval<_Source>()}));
 };
 
 template <class _Dest, class _Source>
-using __check_for_narrowing = typename _If<
+using __check_for_narrowing _LIBCPP_NODEBUG_TYPE =
+  typename _If<
 #ifdef _LIBCPP_ENABLE_NARROWING_CONVERSIONS_IN_VARIANT
     false &&
 #endif
     is_arithmetic<_Dest>::value,
     __narrowing_check,
     __no_narrowing_check
-    >::template _Apply<_Dest, _Source>;
-
-
-template <class... _Types>
-struct __overload;
-
-template <>
-struct __overload<> { void operator()() const; };
-
-template <class _Tp, class... _Types>
-struct __overload<_Tp, _Types...> : __overload<_Types...> {
-  using __overload<_Types...>::operator();
+  >::template _Apply<_Dest, _Source>;
 
+template <class _Tp, size_t _Idx>
+struct __overload {
   template <class _Up>
   auto operator()(_Tp, _Up&&) const -> __check_for_narrowing<_Tp, _Up>;
 };
 
-template <class _Base, class _Tp>
-struct __overload_bool : _Base {
-  using _Base::operator();
-
+template <class _Tp, size_t>
+struct __overload_bool  {
   template <class _Up, class _Ap = __uncvref_t<_Up>>
   auto operator()(bool, _Up&&) const
       -> enable_if_t<is_same_v<_Ap, bool>, __identity<_Tp>>;
 };
 
-template <class... _Types>
-struct __overload<bool, _Types...>
-    : __overload_bool<__overload<_Types...>, bool> {};
-template <class... _Types>
-struct __overload<bool const, _Types...>
-    : __overload_bool<__overload<_Types...>, bool const> {};
-template <class... _Types>
-struct __overload<bool volatile, _Types...>
-    : __overload_bool<__overload<_Types...>, bool volatile> {};
-template <class... _Types>
-struct __overload<bool const volatile, _Types...>
-    : __overload_bool<__overload<_Types...>, bool const volatile> {};
+template <size_t _Idx>
+struct __overload<bool, _Idx> : __overload_bool<bool, _Idx> {};
+template <size_t _Idx>
+struct __overload<bool const, _Idx> : __overload_bool<bool const, _Idx> {};
+template <size_t _Idx>
+struct __overload<bool volatile, _Idx> : __overload_bool<bool volatile, _Idx> {};
+template <size_t _Idx>
+struct __overload<bool const volatile, _Idx> : __overload_bool<bool const volatile, _Idx> {};
+
+template <class ..._Bases>
+struct __all_overloads : _Bases... {
+  void operator()() const;
+  using _Bases::operator()...;
+};
+
+template <class IdxSeq>
+struct __make_overloads_imp;
+
+template <size_t ..._Idx>
+struct __make_overloads_imp<__tuple_indices<_Idx...> > {
+  template <class ..._Types>
+  using _Apply _LIBCPP_NODEBUG_TYPE = __all_overloads<__overload<_Types, _Idx>...>;
+};
+
+template <class ..._Types>
+using _MakeOverloads _LIBCPP_NODEBUG_TYPE = typename __make_overloads_imp<
+    __make_indices_imp<sizeof...(_Types), 0> >::template _Apply<_Types...>;
 
 template <class _Tp, class... _Types>
 using __best_match_t =
-    typename invoke_result_t<__overload<_Types...>, _Tp, _Tp>::type;
+    typename invoke_result_t<_MakeOverloads<_Types...>, _Tp, _Tp>::type;
 
 } // __variant_detail
 
diff --git a/test/libcxx/utilities/meta/stress_tests/stress_test_variant_overloads_impl.sh.cpp b/test/libcxx/utilities/meta/stress_tests/stress_test_variant_overloads_impl.sh.cpp
new file mode 100644
index 000000000..013d434f4
--- /dev/null
+++ b/test/libcxx/utilities/meta/stress_tests/stress_test_variant_overloads_impl.sh.cpp
@@ -0,0 +1,118 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This is a dummy feature that prevents this test from running by default.
+// REQUIRES: template-cost-testing
+
+// Test the cost of the mechanism used to create an overload set used by variant
+// to determine which alternative to construct.
+
+// The table below compares the compile time and object size for each of the
+// variants listed in the RUN script.
+//
+//  Impl           Compile Time  Object Size
+// -----------------------------------------------------
+// flat:              959 ms        792 KiB
+// recursive:      23,444 ms     23,000 KiB
+// -----------------------------------------------------
+// variant_old:    16,894 ms     17,000 KiB
+// variant_new:     1,105 ms        828 KiB
+
+
+// RUN: %cxx %flags %compile_flags -std=c++17 -c %s \
+// RUN:    -ggdb  -ggnu-pubnames -ftemplate-depth=5000 -ftime-trace -g \
+// RUN:    -DTEST_NS=flat_impl -o %S/flat.o
+// RUN: %cxx %flags %compile_flags -std=c++17 -c %s \
+// RUN:    -ggdb  -ggnu-pubnames -ftemplate-depth=5000 -ftime-trace -g \
+// RUN:    -DTEST_NS=rec_impl -o %S/rec.o
+// RUN: %cxx %flags %compile_flags -std=c++17 -c %s \
+// RUN:    -ggdb  -ggnu-pubnames -ftemplate-depth=5000 -ftime-trace -g \
+// RUN:    -DTEST_NS=variant_impl -o %S/variant.o
+
+#include <type_traits>
+#include <tuple>
+#include <cassert>
+#include <variant>
+
+#include "test_macros.h"
+#include "template_cost_testing.h"
+
+template <size_t Idx>
+struct TestType {};
+
+template <class T>
+struct ID {
+  using type = T;
+};
+
+namespace flat_impl {
+
+struct OverloadBase { void operator()() const; };
+
+template <class Tp, size_t Idx>
+struct Overload {
+  auto operator()(Tp, Tp) const -> ID<Tp>;
+};
+
+template <class ...Bases>
+struct AllOverloads : OverloadBase, Bases... {};
+
+template <class IdxSeq>
+struct MakeOverloads;
+
+template <size_t ..._Idx>
+struct MakeOverloads<std::__tuple_indices<_Idx...> > {
+  template <class ...Types>
+  using Apply = AllOverloads<Overload<Types, _Idx>...>;
+};
+
+template <class ...Types>
+using Overloads = typename MakeOverloads<
+    std::__make_indices_imp<sizeof...(Types), 0> >::template Apply<Types...>;
+
+} // namespace flat_impl
+
+
+namespace rec_impl {
+
+template <class... Types> struct Overload;
+
+template <>
+struct Overload<> { void operator()() const; };
+
+template <class Tp, class... Types>
+struct Overload<Tp, Types...> : Overload<Types...> {
+  using Overload<Types...>::operator();
+  auto operator()(Tp, Tp) const -> ID<Tp>;
+};
+
+template <class... Types>
+using Overloads = Overload<Types...>;
+
+} // namespace rec_impl
+
+namespace variant_impl {
+  template <class ...Types>
+  using Overloads = std::__variant_detail::_MakeOverloads<Types...>;
+} // naamespace variant_impl
+
+#ifndef TEST_NS
+#error TEST_NS must be defined
+#endif
+
+#define TEST_TYPE() TestType< __COUNTER__ >,
+using T1 = TEST_NS::Overloads<REPEAT_1000(TEST_TYPE) TestType<1>, TestType<1>, int>;
+static_assert(__COUNTER__ >= 1000, "");
+
+void fn1(T1 x) { DoNotOptimize(&x); }
+void fn2(typename std::invoke_result_t<T1, int, int>::type x) { DoNotOptimize(&x); }
+
+int main() {
+  DoNotOptimize(&fn1);
+  DoNotOptimize(&fn2);
+}