Comment on N4416: Why not make vector::reserve exact?

[Arthur O'Dwyer]

I've been reading Nevin Liber's N4416 "Don’t Move: vector Can Have Your Non-Moveable Types Covered"

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4416.pdf

He proposes a new member function of std::vector<T> whose name is "subject to L(E)WG bikeshedding" but tentatively proposed as std::vector<T>::reserve_initially(size_type n). The semantics of this function would be (A)

    if empty()

        reserve space for exactly n elements

    else

        throw an exception

This is contrasted with the current behavior (since C++98) of std::vector<T>::reserve(size_type n), whose semantics are (B)

    if capacity() < n

        reserve space for at least n elements

    else

        do nothing

I have often wished for a member function of std::vector<T> that could give me a vector with capacity exactly n and no more — for example, if I know my vector's maximum capacity up front and I want to be economical with my memory usage; or if I'm using a user-defined allocator that is good at allocating blocks of one exact size and bad at bigger sizes.

Surely it has occurred to everybody on the Committee by now that it would be super convenient if std::vector<T>::reserve were that function; i.e., if we changed its semantics from (B) above to (C)

    if capacity() < n

        reserve space for exactly n elements

    else

        do nothing

However, in 17 years, this change has not happened. This suggests that there's a really good reason for its not happening. What is that reason? Clearly one reason would be "vendor inertia", but vendors are doing pretty well these days at keeping up with library changes, so maybe that shouldn't be the only blocking reason.

Does anyone on the Committee have some inside information on the reasons for vector::reserve's current (IMHO suboptimal) specification?

Finally, let me open the bikeshed by suggesting that if semantics (C) can't be given to vector::reserve(size_type n), they should at least be given to a new overload vector::reserve(size_type n, decltype(std::reserve_exactly)).  Either way, I see no reason for N4416's proposed semantics (A) to ever make it into the language; they just seem strictly less useful and less efficient than semantics (C).

Thoughts?

–Arthur

[Nevin Liber]

On 4 May 2015 at 22:41, Arthur O'Dwyer <arthur....@gmail.com> wrote:

I've been reading Nevin Liber's N4416 "Don’t Move: vector Can Have Your Non-Moveable Types Covered"

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4416.pdf

That paper looks familiar. :-)

 

I have often wished for a member function of std::vector<T> that could give me a vector with capacity exactly n and no more — for example, if I know my vector's maximum capacity up front and I want to be economical with my memory usage; or if I'm using a user-defined allocator that is good at allocating blocks of one exact size and bad at bigger sizes.

Even if you have a user-defined allocator with those properties, there really is no way (other than specializing vector on the allocator type) for vector to communicate with the allocator to determine the optimal block size to use.  The vector keeps track of capacity independent of the allocator.

 

Surely it has occurred to everybody on the Committee by now that it would be super convenient if std::vector<T>::reserve were that function; i.e., if we changed its semantics from (B) above to (C)

    if capacity() < n

        reserve space for exactly n elements

    else

        do nothing

However, in 17 years, this change has not happened. This suggests that there's a really good reason for its not happening. What is that reason? Clearly one reason would be "vendor inertia", but vendors are doing pretty well these days at keeping up with library changes, so maybe that shouldn't be the only blocking reason.

The committee works on proposals.  I don't know if anyone has proposed this in the past.  I can see a few reasons:

1.  AFAIK implementations just pass the reserve size to the allocator anyway.

2.  vector<bool> cannot enforce this w/o more bookkeeping.

3.  It isn't all that useful w/o something like emplace_back_capped() (or something convoluted like a stateful allocator that allows exactly one allocation).

 

Does anyone on the Committee have some inside information on the reasons for vector::reserve's current (IMHO suboptimal) specification?

I have no knowledge (others around Lenexa might), but my guess is that the initial design was made to maximize vendor freedom.  IIRC vector wasn't initially required to have contiguous space.

 

Finally, let me open the bikeshed by suggesting that if semantics (C) can't be given to vector::reserve(size_type n), they should at least be given to a new overload vector::reserve(size_type n, decltype(std::reserve_exactly)).  Either way, I see no reason for N4416's proposed semantics (A) to ever make it into the language; they just seem strictly less useful and less efficient than semantics (C).

With (C) you cannot store non-moveable types, because the real algorithm is:

if capacity() < n

    reserve space for exactly n elements

    move_if_noexcept elements from old space to new space

    destroy elements in old space

    release old space

else

    do nothing

