[mpl] is there a or_seq like logical metafunction?
Hello, I needs calculate the mlp::or_ of a sequence of nullary logical metafunction. This seams quite simple. I have do the following: <code> template <typename Seq> struct or_seq; template <typename Seq, long N> struct or_seq_aux : mpl::or_< typename mpl::front<Seq>::type, or_seq<typename mpl::pop_front<Seq>::type>
{};
template <typename Seq> struct or_seq_aux<Seq, 1> : mpl::front<Seq>::type {}; template <typename Seq> struct or_seq : or_seq_aux<Seq, mpl::size<Seq>::value> {}; </code> Is there a boost or_seq like logical metafunction? Is there a better way to do it? I would be extremely interested in any suggestions. Best regards --------------------------- Vicente Juan Botet Escriba
AMDG vicente.botet wrote:
Hello,
I needs calculate the mlp::or_ of a sequence of nullary logical metafunction.
This seams quite simple. I have do the following: <code> template <typename Seq> struct or_seq;
template <typename Seq, long N> struct or_seq_aux : mpl::or_< typename mpl::front<Seq>::type, or_seq<typename mpl::pop_front<Seq>::type>
{};
template <typename Seq> struct or_seq_aux<Seq, 1> : mpl::front<Seq>::type {};
template <typename Seq> struct or_seq : or_seq_aux<Seq, mpl::size<Seq>::value> {}; </code>
Is there a boost or_seq like logical metafunction? Is there a better way to do it?
I would be extremely interested in any suggestions.
not_<is_same<typename find_if<Seq, _>::type, typename end<Seq>::type> >? In Christ, Steven Watanabe
Thank you Steven, ----- Original Message ----- From: "Steven Watanabe" <watanabesj@gmail.com> To: <boost@lists.boost.org> Sent: Thursday, March 06, 2008 6:24 AM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction?
AMDG
vicente.botet wrote:
Hello,
I needs calculate the mlp::or_ of a sequence of nullary logical metafunction.
This seams quite simple. I have do the following: <code> template <typename Seq> struct or_seq;
template <typename Seq, long N> struct or_seq_aux : mpl::or_< typename mpl::front<Seq>::type, or_seq<typename mpl::pop_front<Seq>::type>
{};
template <typename Seq> struct or_seq_aux<Seq, 1> : mpl::front<Seq>::type {};
template <typename Seq> struct or_seq : or_seq_aux<Seq, mpl::size<Seq>::value> {}; </code>
Is there a boost or_seq like logical metafunction? Is there a better way to do it?
I would be extremely interested in any suggestions.
not_<is_same<typename find_if<Seq, _>::type, typename end<Seq>::type> >?
In Christ, Steven Watanabe
I have tested your much more compact solution and it works as expected. Here it is with the mpl namespace: template <typename Seq> struct or_seq : mpl::not_< boost::is_same<typename mpl::find_if<Seq, mpl::_>::type, typename mpl::end<Seq>::type> > {}; I don't know if people needs things logical metafunctions like or_seq, and_seq could also be the case. I thing that these two logical metafunctions have a place in mpl. What do you thing? _____________________ Vicente Juan Botet Escriba
On Thu, Mar 6, 2008 at 8:12 PM, vicente.botet <vicente.botet@wanadoo.fr> wrote:
From: "Steven Watanabe" <watanabesj@gmail.com>
AMDG
vicente.botet wrote:
Hello,
I needs calculate the mlp::or_ of a sequence of nullary logical metafunction.
This seams quite simple. I have do the following: <code> template <typename Seq> struct or_seq;
template <typename Seq, long N> struct or_seq_aux : mpl::or_< typename mpl::front<Seq>::type, or_seq<typename mpl::pop_front<Seq>::type>
{};
template <typename Seq> struct or_seq_aux<Seq, 1> : mpl::front<Seq>::type {};
template <typename Seq> struct or_seq : or_seq_aux<Seq, mpl::size<Seq>::value> {}; </code>
Is there a boost or_seq like logical metafunction? Is there a better way to do it?
I would be extremely interested in any suggestions.
not_<is_same<typename find_if<Seq, _>::type, typename end<Seq>::type> >?
In Christ, Steven Watanabe
I have tested your much more compact solution and it works as expected. Here it is with the mpl namespace:
template <typename Seq> struct or_seq : mpl::not_< boost::is_same<typename mpl::find_if<Seq, mpl::_>::type, typename mpl::end<Seq>::type> > {};
It seems a perfect application for fold: template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::quote2<mpl::or_> > , Seq > {}; template<typename Seq> struct and_seq : mpl::apply< mpl::fold<mpl::_1, mpl::true_, mpl::quote2<mpl::and_> > , Seq > {}; -- gpd
AMDG Giovanni Piero Deretta wrote:
It seems a perfect application for fold:
template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::quote2<mpl::or_> > , Seq > {};
template<typename Seq> struct and_seq : mpl::apply< mpl::fold<mpl::_1, mpl::true_, mpl::quote2<mpl::and_> > , Seq > {};
Not quite, because we want it to short circuit. Not to mention that quote2 will not work on and_ and or_. In Christ, Steven Watanabe
On Fri, Mar 7, 2008 at 4:32 PM, Steven Watanabe <watanabesj@gmail.com> wrote:
AMDG
Giovanni Piero Deretta wrote:
It seems a perfect application for fold:
template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::quote2<mpl::or_> > , Seq > {};
template<typename Seq> struct and_seq : mpl::apply< mpl::fold<mpl::_1, mpl::true_, mpl::quote2<mpl::and_> > , Seq > {};
Not quite, because we want it to short circuit.
Hum, I think it actually does short circuit evaulation (haskel-like): struct bad {}; typedef mpl::vector<mpl::false_, mpl::false_, bad> ffb_v; typedef mpl::vector<mpl::false_, mpl::false_, fail> tfb_v; or_seq<ffb_v> gives the expected compile time error (error: no type named 'type' in 'struct fail') , while or_seq<tfb_v> compiles fine (and yelds true).
Not to mention that quote2 will not work on and_ and or_.
I now see that and_ and or_ take n parameters, so the compiler should complain about quote2. (it did work for me because of the gcc extension that allows a template with default parameters to match a template template argument with less parameters.) This should fix the problem: template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::lambda<mpl::or_<mpl::_,mpl::_> > > , Seq
{};
Not shorter than your solution, but it is an MPL only solution. Playing with MPL is always fun :). -- gpd
In Christ, Steven Watanabe
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
AMDG Giovanni Piero Deretta wrote:
Hum, I think it actually does short circuit evaulation (haskel-like):
struct bad {}; typedef mpl::vector<mpl::false_, mpl::false_, bad> ffb_v; typedef mpl::vector<mpl::false_, mpl::false_, fail> tfb_v;
or_seq<ffb_v> gives the expected compile time error (error: no type named 'type' in 'struct fail') , while or_seq<tfb_v> compiles fine (and yelds true).
The short circuiting is done by and_ and or_, what I meant is that you still have to iterate through the entire sequence. In Christ, Steven Watanabe
on Fri Mar 07 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
Giovanni Piero Deretta wrote:
It seems a perfect application for fold:
template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::quote2<mpl::or_> > , Seq > {};
template<typename Seq> struct and_seq : mpl::apply< mpl::fold<mpl::_1, mpl::true_, mpl::quote2<mpl::and_> > , Seq > {};
Not quite, because we want it to short circuit. Not to mention that quote2 will not work on and_ and or_.
Yeah, these should be rewritten in terms of mpl::find. Not sure why mpl::apply was used here either, though maybe I'm missign something. -- Dave Abrahams Boost Consulting http://boost-consulting.com
Hi, ----- Original Message ----- From: "David Abrahams" <dave@boost-consulting.com> To: <boost@lists.boost.org> Sent: Monday, April 28, 2008 3:50 AM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction?
on Fri Mar 07 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
Giovanni Piero Deretta wrote:
It seems a perfect application for fold:
template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::quote2<mpl::or_> > , Seq > {};
template<typename Seq> struct and_seq : mpl::apply< mpl::fold<mpl::_1, mpl::true_, mpl::quote2<mpl::and_> > , Seq > {};
Not quite, because we want it to short circuit. Not to mention that quote2 will not work on and_ and or_.
Yeah, these should be rewritten in terms of mpl::find. Not sure why mpl::apply was used here either, though maybe I'm missign something.
-- Dave Abrahams Boost Consulting http://boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Steven Watanabe suggested also the use of find template <typename Seq> struct or_seq : mpl::not_< boost::is_same<typename mpl::find_if<Seq, mpl::_>::type, typename mpl::end<Seq>::type> > {}; I don't know if people needs things logical metafunctions like or_seq, and_seq could also be the case. I thing that these two logical metafunctions have a place in mpl. What do you thing Aleksey? Best regards _____________________ Vicente Juan Botet Escriba
On Mon, Apr 28, 2008 at 3:50 AM, David Abrahams <dave@boost-consulting.com> wrote:
on Fri Mar 07 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
Giovanni Piero Deretta wrote:
It seems a perfect application for fold:
template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::quote2<mpl::or_> > , Seq > {};
template<typename Seq> struct and_seq : mpl::apply< mpl::fold<mpl::_1, mpl::true_, mpl::quote2<mpl::and_> > , Seq > {};
Not quite, because we want it to short circuit. Not to mention that quote2 will not work on and_ and or_.
Yeah, these should be rewritten in terms of mpl::find. Not sure why mpl::apply was used here either, though maybe I'm missign something.
There is, in fact, no need to use it here. I'm just so used to write 'apply' to prevent ugly "typename ... ::type" boilerplate that instinctively stick it in mpl expressions even when they do not add anything. -- gpd
On 04/27/08 20:50, David Abrahams wrote:
on Fri Mar 07 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
Giovanni Piero Deretta wrote:
It seems a perfect application for fold:
template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::quote2<mpl::or_> > , Seq > {};
template<typename Seq> struct and_seq : mpl::apply< mpl::fold<mpl::_1, mpl::true_, mpl::quote2<mpl::and_> > , Seq > {};
Not quite, because we want it to short circuit. Not to mention that quote2 will not work on and_ and or_.
Yeah, these should be rewritten in terms of mpl::find. Not sure why mpl::apply was used here either, though maybe I'm missign something.
The curren mpl::find uses and_ indirectly (in iter_fold_if.hpp:46). Would such a recursive implementation still work? Anyway, J.Fletcher is now attempting a variadic template rewrite of mpl:;find: http://sourceforge.net/mailarchive/message.php?msg_name=F0DEE5AE9F6027488C06... which doesn't use and_; however, another alternative which does short-circuit is attached. It uses eval_if to short-circuit the evaluation. Fletcher's find, OTOH, used if_; however, I think that's just because he's not interested in optimization yet. A very similar or_ is done by simply exchanging the Zero and One parameters. Interestingly enough, the current and_ uses a similar pattern in that it recursively calls a template (and.hpp:23). The attached (with the similar or.hpp) passes the logical.cpp test.
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost@lists.boost.org> Sent: Saturday, February 07, 2009 8:24 PM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction?
On 04/27/08 20:50, David Abrahams wrote:
on Fri Mar 07 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
Giovanni Piero Deretta wrote:
It seems a perfect application for fold:
template<typename Seq> struct or_seq : mpl::apply< mpl::fold<mpl::_1, mpl::false_, mpl::quote2<mpl::or_> > , Seq > {};
template<typename Seq> struct and_seq : mpl::apply< mpl::fold<mpl::_1, mpl::true_, mpl::quote2<mpl::and_> > , Seq > {};
Not quite, because we want it to short circuit. Not to mention that quote2 will not work on and_ and or_.
Yeah, these should be rewritten in terms of mpl::find. Not sure why mpl::apply was used here either, though maybe I'm missign something.
The curren mpl::find uses and_ indirectly (in iter_fold_if.hpp:46). Would such a recursive implementation still work?
Anyway, J.Fletcher is now attempting a variadic template rewrite of mpl:;find:
http://sourceforge.net/mailarchive/message.php?msg_name=F0DEE5AE9F6027488C06...
which doesn't use and_; however, another alternative which does short-circuit is attached. It uses eval_if to short-circuit the evaluation. Fletcher's find, OTOH, used if_; however, I think that's just because he's not interested in optimization yet.
A very similar or_ is done by simply exchanging the Zero and One parameters. Interestingly enough, the current and_ uses a similar pattern in that it recursively calls a template (and.hpp:23).
The attached (with the similar or.hpp) passes the logical.cpp test.
Hi, Wow, I didn't think that this thread was yet alive. After suggestion of I don't remember who, I have implemented it as /* Calculate the mlp::and_ of a sequence of nullary logical metafunctions.*/ template <typename Seq> struct and_seq : boost::is_same<typename mpl::find_if<Seq, mpl::not_<mpl::_> >::type, typename mpl::end<Seq>::type> {}; /* Calculate the mlp::or_ of a sequence of nullary logical metafunctions. */ template <typename Seq> struct or_seq : mpl::not_<boost::is_same<typename mpl::find_if<Seq, mpl::_>::type, typename mpl::end<Seq>::type> > {}; If there are better ways to do that, you don't tink that this must be encapsulated in the library? Why not add these metafunctions in Boost.MPL? Thanks, Vicente
On 02/07/09 13:29, vicente.botet wrote:
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost@lists.boost.org> Sent: Saturday, February 07, 2009 8:24 PM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction? [snip]
The attached (with the similar or.hpp) passes the logical.cpp test.
Hi,
Wow, I didn't think that this thread was yet alive.
After suggestion of I don't remember who, I have implemented it as
/* Calculate the mlp::and_ of a sequence of nullary logical metafunctions.*/ template <typename Seq> struct and_seq : boost::is_same<typename mpl::find_if<Seq, mpl::not_<mpl::_> >::type, typename mpl::end<Seq>::type> {}; [snip]
If there are better ways to do that, you don't tink that this must be encapsulated in the library? Why not add these metafunctions in Boost.MPL?
Thanks,
OOPS. I misread the post. I was just thinking of and_ and or_. I missed the "sequence of nullary logical metafunctions". Sorry for noise. It just seemed so similar I neglected any differences.
On 02/07/09 13:58, Larry Evans wrote:
On 02/07/09 13:29, vicente.botet wrote: [snip]
After suggestion of I don't remember who, I have implemented it as
/* Calculate the mlp::and_ of a sequence of nullary logical metafunctions.*/ template <typename Seq> struct and_seq : boost::is_same<typename mpl::find_if<Seq, mpl::not_<mpl::_> >::type, typename mpl::end<Seq>::type> {}; [snip]
If there are better ways to do that, you don't tink that this must be encapsulated in the library? Why not add these metafunctions in Boost.MPL?
Thanks,
OOPS. I misread the post. I was just thinking of and_ and or_. I missed the "sequence of nullary logical metafunctions". Sorry for noise. It just seemed so similar I neglected any differences.
Aren't true_ and false_ nullary logical metafunctions. If so then I think what you're requiring is someway to "unpack" the args from Seq<T1,T2,...Tn> into and_<T1,T2,...,Tn> or or_<T1,T2,...,Tn>. Could: http://www.boost.org/doc/libs/1_37_0/libs/mpl/doc/refmanual/unpack-args.html be used to do that? If not, then it's pretty easy to do that with the variadic version of mpl since all Sequences are derived from package<T1,T2,...,Tn> so: template<typename... T> or_seq<package<T...> > : or_<T...> {}; A prototype variadic version of mpl is in the boost vault.
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost@lists.boost.org> Sent: Sunday, February 08, 2009 2:50 PM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction?
On 02/07/09 13:58, Larry Evans wrote:
On 02/07/09 13:29, vicente.botet wrote: [snip]
After suggestion of I don't remember who, I have implemented it as
/* Calculate the mlp::and_ of a sequence of nullary logical metafunctions.*/ template <typename Seq> struct and_seq : boost::is_same<typename mpl::find_if<Seq, mpl::not_<mpl::_> >::type, typename mpl::end<Seq>::type> {}; [snip]
If there are better ways to do that, you don't tink that this must be encapsulated in the library? Why not add these metafunctions in Boost.MPL?
Thanks,
OOPS. I misread the post. I was just thinking of and_ and or_. I missed the "sequence of nullary logical metafunctions". Sorry for noise. It just seemed so similar I neglected any differences.
Aren't true_ and false_ nullary logical metafunctions. If so then I think what you're requiring is someway to "unpack" the args from Seq<T1,T2,...Tn> into and_<T1,T2,...,Tn> or or_<T1,T2,...,Tn>. Could:
http://www.boost.org/doc/libs/1_37_0/libs/mpl/doc/refmanual/unpack-args.html
be used to do that?
Oh! this is quite interesting. I will try it to see how it works. WHich implementation should perdorms better if any difference?
If not, then it's pretty easy to do that with the variadic version of mpl since all Sequences are derived from package<T1,T2,...,Tn> so:
template<typename... T> or_seq<package<T...> > : or_<T...> {};
A prototype variadic version of mpl is in the boost vault.
Thanks for the pointer, Vicente
On 02/10/09 12:45, vicente.botet wrote:
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost@lists.boost.org> Sent: Sunday, February 08, 2009 2:50 PM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction? [snip]
Aren't true_ and false_ nullary logical metafunctions. If so then I think what you're requiring is someway to "unpack" the args from Seq<T1,T2,...Tn> into and_<T1,T2,...,Tn> or or_<T1,T2,...,Tn>. Could:
http://www.boost.org/doc/libs/1_37_0/libs/mpl/doc/refmanual/unpack-args.html
be used to do that?
Oh! this is quite interesting. I will try it to see how it works. WHich implementation should perdorms better if any difference?
I don't know. I assume you mean the two methods: 1) find_if a true_ or false_ 2) unpack then use and_ or or_ If you're using the variadic compiler, then the 2nd would work faster because the unpacking is done by the compiler instead of by template metaprogramming. If not, then I really don't know because I've not looked at the unpack code.
If not, then it's pretty easy to do that with the variadic version of mpl since all Sequences are derived from package<T1,T2,...,Tn> so:
template<typename... T> or_seq<package<T...> > : or_<T...> {};
A prototype variadic version of mpl is in the boost vault.
Thanks for the pointer,
You're most welcome. BTW, what about the while_ template mentioned in my other recent post. It seems that would be most general, and it just uses template recursion and eval_if. If simplified implementation *usually* means faster execution, then maybe while_ would be fastest. I know the non-variadic and_ uses recursion (as I mentioned in my reply to David), so; I don't think that would be a disadvantage. -Regards, Larry
On 02/10/09 13:21, Larry Evans wrote:
On 02/10/09 12:45, vicente.botet wrote: [snip]
Oh! this is quite interesting. I will try it to see how it works. WHich implementation should perdorms better if any difference? [snip] BTW, what about the while_ template mentioned in my other recent post. It seems that would be most general, and it just uses template recursion and eval_if. If simplified implementation *usually* means faster execution, then maybe while_ would be fastest. I know the non-variadic and_ uses recursion (as I mentioned in my reply to David), so; I don't think that would be a disadvantage. [snip] In the vault, under "Template Metaprogramming", there's a profile, in and_seq_profile.zip, of the find_if method and the while_ method for implementing and_seq. The while_ method shows 100 fewer instantiations for a 3 element vector of nullary logical metafunctions.
BTW, the profile was not put in the variadic_templates vault directory because I realized that while_ doesn't need to use the variadic template compiler.
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost@lists.boost.org> Sent: Thursday, February 12, 2009 6:22 PM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction?
On 02/10/09 13:21, Larry Evans wrote:
On 02/10/09 12:45, vicente.botet wrote: [snip]
Oh! this is quite interesting. I will try it to see how it works. WHich implementation should perdorms better if any difference? [snip] BTW, what about the while_ template mentioned in my other recent post. It seems that would be most general, and it just uses template recursion and eval_if. If simplified implementation *usually* means faster execution, then maybe while_ would be fastest. I know the non-variadic and_ uses recursion (as I mentioned in my reply to David), so; I don't think that would be a disadvantage. [snip] In the vault, under "Template Metaprogramming", there's a profile, in and_seq_profile.zip, of the find_if method and the while_ method for implementing and_seq. The while_ method shows 100 fewer instantiations for a 3 element vector of nullary logical metafunctions.
BTW, the profile was not put in the variadic_templates vault directory because I realized that while_ doesn't need to use the variadic template compiler.
Hi, excelent news. Aleksey, do you think that it is worth to include them on Boost.MPL? Thanks Larry, Vicente
On 02/12/09 11:52, vicente.botet wrote:
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost@lists.boost.org> Sent: Thursday, February 12, 2009 6:22 PM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction?
On 02/10/09 13:21, Larry Evans wrote:
On 02/10/09 12:45, vicente.botet wrote: [snip]
Oh! this is quite interesting. I will try it to see how it works. WHich implementation should perdorms better if any difference? [snip] BTW, what about the while_ template mentioned in my other recent post. It seems that would be most general, and it just uses template recursion and eval_if. If simplified implementation *usually* means faster execution, then maybe while_ would be fastest. I know the non-variadic and_ uses recursion (as I mentioned in my reply to David), so; I don't think that would be a disadvantage. [snip] Aleksey, do you think that it is worth to include them on Boost.MPL?
Thanks Larry, Vicente
Sure. However, IIUC, the recent proposed change to iter_fold_if: https://svn.boost.org/trac/boost/ticket/3044#comment:2 should enable iter_fold_if to be used to do what you want. However, whether that patch to ifer_fold_if is better than a replacement of iter_fold_if with the while_recur mentioned here: https://svn.boost.org/trac/boost/ticket/3044#comment:3 is an open question, IMHO. This questions involved are mentioned near the bottom of: http://article.gmane.org/gmane.comp.lib.boost.devel/190527 However, so far, there doesn't seem to be much interest in while_recur; so, I'm guessing you could get by with Steven's patch to iter_fold_if_impl. -Larry
AMDG Larry Evans wrote:
In the vault, under "Template Metaprogramming", there's a profile, in and_seq_profile.zip, of the find_if method and the while_ method for implementing and_seq. The while_ method shows 100 fewer instantiations for a 3 element vector of nullary logical metafunctions.
I'm not seeing any such drastic differences. Even for 10 values, the difference is just under 70 template instantiations on msvc. and about 50 on gcc. Also, for comparing performance, it's probably better to rely on measuring compilation time. Not all templates take the same amount of time to instantiate. In Christ, Steven Watanabe
On 02/12/09 12:20, Steven Watanabe wrote:
AMDG
Larry Evans wrote:
In the vault, under "Template Metaprogramming", there's a profile, in and_seq_profile.zip, of the find_if method and the while_ method for implementing and_seq. The while_ method shows 100 fewer instantiations for a 3 element vector of nullary logical metafunctions.
I'm not seeing any such drastic differences. Even for 10 values, the difference is just under 70 template instantiations on msvc. and about 50 on gcc.
That's curious! I guess the compiler can do some sort of analysis to figure which templates really need to be instantiated and which don't. Maybe when instantiating some template, the compiler looks at which other templates are needed by the methods in that template (wait, there were not methods in while_, but maybe in the IfOps arg to while_) and then instantiates only those, but other compilers don't bother with that and instantiate templates even though they're not used. Steven, do you have any idea why there's a difference? I was using gcc-4.2 on ubuntu. Also, maybe the g++ on windows implements the templates differently than on linux.
Also, for comparing performance, it's probably better to rely on measuring compilation time. Not all templates take the same amount of time to instantiate.
One reason I was interested in the instantiation profiler instead of compile times is that I'd reand elsewhere that timing benchmarks were not that meaningful. I thought number of instantiations would be more meaningful. Guess I was wrong :(
On 02/12/09 16:19, Larry Evans wrote: [snip]
I guess the compiler can do some sort of analysis to figure which templates really need to be instantiated and which don't. Maybe when instantiating some template, the compiler looks at which other templates are needed by the methods in that template (wait, there were not methods in while_, but maybe in the IfOps arg to while_) and then instantiates only those, but other compilers don't bother with that and instantiate templates even though they're not used.
One example of an unneeded instantiations are those for some of the and_ifops::else_. The profile shows that was instantiated 4 times: and_seq_while.cpp:106 4 134 when only the last one is really needed. Which leads to the obvious (at least now) optimization of just making State as the last element in the eval_if super of while_. So, maybe the gcc you're using does this sort of optimization for the find_if but not for the while_ implementation.
On 02/12/09 17:16, Larry Evans wrote: [snip]
when only the last one is really needed. Which leads to the obvious (at least now) optimization of just making State as the last element in the eval_if super of while_.
I tried this with results shown in boost vault/Template Metaprogramming/and_seq_profile.while_no_else.zip. This "op[timization" was ineffective. There were 303 instantiations vs. the 297 in the original version :( .
On 02/13/09 11:36, Larry Evans wrote:
On 02/12/09 17:16, Larry Evans wrote: [snip] [snip]
when only the last one is really needed. Which leads to the obvious (at least now) optimization of just making State as the last element in the eval_if super of while_.
I tried this with results shown in boost vault/Template Metaprogramming/and_seq_profile.while_no_else.zip.
This "op[timization" was ineffective. There were 303 instantiations vs. the 297 in the original version :( .
Changing equal to is_same (and making adjustments to where ::type is placed) resulted in just 185 instantiations!
AMDG Larry Evans wrote:
This "optimization" was ineffective. There were 303 instantiations vs. the 297 in the original version :( .
Changing equal to is_same (and making adjustments to where ::type is placed) resulted in just 185 instantiations!
If you really must optimize this to death... #include <boost/mpl/next.hpp> #include <boost/mpl/deref.hpp> #include <boost/mpl/begin.hpp> #include <boost/mpl/end.hpp> #include <boost/mpl/and.hpp> /* Calculate the mpl::and_ of a sequence of nullary logical metafunctions.*/ template<class Begin, class End> struct and_iter : boost::mpl::and_< typename boost::mpl::deref<Begin>::type, and_iter<typename boost::mpl::next<Begin>::type, End>
{};
template<class End> struct and_iter<End, End> : boost::mpl::false_ {}; template <typename Seq> struct and_seq : and_iter<typename boost::mpl::begin<Seq>::type, typename boost::mpl::end<Seq>::type> {}; #include <and_seq_instances.hpp> In Christ, Steven Watanabe
On 02/15/09 13:29, Steven Watanabe wrote:
AMDG
Larry Evans wrote:
This "optimization" was ineffective. There were 303 instantiations vs. the 297 in the original version :( .
Changing equal to is_same (and making adjustments to where ::type is placed) resulted in just 185 instantiations!
If you really must optimize this to death...
Well, the mpl and fusion people have spent a lot of effort on it; so, I figure it must be worth while.
#include <boost/mpl/next.hpp> #include <boost/mpl/deref.hpp> #include <boost/mpl/begin.hpp> #include <boost/mpl/end.hpp> #include <boost/mpl/and.hpp> /* Calculate the mpl::and_ of a sequence of nullary logical metafunctions.*/ template<class Begin, class End> struct and_iter : boost::mpl::and_< typename boost::mpl::deref<Begin>::type, and_iter<typename boost::mpl::next<Begin>::type, End>
{};
template<class End> struct and_iter<End, End> : boost::mpl::false_ {};
template <typename Seq> struct and_seq : and_iter<typename boost::mpl::begin<Seq>::type, typename boost::mpl::end<Seq>::type> {};
So, in summary, the and_ifops::if_ test has been replaced with the and_iter specialization of <End, End>, and the laziness is achieved by use of and_; however, why not just use eval_if to achieve the laziness: -{--and_seq_eval_if_iter.cpp-- #include <boost/mpl/next.hpp> #include <boost/mpl/deref.hpp> #include <boost/mpl/begin.hpp> #include <boost/mpl/end.hpp> #include <boost/mpl/eval_if.hpp> /* Calculate the mpl::and_ of a sequence of nullary logical metafunctions.*/ template<class Begin, class End> struct and_iter : boost::mpl::eval_if_< typename boost::mpl::deref<Begin>::type, and_iter<typename boost::mpl::next<Begin>::type, End>, boost::mpl::false_
{};
template<class End> struct and_iter<End, End> : boost::mpl::false_ {}; template <typename Seq> struct and_seq : and_iter<typename boost::mpl::begin<Seq>::type, typename boost::mpl::end<Seq>::type> {}; #include <and_seq_instances.hpp> -{--end_seq_eval_if_iter.cpp-- This shaved off a few instantiations (128 vs. 163 on my machine). BTW, Steven, do you know how to get timing? I've tried the following but nothing is output: #the following modelled after time-rule from: # # http://beta.boost.org/doc/tools/jam/jam/language.html#jam.language.variables... # rule timing-rule ( args * : target : start end user system ) { echo $(start) $(end) ; } #the following modelling on: # # http://www.boost.org/doc/tools/jam/jam/language.html#jam.language.variables # __TIMING_RULE__ on and_seq_while-time = timing-rule ; compile and_seq_while.cpp : <include>. <link>static : and_seq_while-time ;
On 02/15/09 14:48, Larry Evans wrote: [snip]
#include <and_seq_instances.hpp> -{--end_seq_eval_if_iter.cpp--
This shaved off a few instantiations (128 vs. 163 on my machine).
OOPS. spoke too soon. Ran the compile test and this version failed the assertions. Please ignore previous post :(
On 02/15/09 15:08, Larry Evans wrote:
On 02/15/09 14:48, Larry Evans wrote: [snip]
#include <and_seq_instances.hpp> -{--end_seq_eval_if_iter.cpp--
This shaved off a few instantiations (128 vs. 163 on my machine).
OOPS. spoke too soon. Ran the compile test and this version failed the assertions.
Please ignore previous post :(
The same error occurred with and_seq_and_iter because: template<class End> struct and_iter<End, End> : boost::mpl::false_ {}; should be: template<class End> struct and_iter<End, End> : boost::mpl::true_ {};
AMDG Larry Evans wrote:
So, in summary, the and_ifops::if_ test has been replaced with the and_iter specialization of <End, End>, and the laziness is achieved by use of and_; however, why not just use eval_if to achieve the laziness:
Because, in theory, mpl::and_ should be just as efficient.
#include <boost/mpl/eval_if.hpp> <snip> This shaved off a few instantiations (128 vs. 163 on my machine).
Watch out. My tool includes non templates in the instantiation count. The total number of instantiations reported depends on the #includes. To get a good comparison, you need to subtract off the number of instantiations caused by just the #includes. (You could look at the call graph, but it's unreliable still).
BTW, Steven, do you know how to get timing? I've tried the following but nothing is output:
<snip> __TIMING_RULE__ on and_seq_while-time = timing-rule ; compile and_seq_while.cpp : <include>. <link>static : and_seq_while-time ;
This doesn't work because __TIMIING_RULE__ affect bjam level targets, but seq_while-time is the name of a Boost.Build main target. Try: obj and_seq_while.o : and_seq_while.cpp ; time and_seq_while.time : and_seq_while.o ; In Christ, Steven Watanabe
On 02/15/09 17:50, Steven Watanabe wrote:
AMDG
Larry Evans wrote:
So, in summary, the and_ifops::if_ test has been replaced with the and_iter specialization of <End, End>, and the laziness is achieved by use of and_; however, why not just use eval_if to achieve the laziness:
Because, in theory, mpl::and_ should be just as efficient.
#include <boost/mpl/eval_if.hpp> <snip> This shaved off a few instantiations (128 vs. 163 on my machine).
Watch out. My tool includes non templates in the instantiation count. The total number of instantiations reported depends on the #includes. To get a good comparison, you need to subtract off the number of instantiations caused by just the #includes. (You could look at the call graph, but it's unreliable still).
Good call. I surrounded the call to and_seq with and #ifndef X and ran with X #def'ed and #undef'ed. Hmm... Got same number of instantiations. OOPS, the code within the #ifndef ... #endif was: typedef and_seq<all_true_seq_max> and_seq_true_max_meta ; when it should have also included: typedef and_seq_true_max_meta::type and_seq_true_max_type ; That made a huge difference in number of instantiations. With that change: implementation profile includes difference -------------- ------- -------- ---------- and_iter 469 152 317 eval_if_iter 465 149 316 while_if_then 510 149 361 The similarity of and_iter and eval_if_iter surprised me because and_ uses several templates from aux_ and I thought they would have added significantly to the count. The while_if_then was an attempt to use a while which was as close as possible to and_iter; yet, still used something like a c while statement. I've seen semantics of while expressed in a recursive equations such as: while ~ if b then c;while else skip. which is pretty close to the way the while_ and the while_if_then are defined. The while_if_then template is: template < class State//nullary metafunction returning current state. , template<class>class If//unary bool_ metafunction , template<class>class Then//unary metafunction > struct while_if_then : eval_if < typename If<typename State::type>::type , while_if_then < Then<typename State::type> , If , Then > , State > { }; Then and_seq using this method was: template<class IterNow, class IterEnd> struct and_if : boost::mpl::deref<IterNow> { }; template<class IterEnd> struct and_if<IterEnd,IterEnd> : boost::mpl::false_ { }; template<class IterNow, class IterEnd> struct and_result : boost::mpl::false_ { }; template<class IterEnd> struct and_result<IterEnd,IterEnd> : boost::mpl::true_ { }; template <typename Seq> struct and_seq { typedef typename boost::mpl::end<Seq>::type end_seq ; template<class IterNow> struct if_ : and_if<IterNow,end_seq> {}; typedef typename boost::mpl::while_if_then < typename boost::mpl::begin<Seq> , if_ , boost::mpl::next >::type end_state ; typedef and_result < end_seq , end_state > type ; }; [snip]
This doesn't work because __TIMIING_RULE__ affect bjam level targets, but seq_while-time is the name of a Boost.Build main target.
Try:
obj and_seq_while.o : and_seq_while.cpp ; time and_seq_while.time : and_seq_while.o ;
Worked great. Thanks Steven! The times for all three implementations were all the same: user: [and_seq_and_iter.o] 0.000016 system: [and_seq_and_iter.o] 0.000003 And this is where the vector size was BOOST_MPL_LIMIT_VECTOR_SIZE, which was 20.
AMDG Larry Evans wrote:
The times for all three implementations were all the same:
user: [and_seq_and_iter.o] 0.000016 system: [and_seq_and_iter.o] 0.000003
And this is where the vector size was BOOST_MPL_LIMIT_VECTOR_SIZE, which was 20.
I don't trust the timings produced by bjam. I know it doesn't work on windows, but I haven't looked at the unix implementation. Can you test something that you know takes a significant amount of time to compile? In Christ, Steven Watanabe
On 02/16/09 11:15, Steven Watanabe wrote:
AMDG
Larry Evans wrote:
The times for all three implementations were all the same:
user: [and_seq_and_iter.o] 0.000016 system: [and_seq_and_iter.o] 0.000003
And this is where the vector size was BOOST_MPL_LIMIT_VECTOR_SIZE, which was 20.
I don't trust the timings produced by bjam. I know it doesn't work on windows, but I haven't looked at the unix implementation. Can you test something that you know takes a significant amount of time to compile?
I don't have anything handy like that. I know some spirit grammars take a long time; however, I don't have any big spirit grammars that might take a long time. Could the spirit guys provide some code?
On 02/16/09 13:43, Larry Evans wrote:
On 02/16/09 11:15, Steven Watanabe wrote:
AMDG
Larry Evans wrote:
The times for all three implementations were all the same:
user: [and_seq_and_iter.o] 0.000016 system: [and_seq_and_iter.o] 0.000003
And this is where the vector size was BOOST_MPL_LIMIT_VECTOR_SIZE, which was 20.
I don't trust the timings produced by bjam. I know it doesn't work on windows, but I haven't looked at the unix implementation. Can you test something that you know takes a significant amount of time to compile?
I don't have anything handy like that. I know some spirit grammars take a long time; however, I don't have any big spirit grammars that might take a long time.
Could the spirit guys provide some code?
Searching the spirit-general showed the post: From: "Steve Drake" <sdrake@hiwaay.net> Newsgroups: gmane.comp.parsers.spirit.general Subject: Compilation has become very slow after adding rule ID's Date: Tue, 20 Mar 2007 22:05:37 -0600 with a .zip file. Downloaded that and got: ... from Main.cpp:18: ../../../../../boost/spirit/tree/tree_to_xml.hpp:18:4: warning: #warning "This header is deprecated. Please use: boost/spirit/include/classic_tree_to_xml.hpp" testing.time ../../../../../bin.v2/tools/profile_templates/timing/SourceFiles.dir/Src/gcc-4.2/debug/link-static/Main.time user: [Main.o] 0.000203 system: [Main.o] 0.000015 ...updated 8 targets... Compilation finished at Mon Feb 16 14:00:43
On 02/07/09 13:29, vicente.botet wrote: [snip]
After suggestion of I don't remember who, I have implemented it as
/* Calculate the mlp::and_ of a sequence of nullary logical metafunctions.*/ template <typename Seq> struct and_seq : boost::is_same<typename mpl::find_if<Seq, mpl::not_<mpl::_> >::type, typename mpl::end<Seq>::type> {};
/* Calculate the mlp::or_ of a sequence of nullary logical metafunctions. */ template <typename Seq> struct or_seq : mpl::not_<boost::is_same<typename mpl::find_if<Seq, mpl::_>::type, typename mpl::end<Seq>::type> > {};
If there are better ways to do that, you don't tink that this must be encapsulated in the library? Why not add these metafunctions in Boost.MPL?
An alternative to using find_if is to use the all_true (and an obvious variation, any_true) from the while.cpp in the while.zip in the boost vault's variadic_templates directory. all_true uses the while_ template, which is briefly described here: http://sourceforge.net/mailarchive/forum.php?thread_name=gmsgd6%24k2%241%40g...
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost@lists.boost.org> Sent: Tuesday, February 10, 2009 7:39 PM Subject: Re: [boost] [mpl] is there a or_seq like logical metafunction?
On 02/07/09 13:29, vicente.botet wrote: [snip]
After suggestion of I don't remember who, I have implemented it as
/* Calculate the mlp::and_ of a sequence of nullary logical metafunctions.*/ template <typename Seq> struct and_seq : boost::is_same<typename mpl::find_if<Seq, mpl::not_<mpl::_> >::type, typename mpl::end<Seq>::type> {};
/* Calculate the mlp::or_ of a sequence of nullary logical metafunctions. */ template <typename Seq> struct or_seq : mpl::not_<boost::is_same<typename mpl::find_if<Seq, mpl::_>::type, typename mpl::end<Seq>::type> > {};
If there are better ways to do that, you don't tink that this must be encapsulated in the library? Why not add these metafunctions in Boost.MPL?
An alternative to using find_if is to use the all_true (and an obvious variation, any_true) from the while.cpp in the while.zip in the boost vault's variadic_templates directory. all_true uses the while_ template, which is briefly described here:
http://sourceforge.net/mailarchive/forum.php?thread_name=gmsgd6%24k2%241%40g...
Thanks to showing that we can get interesting post related to mpl and fusion on the Boost.Spirit mailing list. I will take a look more often from now.
From these alternatives, who knows which is the better one?
Best, Vicente
participants (5)
-
David Abrahams -
Giovanni Piero Deretta -
Larry Evans -
Steven Watanabe -
vicente.botet