[boost] Boost.MPL: "Superlinear unrolling" to avoid recursion depthlimits

[Vesa Karvonen]

Hi,

The following is an example of using "superlinear unrolling". It compiles with

gcc version 2.95.4 20011002 (Debian prerelease)

using the default settings (max template recursion depth should be 17). The example code essentially applies the inc template 262 times. The example code uses partial specialization, but it should not be extremely difficult to remove, if necessary.

I think that superlinear unrolling could be useful for avoiding template recursion depth limitations, but the technique needs further studying.

It seems to be quite tricky to reach maximal iteration counts using this technique. I think that others might have more insight into how to tune the code for maximal iteration counts.

- Vesa Karvonen


#include <iostream>
#include <typeinfo>
#include "boost/mpl/apply_if.hpp"
#include "boost/mpl/if.hpp"
#include "boost/mpl/apply.hpp"
#include "boost/mpl/bool_c.hpp"
#include "boost/mpl/int_c.hpp"
#include "boost/mpl/identity.hpp"

namespace mpl = ::boost::mpl;

template<int d, class P, class O, class X_Outer>
struct until_down {
private:
typedef typename mpl::apply1<O,X_Outer>::type X_In;

typedef typename mpl::apply_if<typename mpl::apply1<P,X_In>::type,
mpl::identity<X_In>,
until_down<d-1,P,O,X_In> >::type X_1;

typedef typename mpl::apply_if<typename mpl::apply1<P,X_1>::type,
mpl::identity<X_1>,
until_down<d-1,P,O,X_1> >::type X_2;
public:
typedef typename mpl::apply_if<typename mpl::apply1<P,X_2>::type,
mpl::identity<X_2>,
until_down<d-1,P,O,X_2> >::type type;
};

template<class P, class O, class X>
struct until_down<0,P,O,X> : mpl::apply1<O,X> {};

template<int d, class P, class O, class X_Outer>
struct until_up {
private:
typedef typename mpl::apply1<O,X_Outer>::type X_In;

typedef typename mpl::apply_if<typename mpl::apply1<P,X_In>::type,
mpl::identity<X_In>,
until_down<d,P,O,X_In> >::type X_1;

typedef typename mpl::apply_if<typename mpl::apply1<P,X_1>::type,
mpl::identity<X_1>,
until_down<d,P,O,X_1> >::type X_2;
public:
typedef typename mpl::apply_if<typename mpl::apply1<P,X_2>::type,
mpl::identity<X_2>,
until_up<d+1,P,O,X_2> >::type type;
};

template<class P, class O, class X>
struct until : mpl::apply_if<mpl::apply1<P,X>,
mpl::identity<X>,
until_up<3,P,O,X> > {};

struct inc {
template<class T>
struct apply {
typedef typename T::next type;
};
};

struct always {
template<class T>
struct apply {
typedef typename mpl::bool_c<false> type;
};
};

template<int X>
struct is {
template<class T>
struct apply : mpl::bool_c<(T::value == X)> {
};
};

int main() {
std::cerr << until<is<262>, inc, mpl::int_c<0> >::type::value << '\n';

return 0;
}


_________________________________________________________________
Protect your PC - get McAfee.com VirusScan Online http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost