Re: [boost] [utility] new auto_buffer class --- RFC

Subject: Re: [boost] [utility] new auto_buffer class --- RFC
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2009-03-02 13:50:53

Peter Dimov skrev:
> Thorsten Ottosen:
>> Peter Dimov skrev:
>>> Thorsten Ottosen:
>>>> Peter Dimov skrev:
>>> ....
>>>>> for x in w
>>>>>    if pred(x)
>>>>>        v.push_back(x)
>>>>>
>>>>> The typical number of elements satisfying pred may be ~7.1, so 
>>>>> making v have a stack capacity of 8 will eliminate a heap 
>>>>> allocation and will be a big win. But you can't determine the 
>>>>> maximum capacity in advance.
>>>>
>>>> Is it not |w|?
>>>
>>> Yes, it technically is bounded by |w|. But using |w| as the capacity 
>>> of v defeats the purpose of the optimization, which is to avoid 
>>> allocating storage for |w| elements (typically on the heap).
>>
>> But then you can't know if using auto_buffer is an optimization.
> 
> It depends on the distribution of |v|. Let's say that in X% of the cases 
> the final |v| is less than a constant K. When X is close enough to 100, 
> using auto_buffer<T,K> is a win. Even though some outliers may cause 
> more than one allocation, the majority will cause zero.

Right. But it is *very* complicated to analyse such a situation.
It could, as you say, include multiple buffer-expansions with
different "movability cost" based on T. And the check for buffer
overflow has a cost. And the fact that push_back() is not inlined
could also have a *major* impact.

<stupid_idea>
I guess it would be an advantage if "push_back" could say

  "if we must go for a heap buffer, make it at least |w|"

So maybe

for x in w
    if pred(x)
       v.push_back(x,|w|)
</stupid_idea>

-Thorsten