Various ideas are now floating around for setting exact reserve capacity.  We'll see if any of them survive after the presentation of this paper later this week.

--

 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Arthur O'Dwyer]

On Monday, May 4, 2015 at 10:04:15 PM UTC-7, Nevin ":-)" Liber wrote:

On 4 May 2015 at 22:41, Arthur O'Dwyer <arthur....@gmail.com> wrote:

I've been reading Nevin Liber's N4416 "Don’t Move: vector Can Have Your Non-Moveable Types Covered"

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4416.pdf

That paper looks familiar. :-)

 

I have often wished for a member function of std::vector<T> that could give me a vector with capacity exactly n and no more — for example, if I know my vector's maximum capacity up front and I want to be economical with my memory usage; or if I'm using a user-defined allocator that is good at allocating blocks of one exact size and bad at bigger sizes.

Even if you have a user-defined allocator with those properties, there really is no way (other than specializing vector on the allocator type) for vector to communicate with the allocator to determine the optimal block size to use.  The vector keeps track of capacity independent of the allocator.

Right, but I'm also the guy writing the client code that reserves the vector! So I might have something like

http://melpon.org/wandbox/permlink/skNNYpHPIr2v42iL

where I know that my allocator will return usable memory iff it is called with the right arguments, but I cannot rely on the std::vector implementation to actually pass those arguments, even when it's "obvious" what should happen.

 

 

Surely it has occurred to everybody on the Committee by now that it would be super convenient if std::vector<T>::reserve were that function; i.e., if we changed its semantics from (B) above to (C)

    if capacity() < n

        reserve space for exactly n elements

    else

        do nothing

However, in 17 years, this change has not happened. This suggests that there's a really good reason for its not happening. What is that reason? Clearly one reason would be "vendor inertia", but vendors are doing pretty well these days at keeping up with library changes, so maybe that shouldn't be the only blocking reason.

The committee works on proposals.  I don't know if anyone has proposed this in the past.  I can see a few reasons:

1.  AFAIK implementations just pass the reserve size to the allocator anyway.

2.  vector<bool> cannot enforce this w/o more bookkeeping.

3.  It isn't all that useful w/o something like emplace_back_capped() (or something convoluted like a stateful allocator that allows exactly one allocation).

I'm aware that the Committee works on proposals; I just couldn't believe that nobody had ever proposed this before, since it seems so obvious. I'd gladly write up the relevant proposal for Kona.

1. If true, this is excellent, because it removes one possible objection to standardizing the practice.

2. I don't see any difficulty with vector<bool> right now, but I'm not sure how it uses its allocator. I'll investigate if I write that proposal.

3. The emplace_back_capped() etc. member functions proposed in N4416 are awesome and I hope they make it in!

 

 

Finally, let me open the bikeshed by suggesting that if semantics (C) can't be given to vector::reserve(size_type n), they should at least be given to a new overload vector::reserve(size_type n, decltype(std::reserve_exactly)).  Either way, I see no reason for N4416's proposed semantics (A) to ever make it into the language; they just seem strictly less useful and less efficient than semantics (C).

With (C) you cannot store non-moveable types, because the real algorithm is:

if capacity() < n

    reserve space for exactly n elements

    move_if_noexcept elements from old space to new space

    destroy elements in old space

    release old space

else

    do nothing

Various ideas are now floating around for setting exact reserve capacity.  We'll see if any of them survive after the presentation of this paper later this week.

Excellent and deadly point.

I'll float a terrible idea: You could change the key step to

    move_if_moveable elements from old space to new space

where move_if_moveable is SFINAE magic that first attempts to move, or else attempts to copy, or else throws an exception. ;)

–Arthur

[David Krauss]

On 2015–05–05, at 11:41 AM, Arthur O'Dwyer <arthur....@gmail.com> wrote:

I've been reading Nevin Liber's N4416 "Don’t Move: vector Can Have Your Non-Moveable Types Covered"

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4416.pdf

He proposes a new member function of std::vector<T> whose name is "subject to L(E)WG bikeshedding" but tentatively proposed as std::vector<T>::reserve_initially(size_type n). The semantics of this function would be (A)

    if empty()

        reserve space for exactly n elements

    else

        throw an exception

I like the idea, but it seems easier to use an adaptor which takes a non-movable type and adds a throwing move constructor:

template< typename non_movable >

struct fake_movable : non_movable {

    using non_movable::non_movable;

    [[noreturn]] fake_movable( fake_movable && )

        { throw sessile_exception(); }

};

