Re: [boost] [offtopic] C++11 useful trick

Subject: Re: [boost] [offtopic] C++11 useful trick
From: Eric Niebler (eric_at_[hidden])
Date: 2012-07-04 03:50:49

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 :-)
>>>
>> http://llvm.org/bugs/show_bug.cgi?id=13263
>>
>>
> This is going way over my current abilities, but the ticket has caught
> attention:
> 
> <snip>
> 
> --- Comment #5 from Richard Smith <richard-llvm_at_[hidden]> 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