This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug c++/68422] New: compile-time cost of sizeof... is exponential
- From: "redi at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: Wed, 18 Nov 2015 21:06:44 +0000
- Subject: [Bug c++/68422] New: compile-time cost of sizeof... is exponential
- Auto-submitted: auto-generated
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