[boost] Stack-based vector container
Gregory Crosswhite
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
Michael Caisse
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
Gregory Crosswhite
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
David Bergman
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
Nelson, Erik - 2
>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.
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.
Dave Abrahams
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
Michael Caisse
> 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
_______________________________________________
Frank Mori Hess
> 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.
Frank Mori Hess
>
> 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.
Howard Hinnant
> 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
Gregory Crosswhite
Great, that looks basically like the idea I was proposing. :-) Thanks!
- Greg
Frank Mori Hess
> > 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
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
Nevin Liber
> 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:ne...@eviloverlord.com> (847) 691-1404
Dave Abrahams
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.
Stewart, Robert
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....@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.
Howard Hinnant
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.
gast128
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...
};
Thorsten Ottosen
> 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
Domagoj Saric
"David Bergman" <David....@bergmangupta.com> wrote in message
news:FF46F967-E45E-4188...@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
"Thorsten Ottosen" <nes...@cs.aau.dk> wrote in message
news:4D2AB8C0...@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
Thorsten Ottosen
>
> "Thorsten Ottosen" <nes...@cs.aau.dk> wrote in message
> news:4D2AB8C0...@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
Bo Persson
> "David Bergman" <David....@bergmangupta.com> wrote in message
> news:FF46F967-E45E-4188...@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
Domagoj Saric
> 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
"Bo Persson" <b...@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
Domagoj Saric
"Domagoj Saric" <dsa...@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...
Emil Dotchevski
>
> "Thorsten Ottosen" <nes...@cs.aau.dk> wrote in message
> news:4D331E6A...@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
Stephan T. Lavavej
> 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.)
Emil Dotchevski
<s...@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
Stephan T. Lavavej
STL
________________________________________
From: boost-...@lists.boost.org [boost-...@lists.boost.org] on behalf of Emil Dotchevski [emildot...@gmail.com]
Sent: Saturday, January 22, 2011 11:05 PM
To: bo...@lists.boost.org
Subject: Re: [boost] Stack-based vector container
Emil Dotchevski
<s...@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.