[proposal] A fixed-capacity vector with embedded storage

[Gonzalo BG]

Hello world,

I wrote a proposal for a fixed-capacity vector with embedded storage since this is one of the data-structures that I use most along with std::vector and boost::small_vector. 

You can find the proposal (and an implementation) here:

https://github.com/gnzlbg/embedded_vector/blob/master/README.md

Since this is the first proposal I write my experience writing proposals is zero. Hopefully some of you might be kind enough to:

- provide me feedback to improve the proposal, 

- maybe be able to champion it in the next meeting (I don't think I will be able to attend it unless it is close to Cologne, Germany),

- so that I can get a paper number for it and it can be discussed in the next meeting.

There are still some issues open in the github repo, which also contains an implementation, but the implementation is a bit-out-of-sync with the latest specification (that will be updated before submitting it).

Best regards, 

Gonzalo

[Zach Laine]

This proposal is quite timely -- I was considering proposing static_vector too.  I'm glad to see this.

Some notes:

"

The main drawback of introducing a new type is, as the design document of the EASTL points out, increased code size. Since this container type is opt-in, only those users that need it will pay this cost. Common techniques to reduce code size where explored in the prototype implementation (e.g. implementing Capacity/value_type agnostic functionality in a base class) without success, but implementations are encouraged to consider code-size as a quality of implementation issue.

"

I really want to see some real numbers on this.  Please instantiate several kinds of static_vector-like things (hand-rolled struct consisting of std::array + size_t, static_vector, your implementation, etc.) in scenarios where you would expect there to be larger code size, and let's see some assembly, or at least relative counts of instructions.  Also, that EASTL design doc link is broken.

At the last meeting, LEWG were taking the stance that (most) additions of noexcept and constexpr would be left up to implementers until the implications were better understood by the community as a whole.

Regarding explicit instantiability, why wouldn't that already be the case for any valid template instantiation?

"

Iterator invalidation

The iterator invalidation rules are different than those for std::vector, since:

moving an embedded_vector invalidates all iterators,

swapping two embedded_vectors invalidates all iterators, and

inserting elements into an embedded_vector never invalidates iterators.

"

That last one is not true -- if I insert a T before the first element, I've invalidated all iterators into the vector, no?  Did you meant push_back() never invalidates?

Zach

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/b6abc3db-61ca-4641-ad80-86a5da719a3a%40isocpp.org.

[rhalb...@gmail.com]

I like this proposal very much. I use boost::static_vector a lot and it has a shortcoming that your proposal fixes, namely not throwing upon exceeding the capacity. This  saves on branching logic inside push_back().

Two remarks. First, emplace_back() returns a reference in C++17. 

Second, you define the op== and other relational operators as friends, which means they are generated as non-member functions at namespace scope. However, all other Standard containers are defined as non-member function templates. The difference is that the latter does not accept user-defined conversions, and the former does. Also they don't have to be friends either. 

The best way to declare the relational operators op== and op< is as non-member non-friend function templates, that delegate to std::equal and std::lexicographical_compare on the embedded_vector's iterator range. Then the others can be defined as usual in terms of the former.

[Gonzalo BG]

@Zach Laine:

Thanks for the feedback. I've filled github issues for all the points you mentioned. I will report back here with the findings about the code-size cost of explicit instantiations of embedded_vector for different Capacities.

> Regarding explicit instantiability, why wouldn't that already be the case for any valid template instantiation?

Non-template member functions, which are instantiated on explicit template instantiations, might not be properly constrained, so their instantiation might fail "loudly". The way I've tried to "fix" this in the proposal is by properly constraining all member functions using concepts, but this is an aspect that I must iterate on with more feedback.

> At the last meeting, LEWG were taking the stance that (most) additions of noexcept and constexpr would be left up to implementers until the implications were better understood by the community as a whole.

Adding constexpr is a breaking change, since functions that were not previously evaluated in unevaluated contexts, and thus could be SFINAEd upon, become always potentially evaluated. This can break a lot of code, and it already happened when libc++ made std::invoke constexpr "as a QoI" feature, a change that needed to be reverted.

Second, embedded_vector can be used inside constexpr functions for trivial types. To conditionally allow this, the API must be made conditionally constexpr.

> That last one is not true -- if I insert a T before the first element, I've invalidated all iterators into the vector, no?  Did you meant push_back() never invalidates?

Yes, good catch! I meant inserting elements at the end never invalidates iterators.

@rhalbersma: first thank you a lot for the feedback, the devil is in the details and I had completely missed all the issues you point out!

> emplace_back() returns a reference in C++17. 

Indeed, I've added an issue to fix this, thanks!

> Second, you define the op== and other relational operators as friends, which means they are generated as non-member functions at namespace scope. However, all other Standard containers are defined as non-member function templates. The difference is that the latter does not accept user-defined conversions, and the former does. Also they don't have to be friends either. 

Indeed, I hadn't realized this until now. As you already know I've filled some issues to improve these.

> The best way to declare the relational operators op== and op< is as non-member non-friend function templates, that delegate to std::equal and std::lexicographical_compare on the embedded_vector's iterator range. Then the others can be defined as usual in terms of the former.

AFAIK std::lexicographical_compare is not constexpr in C++17, but whether the op== and friends use it or not is an implementation detail of the proposal's implementation rather than a blocker. 

--

You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/f78f7191-b043-4e95-990d-a0f9baab9aec%40isocpp.org.

[Rein Halbersma]

On Fri, Dec 9, 2016 at 10:51 AM, Gonzalo BG <gonza...@gmail.com> wrote:

@Zach Laine:

Thanks for the feedback. I've filled github issues for all the points you mentioned. I will report back here with the findings about the code-size cost of explicit instantiations of embedded_vector for different Capacities.

> Regarding explicit instantiability, why wouldn't that already be the case for any valid template instantiation?

Non-template member functions, which are instantiated on explicit template instantiations, might not be properly constrained, so their instantiation might fail "loudly". The way I've tried to "fix" this in the proposal is by properly constraining all member functions using concepts, but this is an aspect that I must iterate on with more feedback.

> At the last meeting, LEWG were taking the stance that (most) additions of noexcept and constexpr would be left up to implementers until the implications were better understood by the community as a whole.

Adding constexpr is a breaking change, since functions that were not previously evaluated in unevaluated contexts, and thus could be SFINAEd upon, become always potentially evaluated. This can break a lot of code, and it already happened when libc++ made std::invoke constexpr "as a QoI" feature, a change that needed to be reverted.

Second, embedded_vector can be used inside constexpr functions for trivial types. To conditionally allow this, the API must be made conditionally constexpr.

> That last one is not true -- if I insert a T before the first element, I've invalidated all iterators into the vector, no?  Did you meant push_back() never invalidates?

Yes, good catch! I meant inserting elements at the end never invalidates iterators.

@rhalbersma: first thank you a lot for the feedback, the devil is in the details and I had completely missed all the issues you point out!

> emplace_back() returns a reference in C++17. 

Indeed, I've added an issue to fix this, thanks!

> Second, you define the op== and other relational operators as friends, which means they are generated as non-member functions at namespace scope. However, all other Standard containers are defined as non-member function templates. The difference is that the latter does not accept user-defined conversions, and the former does. Also they don't have to be friends either. 

Indeed, I hadn't realized this until now. As you already know I've filled some issues to improve these.

> The best way to declare the relational operators op== and op< is as non-member non-friend function templates, that delegate to std::equal and std::lexicographical_compare on the embedded_vector's iterator range. Then the others can be defined as usual in terms of the former.

AFAIK std::lexicographical_compare is not constexpr in C++17, but whether the op== and friends use it or not is an implementation detail of the proposal's implementation rather than a blocker. 

 

Indeed, the reference to <algorithm> was meant to illustrate that it was not necessary to make the comparison operators friends, but that they could be done through the public iterator interface (whether from <algorithm> or hand-implemented to be constexpr).

Note that if you would have a std::array as back-end for this embedded_vector, then you might want to check 

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0031r0.html which has greatly expanded the constexpr-ness of std::array, but with the exception of the op==/op< and swap/fill operations. The rationale being:

Currently comparisons and swap/fill may be implemented with the help of algorithms from <algorithm> header. Marking comparisons with constexpr will break that ability and will potentially lead to performance degradations.

A related proposal to make <algorithm> mostly constexpr http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0202r1.html has not yet been adopted, mainly for concern on intrinsics and C helpers (memset and friends).

So while I would certainly encourage you to push constexpr-ness as a feature of your proposal, I would not expect this to be adopted without discussion. 

 

[Gonzalo BG]

@Rein Halbersma wrote:

> Indeed, the reference to <algorithm> was meant to illustrate that it was not necessary to make the comparison operators friends, but that they could be done through the public iterator interface (whether from <algorithm> or hand-implemented to be constexpr).

>
>Note that if you would have a std::array as back-end for this embedded_vector, then you might want to check
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0031r0.html which has greatly expanded the constexpr-ness of std::array, but with the exception of the op==/op< and swap/fill operations. The rationale being:
>
>Currently comparisons and swap/fill may be implemented with the help of algorithms from <algorithm> header. Marking comparisons with constexpr will break that ability and will potentially lead to performance degradations.
>
> A related proposal to make <algorithm> mostly constexpr http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0202r1.html has not yet been adopted, mainly for concern on intrinsics and C helpers (memset and friends).
>
> So while I would certainly encourage you to push constexpr-ness as a feature of your proposal, I would not expect this to be adopted without discussion.

Thanks for these remarks. I've added a github issue to expand the design rationale of constexpr with mentions of those two paper. How I see it, is that if those papers are accepted, the implementation of the proposal might be greatly simplified. But if they are not accepted, the proposal can still be implemented as is; doing so just has a higher implementation cost. 

I think some aspects of the proposal are controversial. In particular, the "conditionally noexcept interface" and the constexpr features. I actually do not know if the proposal should have these features since there are a lot of trade-offs at play. The features are however implementable, and they do bring significant benefit in some use cases. I am assuming that the proposal won't get accepted at its first revision, but rather that it will at least be revised a couple of times. I thought that for a first revision of the proposal it would be better to add these features to show that they are implementable, that they bring benefit, and so that people can "play" with them and see how they behave or find issues. If it turns out that they should be removed in a second revision, then that's the way it is. But removing them is easy, and maybe they can be pursued in future proposals that are followups to the one you mentioned. 

I should write this down in the paper to explain why I used these features. I do not want the reader to be surprised with a "noexcept/constexpr everywhere! that is not how the standard library does things!". What I actually want is to inform the reader that it is possible to do this. That doing so adds benefits, and that those benefits come with some specification and implementation costs. I think the benefits outweigh the costs (and I try to make a case for this), but I want the reader to be able to form its own opinion about this so that the discussion at the committee can be a constructive one.  

[Rein Halbersma]

On Fri, Dec 9, 2016 at 12:42 PM, Gonzalo BG <gonza...@gmail.com> wrote:

@Rein Halbersma wrote:

> Indeed, the reference to <algorithm> was meant to illustrate that it was not necessary to make the comparison operators friends, but that they could be done through the public iterator interface (whether from <algorithm> or hand-implemented to be constexpr).

>
>Note that if you would have a std::array as back-end for this embedded_vector, then you might want to check
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0031r0.html which has greatly expanded the constexpr-ness of std::array, but with the exception of the op==/op< and swap/fill operations. The rationale being:
>
>Currently comparisons and swap/fill may be implemented with the help of algorithms from <algorithm> header. Marking comparisons with constexpr will break that ability and will potentially lead to performance degradations.
>
> A related proposal to make <algorithm> mostly constexpr http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0202r1.html has not yet been adopted, mainly for concern on intrinsics and C helpers (memset and friends).
>
> So while I would certainly encourage you to push constexpr-ness as a feature of your proposal, I would not expect this to be adopted without discussion.

Thanks for these remarks. I've added a github issue to expand the design rationale of constexpr with mentions of those two paper. How I see it, is that if those papers are accepted, the implementation of the proposal might be greatly simplified. But if they are not accepted, the proposal can still be implemented as is; doing so just has a higher implementation cost. 

 

AFAICS, the first (p0031r0) has already been accepted in the latest draft Standard (N4618) (together with a constexpr reverse_iterator). The second (p0202r1) might not have been discussed yet, I am not sure. You might want to contact the author Antony Polukhin to ask what the Committee feedback was. He is the main driver behind all the latest constexpr library additions.

[Zach Laine]

On Fri, Dec 9, 2016 at 3:51 AM, Gonzalo BG <gonza...@gmail.com> wrote:

@Zach Laine:

Thanks for the feedback. I've filled github issues for all the points you mentioned. I will report back here with the findings about the code-size cost of explicit instantiations of embedded_vector for different Capacities.

> Regarding explicit instantiability, why wouldn't that already be the case for any valid template instantiation?

Non-template member functions, which are instantiated on explicit template instantiations, might not be properly constrained, so their instantiation might fail "loudly". The way I've tried to "fix" this in the proposal is by properly constraining all member functions using concepts, but this is an aspect that I must iterate on with more feedback.

Ah, got it. Perhaps just make that intention a bit more explicit?  An FWIW, I expect that feature to be quite controversial.

> At the last meeting, LEWG were taking the stance that (most) additions of noexcept and constexpr would be left up to implementers until the implications were better understood by the community as a whole.

Adding constexpr is a breaking change, since functions that were not previously evaluated in unevaluated contexts, and thus could be SFINAEd upon, become always potentially evaluated.

I don't think anyone cares about breaking backwards-compatibility with respect to SFINAE.  If we did, nearly every change would be considered a breaking change.

 

This can break a lot of code, and it already happened when libc++ made std::invoke constexpr "as a QoI" feature, a change that needed to be reverted.

That's the whole point, as I understand it.  Standardizing one way or the other closes the door on implementers' making these kinds of mistakes -- and without those kinds of mistakes to inform the design, the right design is harder to come up with.

Second, embedded_vector can be used inside constexpr functions for trivial types. To conditionally allow this, the API must be made conditionally constexpr.

Fair enough.  But wasn't similar logic used to justify constexpr std::invoke?  I'm not advocating for one position or another -- I'm just letting you know what the I took the atmosphere to be in LEWG at the last meeting.

[snip]

Zach

[T. C.]

Some comments after looking through ~half of the page:

> If T's destructor throws the behavior is undefined.

That's implied by [res.on.functions]/2 and does not need to be repeated.

> The embedded_vector<T, Capacity>::size_type is the smallest unsigned integer type that can represent Capacity.

This implies that `evec.size() +1` is sometimes unsigned and sometimes signed, depending on whether size_type is subject to integral promotion. I don't find that to be helpful.

> If the container is not empty, the member function data() returns a pointer such that [data(), data() + size()) is a valid range

Shouldn't this *always* be a valid range regardless of whether the container is empty?

> The whole API of embedded_vector<T, Capacity> is constexpr if is_trivial<T> is true.

A trivial class may have deleted copy/move assignment. A "plain" implementation of e.g. push_back with placement new would work with such a type, but not if you pre-allocate and then attempt to assign.

> Making exceeding the capacity a precondition has some advantages: [...]

If it's a precondition, then it's narrow-contract, and LWG generally doesn't like noexcept on narrow-contract functions. LWG doesn't really like conditional noexcept either, except in a few cases.

Expect the noexcept on things like front()/back()/op[] to disappear.

> /* constexpr ~embedded_vector(); */ // implicitly generated

This comment makes no sense for non-trivially-destructible T.

> void reserve(size_type n) = delete; 

> void shrink_to_fit() = delete; 

What does deleting them add over simply not having those members?

> [detailed specification]

The elements of the specification should match [structure.specifications]. 

> constexpr embedded_vector(size_type n, const value_type& value);

> [...]
> Requirements: value_type shall be EmplaceConstructible into *this from *first.

This doesn't make any sense.

> template<class InputIterator>

> constexpr embedded_vector(InputIterator first, InputIterator last);
> [...]
> Requirements: value_type shall be either:
>    -  CopyInsertable into *this if the reference type of InputIterator is an lvalue reference, or
>    -  MoveInsertable into *this if the reference type of InputIterator is an rvalue reference.

1) Are you intentionally not supporting the case where the value type of the iterator is not the same as the value type of the vector? If so, why?

2) What if "reference" is not a reference type at all? (e.g., vector<bool>::iterator)

This is the one that should be using the EmplaceConstructible wording.

> Effects: exactly last - first calls to value_type[']s copy or move constructor.

First, this might not invoke a copy or move ctor (unless you really meant to ban mismatched value types). Second, last - first needs either the appropriate wording from Clause 25's introduction or be replaced with distance(first, last).

> template<std::size_t M, enable_if_t<(C != M)>>

> constexpr embedded_vector& operator=(embedded_vector<value_type, M>const& other)

The SFINAE is unnecessary. The template/non-template tiebreaker is sufficient to disambiguate.