Hey everyone, In the course of my work as a computational scientist I have written a container that emulates std::vector, but which is backed by an array whose size is fixed at compile time. Concretely, the class looks something like the following: template<typename T,unsigned int buffer_size> class static_vector { ... protected: T data[buffer_size]; T* end_ptr; size_t current_size; } where in the [...] there are methods that emulate (at this time, partially) the interface of std::vector, save that the size of the static_vector is not allowed to grow beyond the buffer_size. The advantage of using a static_vector over vector is performance. In my code I have performed benchmarks that show up to a 30% performance boost of static_vector over vector; the benefit occurs most stongly when working with lots of arrays of small objects, so that the use of dynamic memory rather than stack memory appears to add significant overhead to the computation. (Note that I when running these benchmarks I would use std::vector::reserve() to pre-allocate the array so that std::vector would not perform multiple allocations as the container grew, so that should not have been a source of overhead.) It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for the boost family of libraries. Is there any interest out there for having such a library in boost? If so, I would be happy to do the work of taking what I have and fleshing it out so that it can function as a drop-in replacement for vector, which means modeling the Random Access Container and Back Insertion Sequence concepts as well as adding capacity() and reserve(size_t) (no-op) methods. Thoughts? Cheers, Gregory Crosswhite
On 12/28/2010 03:03 PM, Gregory Crosswhite wrote:
Hey everyone,
In the course of my work as a computational scientist I have written a container that emulates std::vector, but which is backed by an array whose size is fixed at compile time. Concretely, the class looks something like the following:
template<typename T,unsigned int buffer_size> class static_vector { ... protected: T data[buffer_size]; T* end_ptr; size_t current_size; }
where in the [...] there are methods that emulate (at this time, partially) the interface of std::vector, save that the size of the static_vector is not allowed to grow beyond the buffer_size.
The advantage of using a static_vector over vector is performance. In my code I have performed benchmarks that show up to a 30% performance boost of static_vector over vector; the benefit occurs most stongly when working with lots of arrays of small objects, so that the use of dynamic memory rather than stack memory appears to add significant overhead to the computation. (Note that I when running these benchmarks I would use std::vector::reserve() to pre-allocate the array so that std::vector would not perform multiple allocations as the container grew, so that should not have been a source of overhead.)
It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for the boost family of libraries. Is there any interest out there for having such a library in boost? If so, I would be happy to do the work of taking what I have and fleshing it out so that it can function as a drop-in replacement for vector, which means modeling the Random Access Container and Back Insertion Sequence concepts as well as adding capacity() and reserve(size_t) (no-op) methods.
Thoughts?
How is this different than boost::array? <http://www.boost.org/doc/libs/1_45_0/doc/html/array.html> -- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com
On 12/28/10 6:17 PM, Michael Caisse wrote:
On 12/28/2010 03:03 PM, Gregory Crosswhite wrote:
Hey everyone,
In the course of my work as a computational scientist I have written a container that emulates std::vector, but which is backed by an array whose size is fixed at compile time. Concretely, the class looks something like the following:
template<typename T,unsigned int buffer_size> class static_vector { ... protected: T data[buffer_size]; T* end_ptr; size_t current_size; }
where in the [...] there are methods that emulate (at this time, partially) the interface of std::vector, save that the size of the static_vector is not allowed to grow beyond the buffer_size.
The advantage of using a static_vector over vector is performance. In my code I have performed benchmarks that show up to a 30% performance boost of static_vector over vector; the benefit occurs most stongly when working with lots of arrays of small objects, so that the use of dynamic memory rather than stack memory appears to add significant overhead to the computation. (Note that I when running these benchmarks I would use std::vector::reserve() to pre-allocate the array so that std::vector would not perform multiple allocations as the container grew, so that should not have been a source of overhead.)
It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for the boost family of libraries. Is there any interest out there for having such a library in boost? If so, I would be happy to do the work of taking what I have and fleshing it out so that it can function as a drop-in replacement for vector, which means modeling the Random Access Container and Back Insertion Sequence concepts as well as adding capacity() and reserve(size_t) (no-op) methods.
Thoughts?
How is this different than boost::array? <http://www.boost.org/doc/libs/1_45_0/doc/html/array.html>
boost:array has a number of elements that is fixed at compile time. By contrast, my proposed static_vector could grow and shrink as long as the number of elements is kept below the buffer_size. Cheers, Greg
Greg, What you are doing here is to mix two (presumably...) orthogonal aspects, in that you bake in the allocation policy in the vector interface. In fact, a "static allocator" to be used in cases like std::vector was discussed at length on this list a year ago (or was it two years?) /David On Dec 28, 2010, at 6:03 PM, Gregory Crosswhite wrote:
Hey everyone,
In the course of my work as a computational scientist I have written a container that emulates std::vector, but which is backed by an array whose size is fixed at compile time. Concretely, the class looks something like the following:
template<typename T,unsigned int buffer_size> class static_vector { ... protected: T data[buffer_size]; T* end_ptr; size_t current_size; }
where in the [...] there are methods that emulate (at this time, partially) the interface of std::vector, save that the size of the static_vector is not allowed to grow beyond the buffer_size.
The advantage of using a static_vector over vector is performance. In my code I have performed benchmarks that show up to a 30% performance boost of static_vector over vector; the benefit occurs most stongly when working with lots of arrays of small objects, so that the use of dynamic memory rather than stack memory appears to add significant overhead to the computation. (Note that I when running these benchmarks I would use std::vector::reserve() to pre-allocate the array so that std::vector would not perform multiple allocations as the container grew, so that should not have been a source of overhead.)
It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for the boost family of libraries. Is there any interest out there for having such a library in boost? If so, I would be happy to do the work of taking what I have and fleshing it out so that it can function as a drop-in replacement for vector, which means modeling the Random Access Container and Back Insertion Sequence concepts as well as adding capacity() and reserve(size_t) (no-op) methods.
Thoughts?
Cheers, Gregory Crosswhite _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
At Tue, 28 Dec 2010 18:36:46 -0500, David Bergman wrote:
Greg,
What you are doing here is to mix two (presumably...) orthogonal aspects, in that you bake in the allocation policy in the vector interface.
In fact, a "static allocator" to be used in cases like std::vector was discussed at length on this list a year ago (or was it two years?)
Yeah, an allocator with some internal storage that falls back to the heap when it's exausted would allow std::vector's to essentially use the "small string optimization." -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 12/28/2010 04:58 PM, Dave Abrahams wrote:
At Tue, 28 Dec 2010 18:36:46 -0500, David Bergman wrote:
Greg,
What you are doing here is to mix two (presumably...) orthogonal aspects, in that you bake in the allocation policy in the vector interface.
In fact, a "static allocator" to be used in cases like std::vector was discussed at length on this list a year ago (or was it two years?)
Yeah, an allocator with some internal storage that falls back to the heap when it's exausted would allow std::vector's to essentially use the "small string optimization."
+1 i like it! -- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com
On Tuesday 28 December 2010, Dave Abrahams wrote:
Yeah, an allocator with some internal storage that falls back to the heap when it's exausted would allow std::vector's to essentially use the "small string optimization."
It would have to rely on c++0x or implementation-defined behaviour though, as c++03 containers are explicitly not required to support stateful allocators.
At Tue, 28 Dec 2010 22:21:20 -0500, Frank Mori Hess wrote:
On Tuesday 28 December 2010, Dave Abrahams wrote:
Yeah, an allocator with some internal storage that falls back to the heap when it's exausted would allow std::vector's to essentially use the "small string optimization."
It would have to rely on c++0x or implementation-defined behaviour though, as c++03 containers are explicitly not required to support stateful allocators.
Ah, yes; the famous "weasel wording." But AFAIK all real implementations go at least a few steps beyond what's required in that department, as a matter of QOI. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Dec 28, 2010, at 7:58 PM, Dave Abrahams wrote:
At Tue, 28 Dec 2010 18:36:46 -0500, David Bergman wrote:
Greg,
What you are doing here is to mix two (presumably...) orthogonal aspects, in that you bake in the allocation policy in the vector interface.
In fact, a "static allocator" to be used in cases like std::vector was discussed at length on this list a year ago (or was it two years?)
Yeah, an allocator with some internal storage that falls back to the heap when it's exausted would allow std::vector's to essentially use the "small string optimization."
For example: http://home.roadrunner.com/~hinnant/stack_alloc.html -Howard
On Tuesday 28 December 2010, Howard Hinnant wrote:
Yeah, an allocator with some internal storage that falls back to the heap when it's exausted would allow std::vector's to essentially use the "small string optimization."
For example:
That page talks about the allocator working with c++03 containers, but what about 20.1.5 paragraph 4? Quote: "Implementations of containers described in this International Standard are permitted to assume that their Allocator template parameter meets the following two additional requirements beyond those in Table 32. — All instances of a given allocator type are required to be interchangeable and always compare equal to each other..." And then I also see there is an allocator copy constructor postcondition which it does not fulfill: X a(b); post: Y(a) == b
On Dec 28, 2010, at 11:41 PM, Frank Mori Hess wrote:
On Tuesday 28 December 2010, Howard Hinnant wrote:
Yeah, an allocator with some internal storage that falls back to the heap when it's exausted would allow std::vector's to essentially use the "small string optimization."
For example:
That page talks about the allocator working with c++03 containers, but what about 20.1.5 paragraph 4? Quote:
"Implementations of containers described in this International Standard are permitted to assume that their Allocator template parameter meets the following two additional requirements beyond those in Table 32.
— All instances of a given allocator type are required to be interchangeable and always compare equal to each other..."
And then I also see there is an allocator copy constructor postcondition which it does not fulfill: X a(b); post: Y(a) == b
I've changed my documentation to make it clear that the C++03 compatibility part of the design is based on actual C++03 implementations of standard containers as opposed to strictly following the C++03 specification. -Howard
I 've noticed this as well. In our application we use a data sample class which gets created and deleted a lot. It is slow because it uses a std::map, which is heavy on creation and deletion. I was thus thinking about making a custom allocator, but item 10 from Meyers 'Effective STL' talked me out of it, especially stating that portable allocators should be more or less stateless. The obvious use of an allocator was to allocate from a special fast (non thread safe) private memory pool. Btw I was trying the stack_alloc allocator but on VS2003 it fails to compile for list and set. I think it is related that the list/set implementation which instantiate it with an incomplete type: Plauger's list code: template<class _Ty, class _Alloc> class _List_nod { // base class for _List_ptr to hold allocator _Alnod protected: struct _Node; friend struct _Node; typedef typename _Alloc::template rebind<_GENERIC_BASE>::other::pointer _Genptr; etc... };
On 28 December 2010 18:58, Dave Abrahams <dave@boostpro.com> wrote:
Yeah, an allocator with some internal storage that falls back to the heap when it's exausted would allow std::vector's to essentially use the "small string optimization."
Can you do that with just an allocator? How would swap work? Now, if you have static_vector (or equivalent), you could build a vector replacement out of that and std::vector. (I've been toying with this too, but it is not yet ready for prime time.) One other feature I'd like to see is a way to specify zero-initialized vs. uninitialized for POD-types. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
"David Bergman" <David.Bergman@bergmangupta.com> wrote in message news:FF46F967-E45E-4188-9976-6090F2054A51@bergmangupta.com...
What you are doing here is to mix two (presumably...) orthogonal aspects, in that you bake in the allocation policy in the vector interface.
In fact, a "static allocator" to be used in cases like std::vector was discussed at length on this list a year ago (or was it two years?)
This is not quite the same, i.e. std::vector is 'too' generic so it would still incur overhead compared to a simple "stack-buffer-with-an-end-pointer": it contains (and maintains) three pointers (or std::size_ts) begin, end and "reserved end" as opposed to only an end pointer/std::size_t + it is designed around the 'idea' of "fallible allocation", that is it expects allocation requests to possibly throw so in some cases/member functions implementations have to use guard objects and/or explicit exception handling (which the optimizer may or may not be able to remove) ... and this same problem might obfuscate the code (for the compiler) enough so that the optimizer might not be able to detect that a 'std::vector with a static allocator' does not throw and cause it to still emit EH code/unwind funclets (for surrounding/calling code)... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
Domagoj Saric wrote:
"David Bergman" <David.Bergman@bergmangupta.com> wrote in message news:FF46F967-E45E-4188-9976-6090F2054A51@bergmangupta.com...
What you are doing here is to mix two (presumably...) orthogonal aspects, in that you bake in the allocation policy in the vector interface. In fact, a "static allocator" to be used in cases like std::vector was discussed at length on this list a year ago (or was it two years?)
This is not quite the same, i.e. std::vector is 'too' generic so it would still incur overhead compared to a simple "stack-buffer-with-an-end-pointer": it contains (and maintains) three pointers (or std::size_ts) begin, end and "reserved end" as opposed to only an end pointer/std::size_t + it is designed around the 'idea' of "fallible allocation", that is it expects allocation requests to possibly throw so in some cases/member functions implementations have to use guard objects and/or explicit exception handling (which the optimizer may or may not be able to remove) ... and this same problem might obfuscate the code (for the compiler) enough so that the optimizer might not be able to detect that a 'std::vector with a static allocator' does not throw and cause it to still emit EH code/unwind funclets (for surrounding/calling code)...
If you have a fixed size vector, you cannot call functions that might require a reallocation (push_back is out of the question). So the compiler doesn't have to generate those functions at all. Bo Persson
"Bo Persson" <bop@gmb.dk> wrote in message news:ih1uom$ef1$1@dough.gmane.org...
If you have a fixed size vector, you cannot call functions that might require a reallocation (push_back is out of the question). So the compiler doesn't have to generate those functions at all.
Stack-based != fixed-sized... See the original post/proposal... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for
Gregory Crosswhite wrote on Tuesday, December 28, 2010 6:03 PM the
boost family of libraries. Is there any interest out there for having such a library in boost? If so, I would be happy to do the work of taking what I have and fleshing it out so that it can function as a drop-in replacement for vector, which means modeling the Random Access Container and Back Insertion Sequence concepts as well as adding capacity() and reserve(size_t) (no-op) methods.
This is useful... I've independently developed just such a class. It'd be nice to have it in Boost. Erik ---------------------------------------------------------------------- This message w/attachments (message) is intended solely for the use of the intended recipient(s) and may contain information that is privileged, confidential or proprietary. If you are not an intended recipient, please notify the sender, and then please delete and destroy all copies and attachments, and be advised that any review or dissemination of, or the taking of any action in reliance on, the information contained in or attached to this message is prohibited. Unless specifically indicated, this message is not an offer to sell or a solicitation of any investment products or other financial product or service, an official confirmation of any transaction, or an official statement of Sender. Subject to applicable law, Sender may intercept, monitor, review and retain e-communications (EC) traveling through its networks/systems and may produce any such EC to regulators, law enforcement, in litigation and as required by law. The laws of the country of each sender/recipient may impact the handling of EC, and EC may be archived, supervised and produced in countries other than the country in which you are located. This message cannot be guaranteed to be secure or free of errors or viruses. References to "Sender" are references to any subsidiary of Bank of America Corporation. Securities and Insurance Products: * Are Not FDIC Insured * Are Not Bank Guaranteed * May Lose Value * Are Not a Bank Deposit * Are Not a Condition to Any Banking Service or Activity * Are Not Insured by Any Federal Government Agency. Attachments that are part of this EC may have additional important disclosures and disclaimers, which you should read. This message is subject to terms available at the following link: http://www.bankofamerica.com/emaildisclaimer. By messaging with Sender you consent to the foregoing.
On Tuesday 28 December 2010, Gregory Crosswhite wrote:
It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for the boost family of libraries. Is there any interest out there for having such a library in boost?
Yes, but there is already the AutoBuffer submission by Thorsten Ottosen in the review queue.
On 12/28/10 10:19 PM, Frank Mori Hess wrote:
It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for the boost family of libraries. Is there any interest out there for having such a library in boost? Yes, but there is already the AutoBuffer submission by Thorsten Ottosen in
On Tuesday 28 December 2010, Gregory Crosswhite wrote: the review queue.
Great, that looks basically like the idea I was proposing. :-) Thanks! - Greg
Frank Mori Hess wrote:
On Tuesday 28 December 2010, Gregory Crosswhite wrote:
It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for the boost family of libraries. Is there any interest out there for having such a library in boost?
Yes, but there is already the AutoBuffer submission by Thorsten Ottosen in the review queue.
In case anyone wonders, Thorsten's schedule has prevented our setting a review date, but I do hope we can do it soon. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Den 29-12-2010 15:08, Stewart, Robert skrev:
Frank Mori Hess wrote:
On Tuesday 28 December 2010, Gregory Crosswhite wrote:
It seems to me that it would be useful to have this functionality generally available as a library, and in particular it might be a good fit for the boost family of libraries. Is there any interest out there for having such a library in boost?
Yes, but there is already the AutoBuffer submission by Thorsten Ottosen in the review queue.
In case anyone wonders, Thorsten's schedule has prevented our setting a review date, but I do hope we can do it soon.
I expect to finnish pre-review work in february. regards -Thorsten
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message news:4D2AB8C0.7070700@cs.aau.dk...
I expect to finnish pre-review work in february.
Could you possibly add a policy that would 'produce' a strictly static buffer, i.e. that does not use/expand into the heap (to avoid the overhead described in the response to David Bergman)... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
Den 16-01-2011 16:13, Domagoj Saric skrev:
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message news:4D2AB8C0.7070700@cs.aau.dk...
I expect to finnish pre-review work in february.
Could you possibly add a policy that would 'produce' a strictly static buffer, i.e. that does not use/expand into the heap (to avoid the overhead described in the response to David Bergman)...
Maybe. I guess it takes some measurement to see if it is actually needed. For one, the container will allow you to do boost:.auto_buffer<T,N> buffer( n, boost::dont_initialize ); to make it avoid initialization. Futhermore, you may use buffer.unchecked_push_back( x ); to avoid code that checks for a full buffer and subsequent expansion. If that is not good enough, then why not just use boost::array<T,N>? (that is, if you really never will need the heap for any n) -Thorsten
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message news:4D331E6A.2030907@cs.aau.dk...
Den 16-01-2011 16:13, Domagoj Saric skrev:
Could you possibly add a policy that would 'produce' a strictly static buffer, i.e. that does not use/expand into the heap (to avoid the overhead described in the response to David Bergman)...
Maybe. I guess it takes some measurement to see if it is actually needed.
Why should we need to measure? - It is a priori known that overhead exists: containing and maintaining two extra pointers/size_ts, extra indirection for buffer access through a pointer on the stack (as opposed to 'direct' access to a buffer on the stack), 'possible' EH... - The primary, if not the sole purpose of this library is performance... ...so ignoring performance issues known in advance would be self/goal contradicting and a case of premature pessimization (as pretty much most of, so frequently encountered, 'invocations' of the 'root of all evil' rule are)... And measure what and how exactly? - A low level tool like this can be used in a wide range of ways...somewhere the difference will matter little, somewhere it will matter a lot...A 'good' library/tool ideally does not 'cut corners' based on assumptions that something 'will be good enough for everyone' (if it does not need to)...
For one, the container will allow you to do
boost:.auto_buffer<T,N> buffer( n, boost::dont_initialize );
to make it avoid initialization.
Nice. It would be useful if it could do something similar for non-POD types, i.e. it would take a functor in the constructor which it would then 'walk' through the N entries and let it in-place construct them (to avoid the usual default construction then assignment procedure)...
Futhermore, you may use
buffer.unchecked_push_back( x );
to avoid code that checks for a full buffer and subsequent expansion.
AFAICT there is no ('unchecked') resize equivalent... Speaking of which, there seem to be two approaches/syntaxes for using the unchecked/uninitialized versions (of code/functionality), with policies/tags and unchecked_*/uninitialized_* versions of functions...Perhaps it would be a 'happier' solution to go with only one option (policies/tags) or to replace both with a proxy 'unchecked' class...So that when you want 'unchecked' access you call the proxy getter and in effect get different semantics through an identical interface...This would also 'play better' with Boost.Range and <algorithms>...
If that is not good enough, then why not just use boost::array<T,N>? (that is, if you really never will need the heap for any n)
boost::array is not resizable... The gap between std::array and std::vector is larger then it may seem...and it might be worthwhile to use this opportunity to fill it completely...Besides a resizable stack-only/fixed-max-size buffer and a stack-to-heap expandable buffer (auto buffer) there is also a need for a fixed sized (non-resizable) buffer whose size is dynamically determined which also comes in two flavours, a stack-only portable alloca wrapper and a heap version...both can be modeled with a const iterator_range (the only essential difference being that the heap version has a non-trivial destructor that calls delete[]...)... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
"Domagoj Saric" <dsaritz@gmail.com> wrote in message news:ihep0q$gvj$1@dough.gmane.org... <...> ps. a few more ideas: - at first glance, the local scope guard macros could be replaced with meta-functions - the auto_buffer::deallocate 'destructor' callback should be specified (if not hardcoded) as a template parameter (to avoid the overhead of an indirect call) - the pointer/size_t data members should come before the ('huge') storage data member - a single 'policies' template parameter (that takes an MPL type-list) might be a better/'easier to extend' (albeit slower to compile:) solution than multiple template parameters... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
On Sat, Jan 22, 2011 at 6:18 AM, Domagoj Saric <dsaritz@gmail.com> wrote:
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message news:4D331E6A.2030907@cs.aau.dk...
Den 16-01-2011 16:13, Domagoj Saric skrev:
Could you possibly add a policy that would 'produce' a strictly static buffer, i.e. that does not use/expand into the heap (to avoid the overhead described in the response to David Bergman)...
Maybe. I guess it takes some measurement to see if it is actually needed.
Why should we need to measure? - It is a priori known that overhead exists: containing and maintaining two extra pointers/size_ts, extra indirection for buffer access through a pointer on the stack (as opposed to 'direct' access to a buffer on the stack), 'possible' EH... - The primary, if not the sole purpose of this library is performance... ...so ignoring performance issues known in advance would be self/goal contradicting and a case of premature pessimization (as pretty much most of, so frequently encountered, 'invocations' of the 'root of all evil' rule are)...
The performance benefits remain theoretical until measured and, in theory, a "stack-based" vector is not needed because std::vector is allowed to be stack-based when possible. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
[Emil Dotchevski]
std::vector is allowed to be stack-based when possible.
STL containers must support O(1), nofail, non-iterator-invalidating swaps*. According to my understanding, this forbids a "Small Vector Optimization", if not in theory then in practice (i.e. without compromising performance elsewhere). STL (* With a few exceptions, like for std::string's Small String Optimization, and for end iterators to permit container-internal sentinel nodes.)
On Sat, Jan 22, 2011 at 8:11 PM, Stephan T. Lavavej <stl@exchange.microsoft.com> wrote:
[Emil Dotchevski]
std::vector is allowed to be stack-based when possible.
STL containers must support O(1), nofail, non-iterator-invalidating swaps*. According to my understanding, this forbids a "Small Vector Optimization", if not in theory then in practice (i.e. without compromising performance elsewhere).
You're STL after all :) so please correct me if I'm wrong, but according to my understanding the compiler is allowed to "know" the specific semantics of standard functions and classes, and optimize based on that knowledge. In this case, if the compiler can prove that swap isn't called for that vector, there is no problem. I don't think that the compiler is even required to parse any standard headers such as <vector>, it just has to make available (implement) the semantics of the types and the definitions they contain as specified by the standard. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
The As If Rule always applies, but I can confidently say that nobody's compiler and Standard Library implementation conspires in such a way. STL ________________________________________ From: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] on behalf of Emil Dotchevski [emildotchevski@gmail.com] Sent: Saturday, January 22, 2011 11:05 PM To: boost@lists.boost.org Subject: Re: [boost] Stack-based vector container On Sat, Jan 22, 2011 at 8:11 PM, Stephan T. Lavavej <stl@exchange.microsoft.com> wrote:
[Emil Dotchevski]
std::vector is allowed to be stack-based when possible.
STL containers must support O(1), nofail, non-iterator-invalidating swaps*. According to my understanding, this forbids a "Small Vector Optimization", if not in theory then in practice (i.e. without compromising performance elsewhere).
You're STL after all :) so please correct me if I'm wrong, but according to my understanding the compiler is allowed to "know" the specific semantics of standard functions and classes, and optimize based on that knowledge. In this case, if the compiler can prove that swap isn't called for that vector, there is no problem. I don't think that the compiler is even required to parse any standard headers such as <vector>, it just has to make available (implement) the semantics of the types and the definitions they contain as specified by the standard. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sat, Jan 22, 2011 at 11:13 PM, Stephan T. Lavavej <stl@exchange.microsoft.com> wrote:
The As If Rule always applies, but I can confidently say that nobody's compiler and Standard Library implementation conspires in such a way.
Right, so it remains theoretical. My point was that the benefits of a stack-based vector type are also theoretical. Practically speaking, if std::vector is causing performance problems, I don't see myself thinking "ok, I need a stack-based vector." In that case, it makes more sense to me to throw all abstraction out and get down to the metal. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
Actually, I can report from experience that hand-rolling my own stack-based vector allowed me to speed up my code by at least an order of magnitude, so the benefit is not theoretical. My situation was that I was working with vectors that were relatively small and for which I knew the upper-bound at compile time. Since most of the computation was just bitwise operations such as XORs, when I profiled my code I found that the majority of the time was spent allocating and freeing memory for std::vector. Even when I explicitly reserved memory (so that std::vector would only perform an allocation once) there was still a significant overhead. Replacing std::vector with a stack-based vector eliminated this overhead and significantly sped up my code by an order of magnitude. In fact, it was exactly my experience with this performance improvement which inspired me to start this thread in the first place. Cheers, Greg On 1/22/11 11:52 PM, Emil Dotchevski wrote:
On Sat, Jan 22, 2011 at 11:13 PM, Stephan T. Lavavej <stl@exchange.microsoft.com> wrote:
The As If Rule always applies, but I can confidently say that nobody's compiler and Standard Library implementation conspires in such a way. Right, so it remains theoretical.
My point was that the benefits of a stack-based vector type are also theoretical. Practically speaking, if std::vector is causing performance problems, I don't see myself thinking "ok, I need a stack-based vector." In that case, it makes more sense to me to throw all abstraction out and get down to the metal.
Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode _______________________________________________ Unsubscribe& other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Emil Dotchevski" <emildotchevski@gmail.com> wrote in message news:AANLkTin5gq+-zYpW+z9+xGBNW25nvqJOpRJJv484phGJ@mail.gmail.com...
On Sat, Jan 22, 2011 at 11:13 PM, Stephan T. Lavavej <stl@exchange.microsoft.com> wrote:
The As If Rule always applies, but I can confidently say that nobody's compiler and Standard Library implementation conspires in such a way.
Right, so it remains theoretical.
My point was that the benefits of a stack-based vector type are also theoretical.
So, if I got this right, you managed to sort-of-prove that a stack-based partial/nonstd::vector<> implementation is theoretically possible...what I fail to see is how does this, in any way, through analogy or otherwise, implies anything about the benefits of a stack-based vector...much less about the original or other proposals so far listed in this thread...
Practically speaking, if std::vector is causing performance problems, I don't see myself thinking "ok, I need a stack-based vector." In that case, it makes more sense to me to throw all abstraction out and get down to the metal.
As one size does not fit all, 'I don't see myself' is not a valid argument of any kind...By your rationale you not only do not need/want a stack-based vector/array-like container (which was proposed here precisely because there are people that demonstrably need it) but for example also intrusive_ptrs (after all if shared_ptr is somehow causing performance problems we should 'get down to the metal'/raw pointers)...should we have those removed from Boost? If not, what is the issue with including a new container in Boost that tries to solve a specific problem and that noone will force you to use? -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
"Emil Dotchevski" <emildotchevski@gmail.com> wrote in message news:AANLkTinASY3YpYfbXHFhjT44gtO2_1Zs=-nJTo1xhzoU@mail.gmail.com...
The performance benefits remain theoretical until measured
In this context this is as meaningful as saying that the performance benefits of std::vector<>::reserve() remain theoretical until measured... ...or that the assertion that the performance benefits remain theoretical until measured itself remains theoretical until proven... No measurement is required to know that an 'unchecked'+'uninitialised' resize() function compiles down to a single CISC instruction (adding a constant to a pointer) while its 'checked'-possibly-to-heap-expanding-thus-possibly-throwing version compiles to a 'full fat' function that 'pollutes' the caller with EH code/unwind funclets (plus in practice disables certain compiler optimizations)... The fact that this may have little or no consequence on your code or you simply do not care is just as simply irrelevant (because, of course, C++ is still not a 'managed' language and one size does not fit all)... How about, for once, we turn the (mis/ab)used 'root of all evil' rule on its head and disallow premature pessimization until measured and proven 'negligible'...
and, in theory, a "stack-based" vector is not needed because std::vector is allowed to be stack-based when possible.
As already explained a std::vector<> with a stack/static based allocator is not quite equivalent to the original proposal... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
Den 22-01-2011 15:18, Domagoj Saric skrev:
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message news:4D331E6A.2030907@cs.aau.dk...
Den 16-01-2011 16:13, Domagoj Saric skrev:
Could you possibly add a policy that would 'produce' a strictly static buffer, i.e. that does not use/expand into the heap (to avoid the overhead described in the response to David Bergman)...
Maybe. I guess it takes some measurement to see if it is actually needed.
Why should we need to measure? - It is a priori known that overhead exists: containing and maintaining two extra pointers/size_ts, extra indirection for buffer access through a pointer on the stack (as opposed to 'direct' access to a buffer on the stack), 'possible' EH... - The primary, if not the sole purpose of this library is performance... ....so ignoring performance issues known in advance would be self/goal contradicting and a case of premature pessimization (as pretty much most of, so frequently encountered, 'invocations' of the 'root of all evil' rule are)...
And measure what and how exactly?
assembler or runtime.
- A low level tool like this can be used in a wide range of ways...somewhere the difference will matter little, somewhere it will matter a lot...A 'good' library/tool ideally does not 'cut corners' based on assumptions that something 'will be good enough for everyone' (if it does not need to)...
mostly agree.
For one, the container will allow you to do
boost:.auto_buffer<T,N> buffer( n, boost::dont_initialize );
to make it avoid initialization.
Nice. It would be useful if it could do something similar for non-POD types, i.e. it would take a functor in the constructor which it would then 'walk' through the N entries and let it in-place construct them (to avoid the usual default construction then assignment procedure)...
well, you can just do that post-construction wise. No need for another constructor.
Futhermore, you may use
buffer.unchecked_push_back( x );
to avoid code that checks for a full buffer and subsequent expansion.
AFAICT there is no ('unchecked') resize equivalent...
unitialised_resize() ?
Speaking of which, there seem to be two approaches/syntaxes for using the unchecked/uninitialized versions (of code/functionality), with policies/tags and unchecked_*/uninitialized_* versions of functions...Perhaps it would be a 'happier' solution to go with only one option (policies/tags) or to replace both with a proxy 'unchecked' class...So that when you want 'unchecked' access you call the proxy getter and in effect get different semantics through an identical interface...This would also 'play better' with Boost.Range and <algorithms>...
How? Range algorithms use iterators and not much else. boost::push_back( cont, range ) does not call cont.push_back(), and is the preferred way compared to using copy().
If that is not good enough, then why not just use boost::array<T,N>? (that is, if you really never will need the heap for any n)
boost::array is not resizable... The gap between std::array and std::vector is larger then it may seem...and it might be worthwhile to use this opportunity to fill it completely...Besides a resizable stack-only/fixed-max-size buffer and a stack-to-heap expandable buffer (auto buffer) there is also a need for a fixed sized (non-resizable) buffer whose size is dynamically determined which also comes in two flavours, a stack-only portable alloca wrapper
alloca() does not seem to apply here: think about where you would put the call.
and a heap version...both can be modeled with a const iterator_range (the only essential difference being that the heap version has a non-trivial destructor that calls delete[]...)...
As I said, I'm not sure we need all these variants. For example, if the buffer does not need to be expanded, then it is likely the compiler can determine that the capacity_ member is not used. As for the conjectured extra indirection, then I'm not sure it can become any major performance problem, nor do I see how one can avoid it when we need to go for the heap in certain cases. -Thorsten
On Sun, Jan 23, 2011 at 1:01 PM, Thorsten Ottosen <nesotto@cs.aau.dk> wrote:
As for the conjectured extra indirection, then I'm not sure it can become any major performance problem, nor do I see how one can avoid it when we need to go for the heap in certain cases.
Clearly the extra indirection is the only potential problem, otherwise a stack-based vector implementation could probably be replaced by a stack-based std::vector allocator. However, the cost of the extra indirection is platform-dependent and difficult to measure in the abstract. In my experience, most cases when someone has complained about inefficiencies in std::vector boil down to incorrect use: - not using reserve(); - calling push_back()/insert() in a loop (which is inefficient even with reserve); - iterating by redundantly calling end() each time; - using operator[] for sequential access to the elements. So the only meaningful way to evaluate the benefits of a std::vector alternative is to discuss specific use cases, considering other alternatives as well. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
On 23 Jan 2011, at 23:59, Emil Dotchevski wrote:
On Sun, Jan 23, 2011 at 1:01 PM, Thorsten Ottosen <nesotto@cs.aau.dk> wrote:
As for the conjectured extra indirection, then I'm not sure it can become any major performance problem, nor do I see how one can avoid it when we need to go for the heap in certain cases.
Clearly the extra indirection is the only potential problem, otherwise a stack-based vector implementation could probably be replaced by a stack-based std::vector allocator.
However, the cost of the extra indirection is platform-dependent and difficult to measure in the abstract. In my experience, most cases when someone has complained about inefficiencies in std::vector boil down to incorrect use:
- not using reserve(); - calling push_back()/insert() in a loop (which is inefficient even with reserve); - iterating by redundantly calling end() each time; - using operator[] for sequential access to the elements.
I find most modern compilers do not have issues with calling end() repeatedly, or push_back(). Also it is unclear if operator[] or iterators are more efficient. The biggest issue I have with using vector is short-lived vectors, where the time is dominated by calls to new/delete inside the allocator. Of course I could start caching vectors everywhere, but then that introduces threading and singleton issues, which I would prefer to avoid. This is the ideal place for stack-based vectors, where allocating and freeing the vector is (almost) free. Chris
"Christopher Jefferson" <chris@bubblescope.net> wrote in message news:C656C64C-8E00-4D67-ACE1-6A95B9A65281@bubblescope.net...
I find most modern compilers do not have issues with calling end() repeatedly, or push_back().
push_back() is a possibly-new-calling/possibly-throwing 'fat function', in which way do you mean that modern compilers 'do not have issues' with it? And could you please name such a compiler...
Also it is unclear if operator[] or iterators are more efficient.
You know of a (real) use case where indexed based access is faster than pointer based? -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
On 25 Jan 2011, at 23:19, Domagoj Saric wrote:
"Christopher Jefferson" <chris@bubblescope.net> wrote in message news:C656C64C-8E00-4D67-ACE1-6A95B9A65281@bubblescope.net...
I find most modern compilers do not have issues with calling end() repeatedly, or push_back().
push_back() is a possibly-new-calling/possibly-throwing 'fat function', in which way do you mean that modern compilers 'do not have issues' with it? And could you please name such a compiler...
for vector<int>::push_back, gcc will inline the common case (there is no need to allocate new memory) and no inline the memory allocation when the vector grows. Therefore you just end up paying for one comparison of two pointers for each push_back call, to check there is still space.
Also it is unclear if operator[] or iterators are more efficient.
You know of a (real) use case where indexed based access is faster than pointer based?
I have found in the past, depending on the compiler and it's settings, it can be unpredictable. I don't have exact numbers, but there were points in the past where gcc's loop unroller unrolled some index based code, but not pointer based code. They may well have fixed it now. Chris
"Christopher Jefferson" <chris@bubblescope.net> wrote in message news:202EA587-0082-4DD3-A457-CD69710E6BBE@bubblescope.net...
On 25 Jan 2011, at 23:19, Domagoj Saric wrote:
"Christopher Jefferson" <chris@bubblescope.net> wrote in message news:C656C64C-8E00-4D67-ACE1-6A95B9A65281@bubblescope.net...
I find most modern compilers do not have issues with calling end() repeatedly, or push_back().
push_back() is a possibly-new-calling/possibly-throwing 'fat function', in which way do you mean that modern compilers 'do not have issues' with it? And could you please name such a compiler...
for vector<int>::push_back, gcc will inline the common case (there is no need to allocate new memory) and no inline the memory allocation when the vector grows. Therefore you just end up paying for one comparison of two pointers for each push_back call, to check there is still space.
But the code for the branch that allocates memory and is never executed (for known fixed sized problems/usages) still gets generated and causes EH code to be generated for all calling code... Plus the inlining causes template bloat... (When, again, adding a constant/integer to a pointer is all that is necessary...)
You know of a (real) use case where indexed based access is faster than pointer based?
I have found in the past, depending on the compiler and it's settings, it can be unpredictable. I don't have exact numbers, but there were points in the past where gcc's loop unroller unrolled some index based code, but not pointer based code. They may well have fixed it now.
Oh...that's a compiler issue, not something intrinsic to index-vs-pointer based access... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
Den 24-01-2011 00:59, Emil Dotchevski skrev:
On Sun, Jan 23, 2011 at 1:01 PM, Thorsten Ottosen<nesotto@cs.aau.dk> wrote:
As for the conjectured extra indirection, then I'm not sure it can become any major performance problem, nor do I see how one can avoid it when we need to go for the heap in certain cases.
Clearly the extra indirection is the only potential problem, otherwise a stack-based vector implementation could probably be replaced by a stack-based std::vector allocator.
clearly?
However, the cost of the extra indirection is platform-dependent and difficult to measure in the abstract. In my experience, most cases when someone has complained about inefficiencies in std::vector boil down to incorrect use:
- not using reserve(); - calling push_back()/insert() in a loop (which is inefficient even with reserve); - iterating by redundantly calling end() each time;
can be hoisted for vector, but not for most other containers.
- using operator[] for sequential access to the elements.
?
So the only meaningful way to evaluate the benefits of a std::vector alternative is to discuss specific use cases, considering other alternatives as well.
A stack-based allocator will work in C++0x, and probably works ok in C++03. In any case, the array needs to be created externally to the class which is somewhat more inconvenient, especially if you need to copy the vector around. But anyway, I agree on your requirements for a good analysis. -Thorsten
On Jan 23, 2011, at 6:59 PM, Emil Dotchevski wrote:
So the only meaningful way to evaluate the benefits of a std::vector alternative is to discuss specific use cases, considering other alternatives as well.
Some use cases: 1. swap. 2. return an auto local from a factory function. 3. desired behavior when capacity exceeds stack space (go to heap or throw an exception?). Sometimes std::vector is going to want to transfer memory ownership. Those are the use cases I would look at first. What does std::vector<T, stack_alloc<T>> do? What does stack_vector<T> do? What do you want to happen? -Howard
On Sun, Jan 23, 2011 at 4:46 PM, Howard Hinnant <howard.hinnant@gmail.com> wrote:
On Jan 23, 2011, at 6:59 PM, Emil Dotchevski wrote:
So the only meaningful way to evaluate the benefits of a std::vector alternative is to discuss specific use cases, considering other alternatives as well.
Some use cases:
1. swap. 2. return an auto local from a factory function. 3. desired behavior when capacity exceeds stack space (go to heap or throw an exception?).
Sometimes std::vector is going to want to transfer memory ownership. Those are the use cases I would look at first. What does std::vector<T, stack_alloc<T>> do? What does stack_vector<T> do? What do you want to happen?
Assuming that "we just want it to be faster than std::vector in doing X and Y", someone could see the limitations of std::vector as nuisance. Yet this is an indication that performance considerations will probably trump all other design decisions, since std::vector implements a pretty basic concept already. Paraphrasing my earlier concerns, the question is are we going to end up with something universal enough to be reusable, or will its own limitations become nuisance in other (even similar) situations? Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
On Jan 23, 2011, at 8:13 PM, Emil Dotchevski wrote:
On Sun, Jan 23, 2011 at 4:46 PM, Howard Hinnant <howard.hinnant@gmail.com> wrote:
On Jan 23, 2011, at 6:59 PM, Emil Dotchevski wrote:
So the only meaningful way to evaluate the benefits of a std::vector alternative is to discuss specific use cases, considering other alternatives as well.
Some use cases:
1. swap. 2. return an auto local from a factory function. 3. desired behavior when capacity exceeds stack space (go to heap or throw an exception?).
Sometimes std::vector is going to want to transfer memory ownership. Those are the use cases I would look at first. What does std::vector<T, stack_alloc<T>> do? What does stack_vector<T> do? What do you want to happen?
Assuming that "we just want it to be faster than std::vector in doing X and Y", someone could see the limitations of std::vector as nuisance. Yet this is an indication that performance considerations will probably trump all other design decisions, since std::vector implements a pretty basic concept already. Paraphrasing my earlier concerns, the question is are we going to end up with something universal enough to be reusable, or will its own limitations become nuisance in other (even similar) situations?
I think we are in agreement. I think there are issues other than speed here, though speed is certainly a big issue. And I haven't made up my own mind about which direction this project should take. But if there are correctness issues, I think they trump speed issues. Let's say we have: template <class T> using StackVector = <details we don't know yet>; // maybe based on std::vector, maybe not How should this code behave? bool test0(); template <class T> StackVector<T> test1() { StackVector<T> v1; StackVector<T> v2; // ... return test0() ? v1 : v2; } int main() { StackVector<std::string> v1 = test1(); v1 = test1(); } I can think of several reasonable answers: 1. Does not compile. StackVector can't be copied or moved. 2. Compiles and does an element-by-element move on both move construction and move assignment. 3. Compiles and does copies based on C++03 rules; no C++0x move semantics. From reading this thread I get that people want StackVector to avoid heap allocations. But I really have no idea how people want StackVector to behave in situations such as the above. And without a clear understanding of such desired behavior, it seems difficult to design. -Howard
On 24/01/11 02:36, Howard Hinnant wrote:
I can think of several reasonable answers:
1. Does not compile. StackVector can't be copied or moved. 2. Compiles and does an element-by-element move on both move construction and move assignment. 3. Compiles and does copies based on C++03 rules; no C++0x move semantics.
From reading this thread I get that people want StackVector to avoid heap allocations. But I really have no idea how people want StackVector to behave in situations such as the above. And without a clear understanding of such desired behavior, it seems difficult to design.
Throwing my 2cts in here as I went this slippery road already: if we throw the static/dynamically sized problem out of scope, one must separate the need of stack allocated container (aka some vector using a T[N] inside to holds data) which will be copiable/movable on a per element basis and some platform-specific "stack living" container which use w/e specific system call to allocate new space in a function stack (alloca comes ot mind) and have a life span that does not go further than current scope, thus being non copiable but movable on an element basis. Both have different use case and provides different benefit: the first allow for compile-time sized array that ave on new/delete but otherwise have some similar performance than vector ( operator[] and iterator are just not that penalizing nowadays, i urge you to rerun the stepanov_penalty tests), the second has some noticable benefit for small, funtion local buffers that should not outlive the fucntion call. So, what do we want here ?
On 23 January 2011 19:36, Howard Hinnant <howard.hinnant@gmail.com> wrote:
But if there are correctness issues, I think they trump speed issues.
+1. 1. Does not compile. StackVector can't be copied or moved.
2. Compiles and does an element-by-element move on both move construction and move assignment. 3. Compiles and does copies based on C++03 rules; no C++0x move semantics.
I would like to see them copyable (and probably moveable, but I haven't thought that through yet). While the need to copy these things is rare, it still comes up. Calling this StackVector is somewhat of a misnomer, as I'd like to be able to use an object of that type as a member variable, and that aggregate may or may not be on the stack. This is one (but not the only) reason I want it copyable, as types that aren't copyable are a pain to use as member variables.
From reading this thread I get that people want StackVector to avoid heap allocations. But I really have no idea how people want StackVector to behave in situations such as the above. And without a clear understanding of such desired behavior, it seems difficult to design.
1. There are times I know the likely largest size of a container, above which I am willing to pay an allocation cost. 2. There are times I want to limit the maximum size of a container. Note: StackVector does not solve all combinations of (1) and (2), but its a good start. :-) -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
Nevin Liber wrote:
1. There are times I know the likely largest size of a container, above which I am willing to pay an allocation cost.
Thorsten's proposed auto_vector does that.
2. There are times I want to limit the maximum size of a container.
boost::array does that, but then it doesn't have the notion of capacity.
Note: StackVector does not solve all combinations of (1) and (2), but its a good start. :-)
It isn't clear whether there should be one class template, with suitable policies, to handle all of these cases, or whether separate class templates would be easier to understand and use. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On 24 January 2011 11:41, Stewart, Robert <Robert.Stewart@sig.com> wrote:
2. There are times I want to limit the maximum size of a container.
boost::array does that, but then it doesn't have the notion of capacity.
boost::array is a container with an exact size, not (just) a maximum size. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
Nevin Liber wrote:
On 24 January 2011 11:41, Stewart, Robert <Robert.Stewart@sig.com> wrote:
2. There are times I want to limit the maximum size of a container.
boost::array does that, but then it doesn't have the notion of capacity.
boost::array is a container with an exact size, not (just) a maximum size.
That was my point. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
"Nevin Liber" <nevin@eviloverlord.com> wrote in message news:AANLkTimWurT4NnfN4yE10SsJoEhxTZfKRALjiUGWF_NW@mail.gmail.com...
Calling this StackVector is somewhat of a misnomer
I agree on the name issue...calling it a buffer is also a misnomer as it would imply POD storage...
Note: StackVector does not solve all combinations of (1) and (2), but its a good start. :-)
Having a: - resizable fixed-capacity 'vector' (basically a boost::array with an end pointer) - resizable fixed-preallocated-capacitiy+to-heap-expandable vector (IOW AutoBuffer/StackVector, can be implemented in terms of the fixed-capacity 'vector' plus the capacity and 'actual storage' pointers) - fixed size/non-resizable dynamically stack allocated 'vector' - fixed size/non-resizable dynamically heap allocated 'vector' would, with std::array and std::vector, probably cover all areas.... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
"Emil Dotchevski" <emildotchevski@gmail.com> wrote in message news:AANLkTimfZnofwHQygQf6HWh7wvJqfn2nyNhZTtnG6P20@mail.gmail.com...
On Sun, Jan 23, 2011 at 1:01 PM, Thorsten Ottosen <nesotto@cs.aau.dk> wrote:
As for the conjectured extra indirection, then I'm not sure it can become any major performance problem, nor do I see how one can avoid it when we need to go for the heap in certain cases.
Clearly the extra indirection is the only potential problem, otherwise a stack-based vector implementation could probably be replaced by a stack-based std::vector allocator.
I don't see that 'clearly'...the most pronounced effect/issue is highly dependent on the use case and the software and hardware environment... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message news:4D3C972E.30509@cs.aau.dk...
Den 22-01-2011 15:18, Domagoj Saric skrev:
And measure what and how exactly?
assembler or runtime.
As already explained 'runtime' is IMO untestable in practice (in the 'wide range of ways' sense)... Assembler OTOH, if by that you meant inspecting the generated code, is IMO the way to go in this case (especially because it reveals size as well as speed issues)...however no real analysis is probably required as the assembly output is quite predictable here (e.g. in my last post to Emil Dotchevski)...
For one, the container will allow you to do
boost:.auto_buffer<T,N> buffer( n, boost::dont_initialize );
to make it avoid initialization.
Nice. It would be useful if it could do something similar for non-POD types, i.e. it would take a functor in the constructor which it would then 'walk' through the N entries and let it in-place construct them (to avoid the usual default construction then assignment procedure)...
well, you can just do that post-construction wise. No need for another constructor.
How would you do that in an exception-safe way (you need to correctly 'roll-back'/unwind the construction if any of the constructors fail...)?
Futhermore, you may use
buffer.unchecked_push_back( x );
to avoid code that checks for a full buffer and subsequent expansion.
AFAICT there is no ('unchecked') resize equivalent...
unitialised_resize() ?
Is this also 'unchecked'?
...Perhaps it would be a 'happier' solution to go with only one option (policies/tags) or to replace both with a proxy 'unchecked' class...So that when you want 'unchecked' access you call the proxy getter and in effect get different semantics through an identical interface...This would also 'play better' with Boost.Range and <algorithms>...
How? Range algorithms use iterators and not much else.
boost::push_back( cont, range )
By calling/passing boost::push_back( cont.unchecked(), range ) or boost::push_back( cont.uninitialised(), range ) ;)
boost::push_back( cont, range )
does not call cont.push_back(), and is the preferred way compared to using copy().
Yes, it calls insert() which still benefits from 'unchecked' resizing...
The gap between std::array and std::vector is larger then it may seem...and it might be worthwhile to use this opportunity to fill it completely...Besides a resizable stack-only/fixed-max-size buffer and a stack-to-heap expandable buffer (auto buffer) there is also a need for a fixed sized (non-resizable) buffer whose size is dynamically determined which also comes in two flavours, a stack-only portable alloca wrapper
alloca() does not seem to apply here: think about where you would put the call.
Of course, the alloca/'dynamic-stack-based' version would have to use a 'factory macro'...it is still possible to make it type safe...the macro would only allocate local function stack storage and pass it on to a factory function...
and a heap version...both can be modeled with a const iterator_range (the only essential difference being that the heap version has a non-trivial destructor that calls delete[]...)...
As I said, I'm not sure we need all these variants.
I could point out that I have use for both for example in my GIL.IO2 code however IMO no (other) justification is necessary considering that 'all these variants' already exist as C counter-parts (malloc and alloca) as well as all the in-house (C++) versions...
For example, if the buffer does not need to be expanded, then it is likely the compiler can determine that the capacity_ member is not used.
From my experience I'd consider that (highly) unlikely (if any resizing function is called)...
As for the conjectured extra indirection, then I'm not sure it can become any major performance problem,
Again, sometimes it will sometimes it will not...with a library like this we should not go for 'rules of thumb' but rather provide a sharp set of tools... As hinted before, code size is (as always, at least in my book) a concern here just as speed and saving a dozen instructions on every use can be significant when combating template bloat (for example in GIL.IO with certain backends like LibTIFF there are hundreds of possible format combinations each of which instantiates its own set of function templates that use local temporary buffers)...
nor do I see how one can avoid it when we need to go for the heap in certain cases.
Exactly, that's why I asked for a no-heap policy...however now I think its better to model each of the different 'variants' with a separate type/template... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
Den 26-01-2011 00:07, Domagoj Saric skrev:
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message
For one, the container will allow you to do
boost:.auto_buffer<T,N> buffer( n, boost::dont_initialize );
to make it avoid initialization.
Nice. It would be useful if it could do something similar for non-POD types, i.e. it would take a functor in the constructor which it would then 'walk' through the N entries and let it in-place construct them (to avoid the usual default construction then assignment procedure)...
well, you can just do that post-construction wise. No need for another constructor.
How would you do that in an exception-safe way (you need to correctly 'roll-back'/unwind the construction if any of the constructors fail...)?
Not that hard, just do some cleanup in the catch-clause.
Futhermore, you may use
buffer.unchecked_push_back( x );
to avoid code that checks for a full buffer and subsequent expansion.
AFAICT there is no ('unchecked') resize equivalent...
unitialised_resize() ?
Is this also 'unchecked'?
no, IIRC.
...Perhaps it would be a 'happier' solution to go with only one option (policies/tags) or to replace both with a proxy 'unchecked' class...So that when you want 'unchecked' access you call the proxy getter and in effect get different semantics through an identical interface...This would also 'play better' with Boost.Range and <algorithms>...
How? Range algorithms use iterators and not much else.
boost::push_back( cont, range )
By calling/passing boost::push_back( cont.unchecked(), range ) or boost::push_back( cont.uninitialised(), range ) ;)
boost::push_back( cont, range )
does not call cont.push_back(), and is the preferred way compared to using copy().
Yes, it calls insert() which still benefits from 'unchecked' resizing...
so you want to save one if-statement in this rather expensive operation? If so, you can just use copy().
For example, if the buffer does not need to be expanded, then it is likely the compiler can determine that the capacity_ member is not used.
From my experience I'd consider that (highly) unlikely (if any resizing function is called)...
but why do you want to call a resizing operation? I assume in this case that the buffer is fixed after construction.
nor do I see how one can avoid it when we need to go for the heap in certain cases.
Exactly, that's why I asked for a no-heap policy...however now I think its better to model each of the different 'variants' with a separate type/template...
Seems like a big step. Let's see what the assembly analysis comes up with. In the mean time it would help if you could write some small use cases explaining which functions you want to call in the different scenarios (this would also make the discussion more concrete). -Thorsten
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message news:4D3F6599.3090108@cs.aau.dk...
Den 26-01-2011 00:07, Domagoj Saric skrev:
Nice. It would be useful if it could do something similar for non-POD types, i.e. it would take a functor in the constructor which it would then 'walk' through the N entries and let it in-place construct them (to avoid the usual default construction then assignment procedure)...
well, you can just do that post-construction wise. No need for another constructor.
How would you do that in an exception-safe way (you need to correctly 'roll-back'/unwind the construction if any of the constructors fail...)?
Not that hard, just do some cleanup in the catch-clause.
That would be ugh-ly... It would be akin to something like expecting users to manually predestruct a std::string before assigning a new one to it...And wouldn't work anyway...for example what would happen in the auto_buffer destructor in this case: { boost:.auto_buffer<std::string, N> buffer( n, boost::dont_initialize ); throw std::exception(); } how would it know how many (if any) of the N std::strings it holds have been constructed and need to be destroyed? And, regardless of the above, if it is a common task why not provide it in the library?
Futhermore, you may use
buffer.unchecked_push_back( x );
to avoid code that checks for a full buffer and subsequent expansion.
AFAICT there is no ('unchecked') resize equivalent...
unitialised_resize() ?
Is this also 'unchecked'?
no, IIRC.
Then it is not an unchecked_push_back() equivalent...
...Perhaps it would be a 'happier' solution to go with only one option (policies/tags) or to replace both with a proxy 'unchecked' class...So that when you want 'unchecked' access you call the proxy getter and in effect get different semantics through an identical interface...This would also 'play better' with Boost.Range and <algorithms>...
How? Range algorithms use iterators and not much else.
boost::push_back( cont, range )
By calling/passing boost::push_back( cont.unchecked(), range ) or boost::push_back( cont.uninitialised(), range ) ;)
boost::push_back( cont, range )
does not call cont.push_back(), and is the preferred way compared to using copy().
Yes, it calls insert() which still benefits from 'unchecked' resizing...
so you want to save one if-statement in this rather expensive operation? If so, you can just use copy().
No, (as in the push_back case described by Christopher Jefferson) besides the branching you save the _generation_ of a branch of code that will never get executed and that will cause the whole function to be considered as throwing by the compiler...
For example, if the buffer does not need to be expanded, then it is likely the compiler can determine that the capacity_ member is not used.
From my experience I'd consider that (highly) unlikely (if any resizing function is called)...
but why do you want to call a resizing operation? I assume in this case that the buffer is fixed after construction.
It isn't/need not be, the first container type from the list posted in response to Nevin Liber (resizable with fixed-capacity) can be resized without need for 'capacity' or exceptions... Plus, the constructor can also be considered a 'resizing' function (it sets the capacity to an initial value)...
nor do I see how one can avoid it when we need to go for the heap in certain cases.
Exactly, that's why I asked for a no-heap policy...however now I think its better to model each of the different 'variants' with a separate type/template...
Seems like a big step. Let's see what the assembly analysis comes up with. In the mean time it would help if you could write some small use cases explaining which functions you want to call in the different scenarios (this would also make the discussion more concrete).
I honestly don't see why is this a big step...as I don't see the need for actual assembly analysis - the four vector-like container versions I proposed are all rather simple concepts/classes (except of course for the second one, the equivalent of your auto_buffer) and thus relatively simple to implement (ad 'big step') with relatively predictable 'footprint'/generated code (ad 'analysis') and rather obvious use cases (e.g. a "fixed size/non-resizable dynamically stack allocated 'vector'" is obviously to be used in cases where the size of the container is known at runtime but known not to be too large not to fit on the stack and that there will be no need for resizing)... -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman
Den 30-01-2011 17:55, Domagoj Saric skrev:
"Thorsten Ottosen" <nesotto@cs.aau.dk> wrote in message news:4D3F6599.3090108@cs.aau.dk...
Den 26-01-2011 00:07, Domagoj Saric skrev:
Nice. It would be useful if it could do something similar for non-POD types, i.e. it would take a functor in the constructor which it would then 'walk' through the N entries and let it in-place construct them (to avoid the usual default construction then assignment procedure)...
well, you can just do that post-construction wise. No need for another constructor.
How would you do that in an exception-safe way (you need to correctly 'roll-back'/unwind the construction if any of the constructors fail...)?
Not that hard, just do some cleanup in the catch-clause.
That would be ugh-ly... It would be akin to something like expecting users to manually predestruct a std::string before assigning a new one to it...And wouldn't work anyway...for example what would happen in the auto_buffer destructor in this case: { boost:.auto_buffer<std::string, N> buffer( n, boost::dont_initialize ); throw std::exception(); } how would it know how many (if any) of the N std::strings it holds have been constructed and need to be destroyed?
And, regardless of the above, if it is a common task why not provide it in the library?
Could be. We still have algorithms like std::uninitalized_copy() for this case.
Futhermore, you may use
buffer.unchecked_push_back( x );
to avoid code that checks for a full buffer and subsequent expansion.
AFAICT there is no ('unchecked') resize equivalent...
unitialised_resize() ?
Is this also 'unchecked'?
no, IIRC.
Then it is not an unchecked_push_back() equivalent...
I agree unchecked_resize() should be added. -Thorsten
participants (17)
-
Bo Persson -
Christopher Jefferson -
Dave Abrahams -
David Bergman -
Domagoj Saric -
Emil Dotchevski -
Frank Mori Hess -
gast128 -
Gregory Crosswhite -
Howard Hinnant -
Joel Falcou -
Michael Caisse -
Nelson, Erik - 2 -
Nevin Liber -
Stephan T. Lavavej -
Stewart, Robert -
Thorsten Ottosen