Reimplementation of the MPL for C++11

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Reimplementation of the MPL for C++11

Louis Dionne
Hi,

I am currently working on a reimplementation of the MPL for C++11. Although
the library is not complete yet, I would like to gauge interest for the
project from the Boost community.

I wanted to wait until I have resolved some core issues before posting here,
but reading the [modularization] thread made it unbearable to wait any
longer :-). The library is available on GitHub: github.com/ldionne/mpl11.

If some people happen to be interested by the project and would like to get
involved, please get in touch with me.


Regards,

Louis Dionne


N.B.: Some design decisions will be influenced by the community
(if there's interest) and I'm experimenting a lot. Don't be put
off if you see something that you don't like: it might change.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Eric Niebler-4
On 10/18/2013 11:07 AM, Louis Dionne wrote:

> Hi,
>
> I am currently working on a reimplementation of the MPL for C++11. Although
> the library is not complete yet, I would like to gauge interest for the
> project from the Boost community.
>
> I wanted to wait until I have resolved some core issues before posting here,
> but reading the [modularization] thread made it unbearable to wait any
> longer :-). The library is available on GitHub: github.com/ldionne/mpl11.
>
> If some people happen to be interested by the project and would like to get
> involved, please get in touch with me.

Disclaimer: I haven't looked. 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.

I fear that the mpl simply cannot be implemented with variadics without
radically changing the compile-time complexity of things.

--
Eric Niebler
Boost.org
http://www.boost.org

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Louis Dionne
Eric Niebler <eniebler <at> boost.org> writes:

[snip]

> Disclaimer: I haven't looked. 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.
>
> I fear that the mpl simply cannot be implemented with variadics without
> radically changing the compile-time complexity of things.

I think there's a way to do it in O(1), but it's not implemented in the
library right now. See [1].

In my opinion, this is only a tiny part of the MPL and even if it can't be
improved, there are other areas where we benefit from C++11 in the MPL.

Do you feel like that would be a deal breaker if O(1) access was impossible?

Regards,


Louis Dionne

[1]: github.com/dabrahams/mpl11/blob/master/standalone/O1_variadics.cpp



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Paul Fultz II
> 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.

Paul
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Mathias Gaunard-2
In reply to this post by Louis Dionne
On 18/10/13 20:07, Louis Dionne wrote:

> Hi,
>
> I am currently working on a reimplementation of the MPL for C++11. Although
> the library is not complete yet, I would like to gauge interest for the
> project from the Boost community.
>
> I wanted to wait until I have resolved some core issues before posting here,
> but reading the [modularization] thread made it unbearable to wait any
> longer :-). The library is available on GitHub: github.com/ldionne/mpl11.
>
> If some people happen to be interested by the project and would like to get
> involved, please get in touch with me.

It's interesting if it compiles faster and uses less memory.
I doubt that will be the case.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Louis Dionne
In reply to this post by Paul Fultz II
pfultz2 <pfultz2 <at> yahoo.com> writes:

[...]

> 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

[...]

That's how the map is currently implemented, but I don't use the preprocessor
to generate overloads.

See the top of [1] for details, it's pretty simple.

Regards,


Louis Dionne

[1]: github.com/ldionne/mpl11/blob/master/include/boost/mpl11/container/map.hpp



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Abel Sinkovics
In reply to this post by Louis Dionne
Hi,

On 2013-10-18 20:07, Louis Dionne wrote:

> Hi,
>
> I am currently working on a reimplementation of the MPL for C++11. Although
> the library is not complete yet, I would like to gauge interest for the
> project from the Boost community.
>
> I wanted to wait until I have resolved some core issues before posting here,
> but reading the [modularization] thread made it unbearable to wait any
> longer :-). The library is available on GitHub: github.com/ldionne/mpl11.
>
> If some people happen to be interested by the project and would like to get
> involved, please get in touch with me.

I'm developing template metaprogramming libraries and I have built a
"base" library (Metamonad) based on the functional nature of template
metaprogramming. It is mostly an extension of the current Boost.MPL. It
adds algebraic data-types, pattern matching, let expressions, exception
handling, etc.

