Re: C++0x Variadic Templates
on Mon Aug 25 2008, "evilissimo-AT-googlemail.com"
<evilissimo-AT-googlemail.com> wrote:
Hi,
I've been lately playing with variadic templates lately and tried to
find it's limits (by using g++ 4.4.0 experimental)
I am especially interessted in the template meta programming usability
aspects of this extension to the standard.
It's about time somebody started looking at this!
I have been able to generate at compiletime type lists with 256k
elements and transform this list with a compilation time of a few
seconds on my machine.
But one thing really made me wondering. In this paper:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1704.pdf
(Variadic Templates: Exploring the Design Space) Douglas Gregor,
Jaakko J?rvi and Gary Powell where talking about accessing the nth
element in a parameter pack. Actually this would be comparable to the
boost.mpl at implementation.
Imho this is one of the features which should be really easy to
implement and so I am wondering why this has been not taken over into
the standard. The compilation time will be really horrible for bigger
type lists (actually if they're greater than 5 it's already starting
to get really worse (on g++ 4.4 at least))
The reason for this is obvious. The compiler has to intatiate
recursively m instances of at in a list of n types. Where in most
implementations n = m.
If that's because of the O(N^2) instantiation characteristic, you might
want to look at this thread:
http://news.gmane.org/find-root.php?message_id=%3c488220A3.4060704%40providere%2dconsulting.com%3e
(Which can be improved by "loop unrolling") I
have been implementing a quite fast one where I can access the 500th
element in the parameter pack with a compilation time of only about 26
seconds compilation time.
Hmm, even a naive implementation goes much faster than that for me. I'm
using conceptgcc to test on a 2.16 Ghz core duo with 2G of RAM:
for x in 0 1 2; do time conceptgcc -ftemplate-depth-600 get.cpp -o /tmp/get; done
real 0m3.912s
user 0m3.188s
sys 0m0.688s
real 0m3.899s
user 0m3.108s
sys 0m0.740s
real 0m3.865s
user 0m3.128s
sys 0m0.736s
=== CODE: ===
template <class... T>
struct vector
{
};
template <unsigned N, class C>
struct get;
template <unsigned N, class H, class... T>
struct get<N, vector<H, T...> >
: get<N-1, vector<T...> >
{
};
template <class H, class... T>
struct get<0, vector<H, T...> >
{
typedef H type;
};
template <int x> struct i;
typedef vector<> test0;
typedef get<0,vector<int> >::type test1;
typedef vector<
i<0>, i<1>, i<2>, i<3>, i<4>, i<5>, i<6>, i<7>, i<8>, i<9>,
i<10>, i<11>, i<12>, i<13>, i<14>, i<15>, i<16>, i<17>, i<18>, i<19>,
i<20>, i<21>, i<22>, i<23>, i<24>, i<25>, i<26>, i<27>, i<28>, i<29>,
i<30>, i<31>, i<32>, i<33>, i<34>, i<35>, i<36>, i<37>, i<38>, i<39>,
i<40>, i<41>, i<42>, i<43>, i<44>, i<45>, i<46>, i<47>, i<48>, i<49>,
i<50>, i<51>, i<52>, i<53>, i<54>, i<55>, i<56>, i<57>, i<58>, i<59>,
i<60>, i<61>, i<62>, i<63>, i<64>, i<65>, i<66>, i<67>, i<68>, i<69>,
i<70>, i<71>, i<72>, i<73>, i<74>, i<75>, i<76>, i<77>, i<78>, i<79>,
i<80>, i<81>, i<82>, i<83>, i<84>, i<85>, i<86>, i<87>, i<88>, i<89>,
i<90>, i<91>, i<92>, i<93>, i<94>, i<95>, i<96>, i<97>, i<98>, i<99>,
i<100>, i<101>, i<102>, i<103>, i<104>, i<105>, i<106>, i<107>, i<108>, i<109>,
i<110>, i<111>, i<112>, i<113>, i<114>, i<115>, i<116>, i<117>, i<118>, i<119>,
i<120>, i<121>, i<122>, i<123>, i<124>, i<125>, i<126>, i<127>, i<128>, i<129>,
i<130>, i<131>, i<132>, i<133>, i<134>, i<135>, i<136>, i<137>, i<138>, i<139>,
i<140>, i<141>, i<142>, i<143>, i<144>, i<145>, i<146>, i<147>, i<148>, i<149>,
i<150>, i<151>, i<152>, i<153>, i<154>, i<155>, i<156>, i<157>, i<158>, i<159>,
i<160>, i<161>, i<162>, i<163>, i<164>, i<165>, i<166>, i<167>, i<168>, i<169>,
i<170>, i<171>, i<172>, i<173>, i<174>, i<175>, i<176>, i<177>, i<178>, i<179>,
i<180>, i<181>, i<182>, i<183>, i<184>, i<185>, i<186>, i<187>, i<188>, i<189>,
i<190>, i<191>, i<192>, i<193>, i<194>, i<195>, i<196>, i<197>, i<198>, i<199>,
i<200>, i<201>, i<202>, i<203>, i<204>, i<205>, i<206>, i<207>, i<208>, i<209>,
i<210>, i<211>, i<212>, i<213>, i<214>, i<215>, i<216>, i<217>, i<218>, i<219>,
i<220>, i<221>, i<222>, i<223>, i<224>, i<225>, i<226>, i<227>, i<228>, i<229>,
i<230>, i<231>, i<232>, i<233>, i<234>, i<235>, i<236>, i<237>, i<238>, i<239>,
i<240>, i<241>, i<242>, i<243>, i<244>, i<245>, i<246>, i<247>, i<248>, i<249>,
i<250>, i<251>, i<252>, i<253>, i<254>, i<255>, i<256>, i<257>, i<258>, i<259>,
i<260>, i<261>, i<262>, i<263>, i<264>, i<265>, i<266>, i<267>, i<268>, i<269>,
i<270>, i<271>, i<272>, i<273>, i<274>, i<275>, i<276>, i<277>, i<278>, i<279>,
i<280>, i<281>, i<282>, i<283>, i<284>, i<285>, i<286>, i<287>, i<288>, i<289>,
i<290>, i<291>, i<292>, i<293>, i<294>, i<295>, i<296>, i<297>, i<298>, i<299>,
i<300>, i<301>, i<302>, i<303>, i<304>, i<305>, i<306>, i<307>, i<308>, i<309>,
i<310>, i<311>, i<312>, i<313>, i<314>, i<315>, i<316>, i<317>, i<318>, i<319>,
i<320>, i<321>, i<322>, i<323>, i<324>, i<325>, i<326>, i<327>, i<328>, i<329>,
i<330>, i<331>, i<332>, i<333>, i<334>, i<335>, i<336>, i<337>, i<338>, i<339>,
i<340>, i<341>, i<342>, i<343>, i<344>, i<345>, i<346>, i<347>, i<348>, i<349>,
i<350>, i<351>, i<352>, i<353>, i<354>, i<355>, i<356>, i<357>, i<358>, i<359>,
i<360>, i<361>, i<362>, i<363>, i<364>, i<365>, i<366>, i<367>, i<368>, i<369>,
i<370>, i<371>, i<372>, i<373>, i<374>, i<375>, i<376>, i<377>, i<378>, i<379>,
i<380>, i<381>, i<382>, i<383>, i<384>, i<385>, i<386>, i<387>, i<388>, i<389>,
i<390>, i<391>, i<392>, i<393>, i<394>, i<395>, i<396>, i<397>, i<398>, i<399>,
i<400>, i<401>, i<402>, i<403>, i<404>, i<405>, i<406>, i<407>, i<408>, i<409>,
i<410>, i<411>, i<412>, i<413>, i<414>, i<415>, i<416>, i<417>, i<418>, i<419>,
i<420>, i<421>, i<422>, i<423>, i<424>, i<425>, i<426>, i<427>, i<428>, i<429>,
i<430>, i<431>, i<432>, i<433>, i<434>, i<435>, i<436>, i<437>, i<438>, i<439>,
i<440>, i<441>, i<442>, i<443>, i<444>, i<445>, i<446>, i<447>, i<448>, i<449>,
i<450>, i<451>, i<452>, i<453>, i<454>, i<455>, i<456>, i<457>, i<458>, i<459>,
i<460>, i<461>, i<462>, i<463>, i<464>, i<465>, i<466>, i<467>, i<468>, i<469>,
i<470>, i<471>, i<472>, i<473>, i<474>, i<475>, i<476>, i<477>, i<478>, i<479>,
i<480>, i<481>, i<482>, i<483>, i<484>, i<485>, i<486>, i<487>, i<488>, i<489>,
i<490>, i<491>, i<492>, i<493>, i<494>, i<495>, i<496>, i<497>, i<498>, i<499>
>
v500;
int main()
{
typedef get<499, v500>::type u;
}
=== END CODE ===
Of course you could speed this up massively with some specializations to
work on the first, say, 20 elements.
But this is actually wasted resources for
the compiler if you can access other items faster.
Sorry, I don't understand what you mean here. Which other items? The
ones near the beginning of the sequence?
I am not sure how much it is used but i'd expect that there might be
good uses for this kind of feature (accessing the nth element in a
type list) supported by the compiler. Since it will improve meta
programming compilation times a lot.
I'd be nice to hear your opinion about this. Also please let me know
if I have been missing something what would make this possible without
any changes of the current draft for the variadic templates.
Well, it's currently *possible* already. Do you mean you want to do it
in O(1)?
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]