|[boost] [offtopic] C++11 useful trick||Eric Niebler||7/1/12 4:20 PM|
I recently ran into a limitation in recursive functions that make use of
decltype in trailing return types. I've come up with a work-around that
I think is a little non-obvious, so I thought I'd share.
The problem came up while trying to implementing something like a
variadic back() function. The "obvious" implementation doesn't work:
T back(T && t)
template<typename T, typename ...U>
auto back(T && t, U &&... u)
-> decltype(::back(static_cast<U &&>(u)...)) // ERROR
return ::back(static_cast<U &&>(u)...);
int i = ::back(1,2,3);
The problem occurs on the line marked "HERE". Trouble is, the variadic
"back" function is not yet in scope until after the return type.
However, we'd like to use it when specifying the return type.
The solution uses a default function template parameter to make the
::back symbol dependent, thereby deferring it's lookup until phase 2,
when the symbol is visible. Check it:
static T back(T && t)
template<typename T, typename ...U, typename Impl = S>
static auto back(T && t, U &&... u)
-> decltype(Impl::back(static_cast<U &&>(u)...))
return Impl::back(static_cast<U &&>(u)...);
int i = S::back(1,2,3);
The trick is the "typename Impl = S" followed by a (now dependent)
invocation of Impl::back. Voila.
Apologies if this is a known technique, and I'm spamming the list with
old news. It's news to me.
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
|Re: [boost] [offtopic] C++11 useful trick||Steve Ramsey||7/1/12 9:53 PM|
Isn’t it the case that the back function without the U parameter pack has the same function signature as the back function with an empty U parameter pack, which would be the source of your troubles in the first case? The struct-based case simply ensures that the two backs will always have differing signatures since there will always be at least two template parameters for the second function, but this isn’t due to any special struct-related property. Admittedly, I’m still working to understand variadic templates, so I might be off-base here...
|Re: [boost] [offtopic] C++11 useful trick||Eric Niebler||7/1/12 10:03 PM|
You're off base. Although the variadic back *could* be called with 1
argument, overload resolution would prefer the non-variadic function
over the variadic one. But that's irrelevant in this case. look at the
invocation: ::back(1,2,3). That can *only* call the variadic one. It
peels off one element and then tries to call ::back(2,3). That also
could only possibly call the variadic one. However, it can't for the
simple reason that the compiler doesn't know about it until after the
trailing return type is parsed. But by making the invocation of back in
the trailing return type dependent on a template argument, it forces
name lookup to happen later, when the template arguments are known.
|Re: [boost] [offtopic] C++11 useful trick||Roland Bock||7/2/12 1:12 AM|
Hmm, I would have done something like this:
template<typename T, typename ...U>struct back_t
typedef typename back_t<U...>::type type;
typedef T type;
}typename detail::back_t<U...>::type back(T && t, U &&... u)
The advantages I see are that
* nobody will be confused by the Impl parameter.
* no need to put back() into a struct
Do you see any drawbacks?
|Re: [boost] [offtopic] C++11 useful trick||Eric Niebler||7/2/12 10:29 AM|
Yeah, it's booo-ring. ;-) Also, it needlessly instantiates O(N)
templates. And why write both a function template *and* a class template
when the function template alone will do? Now you have to maintain two
computations in parallel. I hate writing metafunctions to compute things
the compiler already knows. And in less trivial examples, the
metafunction wouldn't be so easy to write. BTW, only the implementation
of back needs to go in a struct. The user-visible function could fwd to it.
This is just a trivial example of the technique. I've been doing a lot
of C++11 making use of automatic type deduction via decltype+trailing
return types. This issue comes up fairly often for me, so finding a
solution to this problem was satisfying and greatly simplified my code.
BTW, you can also solve this problem by making the recursive call
unqualified and relying on ADL, but then you're using ADL and have
|Re: [boost] [offtopic] C++11 useful trick||Mathias Gaunard||7/2/12 11:18 AM|
On 02/07/2012 19:29, Eric Niebler wrote:Have you done benchmarks that shows your approach is significantly faster?
Use of a C++11 feature just for the sake of it doesn't seem like such a
good idea to me. Especially since BOOST_TYPEOF in the return type tends
to be quite fragile, so it cannot really be emulated.
|Re: [boost] [offtopic] C++11 useful trick||Eric Niebler||7/2/12 12:41 PM|
On 7/2/2012 11:18 AM, Mathias Gaunard wrote:No.
<baffle> Have I not given enough good reasons above? Maybe I'll just
keep my good ideas to myself next time. :-/
True. This is only for C++11 code. That's why the subject says "C++11
useful trick". :-/
|Re: [boost] [offtopic] C++11 useful trick||Mathias Gaunard||7/2/12 1:23 PM|
On 02/07/2012 21:41, Eric Niebler wrote:Tricks are nice, but they can also obfuscate code somewhat and make it
hard to maintain.
If the trick is very useful, it may become an idiom. If its use is
limited, it's more of a hack.
Don't know what kind of trick this one is just yet. Sorry if I offended you.
|Re: [boost] [offtopic] C++11 useful trick||Ravi||7/2/12 7:26 PM|
On Monday, July 02, 2012 12:41:22 PM Eric Niebler wrote:Please don't. This one is actually pretty widely applicable if you are doing
type deduction in C++11; it took me quite a while to figure this one out when
I ran into it. I, too, fail to see how the reasons you gave were not perfectly
|Re: [boost] [offtopic] C++11 useful trick||Eric Niebler||7/3/12 12:13 AM|
On 7/2/2012 7:26 PM, Ravi wrote:Thanks Ravi. For the record, this trick is also useful for CRTP bases
when you need to static_cast this from base to derived in a return type:
template<typename D = Derived>
auto foo() -> decltype(static_cast<D *>(this)->bar())
return static_cast<D *>(this)->bar();
struct Derived : Base<Derived>
If you try to do this instead:
auto foo() -> decltype(static_cast<Derived *>(this)->bar())
it won't compile because the compiler can't tell that the static_cast is
legit. You might think this would work:
auto foo() -> decltype(std::declval<Derived &>().bar())
...but then it can't find member bar() in Derived.
|Re: [boost] [offtopic] C++11 useful trick||Roland Bock||7/3/12 12:50 AM|
On 2012-07-02 19:29, Eric Niebler wrote:Boring? Hey! :-)
The other arguments are certainly valid, though. I used the attached
versions to compare compilation times:
Using clang with -O3
Obviously the measurement is rather crude and imprecise, but your
version definitely compiles faster. And it is also much shorter and
easier to setup for such a comparison :-)
I'll look through some of the code I've written recently. I guess I can
apply this trick here and there.
Thanks for sharing!
|Re: [boost] [offtopic] C++11 useful trick||Mathias Gaunard||7/3/12 7:52 AM|
On 07/03/2012 09:50 AM, Roland Bock wrote:Given your test, I suggest you benchmark the preprocessed output rather
than the source directly.
|Re: [boost] [offtopic] C++11 useful trick||Kim Barrett||7/3/12 8:00 AM|
On Jul 3, 2012, at 3:13 AM, Eric Niebler wrote:Something like this also showed up in Matt Calabrese's suggested BOOST_ENABLE_IF() macro that appeared in this thread:
I didn't really understand the introduction of the dummy template parameter at the time, and the explanation Matt gave was (rough paraphrase, I can't find the exact quote)
The BoostDetailEnableIfDependentType template parameter exists in order to ensure that the later condition is dependent on a template argument.
which was pretty opaque to me at the time, but with Eric's explanation I think maybe I now understand.
|Re: [boost] [offtopic] C++11 useful trick||Roland Bock||7/3/12 9:22 AM|
On 2012-07-03 16:52, Mathias Gaunard wrote:OK, created preprocessed versions with clang -E and measured again, but
the results are similarly close (and way too much under the influence of
the sheer amount of bytes that need to be processed).
I came up with a new test, see attachments:
Interestingly enough, Eric's version takes a bit longer to compile on my
clang version 3.2 (trunk 155315)
And clang crashes when I add another row of parameters in Eric's
version. No problems with my version...
Can somebody try with a different compiler? Or is this test complete
nonsense for some reason?
|Re: [boost] [offtopic] C++11 useful trick||Eric Niebler||7/3/12 10:36 AM|
Too close to be very meaningful. I find that with TMP, the real costs
don't become evident until you have a non-trivial program.
I hope you filed a bug. :-)
|Re: [boost] [offtopic] C++11 useful trick||Mathias Gaunard||7/3/12 10:46 AM|
On 07/03/2012 06:22 PM, Roland Bock wrote:With GCC 4.7.0, no optimization
Exhausts all my ram (8 GB) after 24.27 seconds
Exhausts all my ram (8 GB) after 25.07 seconds
|Re: [boost] [offtopic] C++11 useful trick||Roland Bock||7/3/12 10:50 AM|
Will do :-)
|Re: [boost] [offtopic] C++11 useful trick||Larry Evans||7/3/12 11:19 AM|
On 07/03/12 12:46, Mathias Gaunard wrote:I'm surprised that with more optimization (-O3) less compile time
is taken (1.28 < 4.87). The gcc 4.7 docs here:
Optimizing compilation takes somewhat more time, and a lot more memory
for a large function.
Anyone know why, in this particular case, -O3 is faster than
with no optimization?
|Re: [boost] [offtopic] C++11 useful trick||Mathias Gaunard||7/3/12 11:29 AM|
On 07/03/2012 08:19 PM, Larry Evans wrote:Without optimizations
Execution times (seconds)
phase setup : 0.01
phase parsing : 0.10
phase lang. deferred : 0.54
phase cgraph : 3.50
phase generate : 4.04
|name lookup : 0.08
|overload resolution : 0.30
Execution times (seconds)
phase setup : 0.01
phase parsing : 0.09
phase lang. deferred : 0.52
phase cgraph : 0.40
phase generate : 0.92
|name lookup : 0.03
|overload resolution : 0.34
Optimizations done by the frontend resulted in much less symbols to
compute the call graph for.
|Re: [boost] [offtopic] C++11 useful trick||Roland Bock||7/3/12 11:52 AM|
On 2012-07-03 19:50, Roland Bock wrote:
>> And clang crashes when I add another row of parameters in Eric'shttp://llvm.org/bugs/show_bug.cgi?id=13263
|Re: [boost] [offtopic] C++11 useful trick||Nathan Ridge||7/3/12 12:18 PM|
>You may want to report that as a GCC bug. I experienced
similar symptoms when reporting PR52748 , it could
well be the same root cause.
|Re: [boost] [offtopic] C++11 useful trick||Eric Niebler||7/3/12 1:42 PM|
On 7/3/2012 12:18 PM, Nathan Ridge wrote:http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53846
This is not likely to be the same bug. N3276 is about decltype causing
the recursive instantiation of a class template -- unconditionally. In
this case, a call to the back function succeeds if you pass fewer
parameters, but fails with more. Seems to merely indicate an inefficient
algorithm, not a fundamental problem.
|Re: [boost] [offtopic] C++11 useful trick||Roland Bock||7/3/12 11:12 PM|
On 2012-07-03 20:52, Roland Bock wrote:This is going way over my current abilities, but the ticket has caught
--- Comment #5 from Richard Smith <richar...@metafoo.co.uk> 2012-07-03 16:31:55 CDT ---
To be clear, we have three problems on the original code:
1) We don't appear to apply the instantiation depth limit in this case (we
still hit a stack overflow with -ftemplate-depth=1).
2) The stack usage per instantiation is sometimes high enough to blow out the
stack before we would have hit the limit anyway (depending on ulimits).
3) The compile-time (and, potentially, runtime) performance is quadratic in the
number of arguments (but this is fundamental to the way the code has been
Your second attachment avoids the first problem by using class templates (for
which the limit is enforced), and mitigates the second problem (because the
stack usage per instantiation is lower for that case).
- original code: Eric's version
- second attachment: my "boring" version
Richard also offers an alternative (see ticket link above) which he
claims to be much more effective, but I haven't comprehended it yet...
|Re: [boost] [offtopic] C++11 useful trick||Eric Niebler||7/4/12 12:50 AM|
On 7/3/2012 11:12 PM, Roland Bock wrote:Clang bug.
Clang QoI. Hope they can get a handle on this one.
After scratching my head about this one, I think what he's getting at is
the number of times arguments have to be copied and pushed on/popped off
the stack. I can see how this can get expensive. The other version you
posted, Roland, has the same problem.
He seems to be saying that instantiating a class template is cheaper (or
requires less stack space?) than instantiating a function template. This
Yes, I get it. He's using a variant of the variadic tuple trick. He
wants to find the Nth element in a parameter pack. So he puts all the
elements in a tuple-like thingy (select_impl) which holds individual
elements, each in its own base class (select_base). But only the Nth
base actually holds onto its argument. (See the partial specialization
of select_base.) His solution instantiates O(N) instances of
select_base, but gets you the Nth element in O(1). Fiendishly clever.
|Re: [boost] [offtopic] C++11 useful trick||Roland Bock||7/4/12 2:07 AM|
On 2012-07-04 09:50, Eric Niebler wrote:Huh! Thanks for the explanation!
Really awesome! :-)
|Re: [boost] [offtopic] C++11 useful trick||Dave Abrahams||7/28/12 7:10 PM|
on Wed Jul 04 2012, Eric Niebler <eric-AT-boostpro.com> wrote:
> He's using a variant of the variadic tuple trick. He wants to find the
> Nth element in a parameter pack. So he puts all the elements in a
> tuple-like thingy (select_impl) which holds individual elements, each
> in its own base class (select_base). But only the Nth base actually
> holds onto its argument. (See the partial specialization of
> select_base.) His solution instantiates O(N) instances of select_base,
> but gets you the Nth element in O(1). Fiendishly clever.
That explanation doesn't match what I'm seeing in his latest attachment
(http://llvm.org/bugs/attachment.cgi?id=8838&action=edit), which doesn't
require storing anything. Which is pretty cool!
BoostPro Computing Software Development Training
http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
|Re: [boost] [offtopic] C++11 useful trick||Eric Niebler||7/28/12 11:55 PM|
On 7/28/2012 7:10 PM, Dave Abrahams wrote:Right, I was commenting on this:
His latest implementation is very, very cool and I've already found
another use for his technique.
I'm slightly dismayed that we need to be so very clever to use variadic
templates efficiently. This stuff is not obvious AT ALL.