No need to modify any containers; this gets the same results from the existing reserve and resize.

It doesn’t address at-most-N semantics for movable types, at least not while allowing insert and erase from the middle. However, I think that’s a job for allocators. There should be a concept of allocator conversion such that std::vector<T, size_limiting_alloc< std::allocator<T> > > can convert to std::vector< T, std::allocator<T> >. (I suspect that this would make allocators work much better in practice overall.)

[Christopher Jefferson]

On 5 May 2015 at 04:41, Arthur O'Dwyer <arthur....@gmail.com> wrote:
> I've been reading Nevin Liber's N4416 "Don’t Move: vector Can Have Your
> Non-Moveable Types Covered"
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4416.pdf
>
>

> Surely it has occurred to everybody on the Committee by now that it would be
> super convenient if std::vector<T>::reserve were that function; i.e., if we
> changed its semantics from (B) above to (C)
>
> if capacity() < n
> reserve space for exactly n elements
> else
> do nothing
>
> However, in 17 years, this change has not happened. This suggests that
> there's a really good reason for its not happening. What is that reason?

This is quite hard in a number of cases:

1) vector<bool> : Allocation has to take place in at least chars, and
given (basically) every modern machine has 8 bit chars, this would
require every vector<bool> stored an extra value, just to ensure they
forbid you from writing to bits of that last byte that you hadn't
reserved explicitly!

2) vector<char> and other small types: It is typical for system
allocators to have a lower bound on allocations (8 bytes is common on
a 64-bit system), and also limits for larger allocations (so above 8K,
you always get a multiple of 4K for example). Once again we might have
to store extra unnessary data, and also we would have to "throw away"
capacity which had already been allocated to a vector, just because
users didn't ask for it.

On this point 2, I am often annoyed the other way, new and malloc may
have allocated more memory than I asked for, and I would like to know
about it and use it!

Chris

[Magnus Fromreide]

So, you would like to see something along the lines of wg14/n1085?

(http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm)

/MF

[Matt Calabrese]

On Mon, May 4, 2015 at 8:41 PM, Arthur O'Dwyer <arthur....@gmail.com> wrote:

I've been reading Nevin Liber's N4416 "Don’t Move: vector Can Have Your Non-Moveable Types Covered"

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4416.pdf

He proposes a new member function of std::vector<T> whose name is "subject to L(E)WG bikeshedding" but tentatively proposed as std::vector<T>::reserve_initially(size_type n). The semantics of this function would be (A)

    if empty()

        reserve space for exactly n elements

    else

        throw an exception

I like the idea, but IMO we really should not be throwing an exception here. Just make it a precondition of the function that the vector must be empty. If someone is catching and actually "handling" the exception, they're just using the exception for control flow and the catch can simply be a branch. The rationale is less than satisfying.

[Nevin Liber]

On 5 May 2015 at 17:15, 'Matt Calabrese' via ISO C++ Standard - Future Proposals <std-pr...@isocpp.org> wrote:

I like the idea, but IMO we really should not be throwing an exception here. Just make it a precondition of the function that the vector must be empty. If someone is catching and actually "handling" the exception, they're just using the exception for control flow and the catch can simply be a branch. The rationale is less than satisfying.

Should LEWG go in that direction, I'm fine with it.

[Bengt Gustafsson]

As for the initial suggestion here, to make the new reserve_initially function unnecessary by changing the behaviour of reserve() this is not possible as it can't be instantiated for a non-movable type, which was the reason to introdice the reserve_initially() function in the first place, according to N4416.

At the same time, I don't see the need to mandate that reserve_initially() does not allow reservation of additional elements. The programmer obviously knows what the max limit is but it does no harm (except maybe some lost memory) to allocate a bit more.

I think that the original intention of the definition of reserve() was to allow implementations to "round up" the allocation to some granularity suitable for the heap implementation, without totally loosing those bytes. Maybe this intent is not possible to fulfil after the

introduction of allocators, due to some deficiency in the allocator API, but I think allocators are newer than reserve()...

So we are actually have two totally separate issues, one which is addressed by N4416 and which to keep it clean should not have changed the wording to "exactly n elements". The other being whether the current meaning of resize() should be changed to mandate "exactly n elements" being reserved.

I like the "core" idea of N4416 to be implemented but when it comes to the reserve exactness I would rather see that the allocator API got fixed with some "round up to suitable boundary" function that containers can use. This of course solves the special issues with vector<bool> mentioned above.

[Nicol Bolas]

