Re: [boost] Re: MPL containers and algorithms

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
analogy
> 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
extend
> > 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
STL,
> > the framework of concepts would be useful in itself. Both MPL and Loki
has
> > such a framework, as well.
>
> This is true, but it has yet to be shown that this applies to template
> metaprogramming (more specifically, 'template
meta-functional-programming').
> This is still an open question:  Can you give me one non-contrived example
that
> demonstrates that a vector-like sequence is faster than a cons-like
sequence
> *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,
here).

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
------------------
List
-----
0 - 50 s
10 - 55 s
20 - 1 min
50 - 1 min 20 s

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

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

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

#define BOOST_MPL_USE_PREPROCESSED_HEADERS
#define BOOST_MPL_LIMIT_VECTOR_SIZE 50

#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<
    range_c<int,0,N>,
    Sequence,
    push_front<_,_>
  >::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;
};

template<>
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
help
> > 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
design.
>
> 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
bother?
> > :) There's a lot of adantage in being able to treat the elements
uniformly.
> > As you know, everything is treated as a type in MPL, including types,
values
> > and metafunctions. This lets the components work with them, without
perhaps
> > 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
templates.
>
> 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
to
> 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
get
> 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
the
> > place. You won't be able to treat metafunctions as first-class citicens,
and
> > 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
disagree
> 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
built
> 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
example?

Regards,

Terje