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

From: Aleksey Gurtovoy (agurtovoy_at_[hidden])
Date: 2002-04-17 03:34:02

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:

    namespace aux {

    template<
          typename First
        , typename Last
        , typename Predicate
        , long Size
        >
    struct do_count_if;

    } // namespace aux

    template<
          typename Sequence
        , typename Predicate
        >
    struct count_if
        : aux::do_count_if<
              typename begin<Sequence>::type
            , typename end<Sequence>::type
            , aux::unrolling_size<Sequence>::value
            >
    {
    };

where 'aux::do_count_if' would be something close to this (sorry, it's
long):

    #define BOOST_MPL_UNROLLING_LIMIT 10

    namespace aux {

    // specializations for known sizes, up to BOOST_MPL_UNROLLING_LIMIT
    template<
          typename First
        , typename Last
        , typename Predicate
        >
    struct do_count_if<First,Last,Predicate,0>
    {
        typedef integral_c<unsigned long,0> type;
        typedef First last_iterator;
    };

    template<
          typename First
        , typename Last
        , typename Predicate
        >
    struct do_count_if<First,Last,Predicate,1>
    {
        typedef First iter0;
        typedef apply<Predicate,typename iter0::type>::type c0;
        typedef integral_c<unsigned long, c0::value> type;
        typedef iter0 last_iterator;
    };

    // ...

    // i == BOOST_MPL_UNROLLING_LIMIT
    template<
          typename First
        , typename Last
        , typename Predicate
        >
    struct do_count_if<First,Last,Predicate,i>
    {
        typedef First iter0;
        typedef apply<Predicate,typename iter0::type>::type c0;
        typedef typename iter0::next i1;
        typedef apply<Predicate,typename iter1::type>::type c1;
        // ...
        typedef typename iter##i-1::next iter##i;
        typedef apply<Predicate,typename iter##i::type>::type c##i;

        typedef integral_c<
              unsigned long
            , c0::value + c1::value + .. + c##i::value
            > type;

        typedef iter##i last_iterator;
    };

    // specialization for sequences with unknown size
    template<
          typename First
        , typename Last
        , typename Predicate
        >
    struct do_count_if<First,Last,Predicate,-1>
    {
        // implement unsophisticated version
        // ...
    };

    // specialization for sequences with known size which
    // exceeds BOOST_MPL_UNROLLING_LIMIT
    template<
          typename First
        , typename Last
        , typename Predicate
        , long Size
        >
    struct do_count_if
    {
        typedef do_count_if<
              First
            , Last
            , Predicate
            , BOOST_MPL_UNROLLING_LIMIT
            > first_segment_;

        typedef do_count_if<
              first_segment_::last_iterator
            , Last
            , Size - BOOST_MPL_UNROLLING_LIMIT
            > rest_;

        typedef integral_c<
              unsigned long
            , first_segment_::type::value + rest_::type::value
            >::type type;
    };

    } // namespace aux

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 :).

Aleksey