[utility] auto_buffer v2
Dear All, Hereby an updated class. Thanks to all who contributed with comments to the first try. I have made the following changes: 1. push_back() overloads are now growing 2. added swap() (boy, was this nasty to implement). I assume the allocator can be wapped without throwing. How do other people copy with this problem? 3. added copy-constructor + copy-assignment 4. made the min capacity equal to N, the number of elements in the stack buffer 5. the size of the internal buffer is now controlled via two policies: template< unsigned N > struct store_n_objects; template< unsigned N > struct store_n_bytes; the default is store_n_objects<256>. The reason is that we don't want the capacity to change just because we compile on a different platform. 6. added comparison operators Comments most welcome! best regards -Thorsten
On Wed, Mar 4, 2009 at 6:54 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
Dear All,
Hereby an updated class. Thanks to all who contributed with comments to the first try.
...
Comments most welcome!
Looking good. Is there a reason why you assert ( this != &r ) in the assignment operator? Certainly this case could be handled by just returning *this, right? Also, the more I think about it, we have only been looking at this as strictly for use on the stack, but nothing prevents someone from using it as a global, or for instance, as a datamember of a type that may not be instantiated on the stack, which may be beneficial as well (or at the very least, nothing prevents someone from using it in such a manner). This means the function "is_on_stack" may be better named "is_stored_locally" or something similar. Just to throw it out there as something to consider, I could definitely see a generalization of this idea not specific to array allocation also being very useful. By this I mean, a template similar to what you have now but dealing with raw memory without a container interface and no stored type specified -- it would just let you do a raw "resize" (or "reallocate"). When the requested size is under N, accessing the data gives you a pointer to the locally stored buffer, otherwise it is to dynamically allocated memory managed by the type, much like auto_buffer. The main use-case I see for this would be as an implementation detail internal to an "any" or "function" or "poly" kind of type to allow objects under a certain size to be stored directly in the type in which it is contained rather than dynamically, resorting to additional allocation only when necessary. Instantiating the template with a different value for N would in effect control how large of an object could be stored locally before having to resort to an additional allocation. I'm not implying that you should implement this, just that it is something to think about. The implementation would be extremely similar and it even seems like the former may be able to be implemented via the latter. -- -Matt Calabrese
Matt Calabrese skrev:
On Wed, Mar 4, 2009 at 6:54 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
Dear All,
Hereby an updated class. Thanks to all who contributed with comments to the first try.
...
Comments most welcome!
Looking good.
Thanks.
Is there a reason why you assert ( this != &r ) in the assignment operator? Certainly this case could be handled by just returning *this, right?
Yes. I must admit I always disliked the discussions on "assignment to *this". I never personally created code that would run into such cases. So I put the assertion there because I don't want to use cycles on this case. I think it is hypothetical.
Also, the more I think about it, we have only been looking at this as strictly for use on the stack, but nothing prevents someone from using it as a global, or for instance, as a datamember of a type that may not be instantiated on the stack, which may be beneficial as well (or at the very least, nothing prevents someone from using it in such a manner).
Right. That is mainly why I added copy-operations.
This means the function "is_on_stack" may be better named "is_stored_locally" or something similar.
Maybe, I'm not sure.
Just to throw it out there as something to consider, I could definitely see a generalization of this idea not specific to array allocation also being very useful. By this I mean, a template similar to what you have now but dealing with raw memory without a container interface and no stored type specified -- it would just let you do a raw "resize" (or "reallocate"). When the requested size is under N, accessing the data gives you a pointer to the locally stored buffer, otherwise it is to dynamically allocated memory managed by the type, much like auto_buffer. The main use-case I see for this would be as an implementation detail internal to an "any" or "function" or
Remark: boost::any desparately needs SBO.
"poly" kind of type to allow objects under a certain size to be stored directly in the type in which it is contained rather than dynamically, resorting to additional allocation only when necessary. Instantiating the template with a different value for N would in effect control how large of an object could be stored locally before having to resort to an additional allocation.
I'm not implying that you should implement this, just that it is something to think about. The implementation would be extremely similar and it even seems like the former may be able to be implemented via the latter.
I guess it is a bit like some people talked about when they referred to allocators with an embedded stack buffer. As one can see from my code, swap and copy-operations are difficult to implement. Especially swap. Therefore such an allocator will be *very* difficult to use correctly in a container. In particular, swap() sometimes only gives the basic guarantee (and no better guarantee is possible!). The partially stack-based allocator works fine if the container is used locally, but seems very problematic for general use-cases. -Thorsten
On Thu, Mar 5, 2009 at 3:56 AM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
As one can see from my code, swap and copy-operations are difficult to implement. Especially swap. Therefore such an allocator will be *very* difficult to use correctly in a container. In particular, swap() sometimes only gives the basic guarantee (and no better guarantee is possible!).
I haven't given it too much thought, but intuitively (perhaps naively on my part), it seems to me like if the types you are instantiating the template with have no-throw copy/copy-assign/swap operations you could satisfy the strong guarantee for the associated auto_buffer operations regardless of if neither, one, or both operands store their data in a separate allocation. -- -Matt Calabrese
Matt Calabrese skrev:
On Thu, Mar 5, 2009 at 3:56 AM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
As one can see from my code, swap and copy-operations are difficult to implement. Especially swap. Therefore such an allocator will be *very* difficult to use correctly in a container. In particular, swap() sometimes only gives the basic guarantee (and no better guarantee is possible!).
I haven't given it too much thought, but intuitively (perhaps naively on my part), it seems to me like if the types you are instantiating the template with have no-throw copy/copy-assign/swap operations you could satisfy the strong guarantee for the associated auto_buffer operations regardless of if neither, one, or both operands store their data in a separate allocation.
swap(), for example, already has the nothrow guarantee under your constraints above. -Thorsten
Thorsten Ottosen wrote:
Hereby an updated class. Thanks to all who contributed with comments to the first try.
Thanks for persisting :).
I have made the following changes:
2. added swap() (boy, was this nasty to implement).
I see what you mean! I hadn't quite understood your implementation; I had assumed that you continued to use the stack space when extending to the heap. The fact that you don't makes swapping more complex. Your current implementation assumes default-constructibility of T (when T is not trivially assignable). For example, the following won't compile: #include "auto_buffer.hpp" class T { public: T(int) {} T& operator=(T) { return *this; } private: T(); }; int main() { boost::auto_buffer<T> a, b; swap(a, b); return 0; } Changes such as the diff below should fix it (I also had to add a couple of #includes to make it compile). However, this change could make certain swaps slower. For example, if T is a std::vector or suchlike which can be much more expensive to copy than to default construct and swap. I'm not sure if there's an implementation which gets the best of both worlds (without resorting to move semantics). --- auto_buffer-1.hpp 2009-03-07 18:09:33.000000000 +0000 +++ auto_buffer.hpp 2009-03-07 18:26:31.000000000 +0000 @@ -6,6 +6,8 @@ #ifndef BOOST_UTILITY_AUTO_BUFFER_HPP_25_02_2009 #define BOOST_UTILITY_AUTO_BUFFER_HPP_25_02_2009 +#include <boost/detail/workaround.hpp> + #if defined(_MSC_VER) && (_MSC_VER >= 1200) # pragma once #endif @@ -16,6 +18,7 @@ #endif #include <boost/assert.hpp> +#include <boost/throw_exception.hpp> #include <boost/iterator/reverse_iterator.hpp> #include <boost/mpl/if.hpp> #include <boost/multi_index/detail/scope_guard.hpp> @@ -288,11 +291,12 @@ auto_buffer* smallest = l.size_ == min_size ? &l : &r; auto_buffer* largest = smallest == &l ? &r : &l; - for( unsigned i = 0u; i < diff; ++i ) - smallest->unchecked_push_back(); - - for( size_type i = 0u; i < max_size; ++i ) + size_type i; + for( i = 0u; i < min_size; ++i ) boost::swap( (*smallest)[i], (*largest)[i] ); + + for( ; i < max_size; ++i ) + smallest->unchecked_push_back( (*largest)[i] ); largest->pop_back_n( diff ); boost::swap( l.capacity_, r.capacity_ ); }
John Bytheway skrev:
Thorsten Ottosen wrote:
Hereby an updated class. Thanks to all who contributed with comments to the first try.
Thanks for persisting :).
No problem.
I have made the following changes:
2. added swap() (boy, was this nasty to implement).
I see what you mean! I hadn't quite understood your implementation; I had assumed that you continued to use the stack space when extending to the heap. The fact that you don't makes swapping more complex.
Interesting idea. It won't work though, as it breaks T* iterators and a bunch of other functions in the interface.
Your current implementation assumes default-constructibility of T (when T is not trivially assignable). For example, the following won't compile:
[snip]
Changes such as the diff below should fix it (I also had to add a couple of #includes to make it compile).
Thanks. -Thorsten
Thorsten Ottosen <thorsten.ottosen <at> dezide.com> writes:
Dear All,
Hereby an updated class. Thanks to all who contributed with comments to the first try.
Hi, I just downloaded the latest version from http://www.cs.aau.dk/~nesotto/boost/ A quick visual inspection appears to indicate that the sign of the inequality in uninitialized_grow() is wrong - i.e. it should be: pointer uninitialized_grow( size_type n ) // strong { if( size_ + n > members_.capacity_ ) reserve( size_ + n ); Also, when I actually use it, I keep having to write: auto_buffer<...> ab; ab.uninitialized_grow(N); because the size constructor only appears to reserve, and not resize - perhaps it can take a boolean, with default set to reserve and resize? Similar problem with resize etc - the natural interface always initializes, which is almost never what you want from a buffer class - 99% of the time you want a buffer to write into. So maybe it might be worth considering changing the interface so the default members all resize uninitialized, and have checked_resize() etc for uncommon cases? Thanks Amit
participants (4)
-
Amit -
John Bytheway -
Matt Calabrese -
Thorsten Ottosen