[Bug c++/68422] New: compile-time cost of sizeof... is exponential

["redi at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

            Bug ID: 68422
           Summary: compile-time cost of sizeof... is exponential
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
                CC: jason at gcc dot gnu.org
  Target Milestone: ---

using size_t = decltype(sizeof(0));

template<size_t... Indexes> struct Index_tuple { };

template<typename ITup1, typename ITup2, size_t ITup1Len> struct Itup_cat;

template<size_t... Ind1, size_t... Ind2, size_t ITup1Len>
  struct Itup_cat<Index_tuple<Ind1...>, Index_tuple<Ind2...>, ITup1Len>
  {
#ifdef NO_SIZEOF
    using type = Index_tuple<Ind1..., Ind2 + ITup1Len...>;
#else
    using type = Index_tuple<Ind1..., (Ind2 + sizeof...(Ind1))...>;
#endif
  };

template<size_t Num>
  struct Build_index_tuple
  : Itup_cat<typename Build_index_tuple<Num / 2>::type,
              typename Build_index_tuple<Num - Num / 2>::type, Num / 2>
  { };

// Specializations to terminate Build_index_tuple recursion:

template<>
  struct Build_index_tuple<1> { typedef Index_tuple<0> type; };

template<>
  struct Build_index_tuple<0> { typedef Index_tuple<> type; };

// And actually use it:
Build_index_tuple<5000> x;


With recent trunk:

$ g++11 intseq.cc -c -ftime-report 

Execution times (seconds)
 phase setup             :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 1%) wall 
  1396 kB ( 1%) ggc
 phase parsing           :   1.24 (98%) usr   0.04 (100%) sys   1.27 (98%) wall
 112465 kB (99%) ggc
 phase lang. deferred    :   0.02 ( 2%) usr   0.00 ( 0%) sys   0.02 ( 2%) wall 
     0 kB ( 0%) ggc
 |overload resolution    :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.03 ( 2%) wall 
   328 kB ( 0%) ggc
 garbage collection      :   0.02 ( 2%) usr   0.00 ( 0%) sys   0.02 ( 2%) wall 
     0 kB ( 0%) ggc
 template instantiation  :   1.24 (98%) usr   0.04 (100%) sys   1.27 (98%) wall
 111544 kB (98%) ggc
 TOTAL                 :   1.26             0.04             1.30            
113894 kB
Extra diagnostic checks enabled; compiler may run slowly.
Configure with --enable-checking=release to disable checks.

But when NO_SIZEOF is defined it is an order of magnitude better:

$ g++11 intseq.cc -c -ftime-report -DNO_SIZEOF

Execution times (seconds)
 phase setup             :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall 
  1396 kB (22%) ggc
 phase parsing           :   0.09 (100%) usr   0.01 (100%) sys   0.10 (91%)
wall    4974 kB (78%) ggc
 phase lang. deferred    :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 9%) wall 
     0 kB ( 0%) ggc
 |overload resolution    :   0.00 ( 0%) usr   0.01 (100%) sys   0.03 (27%) wall
    424 kB ( 7%) ggc
 garbage collection      :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 9%) wall 
     0 kB ( 0%) ggc
 template instantiation  :   0.09 (100%) usr   0.01 (100%) sys   0.10 (91%)
wall    4053 kB (63%) ggc
 TOTAL                 :   0.09             0.01             0.11              
6404 kB
Extra diagnostic checks enabled; compiler may run slowly.
Configure with --enable-checking=release to disable checks.


Changing the sequence length from 5000 to 50000 increases memory use for the
NO_SIZEOF case roughly linearly:

 TOTAL                 :   0.84             0.04             0.90             
38420 kB


But when using sizeof... it uses two orders of magnitude more time and memory:

 TOTAL                 : 116.79             2.15           119.13           
8584131 kB