Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christopher Jefferson (chris_at_[hidden])
Date: 2009-06-11 08:49:13

On 11 Jun 2009, at 13:35, Thorsten Ottosen wrote:

> 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?

It isn't standard I believe, but it exists on at least Mac OS X,  
FreeBSD, linux and windows, and software I write uses it successfully  
on all these platforms.
>
> 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.

stlsoft::auto_buffer seems to have exactly the same restriction as  
your auto_buffer, you must declare the amount of space (or at least an  
upper bound) as a compile-time constant. I haven't got a copy of  
Imperfect C++, but I have to say my personal experience is alloca and  
VLA (I experimented with using a VLA of chars instead of alloca, the  
two are basically implemented the same underneath) work fine.

> 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().

Thanks, that sounds like a good idea.
>
> -Thorsten
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost