On 7/3/2012 11:12 PM, Roland Bock wrote:
On 2012-07-03 20:52, Roland Bock wrote:
On 2012-07-03 19:50, Roland Bock wrote:
On 2012-07-03 19:36, Eric Niebler wrote:
And clang crashes when I add another row of parameters in Eric's version. No problems with my version... I hope you filed a bug. :-) Will do :-)
This is going way over my current abilities, but the ticket has caught attention:
<snip>
--- Comment #5 from Richard Smith <richard-llvm@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).
Clang bug.
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).
Clang QoI. Hope they can get a handle on this one.
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 written).
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.
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).
He seems to be saying that instantiating a class template is cheaper (or requires less stack space?) than instantiating a function template. This surprises me.
- 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...
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. -- Eric Niebler BoostPro Computing http://www.boostpro.com