C++0x Variadic Templates

#1 (**permalink**) 08-25-2008, 02:45 PM

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.

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/wg...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. (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. But this is actually wasted resources for
the compiler if you can access other items faster.

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.

With best regards,

Vinzenz Feenstra

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

#2 (**permalink**) 08-26-2008, 04:21 AM

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/wg...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?...sulting.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! ]

#3 (**permalink**) 08-26-2008, 05:28 PM

[snip]
> 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?...0A3.4060704%40...
Thanks for giving me the link. Actually this is funny. I have not seen
that one but that's similar to my approach. (See below)

> 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:

[snip]

> Of course you could speed this up massively with some specializations to
> work on the first, say, 20 elements.

Well I forgot to mention that I created a huge list (2 ^ 14 elements)
at compile time. ;)
The generation approach is pretty expensive for memory.

Additionally I had a bug which was not accessing the 500th element but
something much higher (actually no idea which one exactly), what I
haven't realized because the list was so big and it compiled.

> > 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?

Actually it should have been "any" instead of "other"...

> Well, it's currently *possible* already. Do you mean you want to do it
> in O(1)?

.... and yes I meant 0(1) access.

Here's my approach for the at:

Code:

#include <boost/mpl/if.hpp>

template<typename... Types>
struct vector
{
enum { size = sizeof...(Types) };

};

namespace detail
{
template<size_t N, typename... Params>
struct at_impl;

template<size_t N>
struct at_helper;

template<typename T, typename... Params>
struct at_impl<0, T, Params...>
{
typedef T type;
};

template<size_t N, typename... Params>
struct at_impl
{
typedef typename at_helper<N>::template apply<Params...>::type
type;
};

template<size_t N>
struct at_helper
{
struct impl_50
{
template<typename... Args>
struct apply
{
template<typename...>
struct result;

template<
typename T0, typename T1, typename T2,
typename T3, typename T4, typename T5,
typename T6, typename T7, typename T8,
typename T9,
typename T10, typename T11, typename T12,
typename T13, typename T14, typename T15,
typename T16, typename T17, typename T18,
typename T19,
typename T20, typename T21, typename T22,
typename T23, typename T24, typename T25,
typename T26, typename T27, typename T28,
typename T29,
typename T30, typename T31, typename T32,
typename T33, typename T34, typename T35,
typename T36, typename T37, typename T38,
typename T39,
typename T40, typename T41, typename T42,
typename T43, typename T44, typename T45,
typename T46, typename T47, typename T48,
typename T49, typename... Rest>
struct result<
T0 ,T1 ,T2 ,T3 ,T4 ,T5 ,T6 ,T7 ,T8 ,T9 ,
T10,T11,T12,T13,T14,T15,T16,T17,T18,T19,
T20,T21,T22,T23,T24,T25,T26,T27,T28,T29,
T30,T31,T32,T33,T34,T35,T36,T37,T38,T39,
T40,T41,T42,T43,T44,T45,T46,T47,T48,T49,
Rest...>
{
typedef typename at_impl<N-50, Rest...>::type
type;
};

typedef typename result<Args...>::type type;
};
};
struct impl_10
{
template<typename... Args>
struct apply
{
template<typename...>
struct result;

template<
typename T0, typename T1, typename T2,
typename T3, typename T4, typename T5,
typename T6, typename T7, typename T8,
typename T9, typename... Rest>
struct result<T0,T1,T2,T3,T4,T5,T6,T7,T8,T9,Rest...>
{
typedef typename at_impl<N-10, Rest...>::type
type;
};

typedef typename result<Args...>::type type;
};
};
struct impl_5
{
template<typename... Args>
struct apply
{
template<typename...>
struct result;

template<
typename T0, typename T1, typename T2,
typename T3, typename T4, typename... Rest>
struct result<T0, T1, T2, T3, T4, Rest...>
{
typedef typename at_impl<N-5, Rest...>::type type;
};

typedef typename result<Args...>::type type;
};
};

struct impl_2
{
template<typename... Args>
struct apply
{
template<typename...>
struct result;

template<
typename T0, typename T1, typename... Rest>
struct result<T0, T1, Rest...>
{
typedef typename at_impl<N-2, Rest...>::type type;
};

typedef typename result<Args...>::type type;
};
};

struct impl_1
{
template<typename... Args>
struct apply
{
template<typename...>
struct result;

template<
typename T0, typename... Rest>
struct result<T0, Rest...>
{
typedef typename at_impl<N-1, Rest...>::type type;
};

typedef typename result<Args...>::type type;
};
};

template<typename... Params>
struct apply
{
typedef typename boost::mpl::if_c
<
(N >= 50),
impl_50,
typename boost::mpl::if_c
<
(N >= 10),
impl_10,
typename boost::mpl::if_c
<
(N >= 5),
impl_5,
typename boost::mpl::if_c
<
(N >= 2),
impl_2,
impl_1
>::type
>::type
>::type
>::type:: template apply<Params...>::type type;
};
};
}