On Thursday, May 7, 2015 at 3:39:19 AM UTC-4, Bengt Gustafsson wrote:

As for the initial suggestion here, to make the new reserve_initially function unnecessary by changing the behaviour of reserve() this is not possible as it can't be instantiated for a non-movable type, which was the reason to introdice the reserve_initially() function in the first place, according to N4416.

At the same time, I don't see the need to mandate that reserve_initially() does not allow reservation of additional elements. The programmer obviously knows what the max limit is but it does no harm (except maybe some lost memory) to allocate a bit more.

For some programmers "some lost memory" is significant harm.

Besides consistency with the wording on the standard `reserve`, I don't see anything to be gained from allowing implementations to allocate extra elements. Remember: the whole point of `reserve_initially` is that the user cannot exceed the boundary. Since you're code will never go beyond the element count you reserve, I see no reason why an implementation would allocate more elements than the user asked.

[David Krauss]

On 2015–05–07, at 8:51 PM, Nicol Bolas <jmck...@gmail.com> wrote:

Besides consistency with the wording on the standard `reserve`, I don't see anything to be gained from allowing implementations to allocate extra elements.

For std::string, it enables the SSO. Perhaps the generic description should be constrained a bit for std::vector, but that’s all.

[David Krauss]

On 2015–05–07, at 8:57 PM, David Krauss <pot...@mac.com> wrote:

For std::string, it enables the SSO. Perhaps the generic description should be constrained a bit for std::vector, but that’s all.

Oh, it’s not as generic as I thought. There’s no std::deque::reserve, only vector and string (and vector<bool>, which might as well have its own exception to any such rule). The allowance for vector might have been written when there was such a thing as a small-vector optimization, and never revised since.

Maybe a defect report is worth a shot…

[Bo Persson]

On 2015-05-07 14:51, Nicol Bolas wrote:
>
>
> On Thursday, May 7, 2015 at 3:39:19 AM UTC-4, Bengt Gustafsson wrote:
>
>
> As for the initial suggestion here, to make the new
> reserve_initially function unnecessary by changing the behaviour of
> reserve() this is not possible as it can't be instantiated for a
> non-movable type, which was the reason to introdice the
> reserve_initially() function in the first place, according to N4416.
>
> At the same time, I don't see the need to mandate that
> reserve_initially() does not allow reservation of additional
> elements. The programmer obviously knows what the max limit is but
> it does no harm (except maybe some lost memory) to allocate a bit more.
>
>
> For some programmers "some lost memory" is significant harm.
>
> Besides consistency with the wording on the standard `reserve`, I don't
> see anything to be gained from allowing implementations to allocate
> extra elements. Remember: the whole point of `reserve_initially` is that

> the user /cannot/ exceed the boundary. Since you're code will never go

> beyond the element count you reserve, I see no reason why an
> implementation would allocate more elements than the user asked.
>

Possibly because the user asked for too few elements. :-)

What should an implementation do with a vector<char> when a user asks
for one element only? Should it be non-conforming to actually allocate 4
or 8 bytes?


Bo Persso

[Nicol Bolas]

You're thinking in terms of what the allocator does. I'm thinking in terms of what the vector does.

The vector tells the allocator that it wants enough memory for X objects. What the allocator has to do to get that is really none of the vector's business.

If you take a std::vector<char> and have it reserve_initially space for only 1 element, then vector::capacity will return one. The result of performing emplace_back_capped more than one will be an exception. It doesn't matter if the allocator returned a valid block containing 1 char or 50; as far as the vector is concerned, there is exactly and only enough space for 1 char.

[Arthur O'Dwyer]

On Thursday, May 7, 2015 at 10:05:50 AM UTC-7, Bo Persson wrote:
>
> On 2015-05-07 14:51, Nicol Bolas wrote:
> > On Thursday, May 7, 2015 at 3:39:19 AM UTC-4, Bengt Gustafsson wrote:
> >
> >     As for the initial suggestion here, to make the new
> >     reserve_initially function unnecessary by changing the behaviour of
> >     reserve() this is not possible as it can't be instantiated for a
> >     non-movable type, which was the reason to introdice the
> >     reserve_initially() function in the first place, according to N4416.

(SFINAE allows you to instantiate a "limited reserve()" for non-moveable elements which wouldn't move anything. But I have since realized that one of my pet peeves about the STL is all the existing SFINAE tricks, so I shouldn't be advocating for any more of them. Also, I've realized that the intended use-case here is v.clear(); v.reserve_initially(n); — it's not that the vector has to be completely new, merely that you have to manually empty it first, in cases where you can't assert it to be empty.)

 

> >     At the same time, I don't see the need to mandate that
> >     reserve_initially() does not allow reservation of additional
> >     elements. The programmer obviously knows what the max limit is but
> >     it does no harm (except maybe some lost memory) to allocate a bit more.
> >
> > For some programmers "some lost memory" is significant harm.
> >
> > Besides consistency with the wording on the standard `reserve`, I don't
> > see anything to be gained from allowing implementations to allocate
> > extra elements. Remember: the whole point of `reserve_initially` is that
> > the user /cannot/ exceed the boundary. Since you're code will never go
> > beyond the element count you reserve, I see no reason why an
> > implementation would allocate more elements than the user asked.
>
> Possibly because the user asked for too few elements.  :-)
>
> What should an implementation do with a vector<char> when a user asks
> for one element only? Should it be non-conforming to actually allocate 4
> or 8 bytes?

Yes, absolutely, 100 percent it should!  If the user asks for exactly 1 element, the vector should not attempt to interfere with the user's request, but instead simply relay that request to the allocator associated with the vector.  Now, the allocator (which actually knows about memory alignment and so on) might well decide to malloc up 4 bytes instead of 1; that's totally fine. The allocator is expected to concern itself with such things. But there needs to be some way for the user to communicate a specific request to his allocator, without interference, and without completely abandoning std::vector.

This is also a good place to point out that std::vector<bool> is not actually a special case in this respect. Any std::vector<bool> will need to have the same m_size and m_capacity members as std::vector<T>; there's nothing in the semantics that requires m_capacity to be a multiple of 8 (or 64, or 100). However, vector<bool> is a special case in one important way: it is the only vector<T> that we intuitively expect to call allocate<U> for any U not equal to T.

–Arthur

P.S. — I would also love to see and/or write a proposal that forbids std::vector<T not equal to bool> to examine its allocator::rebind, just because that keeps biting me every time I try to test anything involving allocators. I keep inheriting from std::allocator and forgetting to override rebind.)

http://melpon.org/wandbox/permlink/83azNz80bH1l8B73 (I feel great, my code works fine with Clang)

http://melpon.org/wandbox/permlink/ZiPX2zMmqMdyjbkX (aw crap, my code doesn't even get called with GCC)

[Nicol Bolas]

On Thursday, May 7, 2015 at 4:04:55 PM UTC-4, Arthur O'Dwyer wrote:

P.S. — I would also love to see and/or write a proposal that forbids std::vector<T not equal to bool> to examine its allocator::rebind, just because that keeps biting me every time I try to test anything involving allocators. I keep inheriting from std::allocator and forgetting to override rebind.)

http://melpon.org/wandbox/permlink/83azNz80bH1l8B73 (I feel great, my code works fine with Clang)

http://melpon.org/wandbox/permlink/ZiPX2zMmqMdyjbkX (aw crap, my code doesn't even get called with GCC)

We don't define the allocator model for specific containers; we define how it works, period. How any individual container implementation uses it is up to that implementation. allocator::rebind is part of the allocator interface, and if an implementation chooses to use it, that's perfectly fine.

The correct way to fix this is with a proper allocator concept. Then, you'll get a compiler error if you try to use a non-conforming-but-would-work-on-this-implementation allocator.

[Arthur O'Dwyer]

On Thu, May 7, 2015 at 6:03 PM, Nicol Bolas <jmck...@gmail.com> wrote:

On Thursday, May 7, 2015 at 4:04:55 PM UTC-4, Arthur O'Dwyer wrote:

P.S. — I would also love to see and/or write a proposal that forbids std::vector<T not equal to bool> to examine its allocator::rebind, just because that keeps biting me every time I try to test anything involving allocators. I keep inheriting from std::allocator and forgetting to override rebind.)

http://melpon.org/wandbox/permlink/83azNz80bH1l8B73 (I feel great, my code works fine with Clang)

http://melpon.org/wandbox/permlink/ZiPX2zMmqMdyjbkX (aw crap, my code doesn't even get called with GCC)

We don't define the allocator model for specific containers; we define how it works, period. How any individual container implementation uses it is up to that implementation. allocator::rebind is part of the allocator interface, and if an implementation chooses to use it, that's perfectly fine.