I have looked at a few things in your mpl11 (sample programs would be
useful). I have noticed the following:

1)
I can see that you have this syntax for if_:

if_<CONDITION, THEN>::
else_if<CONDITION, THEN>::
...
else<ELSE>

which is I think a great DSL for the if structure. Can this be used in a
lambda expression? For example:

sort<
   vector<....>,
   lambda<
     if_<greater<_1, _2>, ...>::
     else<...>
   >
 >

I have built a DSL similar to your if_ for exception handling in
template metaprograms:

try_<...>
::catch_<....>
::catch_<....>

but I could not make it work with lambdas (and a number of things I have
built using similar techniques). So I had to change it to:

try_<....,
   catch_<....>,
   catch_<....>
 >





There are a few things I would reconsider in a rewrite of MPL:

2)
Metafunctions could support lazy evaluation. This makes it possible to
use lazy evaluation strategy in metaprograms which makes the code easier
to read. (Even for a factorial or Fibonacci there are huge differences)

Currently MPL does not support this - for example the following works:

boost::mpl::at_c<
   boost::mpl::push_front<
     boost::mpl::vector<int, double, char>,
     void
   >::type,
   1
 >::type

but the following does not:

boost::mpl::at_c<
   boost::mpl::push_front<
     boost::mpl::vector<int, double, char>,
     void
   >,
   1
 >::type

The problem here is that at_c expects the caller to pass in
push_front<...>::type instead of just push_front<...>. at_c could
assume, that it has to use its argument's ::type instead of the argument
directly.