template<size_t Index, typename T>
struct at;

template<size_t Index, template <typename... > class Vector,
typename... Args>
struct at< Index, Vector<Args...> >
{
static_assert(sizeof...(Args) > Index, "Index for typelist out of
bounds");
typedef typename detail::at_impl<Index, Args...>::type type;
};

As you can see there are specializations for 50, 10, 5, 2 and 1, which
helps me to avoid to go too deep so I don't need to use the -ftemplate-
depth parameter.

evilissimo@evilnotebook:~/projects/vartpl$ for i in 0 1 2; do time g++
meta.cpp -o meta -std=c++0x; done

real 0m1.110s
user 0m0.996s
sys 0m0.116s

real 0m0.855s
user 0m0.812s
sys 0m0.044s

real 0m0.905s
user 0m0.816s
sys 0m0.052s

Also I've implemented a tranform which was quite easy and is quite
fast :)

Code:

template<typename Function, typename Vector>
struct transform;

template<typename Function, template <typename...> class Vector,
typename... Args>
struct transform<Function, Vector<Args...>>
{
typedef Vector< typename Function::template apply<Args>::type...>
type;
};

and a for_each:

Code:

#include <boost/utility/value_init.hpp>
namespace detail
{
template<typename F>
struct for_each_wrap
{
template <typename T>
struct apply
{
struct type
{
type(F f)
{
boost::value_initialized<T> t;
f(boost::get(t));
}
};
};
};

struct init_any
{
template<typename T>
init_any(T)
{
}

init_any(init_any const &)
{
}

~init_any()
{}

init_any & operator=(init_any)
{
return *this;
}

template<typename T>
init_any & operator=(T)
{
return *this;
}
};

template<typename Function, typename Vector>
struct for_each_impl;

template<typename Function, template <typename...> class Vector,
typename... Args>
struct for_each_impl<Function, Vector<Args...>>
{
for_each_impl(Function f)
{
init_any exec[] = {Args(f)...};
(void)exec; // Compiler silence
}
};

template<typename Function, typename Vector>
struct for_each
{
typedef for_each_impl<
Function,
typename transform<
detail::for_each_wrap<Function>,
Vector
>::type
> impl;

for_each(Function f)
{
impl i(f);
(void)i; // compiler silence
}
};
}

template <typename Vector, typename Function>
void for_each(Function f)
{
detail::for_each<Function,Vector> run(f);
(void)run; //compiler silence
}

Not sure what the compiler makes out of it, but when I executed it
with the following code but the comparation to a loop which does the
same is quite impressive:

The compilation time is actually 20 seconds for this code which is
because of the for_each implementation.

Code:

struct test
{
test(size_t & counter)
: m_cnt(counter){}

size_t & m_cnt;

template<typename T>
void operator()(T) const
{
++m_cnt;
}
};

template<typename Integral, Integral Value = 0>
struct integral
{
enum { value = Value };
typedef Integral type;
};

template<int Value>
struct int_
: integral<int, Value>
{};

template<int... Values>
struct make_int_vector
{
typedef vector<int_<Values>...> type;
};

