Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2009-06-11 08:35:41

Christopher Jefferson skrev:
> 
> On 10 Jun 2009, at 22:28, Christopher Jefferson wrote:
> 
>>
>> On 10 Jun 2009, at 22:08, Thorsten Ottosen wrote:
>>
>>> Christopher Jefferson skrev:
>>>
>>>> Very interesting. I have been working on a similar, but much more 
>>>> limited, proposal which just does this for vector.
>>>> I decided I had to implement a new class, because building on top of 
>>>> the 'allocator' framework wasn't sensible, because you waste too 
>>>> much buffer space. For example, I believe your example won't work. 
>>>> I'd be interested to see what you think.
>>>> Consider your example, in g++ (which I know how it operates internally)
>>>> boost::monotonic::inline_storage<100*sizeof(Object)> storage; // 
>>>> create local storage on the stack boost::monotonic::vector<Object> 
>>>> deathrow(storage); // create a std::vector that uses this storage
>>>> foreach (object in world)
>>>> { if (IsDead(object)) deathrow.push_back(object); // allocation is 
>>>> just advancing a pointer }
>>>> This will build a vector which will continuously expand, through 
>>>> sizes 1,2,4,8,16,32. At each step, it will allocate a new block of 
>>>> memory and free the old one, making the storage size 1,3,7,15,31,63. 
>>>> When we try to push_back beyond 32 elements, the next allocation 
>>>> will overflow the buffer.
>>>> Am I missing something?
>>>
>>> Maybe
>>>
>>> http://www.cs.aau.dk/~nesotto/boost/trunk/libs/auto_buffer/doc/html/
>>> http://www.cs.aau.dk/~nesotto/boost/trunk/boost/auto_buffer/
>>>
>>> is what you are looking for?
>>
>> That doesn't do exactly what I want for two reasons, but most might be 
>> fixable.
>>
>> 1) I want run-time variable amounts of space (this does involve some 
>> alloca, and probably macro, hackery).
>> 2) I want it to be an error if it is necessary to go to the heap.
>>
>>
>> For (1) I use a macro something like:
>>
>> #define GET_ALLOCA_MEM(type, x) box<type>(x, alloca(x * sizeof(type))
>>
>> Because obviously you can't call alloca inside the auto_buffer 
>> constructor.
> 
> Replying to myself, passing an external buffer into auto_buffer isn't 
> completely trivial, because you would also have to disable to copy 
> constructor (at least, I can't think of anything else sensible to do).

As far as I know, alloca() is not portable. Am I wrong?

You might use variable lenght arrays (C99), but see "Imperfect C++" by 
Matthew Wilson on why they suck. His analysis is the reason he 
implements stlsoft::auto_buffer instead.

For 2), if you want to get an error when the stacl buffer is exhausted, 
you may write a custom GrowPolicy that gies an error inside 
GrowPolicy::new_capacity().

-Thorsten