C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

TMP Question: Computing the size of the largest type in a l
Goto page 1, 2, 3  Next
 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated)
View previous topic :: View next topic  
Author Message
Scott Meyers
Guest
PostPosted: Thu Apr 22, 2004 2:11 pm    Post subject: TMP Question: Computing the size of the largest type in a l Reply with quote


A client recently asked me if it was possible to use TMP to compute the
size of the largest type in a list of types, i.e., to come up with a
compile-time constant that was that size. I said that it was. I also said
that I'd have to think about how to do it, since TMP isn't really my
thing. I ultimately came up with this, based on Loki's typelists:

template<typename T> struct MaxSize;

template<typename H, typename T>
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

template<>
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};

It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size is 120

This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

2. It uses Loki typelists, but even Andrei admits that his TYPELIST
macros are inferior to other approaches. (See
http://moderncppdesign.com/publications/cuj-02-2002.html.)

3. It may not follow whatever conventions are emerging in the TMP
world. Is "value" the accepted name for the enumerant, for example?

As I said, TMP isn't really my thing, but I know that some people revel in
it. I welcome suggestions on the "right" way to address this problem,
i.e., one that has linear complexity, that uses a typelist facility that is
emerging as one that's "accepted," and that follows "accepted"
conventions.

FWIW, I'm sure that there is Boost support for typelists, but when I went
to Boost and searched for typelists, nothing came up. I know about the
MPL, but since TMP isn't my thing, the idea of the MPL scares me :-)

Thanks for help and insights,

Scott

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Back to top
Yannick Le goc
Guest
PostPosted: Fri Apr 23, 2004 10:59 am    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote


Scott Meyers wrote:
Quote:
A client recently asked me if it was possible to use TMP to compute the
size of the largest type in a list of types, i.e., to come up with a
compile-time constant that was that size. I said that it was. I also said
that I'd have to think about how to do it, since TMP isn't really my
thing. I ultimately came up with this, based on Loki's typelists:

template<typename T> struct MaxSize;

template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

template
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};

It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size is 120

This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

2. It uses Loki typelists, but even Andrei admits that his TYPELIST
macros are inferior to other approaches. (See
http://moderncppdesign.com/publications/cuj-02-2002.html.)

3. It may not follow whatever conventions are emerging in the TMP
world. Is "value" the accepted name for the enumerant, for example?

As I said, TMP isn't really my thing, but I know that some people revel in
it. I welcome suggestions on the "right" way to address this problem,
i.e., one that has linear complexity, that uses a typelist facility that is
emerging as one that's "accepted," and that follows "accepted"
conventions.

FWIW, I'm sure that there is Boost support for typelists, but when I went
to Boost and searched for typelists, nothing came up. I know about the
MPL, but since TMP isn't my thing, the idea of the MPL scares me :-)

Thanks for help and insights,

First of all, using template typelists imply that all computations will
be done through recursive algorithms. So computing the maximum element
of a typelist must be done by a recursive algorithm. Non standard
template C++ implementation provide a for loop, but standard C++
implementation like gcc does not.

So if you remember your first algorithm lessons, I know it's a long time
ago, you can compute linearly the maximum element of a list by a
recursive algorithm. ;-)

Here it is in a template implementation:

using namespace Loki;

template<class L, int current>
struct TempMaxSize;

template<class H, class T, int current>
struct TempMaxSize<Typelist
{
typedef enum{value = TempMaxSize<T, (current > sizeof(H) ? current :
sizeof(H))>::value};
};

template<int current>
struct TempMaxSize<Loki::NullType, current>
{
typedef enum{value = current};
};

template<class L>
struct MaxSize;

template<class H, class T>
struct MaxSize<Typelist
{
typedef enum{value = TempMaxSize<Typelist::value};
};

template<>
struct MaxSize<Loki::NullType>
{
typedef enum{value = 0};
};