int main()
{
typedef make_int_vector<
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
100, 101, 102, 103, 104, 105, 106, 107, 108, 109,
110, 111, 112, 113, 114, 115, 116, 117, 118, 119,
120, 121, 122, 123, 124, 125, 126, 127, 128, 129,
130, 131, 132, 133, 134, 135, 136, 137, 138, 139,
140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
160, 161, 162, 163, 164, 165, 166, 167, 168, 169,
170, 171, 172, 173, 174, 175, 176, 177, 178, 179,
180, 181, 182, 183, 184, 185, 186, 187, 188, 189,
190, 191, 192, 193, 194, 195, 196, 197, 198, 199,
200, 201, 202, 203, 204, 205, 206, 207, 208, 209,
210, 211, 212, 213, 214, 215, 216, 217, 218, 219,
220, 221, 222, 223, 224, 225, 226, 227, 228, 229,
230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
240, 241, 242, 243, 244, 245, 246, 247, 248, 249,
250, 251, 252, 253, 254, 255, 256, 257, 258, 259,
260, 261, 262, 263, 264, 265, 266, 267, 268, 269,
270, 271, 272, 273, 274, 275, 276, 277, 278, 279,
280, 281, 282, 283, 284, 285, 286, 287, 288, 289,
290, 291, 292, 293, 294, 295, 296, 297, 298, 299,
300, 301, 302, 303, 304, 305, 306, 307, 308, 309,
310, 311, 312, 313, 314, 315, 316, 317, 318, 319,
320, 321, 322, 323, 324, 325, 326, 327, 328, 329,
330, 331, 332, 333, 334, 335, 336, 337, 338, 339,
340, 341, 342, 343, 344, 345, 346, 347, 348, 349,
350, 351, 352, 353, 354, 355, 356, 357, 358, 359,
360, 361, 362, 363, 364, 365, 366, 367, 368, 369,
370, 371, 372, 373, 374, 375, 376, 377, 378, 379,
380, 381, 382, 383, 384, 385, 386, 387, 388, 389,
390, 391, 392, 393, 394, 395, 396, 397, 398, 399,
400, 401, 402, 403, 404, 405, 406, 407, 408, 409,
410, 411, 412, 413, 414, 415, 416, 417, 418, 419,
420, 421, 422, 423, 424, 425, 426, 427, 428, 429,
430, 431, 432, 433, 434, 435, 436, 437, 438, 439,
440, 441, 442, 443, 444, 445, 446, 447, 448, 449,
450, 451, 452, 453, 454, 455, 456, 457, 458, 459,
460, 461, 462, 463, 464, 465, 466, 467, 468, 469,
470, 471, 472, 473, 474, 475, 476, 477, 478, 479,
480, 481, 482, 483, 484, 485, 486, 487, 488, 489,
490, 491, 492, 493, 494, 495, 496, 497, 498, 499
>::type ABVector;

size_t count = 0;
test t(count);
for_each<transform<add_pointer, ABVector>::type>(t);
std::cout << count << std::endl;
}

evilissimo@evilnotebook:~/projects/vartpl$ for i in 0 1 2; do time ./
meta;done
500

real 0m0.009s
user 0m0.004s
sys 0m0.008s
500

real 0m0.008s
user 0m0.008s
sys 0m0.000s
500

real 0m0.008s
user 0m0.004s
sys 0m0.004s

versus: // which is basically the same code just "more readable"
int main()
{
size_t count = 0;
for(size_t i = 0; i < 500; ++i)
++count;
std::cout << count << std::endl;
return 0;
}

evilissimo@evilnotebook:~/projects/vartpl$ for i in 0 1 2; do time ./
meta;done
500

real 0m0.008s
user 0m0.004s
sys 0m0.004s
500

real 0m0.008s
user 0m0.004s
sys 0m0.004s
500

real 0m0.007s
user 0m0.004s
sys 0m0.004s

I bet, that the things I've done so far are not really something new,
but still I haven't found much resources about it so maybe this
information about the variadic templates is a kick off for some people
getting some new ideas. I would be glad to read more about it. I am
still thinking of other ways using it.

One thing what is quite awesome is this:

template<typename Container>
struct extract;

template<template <typename...> class Container, typename... Args>
struct extract<Container<Args...>>
{
enum{ size = sizeof...(Args) };
typedef vtmpl::vector< Args... > type;
};

you can extract all parameters of a template. Which might be useful to
transform a container type into another (exchanging allocators, or
compare operators, or maybe key/value types from maps etc)

Maybe I can find some more use cases which are improving the meta
programming aspects.

Regards,
Vinzenz

PS to Dave: Thanks a lot for your reply :)

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

#4 (**permalink**) 08-27-2008, 02:45 AM

David Abrahams wrote:

[...]
>
> 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.

I tried:
template <int x> struct i {};
and:
get<400,v500>::type a1;
get<410,v500>::type a2;
get<420,v500>::type a3;
get<430,v500>::type a4;
get<440,v500>::type a5;
get<450,v500>::type a6;

And this made gcc trash my swap space until my machine froze. And I've
got 4GB RAM.

I've tried to implement the pattern Steve Watanabe suggested, which
essentially is botton-up evaluation:

template<typename C> struct tail;
template<typename H,typename ...T> struct tail<vector<H,T...> >
{
typedef vector<T...> type;
};
template<typename C> struct head;
template<typename H,typename ...T> struct head<vector<H,T...> >
{
typedef H type;
};

template<unsigned N, typename T>
struct get_help
{
typedef typename tail< typename get_help<N-1,T>::type >::type type;
};
template<typename T> struct get_help< 0,T >
{
typedef T type;
};
template<unsigned N,typename T> struct get
{
typedef typename get_help<N,T>::type P;
typedef typename head< P >::type type;
};

This creates significant less instantiations and compiles my example in
~4seconds. I am inclined to see a problem in the fact, that variadic
templates as they are now, might require intricate evaluation
techniques to be useable at all.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

#5 (**permalink**) 08-27-2008, 07:09 AM