I have built a template called lazy<...> (see
http://abel.web.elte.hu/mpllibs/metamonad/manual.html#lazy-metafunctions)
as a workaround, but having the metafunctions of MPL supporting it would
be more efficient.

Also, I have reimplemented some of the things that are in Boost.MPL (eg.
http://abel.web.elte.hu/mpllibs/metamonad/reference.html#pair,
http://abel.web.elte.hu/mpllibs/metamonad/if_.html) in a way that they
support lazy evaluation and use them instead of the original MPL versions.




3)
Naming the lambda arguments _1, _2, ... has limitations. When you use
lambda inside lambda, you can not refer to the arguments of the outer
lambda from the inner one. I have built a lambda implementation where
you can give the arguments names and use that instead of the MPL one.
Here is an example for using it:

using namespace mpllibs::metamonad;
using namespace mpllibs::metamonad::name;

boost::mpl::sort<
   boost::mpl::vector_c<int, 0, 3, 9, 4, 7, 2, 1, 8, 5, 6>,
   lambda_c<x, y, boost::mpl::greater<x, y>>
 >::type

You can read about my lambda implementation here:
http://abel.web.elte.hu/mpllibs/metamonad/manual.html#lambda-expressions 
It is based on syntaxes and variables, which are described earlier on
that page.

This problem can also be solved by using De Brujin indices, but I find
using names more readable so I decided to use this in my lambdas.


Regards,
   Ábel




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

cppljevans
In reply to this post by Louis Dionne
On 10/19/13 12:49, Louis Dionne wrote:

> pfultz2 <pfultz2 <at> yahoo.com> writes:
>
> [...]
>
>> 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
>
> [...]
>
> That's how the map is currently implemented, but I don't use the preprocessor
> to generate overloads.
>
> See the top of [1] for details, it's pretty simple.
>
> Regards,
>
>
> Louis Dionne
>
> [1]: github.com/ldionne/mpl11/blob/master/include/boost/mpl11/container/map.hpp
>
>
>
Hi Dionne,

I tried variadic templates several years ago.
The code is here:

http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/mpl/

Unfortunately, as Eric and Mathias already hinted, the compile
times are much slower than with the existing mpl.  The existing
mpl uses the preprocessor to lessen compile times, a method
mentioned by Eric in his (b) item:

   (b) using the preprocessor and living with arbitrary limits.

Christopher Schmidt used the preprocessor to implement
a variadic fusion using the help of the preprocessor to lessen
compile times but, IIUC, he used some method (I'll call it
"chunking") so that the preprocessor didn't have arbitrary
limits:

   http://lists.boost.org/Archives/boost/2012/03/191091.php

NOTE:  I tried the link in that post to Christopher's code
and it no longer works :(  However, I'm sure Christopher
(if you can find his email address) would be able to
supply an update location for the code.  You might could
use the chunking method to minimize the compile times.

HTH.
-regards,
Larry




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

cppljevans
On 10/20/13 06:23, Larry Evans wrote:
[snip]

> Christopher Schmidt used the preprocessor to implement
> a variadic fusion using the help of the preprocessor to lessen
> compile times but, IIUC, he used some method (I'll call it
> "chunking") so that the preprocessor didn't have arbitrary
> limits:
>
>    http://lists.boost.org/Archives/boost/2012/03/191091.php
>
> NOTE:  I tried the link in that post to Christopher's code
> and it no longer works :(  However, I'm sure Christopher
> (if you can find his email address) would be able to
> supply an update location for the code.  You might could
> use the chunking method to minimize the compile times.
>
The code here:

http://svn.boost.org/svn/boost/sandbox/variadic_templates/sandbox/slim/

might be helpful.  It was based on Chrisopher's code but had
to be modified slightly as mentioned in the post:

http://comments.gmane.org/gmane.comp.compilers.clang.devel/24145

which also mentions the slow compile times when not using the
preprocessor.

-regards,
Larry




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Agustín K-ballo Bergé
On 20/10/2013 09:04 a.m., Larry Evans wrote:

> On 10/20/13 06:23, Larry Evans wrote:
> [snip]
>> Christopher Schmidt used the preprocessor to implement
>> a variadic fusion using the help of the preprocessor to lessen
>> compile times but, IIUC, he used some method (I'll call it
>> "chunking") so that the preprocessor didn't have arbitrary
>> limits:
>>
>>    http://lists.boost.org/Archives/boost/2012/03/191091.php
>>
>> NOTE:  I tried the link in that post to Christopher's code
>> and it no longer works :(  However, I'm sure Christopher
>> (if you can find his email address) would be able to
>> supply an update location for the code.  You might could
>> use the chunking method to minimize the compile times.
>>
> The code here:
>
> http://svn.boost.org/svn/boost/sandbox/variadic_templates/sandbox/slim/
>
> might be helpful.  It was based on Chrisopher's code but had
> to be modified slightly as mentioned in the post:
>
> http://comments.gmane.org/gmane.comp.compilers.clang.devel/24145
>
> which also mentions the slow compile times when not using the
> preprocessor.
>

Compilers appear to have improved since then! I decided to take gcc4.8.1
and fusion::map for a spin, since I happen to have a variadic
implementation of map that does not use recursion. The results of this
crude exercise can be found here:
https://gist.github.com/K-ballo/a44590159133997abcdc

What I read from them is that each technique reduces compile-time and
memory usage in the order I'd expected (C++98 > C++98 preprocessed >
C++11 recursive > C++11 non-recursive), contrary to what this thread
seems to be saying. Additionally, instantiating a 255 element variadic
non-recursive map and getting to the middle of it takes only slightly
more time and just 1.3x the memory it takes doing the same for a 50
element C++03 preprocessed map.

There's lots of potential in variadics, as long as they are implemented
carefully.

Regards,
--
Agustín K-ballo Bergé.-
http://talesofcpp.fusionfenix.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Louis Dionne
In reply to this post by Abel Sinkovics
Abel Sinkovics <abel <at> elte.hu> writes:

> 1)
> I can see that you have this syntax for if_:
>
> if_<CONDITION, THEN>::
> else_if<CONDITION, THEN>::
> ...
> else<ELSE>
>
> which is I think a great DSL for the if structure. Can this be used in a
> lambda expression? For example:

Yes, you can use it with lambda expressions.
This one took a lot of work to get working, though :-).

> 2)
> Metafunctions could support lazy evaluation. This makes it possible to
> use lazy evaluation strategy in metaprograms which makes the code easier
> to read. (Even for a factorial or Fibonacci there are huge differences)