Moreover, if your client wants to compute the maximum element over 500
elements lists, I think your compiler may have trouble to compile it.
Indeed a 500 elements typelist may imply a too long internal data
structure for your compiler. For example my gcc 3.2.2, for a specific
use of typelist, fails to compile a 300 elements list, whereas .NET 2003
microsoft compiler manages but with some warnings.

Yannick


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

Back to top
Anthony Williams
Guest
PostPosted: Fri Apr 23, 2004 11:11 am    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote


Scott Meyers <Usenet (AT) aristeia (DOT) com> writes:

Quote:
A client recently asked me if it was possible to use TMP to compute the
size of the largest type in a list of types, i.e., to come up with a
compile-time constant that was that size. I said that it was. I also said
that I'd have to think about how to do it, since TMP isn't really my
thing. I ultimately came up with this, based on Loki's typelists:

template<typename T> struct MaxSize;

template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

template
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};

It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size is 120

This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

Your implementation *is* linear; TMP is functional, not imperative.

Quote:
2. It uses Loki typelists, but even Andrei admits that his TYPELIST
macros are inferior to other approaches. (See
http://moderncppdesign.com/publications/cuj-02-2002.html.)

Typelists are a common way of doing things in the TMP code I've seen.

Quote:
3. It may not follow whatever conventions are emerging in the TMP
world. Is "value" the accepted name for the enumerant, for example?

It's what boost::mpl uses.

Quote:
FWIW, I'm sure that there is Boost support for typelists, but when I went
to Boost and searched for typelists, nothing came up. I know about the
MPL, but since TMP isn't my thing, the idea of the MPL scares me Smile

<G>

An MPL-ish way of doing it is actually given on the boost::mpl::max_element
doc page, yielding a maxsize implementation thus:

#include "boost/mpl/deref.hpp"
#include "boost/mpl/max_element.hpp"
#include "boost/mpl/transform_view.hpp"
#include "boost/mpl/sizeof.hpp"

template<typename Types>
struct MaxSize:
boost::mpl::deref<typename
boost::mpl::max_element<
boost::mpl::transform_view< Types,boost::mpl::sizeof_
Quote:
::type
::type
{

};

#include "boost/mpl/vector.hpp"
#include <string>

typedef boost::mpl::vector<int,char[50],long,double> types;

std::string y[MaxSize<types>::value]="hello";

Anthony
--
Anthony Williams
Senior Software Engineer, Beran Instruments Ltd.

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

Back to top
David Abrahams
Guest
PostPosted: Fri Apr 23, 2004 11:13 am    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote

Hi Scott,

Scott Meyers <Usenet (AT) aristeia (DOT) com> writes:

Quote:
A client recently asked me if it was possible to use TMP to compute the
size of the largest type in a list of types, i.e., to come up with a
compile-time constant that was that size. I said that it was. I also said
that I'd have to think about how to do it, since TMP isn't really my
thing. I ultimately came up with this, based on Loki's typelists:

template<typename T> struct MaxSize;

template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

template
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};

That's not bad at all.

Quote:
It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size is 120

This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic.

If there's anything quadratic here, it's pretty subtle. You're
probably referring to the repeated naming of MaxSize<T>::value? You
could eliminate that via

template<typename H, typename T>
struct MaxSize< Loki::Typelist {
enum { x = MaxSize<T>::value; }
enum { value = (sizeof(H) > x)
? sizeof(H)
: x
};
};

That's analogous to the runtime:

std::size_t max_size(list_node* p)
{
if (p == 0) return 0;
std::size_t x = max_size(p->next);
return p->size > x ? p->size : x;
}

That said, what you originally wrote isn't really as bad as

std::size_t max_size(list_node* p)
{
if (p == 0) return 0;

return p->size > max_size(p->next)
? p->size : max_size(p->next);
}

would be at runtime. That's because templates are only instantiated
once, and then they're stored in a lookup table in the compiler. You
can think of it as a builtin "memoizing" mechanism, as though every
set of argument values that max_size was called with were stored in a
hash_map:

std::size_t max_size(list_node* p)
{
if (p == 0) return 0;

static hash_map<list_node*, std::size_t> m;
std::size_t& x = m[p];
if (x != 0) return x;

x = p->size > max_size(p->next)
? p->size : max_size(p->next);

return x;
}

The bad news is that most compiler implementations store all
instantiations of a particular template (MaxSize) in a single linked
list, which means that instead of an O(1) hash_map lookup, you get
linear time for each lookup. That said, the constant for doing a
lookup in the linked list is usually negligible compared to the cost
of actually instantiating a template.

Quote:
That's just stupid in general, but it's especially stupid in
the context where the client wants to use the code, which is
with typelists of about 500 types.

:^). Are they really doing anything that large?

Quote:
2. It uses Loki typelists, but even Andrei admits that his TYPELIST
macros are inferior to other approaches. (See
http://moderncppdesign.com/publications/cuj-02-2002.html.)

Yeah, they're ugly. Avoiding them generally requires a bit of
metaprogramming library framework, which is why I'll recommend using
the MPL.

Quote:
3. It may not follow whatever conventions are emerging in the TMP
world. Is "value" the accepted name for the enumerant, for
example?

Yes, but the emergent convention is to do all computation in terms of
types, so you'd always have a type called ::type wrapping the value.

Quote:
As I said, TMP isn't really my thing, but I know that some people
revel in it. I welcome suggestions on the "right" way to address
this problem, i.e., one that has linear complexity, that uses a
typelist facility that is emerging as one that's "accepted," and
that follows "accepted" conventions.

FWIW, I'm sure that there is Boost support for typelists, but when I went
to Boost and searched for typelists, nothing came up. I know about the
MPL, but since TMP isn't my thing, the idea of the MPL scares me Smile

It shouldn't, especially since you have access to the draft of the
upcoming book ;-)

MPL has a number of different type sequences, among them:

list -- a bit like a Loki typelist with nicer declaration syntax

vector -- a more efficient choice for most applications, but with
an extensibility limit on compilers not supporting
typeof().

Note that to make it pretty to create a type sequence with 500
elements you'd probably want to compile with
-DBOOST_MPL_NO_PREPROCESSED_HEADERS and
-DBOOST_MPL_LIMIT_VECTOR_SIZE=500 or -DBOOST_MPL_LIMIT_LIST_SIZE=500.

so:
#include <boost/mpl/vector.hpp>
#include <boost/mpl/max_element.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/sizeof.hpp>
#include <boost/mpl/transform_view.hpp>
namespace mpl = boost::mpl;

struct Foo { char arr[40]; };
class Bar { Foo x, y, z; };

// declare the sequence of types
typedef mpl::vector<char, void*, int, Foo, Bar> Types;

// Find the position of the maximum element
typedef mpl::max_element<
// in a view of the *sizes* of Types
mpl::transform_view
Quote:
::type pos;

// Dereference pos to get the maximum size;
typedef mpl::deref<pos>::type max_size;
unsigned char buffer[max_size::value]; // buffer size is 120

HTH,
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

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

Back to top
Nikolai Borissov
Guest
PostPosted: Fri Apr 23, 2004 4:06 pm    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
Scott Meyers wrote:

Quote:
A client recently asked me if it was possible to use TMP to compute the
size of the largest type in a list of types, i.e., to come up with a
compile-time constant that was that size. I said that it was. I also
said
that I'd have to think about how to do it, since TMP isn't really my
thing. I ultimately came up with this, based on Loki's typelists:

template<typename T> struct MaxSize;

template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

template
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};


It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size is 120

This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

You can insert the calculation of type sizes directly into the typelist.
Something like this:

template <class H, class T>
struct typelist
{
typedef H head;
typedef T tail;
enum{size = MAX(sizeof(H),T::size)};
};

unsigned char buffer[TYPELIST_5(char, void*, int, Foo, Bar)::size];

This is just an idea. I work in environment without partial specialization
(VC++ 6.0) and for that environment I've implemented another solution (see
below). It's real working software that supports up to 500 types. Because
compiler does not support that many template parameters you need to group
types into small chunks up to 25 types each and then work with these chunks.
The compilation is fast, so you can use it for your client immediately.

