std::make_integer_seq should provide O(logN) order

[Bolero MURAKAMI]

In my opinion, std::make_integer_seq should provide Ο(logN) order (template instantiation depth).

It becomes necessary for the generation of a "large integer sequence".

For example:

  using t = make_integer_seq<int, 2000>;

In the simplest implementation of recursion Ο(N), which can not be compiled.

Because maximum depth defined by C++11 is 1024.

- make_integer_seq implementation Ο(N)

----

  template<class T, T N, class Seq = integer_seq<T>, bool Break = N == 0>

  struct make_integer_seq_impl {

    using type = Seq;

  };

  template<class T, T N, T... I>

  struct make_integer_seq_impl<T, N, integer_seq<T, I...>, false>

    : make_integer_seq_impl<T, N - 1, integer_seq<T, N - 1, I...>>

  {};

  template<class T, T N>

  using make_integer_seq = typename make_integer_seq_impl<T, N>::type;

----

If implementation of the Ο(logN), can be compiled.

- make_integer_seq implementation Ο(logN)

----

  template<class T, typename Seq, T Next>

  struct make_integer_seq_next_even;

  template<class T, T... I, T Next>

  struct make_integer_seq_next_even<T, integer_seq<T, I...>, Next> {

    using type = integer_seq<T, I..., (I + Next)...>;

  };

  template<class T, typename Seq, T Next, T Last>

  struct make_integer_seq_next_odd;

  template<class T, T... I, T Next, T Last>

  struct make_integer_seq_next_odd<T, integer_seq<T, I...>, Next, Last> {

    using type = integer_seq<T, I..., (I + Next)..., Last>;

  };

  template<class T, T N, class Enable = void>

  struct make_integer_seq_impl;

  template<class T, T N>

  struct make_integer_seq_impl<T, N, typename enable_if<(N == 0)>::type> {

    using type = integer_seq<T>;

  };

  template<class T, T N>

  struct make_integer_seq_impl<T, N, typename enable_if<(N == 1)>::type> {

    using type = integer_seq<T, 0>;

  };

  template<class T, T N>

  struct make_integer_seq_impl<T, N, typename enable_if<(N > 1 && N % 2 == 0)>::type>

    : make_integer_seq_next_even<T, typename make_integer_seq_impl<T, N / 2>::type, N / 2>

  {};

  template<class T, T N>

  struct make_integer_seq_impl<T, N, typename enable_if<(N > 1 && N % 2 == 1)>::type>

    : make_integer_seq_next_odd<T, typename make_integer_seq_impl<T, N / 2>::type, N / 2, N - 1>

  {};

  template<class T, T N>

  using make_integer_seq = typename make_integer_seq_impl<T, N>::type;

----

Therefore, std::make_integer_seq should be implemented in Ο(logN) order (template recursion depth).

And I think it should be defined as Ο(logN) order by the C++ standard.

It is the benefit for heavy users of template meta-programming, and it will not become to the detriment of other programmers.

My Sprout library provides Ο(logN) ordered index_tuple (the same as make_integer_seq).

The feature's order is very useful for large data computation.

See: https://github.com/bolero-MURAKAMI/Sprout/blob/master/sprout/index_tuple/index_range.hpp

[Nicol Bolas]

What exactly is make_integer_seq from? What proposal is this about?

[Daniel Krügler]

2013/1/27 Nicol Bolas <jmck...@gmail.com>:

> What exactly is make_integer_seq from? What proposal is this about?

See:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3493.html

I agree with Bolero that a logarithmic guarantee would be preferable.
This would be the first example of such a guarantee, but it seems
reasonable to have that.

- Daniel

[Jonathan Wakely]

Yes, my reference implementation is O(N) but it's been pointed out to me that it should be O(logN).

I'm not planning on a new revision of the paper before the next meeting, but was already planning on mentioning that the depth of instantiation can be reduced.

[Martinho Fernandes]

On Tue, Mar 12, 2013 at 2:23 PM, Jonathan Wakely <c...@kayari.org> wrote:
>
>
> On Sunday, January 27, 2013 10:02:18 PM UTC, Daniel Krügler wrote:
>>
>> 2013/1/27 Nicol Bolas <jmck...@gmail.com>:
>> > What exactly is make_integer_seq from? What proposal is this about?
>>
>> See:
>>
>> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3493.html
>>
>> I agree with Bolero that a logarithmic guarantee would be preferable.
>> This would be the first example of such a guarantee, but it seems
>> reasonable to have that.
>

If we're requiring a guarantee on this, why not go for something that
user code cannot actually achieve? Why not require O(1) instantiations
instead?

Mit freundlichen Grüßen,

Martinho

[Jonathan Wakely]

On Tuesday, March 12, 2013 1:27:07 PM UTC, R. Martinho Fernandes wrote:

If we're requiring a guarantee on this, why not go for something that
user code cannot actually achieve? Why not require O(1) instantiations
instead?

 Because the idea of the proposal is to standardise existing practice and I hoped it would be uncontroversial. The more bells and whistles are added to it the less likely it is to be accepted before the heat death of the universe.

 

[Martinho Fernandes]

Ok, that's fair enough. As long as O(1) implementations are nor forbidden ;)

Mit freundlichen Grüßen,

Martinho

[Jonathan Wakely]

I certainly wouldn't object to O(1), and I'll mention it when the proposal is discussed, but I want to gauge the committee's reaction to the basic feature before requiring compiler magic as well.  If the feature is accepted and users consider it important compilers might offer an O(1) make_integer_seq as a Quality of Implementation feature anyway.

TBH I was expecting feedback to say that the generic integer_seq<T, T...> template is not needed and I should just choose one of int_seq<int...> or uint_seq<unsigned...> and forget the others, but noone has commented on that part so I'm pleased the feedback has been "this is great, make it faster!" instead :-)

[Mikael Kilpeläinen]

12.3.2013 14:40, Jonathan Wakely kirjoitti:
>
> TBH I was expecting feedback to say that the generic integer_seq<T,
> T...> template is not needed and I should just choose one of
> int_seq<int...> or uint_seq<unsigned...> and forget the others, but
> noone has commented on that part so I'm pleased the feedback has been
> "this is great, make it faster!" instead :-)
>

integer_seq<T, T...> is consistent with std::integral_constant<T, T>,
except of the integer != integral part.


Mikael