I'm aware of this and I'm currently searching for a general solution. I think
I might have a very elegant solution for this; I'll provide an update when/if
I get it working.

> 3)
> Naming the lambda arguments _1, _2, ... has limitations. When you use
> lambda inside lambda, you can not refer to the arguments of the outer
> lambda from the inner one. I have built a lambda implementation where
> you can give the arguments names and use that instead of the MPL one.

Yes, I'm aware of this. I'm currently working on let-expressions. I'm also
working on generalized placeholders: they can perform arbitrary computations
and return sequences of types so that it's possible to use LambdaExpressions
with variadic parameter packs. Example:

    mpl11::apply<your_metafunction<mpl11::_args>, ParameterPack...>

The obvious extension to this is to have placeholders like mpl11::_args<i, j>
which returns the arguments in the range [i, j). This is a work in progress.

> You can read about my lambda implementation here:
> http://abel.web.elte.hu/mpllibs/metamonad/manual.html#lambda-expressions 
> It is based on syntaxes and variables, which are described earlier on
> that page.

I'll definitely have a look at this, thanks for the pointer!

> This problem can also be solved by using De Brujin indices, but I find
> using names more readable so I decided to use this in my lambdas.

Same here, I'm not planning on using de Bruijn indices.

Regards,


Louis Dionne



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Dave Abrahams
In reply to this post by Paul Fultz II

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


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Michael Marcin-3
On 10/20/2013 11:32 PM, Dave Abrahams wrote:
> 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.
>

Strange the video for this presentation doesn't load for me.

http://blip.tv/boostcon/matt-calabrese-zachary-laine-instantiations-must-go-4161957

Is it working for other?


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Matt Calabrese
My concepts without concepts video also does not load. I tried contacting
Marshall about it, but I never heard back. Certainly there must be backups
somewhere so that they can be re-uploaded, or are they just lost now?


On Mon, Oct 21, 2013 at 11:00 AM, Michael Marcin <[hidden email]>wrote:

> On 10/20/2013 11:32 PM, Dave Abrahams wrote:
>
>> 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<http://zao.se/~zao/boostcon/10/2010_presentations/mon/instantiations_must_go.pdf>
>>
>> IMO real measurement is a requirement for progress in this area.
>>
>>
> Strange the video for this presentation doesn't load for me.
>
> http://blip.tv/boostcon/matt-**calabrese-zachary-laine-**
> instantiations-must-go-4161957<http://blip.tv/boostcon/matt-calabrese-zachary-laine-instantiations-must-go-4161957>
>
> Is it working for other?
>
>
>
> ______________________________**_________________
> Unsubscribe & other changes: http://lists.boost.org/**
> mailman/listinfo.cgi/boost<http://lists.boost.org/mailman/listinfo.cgi/boost>
>



--
-Matt Calabrese

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

cppljevans
In reply to this post by Agustín K-ballo Bergé
On 10/20/13 10:33, Agustín K-ballo Bergé wrote:
> On 20/10/2013 09:04 a.m., Larry Evans wrote:
[snip]

>> The code here:
>>
>> http://svn.boost.org/svn/boost/sandbox/variadic_templates/sandbox/slim/
>>
>> might be helpful.  It was based on Chrisopher's code but had
>> to be modified slightly as mentioned in the post:
>>
>> http://comments.gmane.org/gmane.comp.compilers.clang.devel/24145
>>
>> which also mentions the slow compile times when not using the
>> preprocessor.
>>
>
> Compilers appear to have improved since then! I decided to take gcc4.8.1
> and fusion::map for a spin, since I happen to have a variadic
> implementation of map that does not use recursion. The results of this
> crude exercise can be found here:
> https://gist.github.com/K-ballo/a44590159133997abcdc

This link only has the test driver code and the test results file.
Could you please provide a link to the implementation of this
non-recursive map?

