[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.
Gregory Crosswhite
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
Thorsten Ottosen
>
> "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...
> 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
Emil Dotchevski
> 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
Christopher Jefferson
On 23 Jan 2011, at 23:59, Emil Dotchevski wrote:
> On Sun, Jan 23, 2011 at 1:01 PM, Thorsten Ottosen <nes...@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
Thorsten Ottosen
> On Sun, Jan 23, 2011 at 1:01 PM, Thorsten Ottosen<nes...@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
Howard Hinnant
> 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
Emil Dotchevski
<howard....@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
Howard Hinnant
> On Sun, Jan 23, 2011 at 4:46 PM, Howard Hinnant
> <howard....@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
Joel Falcou
> 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 ?
Nevin Liber
>
> 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:ne...@eviloverlord.com> (847) 691-1404
Stewart, Robert
>
> 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....@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.
Stewart, Robert
> On 24 January 2011 11:41, Stewart, Robert
> <Robert....@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.
>
> maximum size.
That was my point.
Domagoj Saric
"Emil Dotchevski" <emildot...@gmail.com> wrote in message
news:AANLkTinASY3YpYfbXHFhjT44gtO2_1Zs=-nJTo...@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
Domagoj Saric
> On Sat, Jan 22, 2011 at 11:13 PM, Stephan T. Lavavej
> <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.
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
Domagoj Saric
> 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
Domagoj Saric
> On Sun, Jan 23, 2011 at 1:01 PM, Thorsten Ottosen <nes...@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
Domagoj Saric
"Christopher Jefferson" <ch...@bubblescope.net> wrote in message
news:C656C64C-8E00-4D67...@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
Domagoj Saric
"Nevin Liber" <ne...@eviloverlord.com> wrote in message
news:AANLkTimWurT4NnfN4yE10...@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
Thorsten Ottosen
>>>> 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
Christopher Jefferson
On 25 Jan 2011, at 23:19, Domagoj Saric wrote:
>
> "Christopher Jefferson" <ch...@bubblescope.net> wrote in message news:C656C64C-8E00-4D67...@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
Domagoj Saric
> 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
Domagoj Saric
>
> On 25 Jan 2011, at 23:19, Domagoj Saric wrote:
>
>>
>> "Christopher Jefferson" <ch...@bubblescope.net> wrote in message
>> news:C656C64C-8E00-4D67...@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
Thorsten Ottosen
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