I see your rationale, but at the same time I disagree with it.  I have a piece of software that deals with vectors of SixteenByteRecords, and for many parts of the codebase I don't need heap-allocation; I can get by with allocating out of a large static array or even a 4K buffer preallocated on the stack. It's easy to preallocate space for a bunch of SixteenByteRecords (guaranteeing alignment and making sure that I can serve them up really quickly simply by advancing a pointer into the buffer), and it's easy to write an allocator that can allocate them.  This is not a general-purpose allocator; it's a speed optimization that is specialized to allocate SixteenByteRecords only.

The problem is that some vendors' implementations of std::vector<SixteenByteRecord> go out of their way to rebind and even to allocate things that are not SixteenByteRecords, at which point all my performance gains go out the window (on those specific vendors' implementations).  I can't blame the vendors, because they're operating within the current spec for std::vector. The only recourse is to abandon std::vector and replace all uses of it with MyVector (which is bit-for-bit identical except for a few lines in reserve).  This is the sort of problem that standardization is meant to solve!

(You say "We don't define the allocator model for specific containers", but of course the Standard does define the model; it just happens to leave it a little bit too broad in the case of std::vector. I believe the wording change to forbid vector from calling rebind would be a single additional sentence.)

The correct way to fix this is with a proper allocator concept. Then, you'll get a compiler error if you try to use a non-conforming-but-would-work-on-this-implementation allocator.

I'm looking forward to that. However, in addition to "Allocator", we also need a "SpecializedAllocator" or "AlreadyBoundAllocator" concept corresponding to the notion described above. Not all allocators can be rebound arbitrarily... unless I'm missing out on some common idiom here.

–Arthur

[Nicol Bolas]

On Friday, May 8, 2015 at 1:52:22 PM UTC-4, Arthur O'Dwyer wrote:

On Thu, May 7, 2015 at 6:03 PM, Nicol Bolas <jmck...@gmail.com> wrote:

On Thursday, May 7, 2015 at 4:04:55 PM UTC-4, Arthur O'Dwyer wrote:

P.S. — I would also love to see and/or write a proposal that forbids std::vector<T not equal to bool> to examine its allocator::rebind, just because that keeps biting me every time I try to test anything involving allocators. I keep inheriting from std::allocator and forgetting to override rebind.)

http://melpon.org/wandbox/permlink/83azNz80bH1l8B73 (I feel great, my code works fine with Clang)

http://melpon.org/wandbox/permlink/ZiPX2zMmqMdyjbkX (aw crap, my code doesn't even get called with GCC)

We don't define the allocator model for specific containers; we define how it works, period. How any individual container implementation uses it is up to that implementation. allocator::rebind is part of the allocator interface, and if an implementation chooses to use it, that's perfectly fine.

I see your rationale, but at the same time I disagree with it.  I have a piece of software that deals with vectors of SixteenByteRecords, and for many parts of the codebase I don't need heap-allocation; I can get by with allocating out of a large static array or even a 4K buffer preallocated on the stack. It's easy to preallocate space for a bunch of SixteenByteRecords (guaranteeing alignment and making sure that I can serve them up really quickly simply by advancing a pointer into the buffer), and it's easy to write an allocator that can allocate them.  This is not a general-purpose allocator; it's a speed optimization that is specialized to allocate SixteenByteRecords only.

The problem is that some vendors' implementations of std::vector<SixteenByteRecord> go out of their way to rebind and even to allocate things that are not SixteenByteRecords, at which point all my performance gains go out the window (on those specific vendors' implementations).  I can't blame the vendors, because they're operating within the current spec for std::vector. The only recourse is to abandon std::vector and replace all uses of it with MyVector (which is bit-for-bit identical except for a few lines in reserve).  This is the sort of problem that standardization is meant to solve!

I don't see what the problem here is. Just because they didn't ask for the exact type doesn't mean that they asked for more memory than you pre-allocated. So give them a chunk of that pre-allocated memory (rounding up to the nearest SixteenByteRecord).

I see no reason to abandon vector in this case.
 

(You say "We don't define the allocator model for specific containers", but of course the Standard does define the model; it just happens to leave it a little bit too broad in the case of std::vector. I believe the wording change to forbid vector from calling rebind would be a single additional sentence.)

When I said "for specific containers", that's what I meant. The allocator model is what it is equally for all containers. Individual containers don't decide what the model is on a case-by-case basis.

We should not have AllocatorForList, AllocatorForVector, AllocatorForDeque, and so forth. We should have a single Allocator concept with explicit requirements, which is used by all containers. And if a container doesn't use certain elements of that allocator... too bad. You still have to implement the whole thing.