I recently ran into the problem that a local container on the stack, which was likely to be very small, but its size was still not known at compile-time, consumed a considerable amount of runtime because of allocation/deallocation. e.g. void do(istream &i){ vector<int> vec; vec.reserve(20); while(...){ int tmp; i >> tmp; vec.push_back(tmp); } } so I wrote an allocator that I think is generally useful and could be added e.g. to Boost.Array: void do(int n){ int buffer[20]; stack_allocator<int,20> alloc(buffer); vector<int,stack_allocator<int,20> > vec(alloc); vec.reserve(alloc.max_stack_size()); while(...){ int tmp; i >> tmp; vec.push_back(tmp); } } the vector operates on the stack as long as there is enough space, and moves to the heap afterwards. in most cases there is no dynamic allocation. here's the source: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=stack_allocator.hpp&directory=array& it uses the simple_seq_fit allocation algorithm described here: http://www.boost.org/doc/libs/1_37_0/doc/html/interprocess/allocators_contai...
Stefan Strasser wrote:
I recently ran into the problem that a local container on the stack, which was likely to be very small, but its size was still not known at compile-time, consumed a considerable amount of runtime because of allocation/deallocation. [...]
I'd try to find out if the std::vector of that implementation doesn't provide short array optimisation. Peraps STLport does, I'm not sure. That would solve this issue. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
There was an overlong discussion about this some time ago. You could look at boost::auto_buffer. I also have a system that does this using a generalised allocator in the sandbox http://tinyurl.com/o56t5u. Two immediate issues are alignment and the fact that you are using a stateful allocator. However, in the case you provide it would work. It's just not a very interesting case. Cheers, Christian. On Fri, Aug 14, 2009 at 6:21 AM, Mateusz Loskot <mateusz@loskot.net> wrote:
Stefan Strasser wrote:
I recently ran into the problem that a local container on the stack, which was likely to be very small, but its size was still not known at compile-time, consumed a considerable amount of runtime because of allocation/deallocation. [...]
I'd try to find out if the std::vector of that implementation doesn't provide short array optimisation. Peraps STLport does, I'm not sure. That would solve this issue.
Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Stefan Strasser wrote:
so I wrote an allocator that I think is generally useful and could be added e.g. to Boost.Array:
void do(int n){ int buffer[20]; stack_allocator<int,20> alloc(buffer); vector<int,stack_allocator<int,20> > vec(alloc); vec.reserve(alloc.max_stack_size());
while(...){ int tmp; i >> tmp; vec.push_back(tmp); } }
the vector operates on the stack as long as there is enough space, and moves to the heap afterwards. in most cases there is no dynamic allocation.
An implementation is free to consider any instance of an allocator with the same arguments passed to the constructor as equal, IIRC. Does your allocator suffer from this issue? Also, is the container still copyable properly?
Am Friday 14 August 2009 00:24:54 schrieb Mathias Gaunard:
the vector operates on the stack as long as there is enough space, and moves to the heap afterwards. in most cases there is no dynamic allocation.
An implementation is free to consider any instance of an allocator with the same arguments passed to the constructor as equal, IIRC.
Does your allocator suffer from this issue?
I don't think so. the allocator doesn't have any state except a constant pointer to "buffer"(see exmaple above), so multiple copies of the same allocator can be used simultaniously. the only c++ standard requirement it can't fulfil is a default constructor. I'm not sure why that is needed though. but the standard says that Allocator() must be a valid expression.
Also, is the container still copyable properly?
yes. the only issue that might arise is that the buffer on the stack could go out of scope before the vector has, as a result of swap()ing the contents of the vector into another vector with a longer lifetime. but I don't think that's a violation of the standard because that is also true for other allocators, e.g. pool allocators. Am Friday 14 August 2009 00:00:37 schrieb Christian Schladetsch:
Two immediate issues are alignment and the fact that you are using a stateful allocator.
do you consider a constant pointer "stateful", and why is that a problem?
On Fri, Aug 14, 2009 at 12:46 PM, Stefan Strasser <strasser@uni-bremen.de>wrote:
Am Friday 14 August 2009 00:24:54 schrieb Mathias Gaunard:
the vector operates on the stack as long as there is enough space, and moves to the heap afterwards. in most cases there is no dynamic allocation.
An implementation is free to consider any instance of an allocator with the same arguments passed to the constructor as equal, IIRC.
Does your allocator suffer from this issue?
I don't think so. the allocator doesn't have any state except a constant pointer to "buffer"(see exmaple above),
The pointer constitutes state.
so multiple copies of the same allocator can be used simultaniously.
Yes, but a default-constructed stack_allocator<> doesn't have storage so it cannot allocate.
the only c++ standard requirement it can't fulfil is a default constructor. I'm not sure why that is needed though. but the standard says that Allocator() must be a valid expression.
Also, is the container still copyable properly?
yes. the only issue that might arise is that the buffer on the stack could go out of scope before the vector has, as a result of swap()ing the contents of the vector into another vector with a longer lifetime. but I don't think that's a violation of the standard because that is also true for other allocators, e.g. pool allocators.
Am Friday 14 August 2009 00:00:37 schrieb Christian Schladetsch:
Two immediate issues are alignment and the fact that you are using a stateful allocator.
do you consider a constant pointer "stateful", and why is that a problem?
Yes, a pointer is state, and yes it is a problem. STL compliant allocators cannot have meaningful state. You may wish to search the boost list for the thread on 'Monotonic Allocator' to witness this being beaten into me over a period of days. The only way to do this is to use containers that respect stateful allocators. It's something I've been arguing for for a while, and these have now come via Boost.Interprocess.Container, to the proposed Boost.Container library from Ion. So your proposed stack_allocator<> could possibly work, if you used Ion's containers. But it is still not general. What you propose is a subset of a more general allocation model described here http://tinyurl.com/kkr7af. But you are right about performance http://tinyurl.com/l7k2op. Regards, Christian
participants (4)
-
Christian Schladetsch -
Mateusz Loskot -
Mathias Gaunard -
Stefan Strasser