-regards,
Larry



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Agustín K-ballo Bergé
On 22/10/2013 12:28 a.m., Larry Evans wrote:

> On 10/20/13 10:33, Agustín K-ballo Bergé wrote:
>> On 20/10/2013 09:04 a.m., Larry Evans wrote:
> [snip]
>>> The code here:
>>>
>>> http://svn.boost.org/svn/boost/sandbox/variadic_templates/sandbox/slim/
>>>
>>> might be helpful.  It was based on Chrisopher's code but had
>>> to be modified slightly as mentioned in the post:
>>>
>>> http://comments.gmane.org/gmane.comp.compilers.clang.devel/24145
>>>
>>> which also mentions the slow compile times when not using the
>>> preprocessor.
>>>
>>
>> Compilers appear to have improved since then! I decided to take gcc4.8.1
>> and fusion::map for a spin, since I happen to have a variadic
>> implementation of map that does not use recursion. The results of this
>> crude exercise can be found here:
>> https://gist.github.com/K-ballo/a44590159133997abcdc
>
> This link only has the test driver code and the test results file.
> Could you please provide a link to the implementation of this
> non-recursive map?
>

Certainly, you can find the proof of concept implementation I used for
the tests here: http://fusionfenix.com/ktests/boost.fusion.map.zip
It is intended to be used with Boost.Fusion from trunk, you just need to
replace fusion's "map" directory with the "map_" one in the zip.

Keep in mind that it is just a proof of concept. I am working on a full
fledged implementation as time permits, which is not as often as I would
like.

Regards,
--
Agustín K-ballo Bergé.-
http://talesofcpp.fusionfenix.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Marshall Clow-2
In reply to this post by Matt Calabrese
On Oct 21, 2013, at 7:45 PM, Matt Calabrese <[hidden email]> wrote:

> My concepts without concepts video also does not load. I tried contacting
> Marshall about it, but I never heard back. Certainly there must be backups
> somewhere so that they can be re-uploaded, or are they just lost now?

That's because I'm a bozo.

I have the videos (at home), and will try to get them uploaded tomorrow.
Sorry.

> On Mon, Oct 21, 2013 at 11:00 AM, Michael Marcin <[hidden email]>wrote:
>
>> On 10/20/2013 11:32 PM, Dave Abrahams wrote:
>>
>>> 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<http://zao.se/~zao/boostcon/10/2010_presentations/mon/instantiations_must_go.pdf>
>>>
>>> IMO real measurement is a requirement for progress in this area.
>>>
>>>
>> Strange the video for this presentation doesn't load for me.
>>
>> http://blip.tv/boostcon/matt-**calabrese-zachary-laine-**
>> instantiations-must-go-4161957<http://blip.tv/boostcon/matt-calabrese-zachary-laine-instantiations-must-go-4161957>
>>
>> Is it working for other?


-- Marshall

Marshall Clow     Idio Software   <mailto:[hidden email]>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
        -- Yu Suzuki


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

cppljevans
In reply to this post by Agustín K-ballo Bergé
On 10/21/13 22:51, Agustín K-ballo Bergé wrote:

> On 22/10/2013 12:28 a.m., Larry Evans wrote:
>> On 10/20/13 10:33, Agustín K-ballo Bergé wrote:
>>> On 20/10/2013 09:04 a.m., Larry Evans wrote:
>> [snip]
>>>> The code here:
>>>>
>>>> http://svn.boost.org/svn/boost/sandbox/variadic_templates/sandbox/slim/
>>>>
>>>> might be helpful.  It was based on Chrisopher's code but had
>>>> to be modified slightly as mentioned in the post:
>>>>
>>>> http://comments.gmane.org/gmane.comp.compilers.clang.devel/24145
>>>>
>>>> which also mentions the slow compile times when not using the
>>>> preprocessor.
>>>>
>>>
>>> Compilers appear to have improved since then! I decided to take gcc4.8.1
>>> and fusion::map for a spin, since I happen to have a variadic
>>> implementation of map that does not use recursion. The results of this
>>> crude exercise can be found here:
>>> https://gist.github.com/K-ballo/a44590159133997abcdc
>>
>> This link only has the test driver code and the test results file.
>> Could you please provide a link to the implementation of this
>> non-recursive map?
>>
>
> Certainly, you can find the proof of concept implementation I used for
> the tests here: http://fusionfenix.com/ktests/boost.fusion.map.zip
> It is intended to be used with Boost.Fusion from trunk, you just need to
> replace fusion's "map" directory with the "map_" one in the zip.
>
> Keep in mind that it is just a proof of concept. I am working on a full
> fledged implementation as time permits, which is not as often as I would
> like.
>
> Regards,

