Re: [boost] Re: MPL containers and algorithms

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-08-11 23:12:49

----- Original Message -----
From: "Douglas Gregor" <gregod_at_[hidden]>

> On Sunday 11 August 2002 10:04 pm, Paul Mensonides wrote:
> > Furthermore, I don't think that it is
> > practical at this point in time to use *huge* numbers of elements in a
> > compile time container.
>
> Burton et al. did it. They used very large typevectors to achieve huge
> performance gains on finite element analysis problems. Sure, they're in a
> domain where one can afford day-long compile times because a model might be
> used for 6 months or a year before needing a recompile after that, but the
> point is that 10,000 elements was feasible for them and that typevectors made
> that possible.

Okay.  I have a question though.  Do you think it is possible on any compiler to
compute the length of such a construct with an MPL algorithm?  <-- I mean
realistically, not in theory.  There is an obvious physical limit on
instantiation depth.  Sometimes you can change it, but what would you have to
change it to in order to process 10,000 elements?

> > What purpose is there to using typelists when
> > type-vectors are so much faster?  When you are talking about a huge number
> > of elements, that is exactly the case when typelists are _slow_ and also
> > exactly the case when type-vectors are an implementation _nightmare_.
>
> Please explain that last part... how are type-vectors an implementation
> nightmare?

A vector of types that is large is difficult to maintain because there are so
many elements.  Maybe I don't understand what you mean by type-vectors.  What I
mean by them is a series of types that is defined in a tuple-like fashion:

template<> struct type_vector<10> {
    template<class T1, ... class T10> struct args {

        template<int, int D = 0> struct subscript;

        template<int D> struct subscript<0, D> {
            typedef T1 type;
        };

        template<int D> struct subscript<1, D> {
            typedef T2 type;
        };

        // etc.

        template<int D> struct subscript<9, D> {
            typedef T10 type;
        };
    };
};

// etc.

typedef type_vector<3>::args<int, double, char> types;

typedef types::subscript<1> y; // double
typedef types::subscript<0> z; // int

...Or something similar.  In other words, constant-time random access.

> Here's what I'm aiming at. In another message, you said:
>
>   "Sequence abstraction.  I have yet to see a practical example that shows
> that it has purpose.  I'll that I have seen is a lot of what-if's. [sic]"
>
> The typevector example I've given is _not_ speculation; it's not a what-if.
> It's research that was presented at WCGP'02 last month and will be published
> as part of the proceedings of that conference; I can send the preproceedings
> version of the paper privately to any interested persons.

Unless I'm completely misunderstanding you, it only shows the utility of
type-vectors.  My question is, what is the utility of cons-style lists if you
already have a full blown type-vector implementation?

> Perhaps the biggest question that looms for MPL is if the sequence abstraction
> (via iterators) is useful or if it is unnecessary. This work presents a case
> for a data structure other than the typelist, and I think we cannot claim the
> sequence abstraction useless without considering this work.
>
> Doug

I'm not making the case for typelists, I'm making the case that multiple pure
sequence types are not necessary.  I totally agree that type-vectors of some
kind are inherently faster than cons-style lists.  Do you have another example
that implemented with a typelist that is inherently better implemented with a
typelist?

Paul Mensonides