Bruno Dutra wrote:
Peter,
I can confirm peeking at the code that at least clang ships a naive linear recursion implementation of make_index_sequence and I read somewhere that GCC doesn't do any better, however it's well known <http://stackoverflow.com/a/17426611/801438> it may be implemented in O(log(n)) plus taking full advantage of memoization. Since Part 2 of your article is all about benchmarking, have you actually tried it?
Yes, the timings in Part 2 use a log N integer_sequence. // integer_sequence template<class T, T... I> struct integer_sequence { }; template<class S1, class S2> struct append_integer_sequence; template<class T, T... I, T... J> struct append_integer_sequence<integer_sequence<T, I...>, integer_sequence<T, J...>> { using type = integer_sequence< T, I..., ( J + sizeof...(I) )... >; }; template<class T, T N> struct make_integer_sequence_impl; template<class T, T N> using make_integer_sequence = typename make_integer_sequence_impl<T, N>::type; template<class T, T N> struct make_integer_sequence_impl_ { private: static T const M = N / 2; static T const R = N % 2; using S1 = make_integer_sequence<T, M>; using S2 = typename append_integer_sequence<S1, S1>::type; using S3 = make_integer_sequence<T, R>; using S4 = typename append_integer_sequence<S2, S3>::type; public: using type = S4; }; template<class T, T N> struct make_integer_sequence_impl: mp_if_c< N == 0, mp_identity<integer_sequence<T>>, mp_if_c< N == 1, mp_identity<integer_sequence<T, 0>>, make_integer_sequence_impl_<T, N> > > { }; // index_sequence template<std::size_t... I> using index_sequence = integer_sequence<std::size_t, I...>; template<std::size_t N> using make_index_sequence = make_integer_sequence<std::size_t, N>;