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
diff --git a/include/variant b/include/variant
index 88a625d..98a62c9 100644
--- a/include/variant
+++ b/include/variant
@@ -1098,59 +1098,64 @@
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 _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 <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 0000000..013d434
--- /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);
+}