[Bug libstdc++/66059] make_integer_sequence should use a log(N) implementation

["d.frey at gmx dot de" <gcc-bugzilla at gcc dot gnu dot org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66059

--- Comment #8 from Daniel Frey <d.frey at gmx dot de> ---
(In reply to Jonathan Wakely from comment #7)
> (In reply to Daniel Frey from comment #3)
> > A better O(log N) library-only solution than the linked one is available at
> > https://github.com/taocpp/sequences/blob/master/include/tao/seq/
> > make_integer_sequence.hpp
> 
> The version I came up with is very close to Xeo's at stackoverflow. I tried
> something more like yours and it used a LOT more memory.
> 
> Here's what I tested:
> 
> [...snip...]
> 
> As you can see, defining DUP makes it 10 times slower and using 5 times as
> much memory. Looking at your implementation I see only one relevant
> difference, you pass N/2 as a template argument instead of calculating it
> with sizeof... i.e.

Yeah, avoiding sizeof... is crucial. I don't really know why, I just know it
is. And only for GCC, Clang doesn't care if you use sizeof... or pass in the
size explicitly. This behavior from GCC might be worth a look from the compiler
people, as there is no reason why it should use so much more memory.

> and indeed this is even faster than what I just committed. I didn't realise
> sizeof... would have such an impact.
> 
> My one can be optimised to be almost as fast by avoiding sizeof... in
> _Itup_cat.

I guess my version (without the sizeof...) is still better the larger the
numbers get, but it won't make a real difference in practice as it's kind of
unrealistic to generate index sequences with 100000 or more elements.