Re: [boost] Reimplementation of the MPL for C++11

Subject: Re: [boost] Reimplementation of the MPL for C++11
From: Dave Abrahams (dave_at_[hidden])
Date: 2013-10-21 00:32:38

on Sat Oct 19 2013, pfultz2 <pfultz2-AT-yahoo.com> wrote:

>> But knowing the forward-only nature of
> parameter packs, I wonder how you can implement a random-access sequence
> like vector without (a) instantiating O(N) templates, like tuple, or (b)
> using the preprocessor and living with arbitrary limits. 
>
> The O(N) instantiation would happen at creation of the vector, not at
> lookup.
> Something like this:
>
>     template<long N, class... Ts>
>     struct vector_base;
>
>     template<long N, class T, class... Ts>
>     struct vector_base<N, T, Ts...>
>     : vector_base<N+1, Ts...>
>     {
>         using vector_base<N+1, Ts...>::item_;
>         static T item_(long_<N>);
>     };
>
>     template<long N>
>     struct vector_base<N>
>     {
>         static void item_();
>     };
>
>     template<class... Ts>
>     struct vector
>     : vector_base<0, Ts...>
>     {
>     };
>
> Then we have O(1) lookup using decltype:
>
>     template<class Vector, class Index>
>     struct at
>     {
>         typedef decltype(Vector::item_(Index())) type;
>     };
>
> I haven't tested this code yet, but the Boost.MPL works in a similiar way
> for
> compilers that suppor typeof. Of course generating the `item_` overloads
> with
> preprocessor perhaps could be faster than expaning the parameter pack using
> base classes, since it requires O(N) instantiations. However, if the
> prerpocessor version is faster, the `vector` could be specialized up to an
> arbitary limit to be generated by the preprocessor, and then after that it
> would use the base classes to generate the overloads.

True, but Matt Calabrese and Zach Lane proved that the ways we avoid O(N)
instantiation in the existing MPL don't actually result in the expected
speedups:

http://zao.se/~zao/boostcon/10/2010_presentations/mon/instantiations_must_go.pdf

IMO real measurement is a requirement for progress in this area.

-- 
Dave Abrahams