The map.hpp in the zip file shows it uses the preprocessor:
--{--cut here--

namespace boost { namespace fusion
{
     struct void_;
     struct fusion_sequence_tag;

     template <BOOST_PP_ENUM_PARAMS(FUSION_MAX_MAP_SIZE, typename T)>
     struct map :
sequence_base<map<BOOST_PP_ENUM_PARAMS(FUSION_MAX_MAP_SIZE, T)> >
     {
         struct category : random_access_traversal_tag, associative_tag {};
--}--cut here--

with an option to use some preprocessed headers:

--{--cut here--
#if !defined(BOOST_FUSION_DONT_USE_PREPROCESSED_FILES)
#include <boost/fusion/container/map/detail/cpp03/preprocessed/map.hpp>
#else
#if defined(__WAVE__) && defined(BOOST_FUSION_CREATE_PREPROCESSED_FILES)
#pragma wave option(preserve: 2, line: 0, output:
"detail/preprocessed/map" FUSION_MAX_MAP_SIZE_STR ".hpp")
#endif

--}--cut here--

The test results contain, for C++98:

--{--cut here--

C++98:

Execution times (seconds)
  phase parsing           :   5.29 (97%) usr  349702 kB (98%) ggc
--}--cut here--
and:

--{--cut here--
C++98 (preprocessed):

Execution times (seconds)
  phase setup             :   0.01 ( 0%) usr     547 kB ( 0%) ggc
  phase parsing           :   2.64 (93%) usr  112842 kB (95%) ggc
--}--cut here--

However, there's no (preprocessed) indicator for the C++11 results.
Instead, there's only:
--{--cut here--
C++11 (recursive):

Execution times (seconds)
  phase setup             :   0.01 ( 1%) usr     653 kB ( 1%) ggc
  phase parsing           :   0.88 (70%) usr   74763 kB (88%) ggc
--}--cut here--
and:
--{--cut here--
C++11 (non-recursive):

Execution times (seconds)
  phase parsing           :   0.79 (95%) usr   70483 kB (96%) ggc
--}--cut here--

Was:

   defined(BOOST_FUSION_DONT_USE_PREPROCESSED_FILES)

for the both C++11 tests or not?

BTW, the difference between C++11 (recursive) and (non-recursive)
was certainly dramatic for the results prefixed with:

  255 elements in a fusion::map, accessing the 129th one

test (56.93 vs 2.90).

Looks promising.

-regards,
Larry


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Lars Viklund
In reply to this post by Marshall Clow-2
On Tue, Oct 22, 2013 at 06:18:07AM -0700, Marshall Clow wrote:

> On Oct 21, 2013, at 7:45 PM, Matt Calabrese <[hidden email]> wrote:
>
> > My concepts without concepts video also does not load. I tried contacting
> > Marshall about it, but I never heard back. Certainly there must be backups
> > somewhere so that they can be re-uploaded, or are they just lost now?
>
> That's because I'm a bozo.
>
> I have the videos (at home), and will try to get them uploaded tomorrow.
> Sorry.
>
> > On Mon, Oct 21, 2013 at 11:00 AM, Michael Marcin <[hidden email]>wrote:
> >
> >> On 10/20/2013 11:32 PM, Dave Abrahams wrote:
> >>
> >>> 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<http://zao.se/~zao/boostcon/10/2010_presentations/mon/instantiations_must_go.pdf>
> >>>
> >>> IMO real measurement is a requirement for progress in this area.
> >>>
> >>>
> >> Strange the video for this presentation doesn't load for me.
> >>
> >> http://blip.tv/boostcon/matt-**calabrese-zachary-laine-**
> >> instantiations-must-go-4161957<http://blip.tv/boostcon/matt-calabrese-zachary-laine-instantiations-must-go-4161957>
> >>
> >> Is it working for other?

All the videos I could mirror in 2010 are mirrored at:
http://zao.se/~zao/boostcon/10/
and this one in particular is:
http://zao.se/~zao/boostcon/10/Boostcon-MattCalabreseZacharyLaineInstantiationsMustGo495.mov

I started out mirroring the videos for personal use back in 2009, and as
blip.tv showed to be rather unreliable for actually getting at the
videos, I ended up having a semi-public mirror of the videos and
presentations.

I have most (all?) videos from 2009-2011.

Jeroen has a mirror at http://wipkip.nikhef.nl/events/BoostCon/ as well.

--
Lars Viklund | [hidden email]

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Reimplementation of the MPL for C++11

Agustín K-ballo Bergé
In reply to this post by cppljevans
On 22/10/2013 10:27 a.m., Larry Evans wrote:

> On 10/21/13 22:51, Agustín K-ballo Bergé wrote:
>> On 22/10/2013 12:28 a.m., Larry Evans wrote:
>>> On 10/20/13 10:33, Agustín K-ballo Bergé wrote:
>>>> On 20/10/2013 09:04 a.m., Larry Evans wrote:
>>> [snip]
>>>>> The code here:
>>>>>
>>>>> http://svn.boost.org/svn/boost/sandbox/variadic_templates/sandbox/slim/
>>>>>
>>>>>
>>>>> might be helpful.  It was based on Chrisopher's code but had
>>>>> to be modified slightly as mentioned in the post:
>>>>>
>>>>> http://comments.gmane.org/gmane.comp.compilers.clang.devel/24145
>>>>>
>>>>> which also mentions the slow compile times when not using the
>>>>> preprocessor.
>>>>>
>>>>
>>>> Compilers appear to have improved since then! I decided to take
>>>> gcc4.8.1
>>>> and fusion::map for a spin, since I happen to have a variadic
>>>> implementation of map that does not use recursion. The results of this
>>>> crude exercise can be found here:
>>>> https://gist.github.com/K-ballo/a44590159133997abcdc
>>>
>>> This link only has the test driver code and the test results file.
>>> Could you please provide a link to the implementation of this
>>> non-recursive map?
>>>
>>
>> Certainly, you can find the proof of concept implementation I used for
>> the tests here: http://fusionfenix.com/ktests/boost.fusion.map.zip
>> It is intended to be used with Boost.Fusion from trunk, you just need to
>> replace fusion's "map" directory with the "map_" one in the zip.
>>
>
> The map.hpp in the zip file shows it uses the preprocessor:
> --{--cut here--
>
> namespace boost { namespace fusion
> {
>      struct void_;
>      struct fusion_sequence_tag;
>
>      template <BOOST_PP_ENUM_PARAMS(FUSION_MAX_MAP_SIZE, typename T)>
>      struct map :
> sequence_base<map<BOOST_PP_ENUM_PARAMS(FUSION_MAX_MAP_SIZE, T)> >
>      {
>          struct category : random_access_traversal_tag, associative_tag {};
> --}--cut here--
>

You are looking at the C++03 implementation, the one provided by Fusion
already, which is only picked #if
!defined(BOOST_FUSION_HAS_VARIADIC_MAP). The C++11 declaration is the
obvious one:

     template <typename ...T>
     struct map;

> Was:
>
>    defined(BOOST_FUSION_DONT_USE_PREPROCESSED_FILES)
>
> for the both C++11 tests or not?
>

I don't think it was, but it might have been... It is irrelevant for the
C++11 implementations.

Regards,
--
Agustín K-ballo Bergé.-
http://talesofcpp.fusionfenix.com

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