From 890625b2c781b779f65a835e7c7c610c95f010c0 Mon Sep 17 00:00:00 2001
From: Yedidya Feldblum <yfeldblum@fb.com>
Date: Fri, 28 Jul 2017 14:39:32 -0700
Subject: [PATCH] Optimal make_integer_sequence

Summary:
[Folly] Optimal `make_integer_sequence`.

When the builtin `__make_integer_seq` is available, use that. It is the most optimal implementation.

Otherwise, use a tweaked divide-and-conquer implementation. Designed to reuse more template instantiations than the straightforward divide-and-conquer approach in libstdc++ >= 6. And definitely not linearly recursive as in libstdc++ < 6.

Illustrating with an example. Let `M` be whatever template type implements `make_integer_sequence`. For `M<17>`, libstdc++ < 6 does linear recursion (least optimal), instantiating `M<16>`, `M<15>`, ..., `M<1>`. libstdc++ >= 6 does straightforward divide-and-conquer recursion, instantiating `M<8>` and `M<9>`, recursing into `M<4>` and `M<5>`, recursing into `M<2>` and `M<3>`, recursing into `M<1>`. Our implementation does a variant of divide-and-conquer recursion to maximize reuse, instantiating `M<8>` and `M<1>`, recursing into `M<4>`, recursing into `M<2>`.

Implementation derived from `fatal/type/sequence.h`.

Reviewed By: ericniebler

Differential Revision: D5496975

fbshipit-source-id: 449b4e0a1c7b4a5b602752c1d3dd8914bf9a8e71
---
 folly/Utility.h            | 73 ++++++++++++++++++++++++++++++++------
 folly/test/UtilityTest.cpp |  9 +++++
 2 files changed, 71 insertions(+), 11 deletions(-)

diff --git a/folly/Utility.h b/folly/Utility.h
index a9934e8d..86b338ae 100644
--- a/folly/Utility.h
+++ b/folly/Utility.h
@@ -20,6 +20,8 @@
 #include <type_traits>
 #include <utility>
 
+#include <folly/CPortability.h>
+
 namespace folly {
 
 /**
@@ -98,14 +100,59 @@ void as_const(T const&&) = delete;
 
 #endif
 
+namespace utility_detail {
+template <typename...>
+struct make_seq_cat;
+template <
+    template <typename T, T...> class S,
+    typename T,
+    T... Ta,
+    T... Tb,
+    T... Tc>
+struct make_seq_cat<S<T, Ta...>, S<T, Tb...>, S<T, Tc...>> {
+  using type =
+      S<T,
+        Ta...,
+        (sizeof...(Ta) + Tb)...,
+        (sizeof...(Ta) + sizeof...(Tb) + Tc)...>;
+};
+
+// Not parameterizing by `template <typename T, T...> class, typename` because
+// clang precisely v4.0 fails to compile that. Note that clang v3.9 and v5.0
+// handle that code correctly.
+//
+// For this to work, `S0` is required to be `Sequence<T>` and `S1` is required
+// to be `Sequence<T, 0>`.
+
+template <std::size_t Size>
+struct make_seq {
+  template <typename S0, typename S1>
+  using apply = typename make_seq_cat<
+      typename make_seq<Size / 2>::template apply<S0, S1>,
+      typename make_seq<Size / 2>::template apply<S0, S1>,
+      typename make_seq<Size % 2>::template apply<S0, S1>>::type;
+};
+template <>
+struct make_seq<1> {
+  template <typename S0, typename S1>
+  using apply = S1;
+};
+template <>
+struct make_seq<0> {
+  template <typename S0, typename S1>
+  using apply = S0;
+};
+}
+
 #if __cpp_lib_integer_sequence || _MSC_VER
 
 /* using override */ using std::integer_sequence;
 /* using override */ using std::index_sequence;
-/* using override */ using std::make_index_sequence;
 
 #else
 
+// TODO: Remove after upgrading to C++14 baseline
+
 template <class T, T... Ints>
 struct integer_sequence {
   using value_type = T;
@@ -116,22 +163,26 @@ struct integer_sequence {
 };
 
 template <std::size_t... Ints>
-using index_sequence = folly::integer_sequence<std::size_t, Ints...>;
+using index_sequence = integer_sequence<std::size_t, Ints...>;
 
-namespace detail {
-template <std::size_t N, std::size_t... Ints>
-struct make_index_sequence
-    : detail::make_index_sequence<N - 1, N - 1, Ints...> {};
+#endif
 
-template <std::size_t... Ints>
-struct make_index_sequence<0, Ints...> : folly::index_sequence<Ints...> {};
-}
+#if FOLLY_HAS_BUILTIN(__make_integer_seq) || _MSC_FULL_VER >= 190023918
 
-template <std::size_t N>
-using make_index_sequence = detail::make_index_sequence<N>;
+template <typename T, std::size_t Size>
+using make_integer_sequence = __make_integer_seq<integer_sequence, T, Size>;
+
+#else
+
+template <typename T, std::size_t Size>
+using make_integer_sequence = typename utility_detail::make_seq<
+    Size>::template apply<integer_sequence<T>, integer_sequence<T, 0>>;
 
 #endif
 
+template <std::size_t Size>
+using make_index_sequence = make_integer_sequence<std::size_t, Size>;
+
 /**
  *  Backports from C++17 of:
  *    std::in_place_t
diff --git a/folly/test/UtilityTest.cpp b/folly/test/UtilityTest.cpp
index 5507b96f..34ba8692 100644
--- a/folly/test/UtilityTest.cpp
+++ b/folly/test/UtilityTest.cpp
@@ -88,6 +88,15 @@ TEST(FollyIntegerSequence, core) {
   constexpr auto seq3 = folly::make_index_sequence<3>();
   static_assert(seq3.size() == 3, "");
   EXPECT_EQ(3, seq3.size());
+
+  // check our own implementation even when the builtin is available
+  using seq4 = typename folly::utility_detail::make_seq<5>::template apply<
+      folly::integer_sequence<int>,
+      folly::integer_sequence<int, 0>>;
+  EXPECT_EQ(5, seq4{}.size());
+  EXPECT_TRUE((std::is_same<seq4::value_type, int>::value));
+  using seq4_expected = folly::integer_sequence<int, 0, 1, 2, 3, 4>;
+  EXPECT_TRUE((std::is_same<seq4, seq4_expected>::value));
 }
 
 TEST_F(UtilityTest, MoveOnly) {
-- 
2.34.1