Re: [boost] Re: Re: loki::type_list == boost::mpl::list_node

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-04-17 07:22:36

----- Original Message -----
From: "Aleksey Gurtovoy" <agurtovoy_at_[hidden]>

> Hamish Mackenzie wrote:
> > > If you're interested in contributing optimized versions of some of
the
> > > MPL algorithms I'm sure it would be greatly appreciated.
> >
> > I'd be glad to give it a crack, but will need to be able to get at
the
> > raw list.
>
> You don't need to, and making the unrolling work for lists only would
be
> against the library philosophy. If we are talking about possibility of
> implementing the approach that Dave outlined in
> http://lists.boost.org/MailArchives/boost/msg28375.php:
>
> > 1. If we provided specializations for lists up to N elements, it
would
> > handle short lists quickly.
> > 2. There's no point in recursing in these specializations: we know
how
> > long the list is, so we might as well just unroll the entire
> > implementation. That would be likely to further improve compile
times.
> > 3. The unrolled version for longer sequences would just be a special
> > case of the short-sequence specializations
>
> then I would do something along these lines:

<snip>

>
> The 'aux::unrolling_size' template then would return -1 by default,
and
> would be specialized for specific sequence types (e.g. list##i) for
which we
> can determine the size at O(1).
>
> I would gladly accept an optimization of any existing MPL algorithm
based on
> a variation of the above approach (if you do it, though, please
generate
> these numerous specializations using the Preprocessor library, not
copy &
> paste :).
>

After some considerable thought, what you're saying makes sense to me.
However, a question:

Are you insisting on the use of iterators in an optimized count_if for
reasons of generality? Of course it's always hard to tell what's going
to make any given compiler's template engine happy, but this seems a bit
like anti-optimization to me. What Hamish thinks he discovered was that
GCC is really efficient at operating on simple type lists. Why wouldn't
we want to capitalize on that? At least, it seems worth testing both
approaches to see how they compare. I'd only be willing to pay a small
price for generality of the optimized version.

-Dave