[boost] Interest in StaticVector - fixed capacity vector
Andrew Hundt
> I've implemented a small companion class to boost.array that functions
> like a stack allocated vector with fixed capacity. The motivation for this
> class came when I was using boost.array in an interprocess library, when I
> realized that I actually desired an adjustable size boost.array, without the
> complexity of the vector class in the interprocess library. The result is
> StaticVector, which is boost.array directly modified with a size in front of
> the array, and added facilities to match std::vector.
>
> The Implementation is available at:
> https://github.com/ahundt/Boost.StaticVector
>
> Sample Code:
> StaticVector<std::size_t,3> three;
> three.push_back(5);
> three.push_back(2); // size: 2 capacity: 3
> three.push_back(3);
>
> three.push_back(1); // throws std::out_of_range exception indicating the
> capacity has been exceeded
>
> So here is the big question:
> Is there any interest in the class?
>
> Cheers!
> Andrew Hundt
>
>
On Mon, Aug 15, 2011 at 5:20 PM, Nevin Liber <ne...@eviloverlord.com> wrote:
> On 15 August 2011 16:05, Andrew Hundt <ath...@gmail.com> wrote:
>
> > Good point. I've modified elems to be a char array, and I now
> > reinterpret_cast to the class T as necessary. Elements should only be
> > constructed when they are added now.
> >
>
> What are you doing about alignment? Take a look at Synyhesizing Types with
> Specific Alignments in the Type Traits library for a start.
> --
> Nevin ":-)" Liber <mailto:ne...@eviloverlord.com> (847) 691-1404
>
Phil Endecott wrote:
> In the case of StativVector<char,N> where N<256, you should consider using
> uint8_t to store the size - and similar variations. Boost.Integer makes it
> possible to select a suitable type.
Sorry for the duplicate email, but my other email seemed to get lost in the
shuffle. I know its been a while since I sent my first emails regarding
StaticVector, but I have fixed some of the issues others pointed out.
- I added a benchmark based on a move benchmark found on C++Next, that shows
StaticVector outperforming vector by about 30%, which seems reasonable since
there is no dynamic allocation.
- I believe I've resolved the StaticVector alignment using type_traits'
aligned_storage, as suggested by Nevin Liber.
- I've also added the use of Boost.Integer to select the smallest possible
type to track the size of the vector given its capacity, as suggested by
Phil Endecott.
The Implementation is available at:
https://github.com/ahundt/Boost.StaticVector
Anyone still have additional thoughts or interest in this?
Cheers!
Andrew Hundt
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Peter Myerscough-Jackopson
>
> On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <athundt <at> gmail.com> wrote:
>
<snip>
> > three.push_back(2); // size: 2 capacity: 3
> > three.push_back(3);
> >
> > three.push_back(1); // throws std::out_of_range exception indicating the
> > capacity has been exceeded
Is there any chance that the error behaviour code be configurable. StaticVector
looks ideal for embedded environments, BUT commonly exceptions are disabled in
such an environment. It would be nice to have asserts instead of exceptions
available in all cases, so that a programmer can check for room on a push_back
prior to calling it. A specific StaticVector macro would suffice for those that
need it.
(There may also need to be changes for the template specialization of <T,0> as
well, with respect to throwing exceptions.)
As an aside the exceptions should/could be thrown using the
BOOST_THROW_EXCEPTION macro, to support the other boost specific exception
behaviour support. (At least it is something like that.)
Yours,
Peter
Nigel Stewart
StaticVector
> looks ideal for embedded environments, BUT commonly exceptions are
disabled in
> such an environment.
Yes indeed. That would be desirable, as an option.
- Nigel
Matt Calabrese
> On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <ath...@gmail.com> wrote:
>
> > I've implemented a small companion class to boost.array that functions
> > like a stack allocated vector with fixed capacity. The motivation for
> this
> > class came when I was using boost.array in an interprocess library, when
> I
> > realized that I actually desired an adjustable size boost.array, without
> the
> > complexity of the vector class in the interprocess library. The result is
> > StaticVector, which is boost.array directly modified with a size in front
> of
> > the array, and added facilities to match std::vector.
> >
> > The Implementation is available at:
> > https://github.com/ahundt/Boost.StaticVector
I believe there is interest -- in fact, there's already such a library in
the review queue. It's Thorsten Ottosen's AutoBuffer library.
--
-Matt Calabrese
Jeffrey Lee Hellrung, Jr.
> On Sun, Oct 9, 2011 at 1:59 PM, Andrew Hundt <ath...@gmail.com> wrote:
>
> > On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <ath...@gmail.com> wrote:
> >
> > > I've implemented a small companion class to boost.array that functions
> > > like a stack allocated vector with fixed capacity. The motivation for
> > this
> > > class came when I was using boost.array in an interprocess library,
> when
> > I
> > > realized that I actually desired an adjustable size boost.array,
> without
> > the
> > > complexity of the vector class in the interprocess library. The result
> is
> > > StaticVector, which is boost.array directly modified with a size in
> front
> > of
> > > the array, and added facilities to match std::vector.
> > >
> > > The Implementation is available at:
> > > https://github.com/ahundt/Boost.StaticVector
>
>
> I believe there is interest -- in fact, there's already such a library in
> the review queue. It's Thorsten Ottosen's AutoBuffer library.
>
I had thought that was slightly different. I may be misremembering, but I
had thought StaticVector has a statically-determined maximum size, while
AutoBuffer is something like a variant< StaticVector, std::vector >...
- Jeff
Andrew Hundt
> > I believe there is interest -- in fact, there's already such a library in
> > the review queue. It's Thorsten Ottosen's AutoBuffer library.
> >
>
>
the in-object allocation I use. While I'm trying to maintain the simplicity
of boost.array with size tracking, that may not be others' goal. I would be
happy to try adding the allocation style of StaticVector as an additional
allocator in AutoBuffer. Unfortunately, I am not sure how I could add the
functionality I'm looking for to AutoBuffer myself. Is there a resource I
could use to learn what I need to allocate the memory block inside the
AutoBuffer object itself without pointers to externally allocated memory? It
would be greatly appreciated.
> I had thought that was slightly different. I may be misremembering, but I
> had thought StaticVector has a statically-determined maximum size, while
> AutoBuffer is something like a variant< StaticVector, std::vector >...
I happen to be using it in an embedded environment myself, but I can use
exceptions. Is there some good example code somewhere that I can use as a
style guide for implementing a no exceptions option?
Cheers!
Andrew Hundt
Marshall Clow
> Andrew Hundt <athundt <at> gmail.com> writes:
>
>>
>> On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <athundt <at> gmail.com> wrote:
>>
> <snip>
>>> three.push_back(2); // size: 2 capacity: 3
>>> three.push_back(3);
>>>
>>> three.push_back(1); // throws std::out_of_range exception indicating the
>>> capacity has been exceeded
>
> Is there any chance that the error behaviour code be configurable. StaticVector
> looks ideal for embedded environments, BUT commonly exceptions are disabled in
> such an environment. It would be nice to have asserts instead of exceptions
> available in all cases, so that a programmer can check for room on a push_back
> prior to calling it. A specific StaticVector macro would suffice for those that
> need it.
IMHO, That's the whole point of using BOOST_THROW_EXCEPTION(x) instead of a naked "throw x"
If exceptions are disabled, then BOOST_THROW_EXCEPTION just calls exit().
-- Marshall
Marshall Clow Idio Software <mailto:mclow...@gmail.com>
A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
-- Yu Suzuki
Andrew Hundt
StaticVector and AutoBuffer are similar, each has different goals:
*
StaticVector goal:*
A subset of std::vector that closely matches Boost.Array with additional
size tracking, with a fixed capacity defined at compile time.
*AutoBuffer goal:*
A superset of std::vector with a higher performance stack based buffer
that falls back on dynamic allocation when that stack is exhausted.
I have found several cases where AutoBuffer fails to meet the goals tackled
by StaticVector:
1) Memory Size - AutoBuffer cannot handle large 64 bit sizes right now,
although this simple to fix.
2) Object Size - AutoBuffer stores a size, capacity, and a pointer to itself
(or an allocated buffer) making the object size significantly greater for
small buffers. In the smallest reasonable case of an AutoBuffer containing 2
chars, the size would be around 19 bytes, compared to around 3 bytes for
StaticVector. However, I may be counting incorrectly depending on factors
such as alignment.
3) Performance - I expect StaticVector to be at least slightly faster. This
is because StaticVector does not have to determine if data is on the stack
or the heap, and there is one fewer pointer dereference.
4) Allocation - I personally have a specific requirement where I have to
place objects in exactly the right location in memory to work with a legacy
interprocess allocator. This makes the Allocators currently in AutoBuffer an
unacceptable option. I could meet this goal using AutoBuffer with an
allocator that simply throws an exception (bad_alloc?) or returns an error
any time an allocation is attempted, but why have this overhead when it
isn't necessary?
StaticVector has clear limitations due to its fixed capacity. However,
StaticVector seems to target a specific set of goals that are exclusive to
the current implementation of AutoBuffer. While some goals can be worked
around within AutoBuffer, others cannot because the end goal of AutoBuffer
differs from the end goal of StaticVector. Does this seem like a fair
assessment?
*
*
Cheers!
Andrew Hundt
Andrew Hundt
>
> > Is there any chance that the error behaviour code be configurable.
> StaticVector
> > looks ideal for embedded environments, BUT commonly exceptions are
> disabled in
> > such an environment. It would be nice to have asserts instead of
> exceptions
> > available in all cases, so that a programmer can check for room on a
> push_back
> > prior to calling it. A specific StaticVector macro would suffice for
> those that
> > need it.
>
> IMHO, That's the whole point of using BOOST_THROW_EXCEPTION(x) instead of a
> naked "throw x"
>
> If exceptions are disabled, then BOOST_THROW_EXCEPTION just calls exit().
>
> -- Marshall
>
> Marshall Clow Idio Software <mailto:mclow...@gmail.com>
>
>
can now be built with exceptions disabled.
Cheers!
Andrew Hundt
Matt Calabrese
> After looking through AutoBuffer carefully, I have determined that while
> StaticVector and AutoBuffer are similar, each has different goals:
Sorry, you're correct. I mis-remembered.
--
-Matt Calabrese
Peter Myerscough-Jackopson
BOOST_THROW_EXCEPTION can be set to call a user defined function
boost_throw_exception, I am unaware of BOOST_THROW_EXCEPTION calling
exit(). The real issue is that even setting BOOST_NO_EXCEPTION and
BOOST_EXCEPTION_DISABLE, the user of a library is still required to
defined the boost_throw_exception function EVEN if the user checks that
calls are valid, i.e. the user performs their own capacitycheck and
rangecheck prior to calling. This means that you cannot compile up a
library including StaticVector without exceptions without defining
boost_throw_exception, even though because you check conditions prior to
calling functions. This pollutes the library unnecessarily, and means
users of a library that uses StaticVector have to provide a function
that is not used (boost_throw_exception) or that if they have defined it
for their own needs then it is somewhat concerning that an imported
library may appear to want to call it. Both of these are bad, and the
same issue exists inside boost::function. To resolve this it would be
useful to have an extension to the interface in some form to allow a
pushing and popping action to occur without a range/capacity check
function that can throw, but I would like to propose that an assert is
called instead. To maintain safety the checking functions could return
success/failure, and the calling functions maintain the object's state
invariants based upon the return code.
Alternatively the push/pop functions could also return bool signifying
success/failure.
In looking at this I also note that there is a StaticVector( Iter begin,
Iter end ) that calls capacitycheck(). This then potentially throws, is
this truly desirable in a constructor? I see in a number of places where
the StaticVector is essentially copying from another unknown storage
class that could be larger than the StatcVector that it also could
throw, did you consider merely copying all that could be copied? i.e.
the first N objects are copied. I can't think if that would be better or
worse? It would certainly circumvent the need for checking/throwing in
some places.
Yours,
Peter
Ps. As an aside the capacity check function could be static.
Andrew Hundt
>
> BOOST_THROW_EXCEPTION can be set to call a user defined function
> boost_throw_exception, I am unaware of BOOST_THROW_EXCEPTION calling
> exit(). The real issue is that even setting BOOST_NO_EXCEPTION and
> BOOST_EXCEPTION_DISABLE, the user of a library is still required to
> defined the boost_throw_exception function EVEN if the user checks that
> calls are valid, i.e. the user performs their own capacitycheck and
> rangecheck prior to calling.
I can understand the desire to reduce the constant calls to capacitycheck, I
need to give this some thought. This seems like a design choices that is
common enough to have a convention. Is anyone aware of one?
> This means that you cannot compile up a
> library including StaticVector without exceptions without defining
> boost_throw_exception, even though because you check conditions prior to
> calling functions. This pollutes the library unnecessarily, and means
> users of a library that uses StaticVector have to provide a function
> that is not used (boost_throw_exception) or that if they have defined it
> for their own needs then it is somewhat concerning that an imported
> library may appear to want to call it. Both of these are bad, and the
> same issue exists inside boost::function.
Calls to boost::throw_exception also exists in boost.array. I'm not sure
defining boost::throw_exception is an overly onerous requirement for when
exceptions are disabled, and it seems to be a somewhat widely used
convention within boost.
> To resolve this it would be
> useful to have an extension to the interface in some form to allow a
> pushing and popping action to occur without a range/capacity check
> function that can throw, but I would like to propose that an assert is
> called instead.
Since my goal is to provide a mix of the functionality in boost.array and
std::vector, I have matched their interface whenever possible. I don't find
it unreasonable to call BOOST_THROW_EXCEPTION, because it is done in
boost.array. Actually, they call boost::throw_exception, but my
understanding is that the end effect is comparable.
> To maintain safety the checking functions could return
> success/failure, and the calling functions maintain the object's state
> invariants based upon the return code.
>
> Alternatively the push/pop functions could also return bool signifying
> success/failure.
>
The definition of push_back for std::vector is:
void push_back ( const T& x );
which is why I chose to go with the same interface.
>
> In looking at this I also note that there is a StaticVector( Iter begin,
> Iter end ) that calls capacitycheck(). This then potentially throws, is
> this truly desirable in a constructor? I see in a number of places where
> the StaticVector is essentially copying from another unknown storage
> class that could be larger than the StatcVector that it also could
> throw, did you consider merely copying all that could be copied? i.e.
> the first N objects are copied. I can't think if that would be better or
> worse?
Am I correct that insert(pos,first,last) can achieve that purpose? Nasty,
difficult to find bugs would occur if someone makes an error and only the
first N objects are copied silently when they expect all objects to be
copied. Scott Meyers' wonderful Effective C++ third edition, Item 18 "make
interfaces easy to use correctly and hard to use incorrectly" provides a
good explanation of this type of choice.
> Ps. As an aside the capacity check function could be static.
>
>
You are correct, capacitycheck should be static. Thanks for finding that.
Thanks for the time and consideration you have given the implementation.
Cheers!
Andrew Hundt
Emil Dotchevski
<peter.myersco...@macltd.com> wrote:
>>-----Original Message-----
> BOOST_THROW_EXCEPTION can be set to call a user defined function
> boost_throw_exception, I am unaware of BOOST_THROW_EXCEPTION calling
> exit().
BOOST_THROW_EXCEPTION should not be messed with, it is not designed to
be a customization point.
By design, (Boost) libraries use BOOST_THROW_EXCEPTION to enforce
postconditions. The only way to avoid throwing an exception in such
cases is to #define BOOST_NO_EXCEPTIONS and provide a user-defined
boost::throw_exception, which is not allowed to return.
Emil Dotchevski
Reverge Studios, Inc.
http://www.revergestudios.com/reblog/index.php?n=ReCode
Eelis van der Weegen
> Anyone still have additional thoughts or interest in this?
I think this type of container is very useful, and would love to see one
in Boost. Should you decide to submit your library for review, I will
definitely review it. :)
Eelis
Andrew Hundt
> On 2011-10-09 19:59, Andrew Hundt wrote:
>
>> Anyone still have additional thoughts or interest in this?
>>
>
> I think this type of container is very useful, and would love to see one in
> Boost. Should you decide to submit your library for review, I will
> definitely review it. :)
>
> Eelis
>
>
Great, thank you! I'm looking at the submission process page at:
http://www.boost.org/development/submissions.html
It appears I am currently at the "determine interest" stage. What must I do
to make a preliminary submission?
Cheers!
Andrew Hundt
Stewart, Robert
>
> I'm looking at the submission process page at:
>
> http://www.boost.org/development/submissions.html
>
> It appears I am currently at the "determine interest" stage.
> What must I do to make a preliminary submission?
You've already done that since you've made code available. You're really moving into the Refinement step now.
_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
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.
Christian Holmquist
> On Tue, Oct 11, 2011 at 12:41 PM, Eelis van der Weegen <ee...@eelis.net
> >wrote:
>
> > On 2011-10-09 19:59, Andrew Hundt wrote:
> >
> >> Anyone still have additional thoughts or interest in this?
> >>
> >
> > I think this type of container is very useful, and would love to see one
> in
> > Boost. Should you decide to submit your library for review, I will
> > definitely review it. :)
> >
> > Eelis
> >
> >
> Great, thank you! I'm looking at the submission process page at:
>
>
I second that. I've been using boost::array<> with a sentinel value to
indicate end, which is both ugly and requires length to be 1 longer than
needed.
boost::container::static_vector seems like a good addition, maybe it can be
reviewed for inclusion in upcoming Boost.Container.
FWIW, I think that static_vector should throw std::bad_alloc if it runs out
of space, to mimic an out of memory situation for ordinary containers.
(Consider an algorithm that needs temporary storage, and user passes a
static_vector as tmp storage policy. The algorithm might be designed to
handle std::bad_alloc in some way).
- Christian
Jeffrey Lee Hellrung, Jr.
<c.hol...@gmail.com>wrote:
> On 11 October 2011 14:41, Andrew Hundt <ath...@gmail.com> wrote:
>
> > On Tue, Oct 11, 2011 at 12:41 PM, Eelis van der Weegen <ee...@eelis.net
> > >wrote:
> >
> > > On 2011-10-09 19:59, Andrew Hundt wrote:
> > >
> > >> Anyone still have additional thoughts or interest in this?
> > >>
> > >
> > > I think this type of container is very useful, and would love to see
> one
> > in
> > > Boost. Should you decide to submit your library for review, I will
> > > definitely review it. :)
> > >
> > > Eelis
> > >
> > >
> > Great, thank you! I'm looking at the submission process page at:
> >
> >
> I second that. I've been using boost::array<> with a sentinel value to
> indicate end, which is both ugly and requires length to be 1 longer than
> needed.
> boost::container::static_vector seems like a good addition, maybe it can be
> reviewed for inclusion in upcoming Boost.Container.
>
> FWIW, I think that static_vector should throw std::bad_alloc if it runs out
> of space, to mimic an out of memory situation for ordinary containers.
> (Consider an algorithm that needs temporary storage, and user passes a
> static_vector as tmp storage policy. The algorithm might be designed to
> handle std::bad_alloc in some way).
>
I'm presently against any throwing behavior related to resizing of a
StaticVector/static_vector, since one can usually easily check the relevant
preconditions themselves. Just assert. For those who want defined behavior
in resize overflow (or underflow) situations, I'd say derive or wrap. Some
kind of policy template parameter could be possible, but right now it feels
like that's an unnecessary complication on an otherwise relatively simple
data structure.
That's not to say I can't be dissuaded from this opinion.
- Jeff
Marshall Clow
If you are checking all the preconditions yourself, why do you care if it throws or not?
[ That sounds glib - but it's a serious question. ]
Why do you care if it ASSERTs, calls abort (), throws, or gets your cat pregnant?
-- Marshall
Marshall Clow Idio Software <mailto:mclow...@gmail.com>
A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
-- Yu Suzuki
Matt Calabrese
jeffrey....@gmail.com> wrote:
> I'm presently against any throwing behavior related to resizing of a
> StaticVector/static_vector, since one can usually easily check the relevant
> preconditions themselves. Just assert. For those who want defined
> behavior
> in resize overflow (or underflow) situations, I'd say derive or wrap. Some
> kind of policy template parameter could be possible, but right now it feels
> like that's an unnecessary complication on an otherwise relatively simple
> data structure.
>
> That's not to say I can't be dissuaded from this opinion.
My stance is that push_back, for instance, should throw if it goes beyond
capacity. This is primarily for consistency with other containers. I would
say, if it proves useful, to have a non-throwing version by a different name
in addition to push_back that has undefined behavior when going beyond the
capacity. This would be similar to how vectors have both the operator []
overload and the "at" member function.
--
-Matt Calabrese
Christian Holmquist
jeffrey....@gmail.com> wrote:
It's not always you know that you're dealing with a static_vector, but just
some code that expects push_back() to work or throw.
> in resize overflow (or underflow) situations, I'd say derive or wrap. Some
> kind of policy template parameter could be possible, but right now it feels
> like that's an unnecessary complication on an otherwise relatively simple
> data structure.
>
A lot of things get simplified when ignoring correctness.
- Christian
Nathan Ridge
> If you are checking all the preconditions yourself, why do you care if it throws or not?
> [ That sounds glib - but it's a serious question. ]
>
> Why do you care if it ASSERTs, calls abort (), throws, or gets your cat pregnant?
You care because if it throws, it is incurring the runtime cost of checking
whether the precondition has been met. If you also check the precondition
yourself, then this runtime cost is being incurred twice, for no reason.
The design choice between throwing and undefined behaviour (in release
builds, where asserts become no-ops) boils down to the choice of who
should check the precondition: the callee, or the caller. Tradition has
favoured the caller checking the precondition whenever possible, because
the caller has more information and can sometimes check more efficiently
(e.g. by eliding the check altogether in cases where it already knows the
precondition is met). Note that vector::push_back() throwing on out-of-memory
is *not* a counterexample to this - unlike exceeding the capacity of a
StaticVector, running out of memory is not a condition that can be checked
beforehand by the caller.
Regards,
Nate
Nevin Liber
>
>> If you are checking all the preconditions yourself, why do you care if it throws or not?
>> [ That sounds glib - but it's a serious question. ]
>>
>> Why do you care if it ASSERTs, calls abort (), throws, or gets your cat pregnant?
>
> You care because if it throws, it is incurring the runtime cost of checking
> whether the precondition has been met.
So does the assert. The "complication" is there (performance is a
different issue) unless you make it undefined behavior AND ignore it.
> The design choice between throwing and undefined behaviour (in release
> builds, where asserts become no-ops) boils down to the choice of who
> should check the precondition: the callee, or the caller. Tradition has
> favoured the caller checking the precondition whenever possible, because
> the caller has more information and can sometimes check more efficiently
> (e.g. by eliding the check altogether in cases where it already knows the
> precondition is met).
And sometimes is less efficient. For instance, if you are populating
from StaticVector from list iterators (or any non-random access
iterators), it's an O(n) check ahead of time or a complicated wrapper
around a one-at-a-time insert. (Note: this is a bug in the current
implementation of StaticVector, as its iterator constructor currently
requires random access iterators).
> Note that vector::push_back() throwing on out-of-memory
> is *not* a counterexample to this - unlike exceeding the capacity of a
> StaticVector, running out of memory is not a condition that can be checked
> beforehand by the caller.
Sure it is. You can duplicate the functionality of exponential growth
by calling size(), capacity() and reserve() before doing push_back().
I'd really like to see the interface be as close to C++11 std::vector
as possible (other than vector<bool>).
--
Nevin ":-)" Liber <mailto:ne...@eviloverlord.com> (847) 691-1404
_______________________________________________
Andrew Hundt
<c.hol...@gmail.com>wrote:
> On 11 October 2011 14:41, Andrew Hundt <ath...@gmail.com> wrote:
I'm fairly certain that throwing bad_alloc causes a number of show stopping
problems. For example, one may choose to catch the bad_alloc, then free some
extra memory that is being kept around before trying to call push_back
again. Of course the second push_back would also throw bad_alloc, so nothing
good would be accomplished.
Cheers!
Andrew Hundt
Andrew Hundt
> from StaticVector from list iterators (or any non-random access
> iterators), it's an O(n) check ahead of time or a complicated wrapper
> around a one-at-a-time insert. (Note: this is a bug in the current
> implementation of StaticVector, as its iterator constructor currently
> requires random access iterators).
>
>
>
> I'd really like to see the interface be as close to C++11 std::vector
> as possible (other than vector<bool>).
This is definitely one of my goals.
Perhaps it would be reasonable to add an unchecked_push_back like the one in
AutoBuffer. That way, both those that want and do not want extra checks can
be happy.
I am trying to tackle one bug that I simply haven't been able to understand.
My test program benchStaticVector calls a function that adds some random
std::set<std::size_t> to a StaticVector, then returns it to a local variable
and lets it go out of scope. It seems the destructor is being called on the
return, but for some reason the copy isn't happening correctly. Then, when
the local variable goes out of scope free gets called on uninitialized
memory. Does anyone know what type of problem might be the cause of this?
Perhaps I am missing some should-be-obvious function from my implementation?
Thanks for all the great comments!
Cheers!
Andrew Hundt
Stewart, Robert
>
> boost::container::static_vector seems like a good addition,
> maybe it can be reviewed for inclusion in upcoming
That certainly would be the simplest way to add it to Boost and seems like the right place for it. You just need to see if Ion is interested.
_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
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 11 October 2011 20:01, Nathan Ridge
> <zerat...@hotmail.com> wrote:
>
> >> If you are checking all the preconditions yourself, why do
> >> you care if it throws or not?
> >> [ That sounds glib - but it's a serious question. ]
> >>
> >> Why do you care if it ASSERTs, calls abort (), throws, or
> >> gets your cat pregnant?
> >
> > You care because if it throws, it is incurring the runtime
> > cost of checking whether the precondition has been met.
>
> So does the assert. The "complication" is there (performance
> is a different issue) unless you make it undefined behavior AND
> ignore it.
He did call out the runtime cost, so he was addressing performance which you set aside.
> > The design choice between throwing and undefined behaviour
> > (in release builds, where asserts become no-ops) boils down
> > to the choice of who should check the precondition: the
> > callee, or the caller. Tradition has favoured the caller
> > checking the precondition whenever possible, because the
> > caller has more information and can sometimes check more
> > efficiently (e.g. by eliding the check altogether in cases
> > where it already knows the precondition is met).
>
> And sometimes is less efficient. For instance, if you are
> populating from StaticVector from list iterators (or any
> non-random access iterators), it's an O(n) check ahead of time
> or a complicated wrapper around a one-at-a-time insert.
That can be handled by dispatching on iterator category. When the iterators are random access, computing the input range size is O(1), so the insert can be as efficient as possible. Otherwise, a checking copy operation can be used.
Generally, making it undefined behavior when exceeding capacity is the more efficient approach. One can always wrap such a class to create one that checks. The reverse is not true.
> > Note that vector::push_back() throwing on out-of-memory
> > is *not* a counterexample to this - unlike exceeding the
> > capacity of a StaticVector, running out of memory is not a
> > condition that can be checked beforehand by the caller.
>
> Sure it is. You can duplicate the functionality of exponential
> growth by calling size(), capacity() and reserve() before doing
> push_back().
This really comes down to whether static_vector is considered something more akin to std::array or std::vector.
> I'd really like to see the interface be as close to C++11
> std::vector as possible (other than vector<bool>).
Interface is one thing. That doesn't address the idea of throwing exceptions when exceeding capacity. Many wanting to use static_vector in embedded environments don't want exceptions. The rest of us find them useful. Still, BOOST_THROW_EXCEPTION provides a means to configure that, but it affects all Boost code; localizing the effect may be desirable. Matt called for a differently named container as a means to provide the no-exception behavior. I think a policy class, defaulted to the throwing behavior, is the better approach, despite Jeff's thinking it an unnecessary complication.
_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
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.
_______________________________________________
Olaf van der Spek
<Robert....@sig.com> wrote:
>> I'd really like to see the interface be as close to C++11
>> std::vector as possible (other than vector<bool>).
>
> Interface is one thing. That doesn't address the idea of throwing exceptions when exceeding capacity. Many wanting to use static_vector in embedded environments don't want exceptions. The rest of us find them useful. Still, BOOST_THROW_EXCEPTION provides a means to configure that, but it affects all Boost code; localizing the effect may be desirable. Matt called for a differently named container as a means to provide the no-exception behavior. I think a policy class, defaulted to the throwing behavior, is the better approach, despite Jeff's thinking it an unnecessary complication.
Is it a logic error or a runtime error? IMO exceeding the capacity
here is a logic error and should be handled with an assert by default.
Isn't it comparable to doing a pop_back() on an empty vector?
Olaf
Stewart, Robert
> On Wed, Oct 12, 2011 at 12:38 PM, Stewart, Robert
> <Robert....@sig.com> wrote:
> >> I'd really like to see the interface be as close to C++11
> >> std::vector as possible (other than vector<bool>).
> >
> > Interface is one thing. That doesn't address the idea of
> > throwing exceptions when exceeding capacity. Many wanting to
> > use static_vector in embedded environments don't want
> > exceptions. The rest of us find them useful. Still,
> > BOOST_THROW_EXCEPTION provides a means to configure that, but
> > it affects all Boost code; localizing the effect may be
> > desirable. Matt called for a differently named container as
> > a means to provide the no-exception behavior. I think a
> > policy class, defaulted to the throwing behavior, is the
> > better approach, despite Jeff's thinking it an unnecessary
> > complication.
>
> Is it a logic error or a runtime error? IMO exceeding the
> capacity here is a logic error and should be handled with an
> assert by default.
> Isn't it comparable to doing a pop_back() on an empty vector?
It depends upon whether static_vector is modeled like std::vector or std::array and whether we're referring to the subscript operator or push_back(). For the subscript operator, it's a logic error in both std::vector and std::array. For push_back, it's a runtime error (std::bad_alloc) because a vector grows. std::array doesn't have push_back(), of course, but static_vector manages size and capacity separately, so it will. Therefore, it isn't a logic error if you follow std::vector's example.
_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
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.
_______________________________________________
Matt Calabrese
> Matt called for a differently named container as a means to provide the
> no-exception behavior. I think a policy class, defaulted to the throwing
> behavior, is the better approach, despite Jeff's thinking it an unnecessary
> complication.
>
To be clear, I wasn't suggesting two containers, I was suggesting a single
container with something like "push_back" and "unchecked_push_back", similar
to how std::vector has both operator[] and "at" member functions. I don't
think we have to (or even should) make a decision one-way or the other for
the entire type, just like vector doesn't make that decision about
bounds-checking for a given instantiation. Let the user decide on a
case-by-case basis via the member function that they call since it's a
fine-grained trade-off that doesn't have to be made by the type. I'm not
sure how many people share the following view, but I am personally grateful
that the STL does not have two templates "vector" and
"bounds_checked_vector" or a single template with a policy. It's simply not
necessary since the presence of both operator[] and at() covers the issue.
As for having "push_back" and "unchecked_push_back" rather than "push_back"
and "checked_push_back" -- the former approach avoids introducing additional
preconditions to a very common standard container member function name. One
advantage of this in practice is that it makes it easy for users to do
drop-in replacements of std::vector with boost::static_vector without any
subtle introductions of undefined behavior. Another is that it makes it
easier for readers of the code to know the preconditions of the function
without having to look to see if the type uses a "checked_capacity" policy
when instantiating the template or not. If a user can guarantee that a
push_back or resize will not go beyond capacity, they may then go and use a
separately named function and anyone reading the code will immediately see
that choice at the call-site. Reusing the name push_back but with extra
preconditions makes it more difficult for someone to understand what is
going on from the function name since you then have two different kinds of
push_back.
To be clear, I do agree that in most cases a user would often prefer the
unchecked version (just as how in practice, a user may often be able to use
operator[] rather than at()), I only disagree on the name of that function.
Perhaps unchecked_push_back is a nasty name, but that can be changed.
--
-Matt Calabrese
Olaf van der Spek
> To be clear, I do agree that in most cases a user would often prefer the
> unchecked version (just as how in practice, a user may often be able to use
> operator[] rather than at()), I only disagree on the name of that function.
> Perhaps unchecked_push_back is a nasty name, but that can be changed.
What about algorithms that call push_back, like back_inserter?
Will you provide them as well?
Olaf
Andrew Hundt
> Will you provide them as well?
>
> Olaf
I think back_inserter should work until you reach the capacity.
Cheers!
Andrew Hundt
Nathan Ridge
> >> If you are checking all the preconditions yourself, why do you care if it throws or not?
> >> [ That sounds glib - but it's a serious question. ]
> >>
> >> Why do you care if it ASSERTs, calls abort (), throws, or gets your cat pregnant?
> >
> > You care because if it throws, it is incurring the runtime cost of checking
> > whether the precondition has been met.
>
> So does the assert. The "complication" is there (performance is a
> different issue) unless you make it undefined behavior AND ignore it.
An assert does not incur a runtime cost in release builds. It's just a tool
to help catch programming mistakes in debug builds. From an interface
perspective, it's just as if the function assumes the precondition is met
and invokes undefined behaviour otherwise.
> > Note that vector::push_back() throwing on out-of-memory
> > is *not* a counterexample to this - unlike exceeding the capacity of a
> > StaticVector, running out of memory is not a condition that can be checked
> > beforehand by the caller.
>
> Sure it is. You can duplicate the functionality of exponential growth
> by calling size(), capacity() and reserve() before doing push_back().
Fine, "condition that can be checked beforehand by the caller" is not a
sufficiently precise criterion for what should throw and what should assert.
A more precise criterion is to assert when failing to meet a precondition is
a programming/logic error, and throw when it's something beyond the
programmer's control. (Hacks aside, that usually corresponds to conditions
that can be checked beforehand by the caller, and ones that cannot, but this
more precise criterion captures the essence better.)
My point is, exceeding a capacity bound known at compile time clearly falls
into the former category, while running out of memory falls into the latter.
Regards,
Nate
Nathan Ridge
> > I'm presently against any throwing behavior related to resizing of a
> > StaticVector/static_vector, since one can usually easily check the relevant
> > preconditions themselves. Just assert. For those who want defined
> > behavior
> >
> It's not always you know that you're dealing with a static_vector, but just
> some code that expects push_back() to work or throw.
Consider a generic algorithm that takes a "push_back-able" type and inserts
elements into it using push_back(), and expects the push_back() to work to throw.
When you invoke this algorithm, you either know in advance how
many elements it will add, or you don't.
If you do, then when calling this algorithm *with a static_vector*, you need
to check beforehand whether there is enough space in the static_vector.
I think that's a reasonable requirement, given that you know, at the call site,
that you're dealing with a static_vector.
If you don't, then calling the algorithm with a static_vector is a conceptual
error in the first place, because you are passing a container with a fixed
capacity to an algorithm that expects to be able to add a variable number
of elements to it.
Regards,
Nate
Christian Holmquist
I realize the validity of your point, and I don't disagree in general.
But I often look through the eyes of code maintenance for very large
projects, and if
I encounter a line like:
m_Somethings.push_back(...);
I don't consider that a possible source of undefined behaviour.
It's too easy for a maintenance programmer to add another line exactly the
same, without realizing he's broken the preconditions.
If that code would read
m_Somethings.unchecked_push_back(...) it's at least less likely that someone
would add another such line without further investigation.
Either way, some people want an unchecked version and others want a checked
version, both are useful, admittedly.. Question is if we should have
1) push_back() & unchecked_push_back()
or
2) push_back() & checked_push_back().
- christian
Howard Hinnant
> On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <ath...@gmail.com> wrote:
>
>> I've implemented a small companion class to boost.array that functions
>> like a stack allocated vector with fixed capacity. The motivation for this
>> class came when I was using boost.array in an interprocess library, when I
>> realized that I actually desired an adjustable size boost.array, without the
>> complexity of the vector class in the interprocess library. The result is
>> StaticVector, which is boost.array directly modified with a size in front of
>> the array, and added facilities to match std::vector.
>>
>> The Implementation is available at:
>> https://github.com/ahundt/Boost.StaticVector
>>
>> Sample Code:
>> StaticVector<std::size_t,3> three;
>> three.push_back(5);
>> three.push_back(2); // size: 2 capacity: 3
>> three.push_back(3);
>>
>> three.push_back(1); // throws std::out_of_range exception indicating the
>> capacity has been exceeded
>>
>> So here is the big question:
>> Is there any interest in the class?
>>
>> Cheers!
>> Andrew Hundt
>
Fwiw, one can create allocators that allocate off the stack and then turn any container into a static_container. Here's an example vector, list and set: http://home.roadrunner.com/~hinnant/stack_alloc.html
This particular implementation will spill to heap if the static buffer is overrun. But you could easily build another allocator that had another behavior. Just doing an allocator and res-using existing allocator-aware containers (e.g. std::vector) seems like a win to me.
Howard
Andrew Hundt
>
> 1) push_back() & unchecked_push_back()
> or
> 2) push_back() & checked_push_back().
If it was between 1 and 2, I would still find option (1) to be the best,
because it keeps things closer to std::vector. However, one alternative
would be to choose another name for the unchecked version. Its not like
vec.at() or vec[N] really say much about how they check things. Even so, the
lack of naming expressiveness in one function hardly justifies keeping
others cryptic. Nonetheless, perhaps there are other options that work:
3) push_back() & put_back()
4) push_back() & set_back()
I like option 3 much better than 4, since set is already so heavily used,
and better than 2 for the reasons above. I'm undecided between 1 and 3.
Cheers!
Andrew Hundt
Stephan T. Lavavej
> Fwiw, one can create allocators that allocate off the stack and then turn any container into a static_container.
> Here's an example vector, list and set: http://home.roadrunner.com/~hinnant/stack_alloc.html
> This particular implementation will spill to heap if the static buffer is overrun. But you could easily build
> another allocator that had another behavior. Just doing an allocator and res-using existing allocator-aware
> containers (e.g. std::vector) seems like a win to me.
C++03 forbids "internal storage" allocators (when an allocator returns memory from "inside itself").
C++03 20.1.5 [lib.allocator.requirements]'s tables say (they don't copy/paste well, so I have to type them in by hand - these are only the relevant portions):
Variable # Definition
T, U # any type
X # an Allocator class for type T
Y # the corresponding Allocator class for type U
a, a1, a2 # values of type X&
b # a value of type Y
expression # return type # assertion/note pre/post-condition
a1 == a2 # bool # returns true iff storage allocated from each can be deallocated via the other
X a(b); # # post: Y(a) == b
Here's why this rules out "internal storage" allocators.
1. I start with Y b; which is MyAlloc<U> b;
2. I construct X a(b); which is MyAlloc<T> a(b);
3. I construct Y c(a), giving it a name for clarity. That's MyAlloc<U> c(a).
b is the original MyAlloc<U>. c is the doubly-rebound MyAlloc<U>. They're required to compare equal, which means that storage allocated from one can be deallocated from the other and vice versa.
This is possible for stateless allocators (e.g. if you just call malloc/free), or stateful allocators that store things like heap handles (the heap handle is passed along by the rebinding constructor). It is impossible for "internal storage" allocators, because b and c will have separate internal storage.
Also, consider how "internal storage" allocators affect moving and swapping containers.
Taking advantage of C++03's requirements, VC11 contains optimizations that will break "internal storage" allocators, even in the absence of moving/swapping. It avoids storing stateless allocators completely, and stores only one copy of a stateful allocator - rebinding it on the fly whenever it needs to allocate a secret node type, a super secret proxy type, etc. C++03's requirements guarantee that as long as the container keeps at least one copy of a stateful allocator around, regardless of the type that it's for, it can be rebound to any other type and service allocations for that type (i.e. keeping one copy around will keep all allocations around, regardless of their type).
C++03 has no objection to allocators returning memory that happens to live on the stack, as long as it is "separate" from the allocator itself and its lifetime is sufficient.
STL
Andrew Hundt
>
> > The design choice between throwing and undefined behaviour (in release
> > builds, where asserts become no-ops) boils down to the choice of who
> > should check the precondition: the callee, or the caller. Tradition has
> > favoured the caller checking the precondition whenever possible, because
> > the caller has more information and can sometimes check more efficiently
> > (e.g. by eliding the check altogether in cases where it already knows the
> > precondition is met).
>
> And sometimes is less efficient. For instance, if you are populating
> from StaticVector from list iterators (or any non-random access
> iterators), it's an O(n) check ahead of time or a complicated wrapper
> around a one-at-a-time insert. (Note: this is a bug in the current
> implementation of StaticVector, as its iterator constructor currently
> requires random access iterators).
>
>
should separately implement one for boost::single_pass_traversal_tag and
another for boost::random_access_traversal_tag?
I assume I want to simply check the distance between two random access
iterators and return immediately if the size is too big.
Then, if it isn't random access I should just start copying and check if
I've run out of space on each element that is added. Is this correct?
On this topic, what is the difference between
boost::random_access_traversal_tag and std::random_access_iterator_tag, and
should I implement both?
Cheers!
Andrew Hundt
Nathan Ridge
> > And sometimes is less efficient. For instance, if you are populating
> > from StaticVector from list iterators (or any non-random access
> > iterators), it's an O(n) check ahead of time or a complicated wrapper
> > around a one-at-a-time insert. (Note: this is a bug in the current
> > implementation of StaticVector, as its iterator constructor currently
> > requires random access iterators).
> >
> >
> Does this mean that in any of the functions where I have two iterators, I
> should separately implement one for boost::single_pass_traversal_tag and
> another for boost::random_access_traversal_tag?
>
> I assume I want to simply check the distance between two random access
> iterators and return immediately if the size is too big.
> Then, if it isn't random access I should just start copying and check if
> I've run out of space on each element that is added. Is this correct?
Basically, yes. You may also want to have a version for forward iterators -
if you're allowed to traverse the range more than once, then it is usually
more efficient to traverse it once to find out the length, throw (or whatever)
if the length is too big, and otherwise traverse it a second time to actually
insert the elements. (This is not always more efficient - for example, if
your iterators are transform_iterators, and the transformation function
they are calling is expensive, it's not - but I believe several STL
implementations assume it is and do it this way).
> On this topic, what is the difference between
> boost::random_access_traversal_tag and std::random_access_iterator_tag,
Take a look at http://www.boost.org/doc/libs/1_47_0/libs/iterator/doc/new-iter-concepts.html
> and should I implement both?
One or the other, not both. I would image that for Boost libraries, the convention
is to use the Boost concepts, but I'm no authority on this.
Regards,
Nate
Stewart, Robert
>
> > > And sometimes is less efficient. For instance, if you are
> > > populating from StaticVector from list iterators (or any
> > > non-random access iterators), it's an O(n) check ahead of
> > > time or a complicated wrapper around a one-at-a-time
> > > insert. (Note: this is a bug in the current implementation
> > > of StaticVector, as its iterator constructor currently
> > > requires random access iterators).
> > >
> > random access iterators and return immediately if the size is
> > too big. Then, if it isn't random access I should just start
> > copying and check if I've run out of space on each element
> > that is added. Is this correct?
>
> Basically, yes. You may also want to have a version for
> forward iterators - if you're allowed to traverse the range
> more than once, then it is usually more efficient to traverse
> it once to find out the length, throw (or whatever) if the
> length is too big, and otherwise traverse it a second time to
> actually insert the elements. (This is not always more
> efficient - for example, if your iterators are
> transform_iterators, and the transformation function they are
> calling is expensive, it's not - but I believe several STL
> implementations assume it is and do it this way).
Why would you optimize the failure case?
_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
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.
_______________________________________________
Andrew Hundt
>> boost::random_access_traversal_tag and std::random_access_iterator_tag,
>
> Take a look at http://www.boost.org/doc/libs/1_47_0/libs/iterator/doc/new-iter-concepts.html
>
>> and should I implement both?
>
> One or the other, not both. I would image that for Boost libraries, the convention
> is to use the Boost concepts, but I'm no authority on this.
What is the reasoning for not both?
Cheers!
Andrew Hundt
Thijs (M.A.) van den Berg
http://hugoduncan.org/boostable/doc/html/index.html
I can't find any trace in the sandbox... Does anybody know the status of this project?
Andrew Hundt
>> Basically, yes. You may also want to have a version for
>> forward iterators - if you're allowed to traverse the range
>> more than once, then it is usually more efficient to traverse
>> it once to find out the length, throw (or whatever) if the
>> length is too big, and otherwise traverse it a second time to
>> actually insert the elements. (This is not always more
>> efficient - for example, if your iterators are
>> transform_iterators, and the transformation function they are
>> calling is expensive, it's not - but I believe several STL
>> implementations assume it is and do it this way).
>
> Why would you optimize the failure case?
>
I agree that optimizing for the success case is the better choice when
evaluating the length is not O(1). Since StaticVector forces the user
to choose exactly what size it will be at compile time, it can only be
reasonable to assume that they will choose a size that will succeed.
That would make any failure case in which the capacity is exceeded an
extremely exceptional situation which should be evaluated as lazily as
possible. Furthermore, if there is a significant chance that the
capacity will be exceeded, it can be checked by the user before
calling a function in StaticVector. This is similar to the reason why
it is desirable to make an unchecked_push_back style function
available.
Cheers!
Andrew Hundt
Thomas Klimpel
> I found some a references via google about a quadrature project
> (numerical integration).
> http://hugoduncan.org/boostable/doc/html/index.html
>
> I can't find any trace in the sandbox...
How about <https://github.com/boost-vault/Math-Numerics/blob/master/quadrature.tgz>?
> Does anybody know the status of this project?
No idea.
Regards,
Thomas
Dave Abrahams
on Wed Oct 12 2011, Olaf van der Spek <ml-AT-vdspek.org> wrote:
> On Wed, Oct 12, 2011 at 12:38 PM, Stewart, Robert
> <Robert....@sig.com> wrote:
>>> I'd really like to see the interface be as close to C++11
>
>>> std::vector as possible (other than vector<bool>).
>>
>> Interface is one thing. That doesn't address the idea of throwing
>> exceptions when exceeding capacity. Many wanting to use
>> static_vector in embedded environments don't want exceptions. The
>> rest of us find them useful. Still, BOOST_THROW_EXCEPTION provides
>> a means to configure that, but it affects all Boost code; localizing
>> the effect may be desirable. Matt called for a differently named
>> container as a means to provide the no-exception behavior. I think
>> a policy class, defaulted to the throwing behavior, is the better
>> approach, despite Jeff's thinking it an unnecessary complication.
>
> Is it a logic error or a runtime error? IMO exceeding the capacity
> here is a logic error and should be handled with an assert by default.
> Isn't it comparable to doing a pop_back() on an empty vector?
Indeed; I object to handling something that is almost certainly going to
be a programming error with a defined behavior of throwing an exception
(yes, I think std::vector::at is a mistake), for several reasons:
- It limits your ability to detect bugs: once you make the behavior
defined, you don't know whether a programming error has been committed
anymore.
- It responds by unwinding, which can destroy valuable debugging
information
- It does way more than absolutely necessary, which, in a program whose
invariants may be broken, may prevent emergency measures from
completing successfully.
That said, I am not a security guy, and I understand those people who
want to eliminate avoidable, open-ended, undefined behavior whenver
possible. Therefore I think that it might make sense to establish a
BOOST_SEMISECURE mode, and to encourage library authors are
free/encouraged to say something like:
If <some requirement> is not satisfied, the behavior is undefined.
In BOOST_SEMISECURE mode the library will (or may) check <some
requirement> using BOOST_ASSERT.
The point being that
a. We can unambiguously mark some usage as incorrect
b. Those who don't want it don't have to pay for the check
c. The behavior of check failures can be tuned.
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Andrew Hundt
This makes me curious. If logic errors should only be caught with an
assert in the case of defining a specific macro definition, is there
still a case where one should use std::logic_error and family? If not,
does that amount to de facto deprecation?
Nathan Ridge
> > > I assume I want to simply check the distance between two
> > > random access iterators and return immediately if the size is
> > > too big. Then, if it isn't random access I should just start
> > > copying and check if I've run out of space on each element
> > > that is added. Is this correct?
> >
> > Basically, yes. You may also want to have a version for
> > forward iterators - if you're allowed to traverse the range
> > more than once, then it is usually more efficient to traverse
> > it once to find out the length, throw (or whatever) if the
> > length is too big, and otherwise traverse it a second time to
> > actually insert the elements. (This is not always more
> > efficient - for example, if your iterators are
> > transform_iterators, and the transformation function they are
> > calling is expensive, it's not - but I believe several STL
> > implementations assume it is and do it this way).
>
> Why would you optimize the failure case?
On second thought, you probably shouldn't :)
I revisited the STL functions I was referring to that discriminated
between forward iterators and input iterators in this way, and
realized they were the likes of vector::insert(first, last), which
may potentially have to reallocate its storage to be large enough
to store the existing elements plus the new ones. In such a case,
knowing how many elements you have in advance is a big gain,
even if it means iterating through the range a second time,
because otherwise you may end up reallocating multiple times.
For static_vector, doing this really would just be optimizing
the failure case, so it shouldn't be done. Random access iterator
and input iterator versions are sufficient.
Regards,
Nate
Nathan Ridge
> >> On this topic, what is the difference between
> >> boost::random_access_traversal_tag and std::random_access_iterator_tag,
> >
> > Take a look at http://www.boost.org/doc/libs/1_47_0/libs/iterator/doc/new-iter-concepts.html
> >
> >> and should I implement both?
> >
> > One or the other, not both. I would image that for Boost libraries, the convention
> > is to use the Boost concepts, but I'm no authority on this.
>
> What is the reasoning for not both?
Because they're pretty much the same thing.
Your tag dispatching logic will be something like this:
if (boost::iterator_traversal<Iterator>::type is boost::random_access_traversal_tag)
call the random access version
else
call the input iterator version
Of course it won't look like that, the choice will be made at compile time
via template specialization, but that's the logic.
You can also have the logic:
if (std::iterator_traits<Iterator>::iterator_category is std::random_access_iterator_tag)
call the random access version
else
call the input iterator version
But it wouldn't make sense to do something like:
if (boost::iterator_traversal<Iterator>::type is boost::random_access_traversal_tag)
call the random access version
else if (std::iterator_traits<Iterator>::iterator_category is std::random_access_iterator_tag)
call the random access version
else
call the input iterator version
because the first case covers all the random access iterators already.
Hope that makes sense... or maybe I'm misunderstanding what you mean by
"implement both"?
Regards,
Nate
Nathan Ridge
> This makes me curious. If logic errors should only be caught with an
> assert in the case of defining a specific macro definition, is there
> still a case where one should use std::logic_error and family? If not,
> does that amount to de facto deprecation?
Perhaps std::logic_error should be used for errors in the user's logic,
not the programmer's logic?
Regards,
Nate
Thijs (M.A.) van den Berg
> Thijs (M.A.) van den Berg wrote:
>> I found some a references via google about a quadrature project
>> (numerical integration).
>> http://hugoduncan.org/boostable/doc/html/index.html
>>
>> I can't find any trace in the sandbox...
>
> How about <https://github.com/boost-vault/Math-Numerics/blob/master/quadrature.tgz>?
>
>> Does anybody know the status of this project?
>
> No idea.
>
Thanks for the pointer. I've send the author an email, let's see why it's apparently on hold?
Ion Gaztañaga
> Christian Holmquist wrote:
>>
>> boost::container::static_vector seems like a good addition,
>> maybe it can be reviewed for inclusion in upcoming
>> Boost.Containers.
>
> That certainly would be the simplest way to add it to Boost and seems like the right place for it. You just need to see if Ion is interested.
It's interesting but we need some consensus on several issues (If swap
is O(N), should it be provided?, unchecked functions? what to do when
there is no room for more elemnets?) and the implementation should
support movable types and other goodies from boost.Container.
One of the extensions I was thinking for Boost.Container was a fixed
capacity vector, and the solution I planned was reusing
boost::container::vector code, maybe with some extensions supporting a
pseudo-allocator. boost::container:: vector could treat this
pseudo-allocator specially and avoid storing a m_capacity or m_pointer
member to save some words. Then allocate() could implement the policy
(assert, throw, or just ignore).
There are more issues. Do we want to support some kind of StaticVector
compatible with shared memory? then we need to specify pointer and
const_pointer as those define the pointer type stored in iterators...
Anyway, I think that we could implement an approach similar to Howard's
stack_alloc quite easily, and get most benefits with a bit of size overhead.
Ion
Lars Viklund
>
> > Thijs (M.A.) van den Berg wrote:
> >> I found some a references via google about a quadrature project
> >> (numerical integration).
> >> http://hugoduncan.org/boostable/doc/html/index.html
> >>
> >> I can't find any trace in the sandbox...
> >
> > How about <https://github.com/boost-vault/Math-Numerics/blob/master/quadrature.tgz>?
> >
> >> Does anybody know the status of this project?
> >
> > No idea.
> >
>
> Thanks for the pointer. I've send the author an email, let's see why it's apparently on hold?
When posting to the Boost lists (or any mailing list at all), if you
have a new thread of conversation, please send it as a new message to
the list instead of replying to an existing message.
Replying to an existing message will put your new message in the thread
hierarchy of an existing thread instead of top-level.
People like I who read some threads with Mark-Thread-As-Read will never
see it.
--
Lars Viklund | z...@acc.umu.se
Ion Gaztañaga
> C++03 forbids "internal storage" allocators (when an allocator returns memory from "inside itself").
AFAIK, C++11 also requires:
X a(b); Shall not exit via an exception.
post: Y(a) == b, a == X(b)
Best,
Ion
Stephan T. Lavavej
> C++03 forbids "internal storage" allocators (when an allocator returns memory from "inside itself").
[Ion Gaztañaga]
> AFAIK, C++11 also requires:
> X a(b); Shall not exit via an exception.
> post: Y(a) == b, a == X(b)
Yep, thanks for looking that up. I recycled an old mail from my archives where I cited C++03. :->
STL
Andrew Hundt
> It's interesting but we need some consensus on several issues
IMO, here are the most interesting and consensus worthy choices so far
> If swap is O(N), should it be provided?
Yes, I am fairly certain std::array provides a linear swap, and
boost.array definitely provides it, so StaticVector should too.
> unchecked functions?
They should definitely be provided.
> what to do when there is no room for more elements?
After comments by Nate Ridge, Dave Abrahams, and others, I have become
convinced that push_back should be unchecked and exceeding the bounds
should be undefined, with an option to turn on checking.
I haven't been convinced how the option should be defined, though I've
seen several options:
1) locally defined option
2) defined generally for boost
3) combination of 1 and 2, since they are not mutually exclusive
4) policy based.
> and the implementation should support movable
> types and other goodies from boost.Container.
> One of the extensions I was thinking for Boost.Container was a fixed
> capacity vector, and the solution I planned was reusing
> boost::container::vector code, maybe with some extensions supporting a
> pseudo-allocator. boost::container:: vector could treat this
> pseudo-allocator specially and avoid storing a m_capacity or m_pointer
> member to save some words. Then allocate() could implement the policy
> (assert, throw, or just ignore).
>
Interesting. So this stack allocated pseudo-allocator would look and
act (partially) like an allocator, but not fit the definition of one
due to the C++03 and C++11 rules against them.
Is this suggesting that boost::container::vector be directly modified
to support both fixed capacity as well, or just mixing some of the
shared code in?
> There are more issues. Do we want to support some kind of StaticVector
> compatible with shared memory? then we need to specify pointer and
> const_pointer as those define the pointer type stored in iterators...
>
> Anyway, I think that we could implement an approach similar to Howard's
> stack_alloc quite easily, and get most benefits with a bit of size overhead.
so considering the other posts that internal storage allocators are
forbidden, how would this work?
Well that may mark the end of my StaticVector work, but that is how
these things go. At the very least there has been productive
discussion. Although, perhaps the size overhead advantage of
StaticVector would allow room for it considering to the difference it
could make for embedded systems.
Nevin Liber
> After comments by Nate Ridge, Dave Abrahams, and others, I have become
> convinced that push_back should be unchecked and exceeding the bounds
> should be undefined, with an option to turn on checking.
While I really disagree with this (as there are both use cases for it
and, more importantly, it is no longer a drop in replacement for
vector because your push_back will now behave differently), don't just
do it for push_back; do it for all the insert methods as well.
--
Nevin ":-)" Liber <mailto:ne...@eviloverlord.com> (847) 691-1404
Andrew Hundt
> On 13 October 2011 18:08, Andrew Hundt <ath...@gmail.com> wrote:
>> After comments by Nate Ridge, Dave Abrahams, and others, I have become
>> convinced that push_back should be unchecked and exceeding the bounds
>> should be undefined, with an option to turn on checking.
>
>
> While I really disagree with this (as there are both use cases for it
> and, more importantly, it is no longer a drop in replacement for
> vector because your push_back will now behave differently),
While I wish it could be a drop in replacement, I think it would be
unreasonable to throw bad_alloc, since no allocations even happen at
all. Thus, it couldn't be a truly drop in replacement anyway.
Additionally, I found that since the behavior of accessing
vector.begin()-1 is undefined, that makes an undeniably compelling
argument that the correct behavior for accessing StaticVector.end()+1
should also be undefined.
> don't just do it for push_back; do it for all the insert methods as well.
that is the plan
Cheers!
Andrew Hundt
Christian Holmquist
>
> After comments by Nate Ridge, Dave Abrahams, and others, I have become
> convinced that push_back should be unchecked and exceeding the bounds
> should be undefined, with an option to turn on checking.
>
> I haven't been convinced how the option should be defined, though I've
> seen several options:
> 1) locally defined option
> 2) defined generally for boost
>
2) Please no. Global policies like BOOST_NO_THREADS and, as I think this
discussion have shown, BOOST_THROW_EXCEPTION is not fine grained enough.
There seems to be some consensus on the usefulness of undefined behaviour if
exhausting the capacity of the vector, which is fine (even as default if
stated clearly in the docs), as long as user can opt for an alternative that
throws.
> 3) combination of 1 and 2, since they are not mutually exclusive
> 4) policy based.
>
4) seems like the best compromise. (how does 4 differ from 1?).
- Christian
Stewart, Robert
> On Thu, Oct 13, 2011 at 10:36 PM, Nevin Liber
> <ne...@eviloverlord.com> wrote:
> > On 13 October 2011 18:08, Andrew Hundt <ath...@gmail.com>
> wrote:
>
> >> After comments by Nate Ridge, Dave Abrahams, and others, I
> >> have become convinced that push_back should be unchecked
> >> and exceeding the bounds should be undefined, with an option
> >> to turn on checking.
> >
> > While I really disagree with this (as there are both use
> > cases for it and, more importantly, it is no longer a drop in
> > replacement for vector because your push_back will now behave
> > differently),
>
> While I wish it could be a drop in replacement, I think it
> would be unreasonable to throw bad_alloc, since no allocations
> even happen at all. Thus, it couldn't be a truly drop in
> replacement anyway.
That's a weak argument. An exception on exceeding capacity would be a point of consistency. The exception isn't the same in each case, of course, but both could be std::exception derivates, which could still be useful.
> Additionally, I found that since the behavior of accessing
> vector.begin()-1 is undefined, that makes an undeniably
> compelling argument that the correct behavior for accessing
> StaticVector.end()+1 should also be undefined.
*v.end() and v.end() + 1 are undefined, so of course *(v.end() + 1) is undefined. However, that doesn't advance your point. It is always undefined behavior to try to access beyond the size. That has nothing to do with capacity, which is the point under discussion.
I'm not necessarily arguing for an exception on exceeding the capacity. I'm just trying to flag argumentation issues.
_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
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.
_______________________________________________
Ion Gaztañaga
> 2011/10/13 Ion Gaztañaga<igazt...@gmail.com>:
>> It's interesting but we need some consensus on several issues
>
> IMO, here are the most interesting and consensus worthy choices so far
>
>> If swap is O(N), should it be provided?
>
> Yes, I am fairly certain std::array provides a linear swap, and
> boost.array definitely provides it, so StaticVector should too.
>
>> unchecked functions?
>
> They should definitely be provided.
Anyway, IMHO comparing begin()-1 with push_back is not a good example
for me. Programmers know front() has preconditions, but we currently
have no push_back preconditions for push_back, insert, etc. and this can
be a great source of mistakes. A solution could be selecting the
behaviour by pseudo-allocator type options at compile time:
boost::container::vector
< int
, fixed_buffer<int, /*options*/throw_when_capacity_exceeded OR
unchecked_capacity OR ... > >;
> Interesting. So this stack allocated pseudo-allocator would look and
> act (partially) like an allocator, but not fit the definition of one
> due to the C++03 and C++11 rules against them.
It's just to add and extend allocator concept and add support for it in
boost::container::vector. It's a hack, but allows reusing a lot of code.
> Is this suggesting that boost::container::vector be directly modified
> to support both fixed capacity as well, or just mixing some of the
> shared code in?
It's an option.
>
>> There are more issues. Do we want to support some kind of StaticVector
>> compatible with shared memory? then we need to specify pointer and
>> const_pointer as those define the pointer type stored in iterators...
>>
>> Anyway, I think that we could implement an approach similar to Howard's
>> stack_alloc quite easily, and get most benefits with a bit of size overhead.
>
> so considering the other posts that internal storage allocators are
> forbidden, how would this work?
Those are forbidden by the standard, but a concrete implementation can
support extensions, provided it still supports standard allocators. In
this case boost::container::vector (and only this container) can change
its behaviour when some specially marked (pseudo-)allocator is used.
> Well that may mark the end of my StaticVector work, but that is how
> these things go. At the very least there has been productive
> discussion. Although, perhaps the size overhead advantage of
> StaticVector would allow room for it considering to the difference it
> could make for embedded systems.
The pseudo-allocator way is just an idea, I don't know if we can find
much more problems in the way.
Ion
Krzysztof Czainski
> After comments by Nate Ridge, Dave Abrahams, and others, I have become
> convinced that push_back should be unchecked and exceeding the bounds
> should be undefined, with an option to turn on checking.
>
> I haven't been convinced how the option should be defined, though I've
> seen several options:
> 1) locally defined option
> 2) defined generally for boost
> 3) combination of 1 and 2, since they are not mutually exclusive
> 4) policy based.
Hi,
I program for embedded, and I've beed observing this discussion with
interest.
+1 for policy based from me. I can imagine using different policy
StaticVectors in the same app.
Regards,
Kris
Stewart, Robert
>
> I program for embedded, and I've beed observing this
> discussion with interest.
>
> +1 for policy based from me. I can imagine using different
> policy StaticVectors in the same app.
For sake of completeness, I'll note that Ion's idea of using a specially recognized allocator to effect the different behaviors in boost::containers::vector is in this vein. That is, being policy-based doesn't mean it has to be
static_vector
<
class T
, size_t N
, class CapacityExhaustionPolicy
>
_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
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
but we currently have no
> push_back preconditions for push_back, insert, etc. and this can be a great
> source of mistakes.
I agree. And unlike at() vs. operator[], in this case we are moving
enforcement of the class invariants from the class itself the caller,
just to save an "if" check.
I really don't want to see a policy controlling this; rather, have
unchecked_push_back and unchecked_insert for those who need every
ounce of performance at the expense of safety.
--
Nevin ":-)" Liber <mailto:ne...@eviloverlord.com> (847) 691-1404
_______________________________________________
Andrew Hundt
> me. Programmers know front() has preconditions, but we currently have no
> push_back preconditions for push_back, insert, etc. and this can be a great
> source of mistakes. A solution could be selecting the behaviour by
> pseudo-allocator type options at compile time:
>
> boost::container::vector
> < int
> , fixed_buffer<int, /*options*/throw_when_capacity_exceeded OR
> unchecked_capacity OR ... > >;
>
I'm not sure that changing the policy will eliminate mistakes. I bet
that any time unchecked is selected so that push_back is not checked,
a fair number of programmers and others who are unfamiliar,
particularly those doing maintenance, will probably still make that
mistake.
Actually, I think the only way to genuinely avoid that mistake as much
as possible would be to have push_back always be checked, and also
have unchecked_push_back/insert.unchecked_push_back?
I know I'm arguing with own thoughts from yesterday. However,
selecting the 'right design' for this container does mean it has to be
considered both on its own, and in terms of what the other containers
do, because that is how people will expect this one to work.
>
> It's just to add and extend allocator concept and add support for it in
> boost::container::vector. It's a hack, but allows reusing a lot of code.
I'm always a fan of reusing a lot of code. Is it possible to provide
different member functions based on different policies? Specifically,
a fixed size vector definitely requires a full() function. If not, how
to share the code between these implementations may require some extra
thought.
>> Is this suggesting that boost::container::vector be directly modified
>> to support both fixed capacity as well, or just mixing some of the
>> shared code in?
>
> It's an option.
>>
>>> There are more issues. Do we want to support some kind of StaticVector
>>> compatible with shared memory? then we need to specify pointer and
>>> const_pointer as those define the pointer type stored in iterators...
>>>
>>> Anyway, I think that we could implement an approach similar to Howard's
>>> stack_alloc quite easily, and get most benefits with a bit of size
>>> overhead.
>>
Any idea what the size overhead would be, typically?
>> so considering the other posts that internal storage allocators are
>> forbidden, how would this work?
>
> Those are forbidden by the standard, but a concrete implementation can
> support extensions, provided it still supports standard allocators. In this
> case boost::container::vector (and only this container) can change its
> behaviour when some specially marked (pseudo-)allocator is used.
Thanks for the clarification.
>
> The pseudo-allocator way is just an idea, I don't know if we can find much
> more problems in the way.
Is there a reference or something that explains the various costs in
terms of such as object size and code execution of policy based
design? I've used it, but I need to read a bit more to make sure I
have the complete picture.
Side note:
Can anyone think of a better name than unchecked_push_back?
Paul A. Bristow
> From: boost-...@lists.boost.org [mailto:boost-...@lists.boost.org] On Behalf Of Andrew
> Hundt
> Sent: Friday, October 14, 2011 4:07 PM
> To: bo...@lists.boost.org
> Subject: Re: [boost] Interest in StaticVector - fixed capacity vector
> Side note:
> Can anyone think of a better name than unchecked_push_back?
push_back_unchecked ?
Then it will appear in the sensible place in any alphabetical list of functions.
Paul
---
Paul A. Bristow,
Prizet Farmhouse, Kendal LA8 8AB UK
+44 1539 561830 07714330204
pbri...@hetp.u-net.com
Andrew Hundt
> 2011/10/14 Ion Gaztañaga <igazt...@gmail.com>:
> but we currently have no
>> push_back preconditions for push_back, insert, etc. and this can be a great
>> source of mistakes.
>
> I agree. And unlike at() vs. operator[], in this case we are moving
> enforcement of the class invariants from the class itself the caller,
> just to save an "if" check.
That if check can be quite a difference after its called for the
billionth time in an inner loop, though you address this just below.
:-)
> I really don't want to see a policy controlling this; rather, have
> unchecked_push_back and unchecked_insert for those who need every
> ounce of performance at the expense of safety.
I definitely see a lot of clarity in implementing it this way. I just
wish there was a nicer name than unchecked_push_back.
Policies could be both a blessing and a curse. It makes it
extraordinarily easy to switch from checked to unchecked push back in
a large code base without going through everything by hand. You can
test your code with the checked policy, then turn it off to get the
performance. On the other hand, maybe you should be going through all
the code when you want to switch from checked to unchecked to make
sure there are no dependencies on that policy that would become a bug.
Andrew Hundt
<pbri...@hetp.u-net.com> wrote:
> push_back_unchecked ?
>
> Then it will appear in the sensible place in any alphabetical list of functions.
>
I was thinking about that, but from what I've read on the list it
seems people prefer clearer and more correct english in the function
names whenever possible.
The one I keep coming across is:
put_back()
Does that currently imply anything I'm not thinking of? It seems like
something someone would look up if they haven't seen it, then use it
correctly. It does not directly imply unchecked, but it does seem
appropriate.
Cheers!
Andrew Hundt
Krzysztof Czainski
> +1 for policy based from me. I can imagine using different
> policy StaticVectors in the same app.
Andrew Hundt:
> > Side note:
> > Can anyone think of a better name than unchecked_push_back?
>
2011/10/14 Paul A. Bristow <pbri...@hetp.u-net.com>:
> push_back_unchecked ?
>
> Then it will appear in the sensible place in any alphabetical list of
> functions.
>
I think having both checked, and unchecked versions is a good idea. I prefer
the name push_back_unchecked for the same reason, as Andrew.
However, I'd still like to have the option of choosing a policy for the
"ckecked" versions, so I can pass different StaticVectors to the same
algorithm in different contexts: a checking-one-way version of StaticVector,
or a checking-another-way version, or maybe a not-checking version. This
maybe sounds dangerous, but I would like that to be possible.
Regards
Kris
Dave Abrahams
on Thu Oct 13 2011, Nevin Liber <nevin-AT-eviloverlord.com> wrote:
> On 13 October 2011 18:08, Andrew Hundt <ath...@gmail.com> wrote:
>> After comments by Nate Ridge, Dave Abrahams, and others, I have become
>> convinced that push_back should be unchecked and exceeding the bounds
>> should be undefined, with an option to turn on checking.
>
> While I really disagree with this (as there are both use cases for it
Use-cases, please!
Let's not overlook anything important in this discussion.
> and, more importantly, it is no longer a drop in replacement for
> vector because your push_back will now behave differently),
How could it ever be a "drop-in replacement for vector" when it comes to
exceeding a reasonably low length bound? A vector is probably going to
succeed to push_back past that bound, while this class definitely won't.
Unless you plan to intentionally leverage this exception (in which case
vector wasn't serving your needs, so your code needs more than a
"drop-in-replacement" anyway), then it's *going* to change the behavior
of your program if and when you cause it to be thrown.
Maybe I'm missing something.
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Dave Abrahams
From my point of view, they've always been deprecated ;-)
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Krzysztof Czainski
> 2011/10/14 Paul A. Bristow <pbri...@hetp.u-net.com>:
>
>> push_back_unchecked ?
>>
>> Then it will appear in the sensible place in any alphabetical list of
>> functions.
>>
>
> I think having both checked, and unchecked versions is a good idea. I
> prefer the name push_back_unchecked for the same reason, as Andrew.
>
* sorry, Paul, not Andrew ;-)
Nathan Ridge
> I was thinking about that, but from what I've read on the list it
> seems people prefer clearer and more correct english in the function
> names whenever possible.
>
> The one I keep coming across is:
> put_back()
>
> Does that currently imply anything I'm not thinking of? It seems like
> something someone would look up if they haven't seen it, then use it
> correctly. It does not directly imply unchecked, but it does seem
> appropriate.
The names put_back() vs. push_back() suggest absolutely nothing about
how these functions might be different. I'd much prefer a name that's
descriptive, like unchecked_push_back, even if it's longer and clumsier.
It seems the main options that have been proposed are:
* push_back and unchecked_push_back
* checked_push_back and push_back
* just push_back, with behaviour controlled by a policy
This might be overkill, but we can make everyone happy by
having all three:
* unchecked_push_back which does what it says; AND
* checked_push_back which does what it says; AND
* push_back which calls one or the other based on a policy
That leaves just one thing to quibble about - the default value of the
policy - but even that choice becomes less important, because those
who feel strongly about the default behaviour of push_back being
one or the other can just use the explicitly-named version instead.
Regards,
Nate
Andrew Hundt
> * checked_push_back which does what it says; AND
> * push_back which calls one or the other based on a policy
>
> That leaves just one thing to quibble about - the default value of the
> policy - but even that choice becomes less important, because those
> who feel strongly about the default behaviour of push_back being
> one or the other can just use the explicitly-named version instead.
>
I love the sound of design-by-committee in the morning :-)
More seriously, I do think that makes sense since it allows the user
to select the appropriate function for their design, but use the
alternate one when necessary.
If this is what is finally settled on, I would prefer to default to a
checked policy because then it will catch and prevent mistakes by
default. If you have an exceptional reason for the performance, you
can switch to the alternate function/policy.
Cheers!
Andrew Hundt
Paul A. Bristow
> -----Original Message-----
> From: boost-...@lists.boost.org [mailto:boost-...@lists.boost.org] On Behalf Of Andrew
> Hundt
> Sent: Friday, October 14, 2011 5:04 PM
> To: bo...@lists.boost.org
> Subject: Re: [boost] Interest in StaticVector - fixed capacity vector
>
> > * unchecked_push_back which does what it says; AND
> > * checked_push_back which does what it says; AND
> > * push_back which calls one or the other based on a policy
> >
> > That leaves just one thing to quibble about - the default value of the
> > policy - but even that choice becomes less important, because those
> > who feel strongly about the default behaviour of push_back being one
> > or the other can just use the explicitly-named version instead.
> >
>
> I love the sound of design-by-committee in the morning :-)
>
> More seriously, I do think that makes sense since it allows the user to select the appropriate
function for
> their design, but use the alternate one when necessary.
>
> If this is what is finally settled on, I would prefer to default to a checked policy because then
it will catch
> and prevent mistakes by default. If you have an exceptional reason for the performance, you can
switch to
> the alternate function/policy.
I also prefer checked by default.
But it is true that a policy solution will impose a run-time penalty? Can't it be a compile-time
choice?
Of course, there still remains opportunity for the design-by-committee members to discuss what the
default should be ;-)
Paul
---
Paul A. Bristow,
Prizet Farmhouse, Kendal LA8 8AB UK
+44 1539 561830 07714330204
pbri...@hetp.u-net.com
Vicente J. Botet Escriba
> Side note: Can anyone think of a better name than unchecked_push_back?
Hi,
I know that people don't like tags too much, but tags could open the
interface so, the choice of check policy can be deferred at a higher level.
I would use the following overloads:
void push_back( const T& x );
void push_back(no_check_t, const T& x);
void push_back(check_t, const T& x ) {
return push_back(x);
}
With this interface we can define an algorithm using push_back that is
templated by the check policy
template <typename CheckPolicy>
void algo(...)
{
// use push_back(CheckPolicy(), x);
}
A user could use it also directly as
push_back(no_check, x);
Best,
Vicente
Andrew Hundt
>
> on Thu Oct 13 2011, Nevin Liber <nevin-AT-eviloverlord.com> wrote:
>
>> On 13 October 2011 18:08, Andrew Hundt <ath...@gmail.com> wrote:
>>> After comments by Nate Ridge, Dave Abrahams, and others, I have become
>>> convinced that push_back should be unchecked and exceeding the bounds
>>> should be undefined, with an option to turn on checking.
>>
>> While I really disagree with this (as there are both use cases for it
>
> Use-cases, please!
use case for unchecked:
copying point clouds, packets, geometry, or other sets of small
objects with fixed size through an intermediate buffer that either has
to be allocated frequently, where space is extremely limited, or where
allocation is simply not an option.
use case for checked:
copying user input where you have a fixed length limit anyway due to
other limitations, or the type of data being input, or any other case
where performance is not important and correctness/lack of errors is.
> Let's not overlook anything important in this discussion.
>
>> and, more importantly, it is no longer a drop in replacement for
>> vector because your push_back will now behave differently),
>
> How could it ever be a "drop-in replacement for vector" when it comes to
> exceeding a reasonably low length bound? A vector is probably going to
> succeed to push_back past that bound, while this class definitely won't.
> Unless you plan to intentionally leverage this exception (in which case
> vector wasn't serving your needs, so your code needs more than a
> "drop-in-replacement" anyway), then it's *going* to change the behavior
> of your program if and when you cause it to be thrown.
>
> Maybe I'm missing something.
- Perhaps one uses vector while prototyping on their nice quad core 64
bit machine, then they need to cut things down and set strict limits
once the prototype works to get it on their cell phone, game console,
or even smaller device like a router or radio chip.
- On the completely opposite end of the spectrum, processing an extremely large
dataset that has fixed size datums. One could again prototype with vectors,
but now they need something a bit more constrained to optimize
performance for their datacenter.
- Yet another case is existing code that
uses vectors, but have a constraint that makes a perfect case for switching
to StaticVectors like the ones above.
I know there are other alternatives to achieve this, but it seems in
many cases it could be a good choice.
Cheers!
Andrew Hundt
Ion Gaztañaga
> But it is true that a policy solution will impose a run-time penalty? Can't it be a compile-time
> choice?
I'm proposing a compile-time choice so with a bit of code refactoring
the unchecked solution can be extremely efficient, at least in release
mode and a decent optimizer.
Best,
Ion
Dave Abrahams
on Fri Oct 14 2011, Andrew Hundt <athundt-AT-gmail.com> wrote:
> On Fri, Oct 14, 2011 at 6:32 AM, Dave Abrahams <da...@boostpro.com> wrote:
>>
>
>> on Thu Oct 13 2011, Nevin Liber <nevin-AT-eviloverlord.com> wrote:
>>
>>> On 13 October 2011 18:08, Andrew Hundt <ath...@gmail.com> wrote:
>>>> After comments by Nate Ridge, Dave Abrahams, and others, I have become
>>>> convinced that push_back should be unchecked and exceeding the bounds
>>>> should be undefined, with an option to turn on checking.
>>>
>>> While I really disagree with this (as there are both use cases for it
>>
>> Use-cases, please!
>
> use case for unchecked:
> copying point clouds, packets, geometry, or other sets of small
> objects with fixed size through an intermediate buffer that either has
> to be allocated frequently, where space is extremely limited, or where
> allocation is simply not an option.
I know those, of course. Another one you failed to mention:
when you want to implement your own checking ;-)
> use case for checked:
> copying user input where you have a fixed length limit anyway due to
> other limitations,
How do you use the exception in a correct program for this case?
> or the type of data being input, or any other case where performance
> is not important and correctness/lack of errors is.
Is throwing an exception going to turn an incorrect program into a
correct one?
>> How could it ever be a "drop-in replacement for vector" when it comes to
>> exceeding a reasonably low length bound? A vector is probably going to
>> succeed to push_back past that bound, while this class definitely won't.
>> Unless you plan to intentionally leverage this exception (in which case
>> vector wasn't serving your needs, so your code needs more than a
>> "drop-in-replacement" anyway), then it's *going* to change the behavior
>> of your program if and when you cause it to be thrown.
>>
>> Maybe I'm missing something.
>
> - Perhaps one uses vector while prototyping on their nice quad core 64
> bit machine, then they need to cut things down and set strict limits
> once the prototype works to get it on their cell phone, game console,
> or even smaller device like a router or radio chip.
Yeah... in that case they almost certainly don't want to pay for the
check. But if they do want a check, how is an exception going to help
them?
> - On the completely opposite end of the spectrum, processing an extremely large
> dataset that has fixed size datums. One could again prototype with vectors,
> but now they need something a bit more constrained to optimize
> performance for their datacenter.
Again, how does the exception help? How do you use that?
> - Yet another case is existing code that
> uses vectors, but have a constraint that makes a perfect case for switching
> to StaticVectors like the ones above.
These are all basically the same case AFAICT ;-)
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Andrew Hundt
>> copying user input where you have a fixed length limit anyway due to
>> other limitations,
>
> How do you use the exception in a correct program for this case?
ah, exceptions in a correct program! I don't believe I have ever seen
a program that is both nontrivial and correct :-)
I cannot think of cases where given a correct program an exception
should be thrown with a fixed capacity vector, aside from testing that
the exceptions are thrown correctly :-). As far as I can think at the
moment, if your program is correct you should never exceed the
capacity of a fixed size vector.
>> or the type of data being input, or any other case where performance
>> is not important and correctness/lack of errors is.
>
> Is throwing an exception going to turn an incorrect program into a
> correct one?
If you catch that exception and do something reasonable, would it not?
Perhaps this only makes the argument of making it "less wrong".
>>> How could it ever be a "drop-in replacement for vector" when it comes to
>>> exceeding a reasonably low length bound? A vector is probably going to
>>> succeed to push_back past that bound, while this class definitely won't.
>>> Unless you plan to intentionally leverage this exception (in which case
>>> vector wasn't serving your needs, so your code needs more than a
>>> "drop-in-replacement" anyway), then it's *going* to change the behavior
>>> of your program if and when you cause it to be thrown.
>>>
>>> Maybe I'm missing something.
>>
>> - Perhaps one uses vector while prototyping on their nice quad core 64
>> bit machine, then they need to cut things down and set strict limits
>> once the prototype works to get it on their cell phone, game console,
>> or even smaller device like a router or radio chip.
>
> Yeah... in that case they almost certainly don't want to pay for the
> check. But if they do want a check, how is an exception going to help
> them?
Black box:
If you have to use an existing algorithm or function that you cannot
change or do not know exactly how the internals work, you can catch
the exception and handle it in a reasonable way.
Alternately, if you are creating the black box, you could do the same
for the data they give you.
Prototyping:
I find exceptions helpful when they immediately kill my program when I
do something wrong at the prototyping stage, as compared to random
stack jumps into other places when I'm just allowed to try and access
that memory. Much easier to find and fix quickly :-)
If you have been looking for an opinion on exceptions versus
assertions I'm willing to hear out others. I don't feel
particularly strongly either way at the moment.
>
>> - On the completely opposite end of the spectrum, processing an extremely large
>> dataset that has fixed size datums. One could again prototype with vectors,
>> but now they need something a bit more constrained to optimize
>> performance for their datacenter.
>
> Again, how does the exception help? How do you use that?
The execution of what?
>> - Yet another case is existing code that
>> uses vectors, but have a constraint that makes a perfect case for switching
>> to StaticVectors like the ones above.
>
> These are all basically the same case AFAICT ;-)
Ah... I read your request as one for different end use cases :-) so I
answered a different question.
Cheers!
Andrew Hundt
Christian Holmquist
>
>
> Is throwing an exception going to turn an incorrect program into a
> correct one?
>
I'm probably completely misunderstanding your point of view, or rather,
what is your point of view?
Not throwing the exception will turn a correct program into an incorrect one
if that program relies on the exception.
That's the case I'm most worried about, incorrect programs not so much.
I find them difficult to reason about, but maybe that's just me..
>
> --
> Dave Abrahams
> BoostPro Computing
> http://www.boostpro.com
>
>
>
>
- Christian
Dave Abrahams
on Fri Oct 14 2011, Andrew Hundt <athundt-AT-gmail.com> wrote:
>>> use case for checked:
>>> copying user input where you have a fixed length limit anyway due to
>>> other limitations,
>>
>> How do you use the exception in a correct program for this case?
>
> ah, exceptions in a correct program! I don't believe I have ever seen
> a program that is both nontrivial and correct :-)
>
> I cannot think of cases where given a correct program an exception
> should be thrown with a fixed capacity vector, aside from testing that
> the exceptions are thrown correctly :-). As far as I can think at the
> moment, if your program is correct you should never exceed the
> capacity of a fixed size vector.
>
>>> or the type of data being input, or any other case where performance
>>> is not important and correctness/lack of errors is.
>>
>> Is throwing an exception going to turn an incorrect program into a
>> correct one?
>
> If you catch that exception and do something reasonable, would it not?
No. "Reasonable" doesn't mean you fulfill your original
intention/specification. You don't normally write specifications that
say, "...unless the code is wrong, in which case I'll do something
reasonable," nor do you code to perform an operation in two different
ways in case one of them turns out to have coding errors, do you?
> Perhaps this only makes the argument of making it "less wrong".
Is that like "less pregnant?"
More precisely, it avoids some undefined behaviors, which has some
security benefits. That's why I proposed the SEMISECURE mode.
>>>> How could it ever be a "drop-in replacement for vector" when it comes to
>>>> exceeding a reasonably low length bound? A vector is probably going to
>>>> succeed to push_back past that bound, while this class definitely won't.
>>>> Unless you plan to intentionally leverage this exception (in which case
>>>> vector wasn't serving your needs, so your code needs more than a
>>>> "drop-in-replacement" anyway), then it's *going* to change the behavior
>>>> of your program if and when you cause it to be thrown.
>>>>
>>>> Maybe I'm missing something.
>>>
>>> - Perhaps one uses vector while prototyping on their nice quad core 64
>>> bit machine, then they need to cut things down and set strict limits
>>> once the prototype works to get it on their cell phone, game console,
>>> or even smaller device like a router or radio chip.
>>
>> Yeah... in that case they almost certainly don't want to pay for the
>> check. But if they do want a check, how is an exception going to help
>> them?
>
> Black box:
> If you have to use an existing algorithm or function that you cannot
> change or do not know exactly how the internals work, you can catch
> the exception and handle it in a reasonable way.
Too much hand-waving. What possible "reasonable way?" Are you going to
try to achieve the same semantics in a different way?
[And why "how the internals work" matters is beyond me].
> Alternately, if you are creating the black box, you could do the same
> for the data they give you.
Ditto
> Prototyping:
> I find exceptions helpful when they immediately kill my program when I
> do something wrong at the prototyping stage, as compared to random
> stack jumps into other places when I'm just allowed to try and access
> that memory. Much easier to find and fix quickly :-)
Thus a recommendation for a SEMISECURE mode where you can tune the
response. The builtin assert() facility almost always kills your
program at /least/ as usefully and quickly as an exception.
>>> - On the completely opposite end of the spectrum, processing an extremely large
>>> dataset that has fixed size datums. One could again prototype with vectors,
>>> but now they need something a bit more constrained to optimize
>>> performance for their datacenter.
>>
>> Again, how does the exception help? How do you use that?
>
> The execution of what?
Did I write "execution?"
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Peter Dimov
> On 14 October 2011 12:55, Dave Abrahams <da...@boostpro.com> wrote:
> > Is throwing an exception going to turn an incorrect program into a
> > correct one?
>
> I'm probably completely misunderstanding your point of view, or rather,
> what is your point of view?
He's saying that if a program does a push_back when the capacity has been
reached, this program has a logic error, and throwing an exception will not
make the error go away.
I'm not so sure of that, because doing a push_back when the capacity has
been reached is not necessarily a logic error if the code is well aware of
the possibility and prepared to handle the exception.
try
{
do some push_backs into a static_vector; we don't know how many
}
catch( out_of_capacity& )
{
// ignore, what we gathered so far is good enough for gov't use
Andrew Hundt
>>> correct one?
>>
>> If you catch that exception and do something reasonable, would it not?
>
> No. "Reasonable" doesn't mean you fulfill your original
> intention/specification. You don't normally write specifications that
> say, "...unless the code is wrong, in which case I'll do something
> reasonable,"
I'm fairly certain that writing specifications this way is quite
common. For instance, consider a program that catches exceptions and
crashes, then generates and sends a bug report to the creators. Does
that application not catch when the code is wrong, then do something
reasonable? Of course this is not correct behavior with respect to the
original goal, but I would argue that is is correct behavior with
respect to a secondary goal of finding incorrect behavior that
prevents reaching the original goal.
Furthermore, I don't believe I am being very original with this idea.
Java has the ArrayOutOfBounds exception. Please, I beg you not to take
this as the belief that Java is correct. I am simply unconvinced by
your argument and I am playing devil's advocate by pointing out an
example counter to the point you are making.
> nor do you code to perform an operation in two different
> ways in case one of them turns out to have coding errors, do you?
I believe this is typically done by the competition. :-)
>
>> Perhaps this only makes the argument of making it "less wrong".
>
> Is that like "less pregnant?"
>
Yep. That is exactly what I was trying to say. :-)
> More precisely, it avoids some undefined behaviors, which has some
> security benefits. That's why I proposed the SEMISECURE mode.
Why should the mode be SEMISECURE by default, and not a
RELAXED_SECURITY mode for when you absolutely need the highest
performance?
also, what is the disadvantage of providing, push_back(),
checked_push_back(), and unchecked_push_back(), where a policy or
struct tag allows the checkedness (pardon my word frankenstein) to be
decided at either the instantiation or the call site, respectively?
To draw an analogy, designing code to use RAII can sometimes incur a
performance penalty with the benefit of preventing a failure to
release a resource. Of course you can always "just free" that resource
by hand, but changes in one portion of an application can have
unforeseen consequences in another to those who are dealing with a
small portion of a very large or complex system. Therefore it has
become commonplace to pay a small penalty for the benefit of
preventing problems. In this case, that problem is undefined behavior,
and the penalty is the checks. Perhaps an out of bounds error does not
meet the complexity level required for such a cost to be worthwhile,
but if I am not mistaken myself, it is one of the most common mistakes
made by anyone. However, this does not prevent one from making the
other choice, and calling the unchecked version when they absolutely
need the performance.
The core of what I am saying is that checks + exceptions make it
easier to find, prevent, and/or report problems.
There are a some items I would like to verify so I can clarify my
understanding of your argument.
First, I believe that you are saying that code is already incorrect
when it goes out of bounds, so you might as well just let it keep
running with undefined behavior unless a special SEMISECURE flag is
set. Furthermore, by the time you reach the point where I am proposing
that an exception be thrown, the code is already incorrect, therefore
the exception will never prevent an error, and thus the exception
should not exist. Is this correct?
What are the metrics by which you define an exception as both
incorrect and/or worse? What is lost by using an exception? Does it
break a convention, reduce performance, break purity, or upend general
happiness?
>>>>> How could it ever be a "drop-in replacement for vector" when it comes to
>>>>> exceeding a reasonably low length bound? A vector is probably going to
>>>>> succeed to push_back past that bound, while this class definitely won't.
>>>>> Unless you plan to intentionally leverage this exception (in which case
>>>>> vector wasn't serving your needs, so your code needs more than a
>>>>> "drop-in-replacement" anyway), then it's *going* to change the behavior
>>>>> of your program if and when you cause it to be thrown.
>>>>>
>>>>> Maybe I'm missing something.
>>>>
>>>> - Perhaps one uses vector while prototyping on their nice quad core 64
>>>> bit machine, then they need to cut things down and set strict limits
>>>> once the prototype works to get it on their cell phone, game console,
>>>> or even smaller device like a router or radio chip.
>>>
>>> Yeah... in that case they almost certainly don't want to pay for the
>>> check. But if they do want a check, how is an exception going to help
>>> them?
>>
>> Black box:
>> If you have to use an existing algorithm or function that you cannot
>> change or do not know exactly how the internals work, you can catch
>> the exception and handle it in a reasonable way.
>
> Too much hand-waving. What possible "reasonable way?" Are you going to
> try to achieve the same semantics in a different way?
I would expect to most frequently use it to report the problem.
>
> [And why "how the internals work" matters is beyond me].
>
>> Alternately, if you are creating the black box, you could do the same
>> for the data they give you.
>
> Ditto
>
>> Prototyping:
>> I find exceptions helpful when they immediately kill my program when I
>> do something wrong at the prototyping stage, as compared to random
>> stack jumps into other places when I'm just allowed to try and access
>> that memory. Much easier to find and fix quickly :-)
>
> Thus a recommendation for a SEMISECURE mode where you can tune the
> response. The builtin assert() facility almost always kills your
> program at /least/ as usefully and quickly as an exception.
Ah, this is at least a partial answer to my questions above. Is it
also straightforward possible to handle an assert and report it if the
programmer is not present to witness it?
>>>> - On the completely opposite end of the spectrum, processing an extremely large
>>>> dataset that has fixed size datums. One could again prototype with vectors,
>>>> but now they need something a bit more constrained to optimize
>>>> performance for their datacenter.
>>>
>>> Again, how does the exception help? How do you use that?
>>
>> The execution of what?
>
> Did I write "execution?"
my ability to read failed me :-). Here I was advocating how drop-in
replacement of std::vector with StaticVector would be useful.
Exceptions would help StaticVector achieve this because std::vector
throws one when there is no more space.
I'm sure there is a gaping whole in my argument somewhere, so please
poke away :-)
Cheers!
Andrew Hundt
Christian Holmquist
> Christian Holmquist wrote:
>
>> On 14 October 2011 12:55, Dave Abrahams <da...@boostpro.com> wrote:
>> > Is throwing an exception going to turn an incorrect program into a
>> > correct one?
>>
>> I'm probably completely misunderstanding your point of view, or rather,
>> what is your point of view?
>>
>
> He's saying that if a program does a push_back when the capacity has been
> reached, this program has a logic error, and throwing an exception will not
> make the error go away.
To me this is like saying that if any exception is thrown, the program has a
logic error. It's not very helpful though. All code which does not deal with
global OS data (such as the heap, files, etc) can be written as no throw, if
enough details are exposed for the user. But I want code to throw so that I
don't need to worry and check all details everywhere.
How much juggling would I need to do to parse a comma separated text of
integers into a static_vector?
static_vector<int, 4> v;
spirit::parse("1, 2, 3, 4, 5", int_ % ',', space, v); // undefined
behaviour???
Sure, the above can be seen as having a 'logic error' because the grammar
says parse N but the capacity can only handle N < 5. But the the code can
never parse N anyways, because sooner or later even a std::vector runs out
of memory space.
I simply find it hard to accept that a predefined maximum capacity, being at
compile time or runtime, should run into undefined behaviour if that
capacity is exceeded. There's too much code in the world already that
doesn't check limits.. STL containers has helped tremendously in this
regard, I don't see why one would want to go in another direction.
- Christian
Simonson, Lucanus J
From: boost-...@lists.boost.org [mailto:boost-...@lists.boost.org] On Behalf Of Andrew Hundt
Sent: Friday, October 14, 2011 8:14 AM
To: bo...@lists.boost.org
Subject: Re: [boost] Interest in StaticVector - fixed capacity vector
>> I really don't want to see a policy controlling this; rather, have
>> unchecked_push_back and unchecked_insert for those who need every
>> ounce of performance at the expense of safety.
>I definitely see a lot of clarity in implementing it this way. I just
>wish there was a nicer name than unchecked_push_back.
If I were writing the code I would name it push_back_blindly. I have several _blindly functions in polygon. The generally mean that the caller assumes responsibility for maintaining the class invariant and that the class should skip the usual checks for performance reasons. Typically these are intended for use within the class itself, but I make them public instead of private because I trust that I can use them properly from within or without. I think unchecked_push_back is perfectly fine too.
Regards,
Luke
Dave Abrahams
on Fri Oct 14 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:
> Christian Holmquist wrote:
>> On 14 October 2011 12:55, Dave Abrahams <da...@boostpro.com> wrote:
>
>> > Is throwing an exception going to turn an incorrect program into a
>> > correct one?
>>
>> I'm probably completely misunderstanding your point of view, or rather,
>> what is your point of view?
>
> He's saying that if a program does a push_back when the capacity has
> been reached, this program has a logic error, and throwing an
^
almost certainly -----------^
> exception will not make the error go away.
>
> I'm not so sure of that, because doing a push_back when the capacity
> has been reached is not necessarily a logic error if the code is well
> aware of the possibility and prepared to handle the exception.
>
> try
> {
> do some push_backs into a static_vector; we don't know how many
> }
> catch( out_of_capacity& )
> {
> // ignore, what we gathered so far is good enough for gov't use
> }
Yes, it's possible, but highly unusual, for someone to use the class
that way. And we were talking about being a drop-in replacement for
std::vector, in which case you wouldn't have coded for this kind of
possibility unless your data was way too big for StaticVector in the
first place.
Once you give people a guarantee that an exception will be thrown, they
can go ahead and take advantage of it like above. I'm not sure that
should be encouraged at all, much less in this case where StaticVector
is an optimization and the above is a terribly inefficient idiom.
Violating the otherwise-precondition is easily and cheaply avoided,
which makes it suitable as a precondition.
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Dave Abrahams
on Fri Oct 14 2011, Andrew Hundt <athundt-AT-gmail.com> wrote:
>>>> Is throwing an exception going to turn an incorrect program into a
>
>>>> correct one?
>>>
>>> If you catch that exception and do something reasonable, would it not?
>>
>> No. "Reasonable" doesn't mean you fulfill your original
>> intention/specification. You don't normally write specifications that
>> say, "...unless the code is wrong, in which case I'll do something
>> reasonable,"
>
> I'm fairly certain that writing specifications this way is quite
> common.
I was asking about you, personally.
> For instance, consider a program that catches exceptions and crashes,
> then generates and sends a bug report to the creators. Does that
> application not catch when the code is wrong, then do something
> reasonable?
Its specification doesn't say "do something reasonable;" it says "send a
bug report to the creators."
> Of course this is not correct behavior with respect to the original
> goal, but I would argue that is is correct behavior with respect to a
> secondary goal of finding incorrect behavior that prevents reaching
> the original goal.
Sure, but exceptions are a poor way to get that effect.
> Furthermore, I don't believe I am being very original with this idea.
> Java has the ArrayOutOfBounds exception. Please, I beg you not to take
> this as the belief that Java is correct. I am simply unconvinced by
> your argument and I am playing devil's advocate by pointing out an
> example counter to the point you are making.
I don't know what to say. Java is a mostly-different story; they have
no undefined behavior in the language, so they have to do something
else. IMO using EH to deal with programming errors is usually a
mistake, but it's one that's been repeated far and wide.
>> More precisely, it avoids some undefined behaviors, which has some
>> security benefits. That's why I proposed the SEMISECURE mode.
>
> Why should the mode be SEMISECURE by default, and not a
> RELAXED_SECURITY mode for when you absolutely need the highest
> performance?
Everybody wants a different default; I'm not here to argue about that
except that I'll say people get upset when they turn on all the
optimizations and then pay for checks they weren't expecting.
> also, what is the disadvantage of providing, push_back(),
> checked_push_back(), and unchecked_push_back(), where a policy or
> struct tag allows the checkedness (pardon my word frankenstein) to be
> decided at either the instantiation or the call site, respectively?
Creeping—nay, rampaging—complexity.
> To draw an analogy, designing code to use RAII can sometimes incur a
> performance penalty with the benefit of preventing a failure to
> release a resource. Of course you can always "just free" that resource
> by hand, but changes in one portion of an application can have
> unforeseen consequences in another to those who are dealing with a
> small portion of a very large or complex system. Therefore it has
> become commonplace to pay a small penalty for the benefit of
> preventing problems. In this case, that problem is undefined behavior,
> and the penalty is the checks. Perhaps an out of bounds error does not
> meet the complexity level required for such a cost to be worthwhile,
> but if I am not mistaken myself, it is one of the most common mistakes
> made by anyone. However, this does not prevent one from making the
> other choice, and calling the unchecked version when they absolutely
> need the performance.
>
> The core of what I am saying is that checks + exceptions make it
> easier to find, prevent, and/or report problems.
The checks are not the problem; the exceptions are. And they don't help
with finding, preventing, or reporting problems.
> There are a some items I would like to verify so I can clarify my
> understanding of your argument.
>
> First, I believe that you are saying that code is already incorrect
> when it goes out of bounds,
Probably.
> so you might as well just let it keep running with undefined behavior
> unless a special SEMISECURE flag is set.
No.
> Furthermore, by the time you reach the point where I am proposing that
> an exception be thrown, the code is already incorrect, therefore the
> exception will never prevent an error, and thus the exception should
> not exist. Is this correct?
That's one way to look at it, but it's not what I said. The main
problems are the ones I cited before in this thread (you can go back and
look them up).
> What are the metrics by which you define an exception as both
> incorrect and/or worse? What is lost by using an exception? Does it
> break a convention, reduce performance, break purity, or upend general
> happiness?
All answered already in my first posting in the thread.
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Adam Wulkiewicz
>> What are the metrics by which you define an exception as both
>> incorrect and/or worse? What is lost by using an exception? Does it
>> break a convention, reduce performance, break purity, or upend general
>> happiness?
>
> All answered already in my first posting in the thread.
>
Exceptions shouldn't be used to report programmer's errors. Putting an
element outside the array is a programmer's error as e.g. dereferencing
iterator pointing somwhere outside some range. Programmer can prevent
this and therefore he should. He should check ranges or equality to the
end iterator. If the exception is thrown it don't change anything, the
programmer must fix the code. Asserts should be used in this case.
But in the case of bad memory allocation he probably can't do anything
in this part of code. Maby he allocates to much somewhere in the other
part of the code? But, maby some other application allocates hudge
amount of memory or the system is broken etc. This is something unexpected.
You want to mimic std::vector behaviour with bad_alloc exceptions and I
understand that. So maby it's a good idea to change the name from
static_vector to e.g. pushable_array or other XXX_array and it will be
clear that this container is similar to the array not the vector and
will not throw any bad_alloc exception because it don't even allocates
the memory.
Regards,
Adam
Peter Dimov
> How much juggling would I need to do to parse a comma separated text of
> integers into a static_vector?
>
> static_vector<int, 4> v;
> spirit::parse("1, 2, 3, 4, 5", int_ % ',', space, v); // undefined
> behaviour???
That's a good example of the sort I had in mind. We could use a vector but
why bother parsing 108 integers when we know that we don't support (or need)
more than four?
Peter Dimov
> on Fri Oct 14 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:
> > try
> > {
> > do some push_backs into a static_vector; we don't know how many
> > }
> > catch( out_of_capacity& )
> > {
> > // ignore, what we gathered so far is good enough for gov't use
> > }
>
> Yes, it's possible, but highly unusual, for someone to use the class
> that way.
I'm not sure of that either. What makes you think so? What are the "proper"
uses for it?
Adam Wulkiewicz
> Dave Abrahams wrote:
>>
>> on Fri Oct 14 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:
>> > try
>> > {
>> > do some push_backs into a static_vector; we don't know how many
>> > }
>> > catch( out_of_capacity& )
>> > {
>> > // ignore, what we gathered so far is good enough for gov't use
>> > }
>>
>> Yes, it's possible, but highly unusual, for someone to use the class
>> that way.
>
> I'm not sure of that either. What makes you think so? What are the "proper"
> uses for it?
Exceptions shouldn't be used for something which is not an exceptional
case. In this case it's checking how many elements you may push. They
shouldn't be used as a part of "normal" program flow. I'd rather use
the following:
while ( sv.size() < sv.capacity() && keep_pushing )
// do a push_back into a static_vector
If someone saw a try/catch block he would think it's something unusual
handled here, but it isn't. What would you do if std::vector had
thrown std::bad_alloc? Ignore it as well? Probably not because it's an
exceptional case and you probably should finish some routine,
deallocate memory, release resources, exit your program, redesign your
code because blocks of memory you want to allocate are too big or do
something similar.
Regards,
Adam
Dave Abrahams
on Fri Oct 14 2011, Christian Holmquist <c.holmquist-AT-gmail.com> wrote:
> On 14 October 2011 16:07, Peter Dimov <pdi...@pdimov.com> wrote:
>
>> Christian Holmquist wrote:
>>
>>> On 14 October 2011 12:55, Dave Abrahams <da...@boostpro.com> wrote:
>>> > Is throwing an exception going to turn an incorrect program into a
>>> > correct one?
>>>
>>> I'm probably completely misunderstanding your point of view, or rather,
>>> what is your point of view?
>>>
>>
>> He's saying that if a program does a push_back when the capacity has been
>> reached, this program has a logic error, and throwing an exception will not
>> make the error go away.
>
> To me this is like saying that if any exception is thrown, the program has a
> logic error.
I don't see how anyone could draw that conclusion.
> It's not very helpful though. All code which does not deal with global
> OS data (such as the heap, files, etc) can be written as no throw,
> if enough details are exposed for the user.
Only by reporting the error another way. There's no way for a user to
check beforehand that there is going to be enough memory to complete any
given job requiring a dynamic allocation. And if you consider memory
"global OS data" then yes, the code that doesn't need to allocate
resources and can always complete successfully in the absence of
erroneous usage should be no-throw.
On the other hand, /this/ problem is in the user's power to prevent, and
I assert that in the vast majority of imaginable use cases the user will
have tried to get prevention right (i.e. will have tried to choose the
length to be sure everything fits).
> But I want code to throw so that I don't need to worry and check all
> details everywhere.
If your code detects a programming error, you need to worry. Yes, it's
true that once you say "I'm going to throw under these conditions" it's
no longer certain that it's a programming error, but I assert that in
this case it remains highly likely. But then the library is no longer
allowed to treat it as an error and helpfully do the most appropriate
thing for debugging purposes; it has to throw an exception, because it
promised to.
What's your program's response to that exception? In many programs when
there's an exception it gets logged and it tries again later. By the
time you catch the exception far from the call site, you no longer know
for sure whether it was a programmer error or not, so you don't really
have a choice. This is how bugs stay hidden.
We mostly have a consistent practice in the C++ standard library and in
Boost that we respond to programming errors with undefined behavior and
*not* with a documented defined behavior, which has the effect of making
it harder to detect bugs. [Now I'm proposing broadening that practice in
Boost to help avoid undefined behavior.]
> How much juggling would I need to do to parse a comma separated text of
> integers into a static_vector?
> static_vector<int, 4> v;
> spirit::parse("1, 2, 3, 4, 5", int_ % ',', space, v); // undefined
> behaviour???
Nobody likes "unefined behaviour???" But please allow me to replace
that comment with:
"// throws an exception???"
It's just not the most appropriate response. For those who want
checking, dropping into the debugger or dumping core or logging and
terminating would be better, and those who don't will be annoyed to pay
for unneeded checks when their code is correct. Why should the library
be locked into providing what is almost always a suboptimal response?
> Sure, the above can be seen as having a 'logic error' because the grammar
> says parse N but the capacity can only handle N < 5.
Um, yeah, and because you wrote the existence of 5 items right into the
program at the call site. In most cases there's a better chance that
it's not a logic error. If this isn't a logic error, it's a perverse
way of writing "throw capacity_exceeded()" for which the programmer
should receive fifty lashes with a wet noodle.
> But the the code can never parse N anyways, because sooner or later
> even a std::vector runs out of memory space.
Oh, come now. By that reasoning, code using std::vector can never do
anything with N.
> I simply find it hard to accept that a predefined maximum capacity,
> being at compile time or runtime, should run into undefined behaviour
> if that capacity is exceeded. There's too much code in the world
> already that doesn't check limits. STL containers has helped
> tremendously in this regard,
Huh? Except for at(), STL containers aren't spec'd to check for misuse
or out-of-bounds access. The ones that do check are doing so... **as an
expression of undefined behavior**.
> I don't see why one would want to go in another direction.
That's why I'm specifically proposing a mode that *does* do the
checking. But we should *not* encode into the library spec that the
response to a failed check is an exception in those cases where a failed
check is most likely to represent a programming error.
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Dave Abrahams
on Sat Oct 15 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:
> Dave Abrahams wrote:
>> on Fri Oct 14 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:
>
>> > try
>> > {
>> > do some push_backs into a static_vector; we don't know how many
>> > }
>> > catch( out_of_capacity& )
>> > {
>> > // ignore, what we gathered so far is good enough for gov't use
>> > }
>>
>> Yes, it's possible, but highly unusual, for someone to use the class
>> that way.
>
> I'm not sure of that either. What makes you think so?
a. It's not an idiom typically used with C++
b. It's very inefficient in a context where we're surely
trying to optimize (otherwise why use StaticVector?)
I also want to add that the above code would be broken and wrong if you
were using vector instead of static_vector, unless you know the number of
possible push_backs is bounded.
> What are the "proper" uses for it?
It sounds like you're asking me to prove something for which we both
know there's no proof. If you design the class to throw exceptions when
the fixed capacity is exceeded, your code above is perfectly "proper."
The problem is that once we get a step away from the call site, we can't
tell wether the usage was proper anymore.
If we can figure out how to get cars to bounce harmlessly out of
collisions we could decide to make it legal to ignore stop signs and
just count on the bounce to handle it. Should we? It would then be
impossible to yank the out-of-control drivers off the road, and if
people start taking advantage of this protection, it's going to slow
down traffic. If instead we can capture colliding drivers and send them
to driving school, isn't that better?
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Peter Dimov
> I'd rather use the following:
>
> while ( sv.size() < sv.capacity() && keep_pushing )
> // do a push_back into a static_vector
Yeah, if you get to rewrite all the functions that lead to the push_back.
Like spirit::parse and everything it calls.
Peter Dimov
> Nobody likes "unefined behaviour???" But please allow me to replace
> that comment with:
>
> "// throws an exception???"
>
> It's just not the most appropriate response. For those who want
> checking, dropping into the debugger or dumping core or logging and
> terminating would be better, and those who don't will be annoyed to pay
> for unneeded checks when their code is correct.
We (as in the authors of the example) fall in neither category of yours. We
want the algorithm that does push_back to terminate when it reaches
capacity. Which is exactly what it will do, without having to be rewritten.
> Why should the library be locked into providing what is almost always a
> suboptimal response?
It's your (and others') assertion that this is almost always a suboptimal
response. You haven't backed it up. Yes, it's trivial to argue that logic
errors should not be exceptions, but why is push_back over capacity "almost
always" a logic error? Heck... why is it a logic error at all, except in the
trivial case in which you start with an empty static_vector<T, N> and do
exactly N push_backs, a case which more or less calls for an array because
it doesn't exploit the fact that size() can be different from capacity()?
Stated differently, is the number of push_backs always a compile time
constant? Does it not come, more often than not, from runtime input?
Peter Dimov
> on Sat Oct 15 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:
> > What are the "proper" uses for it?
>
> It sounds like you're asking me to prove something for which we both
> know there's no proof.
Not really. As I already said in the other message, doing more push_backs
than a compile-time constant size is a logic error only when the number of
push_backs is a compile-time constant as well. So, it follows that it is
only proper to use static_vector when the number of push_backs is known at
compile time. So I was wondering what some of these (nontrivial and variable
size) uses are.
As an example, a case in which 99.4% of the time the number of push_backs
doesn't exceed capacity is a legitimate use, but it's not a logic error, and
quite fits the mantra that "exceptions should be exceptional".
Christian Holmquist
> > But I want code to throw so that I don't need to worry and check all
> > details everywhere.
>
> If your code detects a programming error, you need to worry. Yes, it's
> true that once you say "I'm going to throw under these conditions" it's
> no longer certain that it's a programming error, but I assert that in
> this case it remains highly likely. But then the library is no longer
> allowed to treat it as an error and helpfully do the most appropriate
> thing for debugging purposes; it has to throw an exception, because it
> promised to.
>
It's by no means the most helpful and appropriate thing to, even for
debugging purposes. If I want to catch
exceptions when thrown, i instruct my environment to do so.
But real world errors don't appear under a debugger, they appear on end
users machines
or on remote server sites and always in release builds. If something doesn't
show up in an error log, it didn't happen...
I realize I'm standing with another background than most others here, so I
simply rest my case.
It's been interesting anyways, hope I haven't disturbed too much =)
> --
> Dave Abrahams
> BoostPro Computing
> http://www.boostpro.com
>
>
> _______________________________________________
>
Cheers,
- Christian
Peter Dimov
> If we can figure out how to get cars to bounce harmlessly out of
> collisions we could decide to make it legal to ignore stop signs and
> just count on the bounce to handle it. Should we?
Cars are cars, and static_vector::push_back is, well,
static_vector::push_back. They have nothing in common. You can't
mechanically apply the same rule to both. push_back throwing doesn't imply
operator[] throwing, for example. Their uses are different. A throwing
static_vector::push_back enables existing algorithms that use push_back or
back_inserter to continue to work without their behavior becoming undefined.
A throwing static_vector::operator[]... does not enable anything. :-)
Adam Wulkiewicz
> Adam Wulkiewicz wrote:
>
>> I'd rather use the following:
>>
>> while ( sv.size() < sv.capacity() && keep_pushing )
>> // do a push_back into a static_vector
>
> Yeah, if you get to rewrite all the functions that lead to the
> push_back. Like spirit::parse and everything it calls.
Yes and should I know what spirit::parse do if some exception is thrown
inside? Maby it returns empty vector, whatever? Is it aware that some of
the exceptions are ok? I don't know it and I do not want to know it.
From the previous example. If you know that you need only 4 elements
and you use std::vector since there is no static_vector yet, must you
parse all of the elements? You'll probably provide some wrapper/adaptor.
This adaptor will probably work with std::vector and static_vector as
well. Not to mention all other containers that has push_back().
This usage is some special case. Of course, you'll find some number of
those but in general this way of thinking will be wrong.
Regards,
Adam