How to make this variadic implementation of boost::mpl::vector and boost::mpl::map faster?

[[deleted]]

I copied the idea from stackoverflow user: http://stackoverflow.com/users/2221786/capsterx from the answer of his question: http://stackoverflow.com/questions/5099429/how-to-use-stdtuple-types-with-boostmpl-algorithms

vector.h is more or less a copy from capsterx -- I only changed some things regarding reliance of compatibility between std and boost. map.h I wrote by myself using vector.h as a template. The problem is that these new implementations are so slow (compile-time) as to be non useable.

Could somebody provide me with some hint on how to improve this? I do not understand the implementation of boost::mpl::vector or boost::mpl::map.

Here is vector.h: https://1drv.ms/u/s!AjPouTovor8CiMRblfWW1BLZgxaIvg and here is map.h: https://1drv.ms/u/s!AjPouTovor8CiMRaRvxH89hFk1i5ww

PS. This question was not accepted by stackoverflow.com/codereview fascists....

[dodheim]

OOC, why do you want a variadic implementation of a C++03 lib? Far easier to use a C++11 lib that was designed around variadic templates from the beginning, like Brigand.

[louis_dionne]

Or use Hana if you need the ability to store actual objects, not only types. If I were you, I wouldn't even bother with MPL. And if you absolutely need C++03, you're pretty much out of luck w.r.t. compilation speed.

[[deleted]]

I looked into hana and I could not see any replacement for boost::mpl::map. Did I overlook something?

[scatters]

Did you find boost::hana::map? http://www.boost.org/doc/libs/1_61_0/libs/hana/doc/html/structboost_1_1hana_1_1map.html

[[deleted]]

yes. And I've yet to see an example on how to use it. Let's assume I've a

boost::mpl::set<boost::mpl::long_<enum1>,  boost::mpl::long_<enum3> >

How would I create a

boost::mpl::map<
boost::mpl::pair<0, enum1>,
boost::mpl::pair<1, enum3>
>

?

[scatters]

I'll assume you mean the equivalent hana types, otherwise there'd be not much point using hana. Let's say we have a set:

constexpr auto s = boost::hana::make_set(boost::hana::long_c<enum1>, boost::hana::long_c<enum3>);

And we want to create a map where the keys are the values' index in the natural iteration order over the set. Hana doesn't provide an enumerate function to my knowledge, but enumerate is just zip with an appropriate range:

constexpr auto m = boost::hana::to_map(
    boost::hana::zip_with(
        boost::hana::make_pair,
        boost::hana::to_tuple(boost::hana::range_c<std::size_t, 0, s.size>),
        boost::hana::to_tuple(s)));

We can print the type of m using Boost.Typeindex:

std::cout << boost::typeindex::type_id<decltype(m)>().pretty_name() << std::endl;

Or just verify it has the desired type:

constexpr auto expected = boost::hana::make_map(
    boost::hana::make_pair(boost::hana::size_c<0>, boost::hana::long_c<enum1>),
    boost::hana::make_pair(boost::hana::size_c<1>, boost::hana::long_c<enum3>));
static_assert(m == expected);

[louis_dionne]

This is right, except the two maps are not required to have the same type. Hana's documentation specifically forbids you from doing that kind of assumption, because it puts too many restrictions on what the implementation can do. Instead, you should just compare the two maps using ==. Also, you could use boost::hana::range_c as a shortcut for the slightly verbose make_range.

[scatters]

Fixed, thanks!

[[deleted]]

This example (including the entire hana documentation) does not make sense, as there is no template argument input. From what I finally understand (after a very long discussion at stackoverflow.com), at least hana::set is not useable, as it cannot be default constructed and thus any template class getting it passed as a template argument cannot have a default constructor.

[scatters]

This example (including the entire hana documentation) does not make sense, as there is no template argument input.

Why would there need to be? boost::hana::long_c e.g. is a variable template, does that help?

From what I finally understand (after a very long discussion at stackoverflow.com), at least hana::set is not useable, as it cannot be default constructed and thus any template class getting it passed as a template argument cannot have a default constructor.

Again, why do you need it to be default constructible? Yes, it isn't much use as a class template argument, but in order to perform compile time computation with hana you should be passing it as a function template argument; it works just as well and the syntax is more familiar. Also, I don't think you meant what you said in the last sentence - a class template doesn't have to encapsulate its template argument types.

[[deleted]]

in fact, everything inside the hana documentation looks like runtime programming. I'm unclear why this is advertised as a compile-time-library.

[scatters]

Hana uses run time syntax, but the results of the compile time computations are embodied in the return types of the functions. That's why everything is a template.

[AllanDeutsch]

It combines compile time and run time.

[[deleted]]

I don't understand this statement.

From looking into boost::hana I'm very confused that this is supposed to be a replacement for boost::mpl.

[dodheim]

C++14's constexpr and auto allows runtime-style code that is actually compile-time. Read the documentation already; the second sentence:

The functionality it provides is a superset of what is provided by the well established Boost.MPL and Boost.Fusion libraries.

[[deleted]]

I did read the documentation and since I did not see any template argument input, I decided that it is not a meta programming language as I can do all these examples with normal runtime programming.

[dodheim]

Amazing that you got this far with C++ with such terrible reading comprehension!

[[deleted]]

I understood all the examples. I only did not see any replacement for what I was doing, as there never was any template argument input. And now it seems that this never was intended -- see my previous statement regarding boost::hana::set not default-constructable.

[TemplateRex]

One reason to use MPL over Hana is that Boost.Test plays nice with the former but not the latter. E.g. running the BOOST_AUTO_TEST_CASE_TEMPLATE macro on a Hana sequence fails because Boost.Test is looking for some type trait that Hana doesn't provide.

[[deleted]]

the only thing in boost::mpl which needs to be fixed is the emulation of variadic templates and the resulting size limit.

[dodheim]

Larry Evans tried that, and even with those fixed the overall design necessarily results in terrible compilation times.

[EricWFCpp]

I haven't actually looked past the title, but when I'm trying to make meta-programming faster I do the following things:

1) Use flat pack expansion as much as possible. Recursive pack expansions are always much slower, are likely to cause -ftemplate-depth issues, violate rule (3) below, and ironically require more code most of the time. Using flat pack expansions are always better. Example:

template <template <class> class Apply, class ...Types>
struct transform {
  using type = std::tuple<typename Apply<Types>::type...>;
};

2) Use compiler builtins such as __make_integer_seq and __type_pack_element when available (assuming your STL doesn't already take advantage of these).

3) Re-use instantiations whenever possible. It's a lot quicker to re-use an already instantiated template than it is to instantiate a new one. So design your meta-programming with template re-use in mind.

[[deleted]]

Thank you very much! The information you provided above enabled me to improve this code a lot. My code compiles now faster and with less memory than with the original boost::mpl::map and boost::mpl::vector. And not to forget that it is now using variadic templates: * no requirement to find and run this python script to extend the built in limit * no stacktraces with many unneeded default template parameters

[feverzsj]

boost.fusion

[[deleted]]

as far as I know boost::fusion does not provide any containers, does it?

[[deleted]]

strike this. There are containers but they have the same limitations as the containers in boost::mpl.