Regards,

Nikolai Borissov

//--------------------------------------------------------------------------
------------------
// Test of typelist for max type size

#define MAX(a,b) ((a)>(b)?(a)Sadb))
#define NOTYPE_SIZE 0

struct NullType {};

template<typename T01=NullType, typename T02=NullType,
typename T03=NullType, typename T04=NullType,
typename T05=NullType, typename T06=NullType,
typename T07=NullType, typename T08=NullType,
typename T09=NullType, typename T10=NullType,
typename T11=NullType, typename T12=NullType,
typename T13=NullType, typename T14=NullType,
typename T15=NullType, typename T16=NullType,
typename T17=NullType, typename T18=NullType,
typename T19=NullType, typename T20=NullType,
typename T21=NullType, typename T22=NullType,
typename T23=NullType, typename T24=NullType,
typename T25=NullType
Quote:

struct MaxType

{ typedef MaxType T14,T15,T16,T17,T18,T19,T20,T21,T22,T23,T24,T25,NullType
Quote:
MT_Next;

enum{ size = MAX(sizeof(T01),MT_Next::size) };
};

template<> struct MaxType<> {enum{size=NOTYPE_SIZE};};


template<typename T01=NullType, typename T02=NullType,
typename T03=NullType, typename T04=NullType,
typename T05=NullType, typename T06=NullType,
typename T07=NullType, typename T08=NullType,
typename T09=NullType, typename T10=NullType,
typename T11=NullType, typename T12=NullType,
typename T13=NullType, typename T14=NullType,
typename T15=NullType, typename T16=NullType,
typename T17=NullType, typename T18=NullType,
typename T19=NullType, typename T20=NullType
Quote:

struct MaxTypeMaxType

{
typedef MaxTypeMaxType T11,T12,T13,T14,T15,T16,T17,T18,T19,T20,NullType
Quote:
MTMT_Next;
enum{ size = MAX(T01::size,MTMT_Next::size) };

};

template<> struct MaxTypeMaxType<> {enum{size=NOTYPE_SIZE};};

// Test
struct tt {char arr[27];};

void test_max_type()
{
typedef MaxType<> MT1;
typedef MaxType<long,int,char*,tt,int(&)[33]> MT2;
typedef MaxType<int,int,int,int,int,int,int,long,int,short,int,unsigned
long,
int,long,int,int,char,int,int,int,int,int,int,int,int
Quote:
MT3;
typedef

MaxType
long,long,short,char,long,long,long,long,long,long,long,long,int(&)[34]
Quote:
MT4;

long S = MaxTypeMaxType
Quote:
::size; // 136
long S1 = MaxType<>::size; // 0

long S2 = MaxType<>::size; // 0
}


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

Back to top
Marco Manfredini
Guest
PostPosted: Fri Apr 23, 2004 4:11 pm    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
Scott Meyers wrote:

Quote:
template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};


Quote:
1. It's horribly inefficient. For each type in the list, it
computes
the maximum size of all the later types in the list. What
should be a linear-time operation is thus quadratic.

Sorry, this looks quite linear to me. Why do you believe, that MaxSize<>
has quadratic complexity? [MaxSize<T> is instantianted (=computed) once
for every value of T]








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

Back to top
Dhruv Matani
Guest
PostPosted: Fri Apr 23, 2004 11:00 pm    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
On Thu, 22 Apr 2004 10:11:51 -0400, Scott Meyers wrote:


Quote:
1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

Or, you could try this constant time approach, modulo any alignment
constarints imposed by the compiler, which mostly can be removed by using
some pragma directive if applicable.


#include <iostream>
using namespace std;

template <typename T1, typename T2>
union Max_size
{
char _u1[sizeof(T1)];
char _u2[sizeof(T2)];
};


#define MAX_SIZE_5(A1,A2,A3,A4,A5)
sizeof(Max_size<A1,Max_size > > )


struct Foo
{
char temp[43];
};

int main()
{
int Max =
MAX_SIZE_5(int,char,float,Foo,double);
cout<<"Maximum Size is: "< }


--
Regards,
-Dhruv.

Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html


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

Back to top
Andrei Alexandrescu (See
Guest
PostPosted: Fri Apr 23, 2004 11:01 pm    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
"Scott Meyers" <Usenet (AT) aristeia (DOT) com> wrote

Quote:
A client recently asked me if it was possible to use TMP to compute the
size of the largest type in a list of types, i.e., to come up with a
compile-time constant that was that size. I said that it was. I also
said
that I'd have to think about how to do it, since TMP isn't really my
thing. I ultimately came up with this, based on Loki's typelists:
[code snipped]


Quote:
This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

I think it's not quadratic, it's linear (in both time and space). The
algorithm computes the maximum size of the tail in one shot and compares it
with the size of the head. The computation is done only once. For comparison
purposes, you may want to compare the C++ metacode with code written in a
classic functional language. The ML equivalent is:

fun MaxSize(head::tail) = max(sizeof(head), MaxSize(tail))
Quote:

MaxSize(nil) = 0


The only inefficiency is the linear space requirement caused by non-tail
recursion. You could convert the function above to use tail recursion, but
that is useless in C++ because the compiler won't recognize tail recursion.

One thing you can do to help the compiler is to incantate MaxSize<T>::value
only once and save it in a 'temporary' enum, to make it clear to a poor
compiler that they don't need to compute it twice. That's still linear and
not quadratic.

Quote:
2. It uses Loki typelists, but even Andrei admits that his TYPELIST
macros are inferior to other approaches. (See
http://moderncppdesign.com/publications/cuj-02-2002.html.)

The main problem is that they don't recognize the angular brackets. They
won't be slower than other approaches though.

I hate macros.

Quote:
3. It may not follow whatever conventions are emerging in the TMP
world. Is "value" the accepted name for the enumerant, for example?

I think so.

Quote:
FWIW, I'm sure that there is Boost support for typelists, but when I went
to Boost and searched for typelists, nothing came up. I know about the
MPL, but since TMP isn't my thing, the idea of the MPL scares me Smile

Now that's not as scary as the preprocessor library Surprised).


Andrei



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

Back to top
Dhruv Matani
Guest
PostPosted: Fri Apr 23, 2004 11:02 pm    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
On Thu, 22 Apr 2004 10:11:51 -0400, Scott Meyers wrote:

Quote:
template<typename T> struct MaxSize;

template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

BTW, does this compile? You should probably use just one template
parameter, and then derive the T and H parameters from nested typedefs if
they exist, or create some.

Quote:
template
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};

It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size is 120

This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

Why not cache the value of the return from MaxSize<T>::value?

Something like this: (Untested code):

template<typename H, typename T>
struct MaxSize< Loki::Typelist {
static const int _temp = MaxSize<T>::value;
enum { value = (sizeof(H) > _temp)
? sizeof(H)
: _temp
};
};


--
Regards,
-Dhruv.

Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html


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

Back to top
Stephen C. Dewhurst
Guest
PostPosted: Fri Apr 23, 2004 11:10 pm    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
On 22 Apr 2004 10:11:51 -0400, Scott Meyers <Usenet (AT) aristeia (DOT) com>
wrote:

Quote:
A client recently asked me if it was possible to use TMP to compute the
size of the largest type in a list of types, i.e., to come up with a
compile-time constant that was that size. I said that it was. I also said
that I'd have to think about how to do it, since TMP isn't really my
thing. I ultimately came up with this, based on Loki's typelists:

template<typename T> struct MaxSize;

template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

template
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};

It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size is 120

This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

I don't think efficiency is going to be a real problem here, since
it's easy enough to reformulate the algorithm to be linear, and I
doubt that your client will be doing this in a large percentage of
their (its?) code. I think the real problem may well be limitations
on depth of recursion in template instantiation. As you recall, Annex
B of the C++ std suggests a level of 17, whereas most compilers can
manage at least 60ish, and others can manage over 1000. We should
probably work on coming up with a logarithmic algorithm. (I'll think
on it and get back to you.)

Quote:
2. It uses Loki typelists, but even Andrei admits that his TYPELIST
macros are inferior to other approaches. (See
http://moderncppdesign.com/publications/cuj-02-2002.html.)

Is this really a problem?

Quote:
3. It may not follow whatever conventions are emerging in the TMP
world. Is "value" the accepted name for the enumerant, for example?

As I said, TMP isn't really my thing, but I know that some people revel in
it. I welcome suggestions on the "right" way to address this problem,
i.e., one that has linear complexity, that uses a typelist facility that is
emerging as one that's "accepted," and that follows "accepted"
conventions.

I suggest you follow mine.

Quote:
FWIW, I'm sure that there is Boost support for typelists, but when I went
to Boost and searched for typelists, nothing came up. I know about the
MPL, but since TMP isn't my thing, the idea of the MPL scares me Smile

I really think you should use a typelist meta-algorithm (see
[url]http://www.semantics.org/code.html#typelist_meta_algorithms)[/url]. How
about the following?

// MaxElement
//
// Similar to STL max_element; calculates index of maximum element.
// Also tells you what that maximum element is.
// This version assumes a non-empty typelist.
template <class TList, template
struct MaxElement;

template <typename Head, template
struct MaxElement<typelist {
enum { r = 0 };
typedef Head R;
};

template <typename Head, class Tail, template class Comp>
struct MaxElement<typelist {
typedef MaxElement<Tail,Comp> METail;
typedef typename METail::R TR;
enum { r = !!Comp<Head,TR>::r ? METail::r+1 : 0 };
typedef typename Select<!!r, TR, Head>::R R;
};

Then you can define the appropriate meta-comparator:

template <typename A, typename B>
struct Smaller {
enum { r = sizeof(A) < sizeof(B) };
};

and finally answer the question (assuming that "Types" is the typelist
of interest):

const int max =
sizeof(TypeAt::R);

If I'm not mistaken (I frequently am) this has linear complexity, but
also (unfortunatly) linear recursion depth.

Steve
www.semantics.org

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

Back to top
Andreas Huber
Guest
PostPosted: Fri Apr 23, 2004 11:37 pm    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
Scott Meyers wrote:
Quote:
A client recently asked me if it was possible to use TMP to compute
the size of the largest type in a list of types, i.e., to come up
with a compile-time constant that was that size. I said that it was.
I also said that I'd have to think about how to do it, since TMP
isn't really my thing. I ultimately came up with this, based on
Loki's typelists:

template<typename T> struct MaxSize;

template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

template
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};

It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size
is 120

The mpl equivalent would look as follows (taken from the mpl::max_element
docs, tested with MSVC7.1):

#include <boost/mpl/list.hpp>
#include <boost/mpl/max_element.hpp>
#include <boost/mpl/transform_view.hpp>
#include <boost/mpl/sizeof.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/deref.hpp>

#include <iostream>

namespace mpl = boost::mpl;
using namespace mpl::placeholders;

struct Foo { char arr[40]; };
class Bar { Foo x, y, z; };

int main()
{
typedef mpl::list< char, void*, int, Foo, Bar > types;
typedef mpl::max_element<
mpl::transform_view< types, mpl::sizeof_< _1 > >
Quote:
::type iterator;
std::cout << mpl::deref< iterator >::type::value;

return 0;
}


Or, a bit more verbose and demonstrating the power of mpl much better:

#include <boost/mpl/less.hpp>
#include <boost/mpl/sizeof.hpp>
#include <boost/mpl/list.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/max_element.hpp>
#include <boost/mpl/deref.hpp>

#include <iostream>
#include <typeinfo>

namespace mpl = boost::mpl;
using namespace mpl::placeholders;

template< class Left, class Right >
struct size_less
{
typedef typename mpl::less<
mpl::sizeof_< Left >,
mpl::sizeof_< Right > >::type type;
};

struct Foo { char arr[40]; };
class Bar { Foo x, y, z; };

int main()
{
typedef mpl::list< char, void*, int, Foo, Bar > types;
typedef mpl::max_element< types, size_less< _1, _2 > >::type iterator;
typedef mpl::deref< iterator >::type max_sized_type;

std::cout << typeid( max_sized_type ).name() << "n";
std::cout << sizeof( max_sized_type ) << "n";
return 0;
}

Quote:
This works, but

1. It's horribly inefficient. For each type in the list, it
computes the maximum size of all the later types in the list.
What should be a linear-time operation is thus quadratic.

boost::max_element has linear complexity.

Quote:
That's just stupid in general, but it's especially stupid in
the context where the client wants to use the code, which is
with typelists of about 500 types.

BTW, the maximum size of an mpl::list is 50, so you'd have to use multiple
lists. But IIRC the same is also true for Loki typelists.

Quote:

2. It uses Loki typelists, but even Andrei admits that his TYPELIST
macros are inferior to other approaches. (See
http://moderncppdesign.com/publications/cuj-02-2002.html.)

3. It may not follow whatever conventions are emerging in the TMP
world. Is "value" the accepted name for the enumerant, for
example?

Yes, by convention "value" is used for non-type results. "type" is used for
type results.

Quote:
As I said, TMP isn't really my thing, but I know that some people
revel in it. I welcome suggestions on the "right" way to address
this problem, i.e., one that has linear complexity, that uses a
typelist facility that is emerging as one that's "accepted," and that
follows "accepted" conventions.

My experience with TMP and boost::mpl is only moderate, but it seems there
is no other library that is as easy to use, complete and working on so many
platforms as boost::mpl. Especially the last point is important as many
compilers have deficiencies that'd force you to use lots of workarounds with
the Loki typelist approach. boost::mpl does a tremendous job at shielding
you from compiler bugs.
BTW, a good mpl tutorial can be found here:

http://www.boost.org/libs/mpl/doc/paper/mpl_paper.pdf

Quote:
FWIW, I'm sure that there is Boost support for typelists, but when I
went to Boost and searched for typelists, nothing came up. I know
about the MPL, but since TMP isn't my thing, the idea of the MPL
scares me Smile

That was my initial reaction also, but I very soon came to appreciate the
much higher level of abstraction and better readability of mpl code.

Regards,

Andreas


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

Back to top
Hyman Rosen
Guest
PostPosted: Fri Apr 23, 2004 11:59 pm    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
Anthony Williams wrote:
Quote:
Your implementation *is* linear; TMP is functional, not imperative.

It's quadratic. TMP requires the compiler to generate all of the
intermediate and recursive types. The names of those types contain
all of the names of the template parameters. The total length of
all of those generated names (or their underlying data structures)
is quadratic in the number of types.

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

Back to top
Hyman Rosen
Guest
PostPosted: Sat Apr 24, 2004 12:03 am    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
David Abrahams wrote:
Quote:
If there's anything quadratic here, it's pretty subtle.

It's not subtle at all. The top-level Typelist is a construct
that incorporates all of the types in the list. Then each
recursive invocation incorporates one type fewer. The ensemble
thus consists of types whose total name length is quadratic in
the number of types. The compiler has to generate all of these
in its processing, so it takes time quadratic in the number of
types to compile the code.

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

Back to top
Hendrik Schober
Guest
PostPosted: Sat Apr 24, 2004 12:08 am    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
Yannick Le goc <Yannick.Legoc (AT) imag (DOT) fr> wrote:
Quote:
[...]
Moreover, if your client wants to compute the maximum element over 500
elements lists, I think your compiler may have trouble to compile it.
Indeed a 500 elements typelist may imply a too long internal data
structure for your compiler. For example my gcc 3.2.2, for a specific
use of typelist, fails to compile a 300 elements list, whereas .NET 2003
microsoft compiler manages but with some warnings.

This largely depends on the compiler (and
its settings). About a year ago I tested a
classic factorial TMP example on various
compilers and found that they die (usually
with a "template too complex" or something
similar) at very different recursion depths.
While CW8 (or was it CW9?) got as far as !63,
VC6 died at !37, and Comeau's online compiler
(back then) got up to !64, VC7.1 made it all
the way to !1073(!), before it gave up.
I never tested this with GCC, but I believe
you can set its template recursion depth with
a compielr switch.
(BTW, of course, with 32bit ints the results
were not usefull above !13, and with 64bit
ints above !20, but the factorial more or
less accidental became the benchmark. Surprised> )

Quote:
Yannick

Schobi

--
[email]SpamTrap (AT) gmx (DOT) de[/email] is never read
I'm Schobi at suespammers dot org

"Sometimes compilers are so much more reasonable than people."
Scott Meyers



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

Back to top
Walt Karas
Guest
PostPosted: Sat Apr 24, 2004 12:45 am    Post subject: Re: TMP Question: Computing the size of the largest type in Reply with quote
Scott Meyers <Usenet (AT) aristeia (DOT) com> wrote

Quote:
A client recently asked me if it was possible to use TMP to compute the
size of the largest type in a list of types, i.e., to come up with a
compile-time constant that was that size. I said that it was. I also said
that I'd have to think about how to do it, since TMP isn't really my
thing. I ultimately came up with this, based on Loki's typelists:

template<typename T> struct MaxSize;

template<typename H, typename T
struct MaxSize< Loki::Typelist {
enum { value = (sizeof(H) > MaxSize<T>::value)
? sizeof(H)
: MaxSize<T>::value
};
};

template
struct MaxSize<Loki::NullType> {
enum { value = 0 };
};

It can be used like this:

struct Foo { char arr[40]; };

class Bar { Foo x, y, z; };

typedef TYPELIST_5(char, void*, int, Foo, Bar) Types;

unsigned char buffer[MaxSize<Types>::value]; // buffer size is 120

This works, but

1. It's horribly inefficient. For each type in the list, it computes
the maximum size of all the later types in the list. What should be
a linear-time operation is thus quadratic. That's just stupid in
general, but it's especially stupid in the context where the client
wants to use the code, which is with typelists of about 500 types.

2. It uses Loki typelists, but even Andrei admits that his TYPELIST
macros are inferior to other approaches. (See
http://moderncppdesign.com/publications/cuj-02-2002.html.)

3. It may not follow whatever conventions are emerging in the TMP
world. Is "value" the accepted name for the enumerant, for example?

As I said, TMP isn't really my thing, but I know that some people revel in
it. I welcome suggestions on the "right" way to address this problem,
i.e., one that has linear complexity, that uses a typelist facility that is
emerging as one that's "accepted," and that follows "accepted"
conventions.

FWIW, I'm sure that there is Boost support for typelists, but when I went
to Boost and searched for typelists, nothing came up. I know about the
MPL, but since TMP isn't my thing, the idea of the MPL scares me :-)

Thanks for help and insights,

Scott


1. You probably could just define the union of all the types, then take
the sizeof the union.

2. The runaway template expansion is all done at compile time, so who
cares.

3. You could do this:

template<typename H, typename T>
class MaxSize< Loki::Typelist {
private:
enum { tail_value = MaxSize<T>::value };
public:
enum { value = (sizeof(H) > tail_value)
? sizeof(H)
: tail_value
};
};

Wouldn't this be O(n)?

Does TYPELIST_500() exist? Alternative:

#define P__LIST X(char) X(void*) X(int) X(Foo) X(Bar)
#define P__NAME Types
#include "MkTypelist.h"
#undef P__LIST
#undef P__NAME

Contents of MkTypelist.h:

#undef X
#define X(T) Loki::Typelist<T,

typedef P__LIST Loki::NullType

#undef X
// Make sure '>' is surrounded by newlines.
#define X(T)
Quote:


P__LIST P__NAME ;

#undef X

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

Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT
Goto page 1, 2, 3  Next
Page 1 of 3

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.