Boost logo

Boost :

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-11 12:48:12

>From: "Paul Mensonides" <pmenso57_at_[hidden]>

> > This basically gives you an iterator.
> >
> > You've shown that iterators are useful (!) :)
> It isn't really an iterator. In this sense, it is just a typedef. The
> to iterators only applies in the presence of multiple sequence types.

Well, the implementation of iterator, for cons-lists, is very much like a
cons-list, in itself, in MPL. You can map it to cons, with "type" being
"head" and "next" being "tail". That's what I meant.

> > Well, as you know, one of the great strengths of STL is that you may
> > it, as well. As long as your component implements the concept required,
> > it'll work with the rest of STL. So even if there wasn't anything in
> > the framework of concepts would be useful in itself. Both MPL and Loki
> > such a framework, as well.
> This is true, but it has yet to be shown that this applies to template
> metaprogramming (more specifically, 'template
> This is still an open question: Can you give me one non-contrived example
> demonstrates that a vector-like sequence is faster than a cons-like
> *and* vice versa?

I've done some timing (using g++ 2.95.3, as especially EDG based compilers
such as Intel C++ tend to take very long, if the preprocessor is used), and
found that the way lists and vectors are implemented in MPL, they are
similar in efficiency. Since I couldn't get longer vectors than 50, I used a
program with a list or vector of 40 elements, and repeatedly made new types,
by adding a new type at the end of this one type.

Here's the results I got (I include the complete program used, at the end,

The first number in the tables below is the number of calls to push_front,
on the 40-element sequence (making it 41 elements), and it ranges from 0 to
1000. By subtracting the time for 0, you can get the time it takes,
including the recursion. The push_front is also unrolled 10 times in the
program, to minimise the effect of the recursion on the result.

Intel C++ 6.0
0 - 50 s
10 - 55 s
20 - 1 min
50 - 1 min 20 s

0 - Hang (I didn't get a 40-element vector to work, there)

g++ 2.95.3
0 - 17 s
10 - 17 s
100 - 28 s
1000 - 2 min 20 s

0 - 13 s
10 - 13 s
100 - 17 s
1000 - 1 min

As can be seen, vector performs about 2 times faster, for push_front.

Here's the program:

--- Start ---


#include <iostream>
#include <boost/mpl/int_c.hpp>
#include <boost/mpl/list.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/range_c.hpp>
#include <boost/mpl/copy.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/size.hpp>

using namespace boost::mpl;

// Generate a sequence containing N elements

template<class Sequence,int N>
struct make_sequence
  typedef copy<
>::type type;

typedef vector<> SequenceType; // Change to test for list
const int length=40;
const int iterations=1000; // Number of calls to push_front

typedef make_sequence<SequenceType,length>::type Sequence;

// As far as I can tell, there's no basic iteration algorithm in MPL (that
doesn't iterate over a list), so I'm using specialisations, here.

template<int N>
struct sequence_test
  typedef typename push_front<Sequence,int_c<N> >::type NewSequence1;
  typedef typename push_front<Sequence,int_c<N-1> >::type NewSequence2;
  typedef typename push_front<Sequence,int_c<N-2> >::type NewSequence3;
  typedef typename push_front<Sequence,int_c<N-3> >::type NewSequence4;
  typedef typename push_front<Sequence,int_c<N-4> >::type NewSequence5;
  typedef typename push_front<Sequence,int_c<N-5> >::type NewSequence6;
  typedef typename push_front<Sequence,int_c<N-6> >::type NewSequence7;
  typedef typename push_front<Sequence,int_c<N-7> >::type NewSequence8;
  typedef typename push_front<Sequence,int_c<N-8> >::type NewSequence9;
  typedef typename push_front<Sequence,int_c<N-9> >::type NewSequence10;

  typedef typename sequence_test<N-10>::type type;

struct sequence_test<0>
  typedef sequence_test type;

int main()
typedef sequence_test<iterations>::type type;

std::cout << size<Sequence>::value << '\n'; // Just to check the size

--- End ---

Even though vector performs faster, here, there are other issues with
vector, such as it being fixed maximum length, or requiring the use of the
preprocessor to increase this length. This may be expensive.

> > I understand. Well, like I said, I think performance measurements could
> > to find out the possible merit of having several sequence types. Even if
> > there are several sequence types, then it doesn't really change the
> All that I ask is for one realistic example that shows a worthwhile
increase in
> speed using one sequence vs. another and vice versa.

As mentioned above, speed is not the only issue.

> > Well, this is covered some in the MPL paper. You can, but there are some
> > issues. You may pass them as template template parameters, and you may
> > return them as member templates. But I'm almost tempted to say, why
> > :) There's a lot of adantage in being able to treat the elements
> > As you know, everything is treated as a type in MPL, including types,
> > and metafunctions. This lets the components work with them, without
> > even knowing what they are. You can use the same algorithm for types and
> > values, for example. I think the same advantage is the case for
> I agree with this as far as pure metaprogramming goes, and I like this
aspect of
> the STL. It is a different situation when you are using metaprogramming
> facilitate real code.

In what way could the use of template template parameters, rather than
classes with member templates, be of help here, you mean?

> A template-template binding and deduction mechanism would
> be useful for such a thing. Also, if we don't use it, it is not likely to
> improved. :)

I understand what you mean. I think Andrei has proposed, for template
template parameters, something like "template Function", rather than the
current syntax "template<class> class Function", so that it wouldn't be
restricted to a certain arity.

However, this would still mean you couldn't mix it with types, as you can
now, using types, with member templates.

> > It seems we agree on the complexity of passign templates around, in the
> > general case. If you don't wrap them up, it will simply collide all over
> > place. You won't be able to treat metafunctions as first-class citicens,
> > I think such uniform, generic treatment is key to its power. It lets you
> > relatively easily transform metafunctions, store them, pass them around,
> > etc.
> I don't disagree with the utility of this abstraction. However, I do
> with this reason for it. You can easily encode any of the above into a
type at
> will. What that engenders is a simple subset with more elaborate designs
> on top of it.

I don't think I understood you, here. The question was using templates vs
using classes with member templates. Could you try to explain, or give an



Boost list run by bdawes at, gregod at, cpdaniel at, john at