Interesting variadic template trick
Hi, As some might know, I'm currently working on a reimplementation of the MPL for C++11. In doing so, I came across a technique that I did not know of and I thought I would share my discovery with the community. If this is already well known, please excuse my ignorance. The goal is to implement fast compile-time conjunction and disjunction. It goes like this: template <typename ...T> void allow_expansion(T&&...); template <typename ...T> struct or_ { static constexpr bool value = !noexcept( allow_expansion((T::value ? throw : 0)...) ); }; That's it! Note that disjunction is easily obtained in a similar way. The benefit of this technique over traditional implementations is that it's several times faster according to my benchmarks. However, you might have noticed that short-circuit evaluation is not respected so the above technique is only suitable when short-circuit evaluation is not required. If you find this interesting, see [1] for a collection of similar techniques. The one I posted above seems to be the fastest with Clang and GCC. Regards, Louis Dionne [1] https://gist.github.com/ldionne/7522393
Louis Dionne <ldionne.2 <at> gmail.com> writes:
template <typename ...T> void allow_expansion(T&&...);
template <typename ...T> struct or_ { static constexpr bool value = !noexcept( allow_expansion((T::value ? throw : 0)...) ); };
How embarrassing; my unit test was very poor and the above trick does not seem to work. However, the following was tested more rigorously and works (with similar performance improvements): template <typename ...T> constexpr bool all_pointers(T*...) { return true; } template <typename ...T> constexpr bool all_pointers(T...) { return false; } template <typename ...T> struct or_ { static constexpr bool value = !all_pointers( ((typename std::conditional<T::value, int, void*>::type)0)... ); }; template <> struct or_<> { static constexpr bool value = false; }; Regards, Louis Dionne
On Mon, Nov 18, 2013 at 8:42 AM, Louis Dionne <ldionne.2@gmail.com> wrote:
Louis Dionne <ldionne.2 <at> gmail.com> writes:
template <typename ...T> void allow_expansion(T&&...);
template <typename ...T> struct or_ { static constexpr bool value = !noexcept( allow_expansion((T::value ? throw : 0)...) ); };
How embarrassing; my unit test was very poor and the above trick does not seem to work. However, the following was tested more rigorously and works (with similar performance improvements):
template <typename ...T> constexpr bool all_pointers(T*...) { return true; }
template <typename ...T> constexpr bool all_pointers(T...) { return false; }
template <typename ...T> struct or_ { static constexpr bool value = !all_pointers( ((typename std::conditional<T::value, int, void*>::type)0)... ); };
template <> struct or_<> { static constexpr bool value = false; };
It requires N instantiations of std::conditional, doesn't it? In that case is it actually faster than the naive recursive instantiation of or_?
AMDG On 11/17/2013 09:55 PM, Andrey Semashev wrote:
template <typename ...T> struct or_ { static constexpr bool value = !all_pointers( ((typename std::conditional<T::value, int, void*>::type)0)... ); };
template <> struct or_<> { static constexpr bool value = false; };
It requires N instantiations of std::conditional, doesn't it? In that case is it actually faster than the naive recursive instantiation of or_?
No it doesn't. It requires exactly two instantiations of std::conditional for all uses of or_. In Christ, Steven Watanabe
On Mon, Nov 18, 2013 at 10:18 AM, Steven Watanabe <watanabesj@gmail.com> wrote:
AMDG
On 11/17/2013 09:55 PM, Andrey Semashev wrote:
template <typename ...T> struct or_ { static constexpr bool value = !all_pointers( ((typename std::conditional<T::value, int, void*>::type)0)... ); };
template <> struct or_<> { static constexpr bool value = false; };
It requires N instantiations of std::conditional, doesn't it? In that case is it actually faster than the naive recursive instantiation of or_?
No it doesn't. It requires exactly two instantiations of std::conditional for all uses of or_.
You mean the compiler can optimize multiple instantiations for different T::value values to just unique ones?
On 18 November 2013 06:54, Andrey Semashev wrote:
No it doesn't. It requires exactly two instantiations of std::conditional for all uses of or_.
You mean the compiler can optimize multiple instantiations for different T::value values to just unique ones?
How many unique values of bool do you think there are? :-)
On Mon, Nov 18, 2013 at 1:58 PM, Jonathan Wakely <jwakely.boost@kayari.org> wrote:
On 18 November 2013 06:54, Andrey Semashev wrote:
No it doesn't. It requires exactly two instantiations of std::conditional for all uses of or_.
You mean the compiler can optimize multiple instantiations for different T::value values to just unique ones?
How many unique values of bool do you think there are? :-)
I probably didn't express myself clear. I was asking whether the compiler is able to optimize N identical instantiations to the cost of just one.
On 18 November 2013 10:07, Andrey Semashev wrote:
On Mon, Nov 18, 2013 at 1:58 PM, Jonathan Wakely <jwakely.boost@kayari.org> wrote:
On 18 November 2013 06:54, Andrey Semashev wrote:
No it doesn't. It requires exactly two instantiations of std::conditional for all uses of or_.
You mean the compiler can optimize multiple instantiations for different T::value values to just unique ones?
How many unique values of bool do you think there are? :-)
I probably didn't express myself clear. I was asking whether the compiler is able to optimize N identical instantiations to the cost of just one.
There aren't N identical instantiations, there can only be two. Instantiating a given template specialization is only done once per translation unit. When it's already instantiated there's nothing to "optimize", the compiler just refers to the existing instantiation and uses it, similar to how it would use a non-template class. Across multiple translation units there might be duplicate instantiations that can be discarded, but that's dealt with by the linker, in the same way as duplicate copies of inline functions, vtables and RTTI info.
On Mon, Nov 18, 2013 at 3:27 PM, Jonathan Wakely <jwakely.boost@kayari.org> wrote:
On 18 November 2013 10:07, Andrey Semashev wrote:
I probably didn't express myself clear. I was asking whether the compiler is able to optimize N identical instantiations to the cost of just one.
There aren't N identical instantiations, there can only be two.
Instantiating a given template specialization is only done once per translation unit. When it's already instantiated there's nothing to "optimize", the compiler just refers to the existing instantiation and uses it, similar to how it would use a non-template class.
Across multiple translation units there might be duplicate instantiations that can be discarded, but that's dealt with by the linker, in the same way as duplicate copies of inline functions, vtables and RTTI info.
You're right, of course. Thanks.
Andrey Semashev <andrey.semashev <at> gmail.com> writes:
It requires N instantiations of std::conditional, doesn't it? In that case is it actually faster than the naive recursive instantiation of or_?
Regarding the number of instantiations, others have already answered. Regarding the improvement over a naive or_, have a look at the bottom of the gist at [1]; I updated it with some benchmarks. You will see that there is indeed a noticeable improvement. Regards, Louis Dionne
On 11/18/2013 5:34 AM, Louis Dionne wrote:
Andrey Semashev <andrey.semashev <at> gmail.com> writes:
It requires N instantiations of std::conditional, doesn't it? In that case is it actually faster than the naive recursive instantiation of or_?
Regarding the number of instantiations, others have already answered.
Regarding the improvement over a naive or_, have a look at the bottom of the gist at [1]; I updated it with some benchmarks. You will see that there is indeed a noticeable improvement.
Clever. Thanks for posting! -- Eric Niebler Boost.org http://www.boost.org
On 18/11/2013 05:25, Louis Dionne wrote:
Hi,
As some might know, I'm currently working on a reimplementation of the MPL for C++11. In doing so, I came across a technique that I did not know of and I thought I would share my discovery with the community. If this is already well known, please excuse my ignorance.
The goal is to implement fast compile-time conjunction and disjunction. It goes like this:
template <typename ...T> void allow_expansion(T&&...);
template <typename ...T> struct or_ { static constexpr bool value = !noexcept( allow_expansion((T::value ? throw : 0)...) ); };
An obvious problem with this is that it doesn't compile if exceptions are disabled. And I think being able to use meta-programming without exceptions is an important property to have.
On 20/11/2013 03:13, Quoth Mathias Gaunard:
template <typename ...T> struct or_ { static constexpr bool value = !noexcept( allow_expansion((T::value ? throw : 0)...) ); };
An obvious problem with this is that it doesn't compile if exceptions are disabled. And I think being able to use meta-programming without exceptions is an important property to have.
If you look at the followup, it doesn't use noexcept any more.
participants (7)
-
Andrey Semashev -
Eric Niebler -
Gavin Lambert -
Jonathan Wakely -
Louis Dionne -
Mathias Gaunard -
Steven Watanabe