On Aug 27, 3:45 am, Marco Manfredini <ok_nospam...@phoyd.net> wrote:
[snip]
>
> I tried:
> template <int x> struct i {};
> and:
> get<400,v500>::type a1;
> get<410,v500>::type a2;
> get<420,v500>::type a3;
> get<430,v500>::type a4;
> get<440,v500>::type a5;
> get<450,v500>::type a6;
>
> And this made gcc trash my swap space until my machine froze. And I've
> got 4GB RAM.

That's why I started this discussion ;) I've just 2GB RAM and it
happend to me quite often ;)

[snip]
>
> This creates significant less instantiations and compiles my example in
> ~4seconds.

With my approach I've been able to compile the in less than 2 seconds
on my notebook (AMD Turion x2 with 2GB RAM)

evilissimo@evilnotebook:~/projects/vartpl$ for i in 0 1 2; do time g++
meta.cpp -o meta -std=c++0x; done

real 0m1.793s
user 0m1.188s
sys 0m0.100s

real 0m1.277s
user 0m1.160s
sys 0m0.116s

real 0m1.300s
user 0m1.144s
sys 0m0.156s

> I am inclined to see a problem in the fact, that variadic
> templates as they are now, might require intricate evaluation
> techniques to be useable at all.

I don't think it's more complex than before, but still there will be a
need to have a more compile time efficient (memory & complexity) way
to access types or elements in a parameter pack of variadic templates,
especially for template meta programming.

No question variadics brought already loads of improvements but still
I am thinking that a language supported way of accessing the nth
element in a parameter pack (something like sizeof... but for
indexing) would be a real improvement.

But however, maybe I fail to see the major usage of template meta
programming as it is not something I can use alot (altough I wish I
could use it at some more places (where appropriate)). Usually I am
just "playing" around with these kind of features.

However it might be that the indexing is not so important but still
I'd like to know what was the reason for this not being implemented,
since it was thought of in the document I've linked in my initial
post.

Regards,
Vinzenz

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

#6 (**permalink**) 08-28-2008, 09:33 PM

on Tue Aug 26 2008, "evilissimo-AT-googlemail.com"
<evilissimo-AT-googlemail.com> wrote:

> [snip]
>> 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?...0A3.4060704%40...
> Thanks for giving me the link. Actually this is funny. I have not seen
> that one but that's similar to my approach. (See below)
>
>> 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:
>
> [snip]
>
>> Of course you could speed this up massively with some specializations to
>> work on the first, say, 20 elements.
>
> Well I forgot to mention that I created a huge list (2 ^ 14 elements)
> at compile time. ;)
> The generation approach is pretty expensive for memory.

Urr, yeah. But then it doesn't look like you were measuring the
slowness of the thing you thought you were measuring.

> Additionally I had a bug which was not accessing the 500th element but
> something much higher (actually no idea which one exactly), what I
> haven't realized because the list was so big and it compiled.
>
>> > 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?
>
> Actually it should have been "any" instead of "other"...

I still don't understand what you mean by "wasted resources" nor do I
understand why the time it takes to reach a different element is
relevant.

>> Well, it's currently *possible* already. Do you mean you want to do it
>> in O(1)?
>
> ... and yes I meant 0(1) access.

If your compiler supports typeof() or decltype() you can do it in O(1)
instantiations. See boost::mpl::vector, which is a typelist
implementation on such compilers. So it seems to me to be pointless to
explore C++0x metaprogramming without using all its features; C++0x is
going to completely change the landscape.

> Here's my approach for the at:
>
> [code]
> #include <boost/mpl/if.hpp>
>
> template<typename... Types>
> struct vector
> {
> enum { size = sizeof...(Types) };
>
> };
>
> namespace detail
> {
> template<size_t N, typename... Params>
> struct at_impl;
>
> template<size_t N>
> struct at_helper;
>
> template<typename T, typename... Params>
> struct at_impl<0, T, Params...>
> {
> typedef T type;
> };
>
> template<size_t N, typename... Params>
> struct at_impl
> {
> typedef typename at_helper<N>::template apply<Params...>::type
> type;
> };
>
<sorry, no time to read it all>

> As you can see there are specializations for 50, 10, 5, 2 and 1, which
> helps me to avoid to go too deep so I don't need to use the -ftemplate-
> depth parameter.

You _do_ know that the MPL is already doing that sort of unrolling (with
far fewer iterations)?

If you really want to avoid depth, make the size of your list accessible
in O(1) and do binary unrolling.

> evilissimo@evilnotebook:~/projects/vartpl$ for i in 0 1 2; do time g++
> Maybe I can find some more use cases which are improving the meta
> programming aspects.
>
> Regards,
> Vinzenz
>
> PS to Dave: Thanks a lot for your reply :)

it's an interesting topic.

--
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! ]

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode