Boost logo

Boost :

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
> > > 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
> > raw list.
> You don't need to, and making the unrolling work for lists only would
> against the library philosophy. If we are talking about possibility of
> implementing the approach that Dave outlined in
> > 1. If we provided specializations for lists up to N elements, it
> > handle short lists quickly.
> > 2. There's no point in recursing in these specializations: we know
> > long the list is, so we might as well just unroll the entire
> > implementation. That would be likely to further improve compile
> > 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:


> The 'aux::unrolling_size' template then would return -1 by default,
> 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
> 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.


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