Why does vector::reserve() not grow exponentially ?

[Bonita Montero]

vector is specified to have a amortized constant overhead for inserting
new elements. Because of that ::emplace_back() et al grow the capacity
exponentiallly if necessarsy (2x for libstdc++, 1.5x for MSVC). But why
does this not apply for vector::reserve() ? It could simply handle the
reservations in a way that the increase which should be made is below
the next exponential step, the given size doesn't count but the next
anticipated step. That would be the most logical way for me to handle
this issue.

[Bo Persson]

I believe the idea is that you use reserve() when you have a good idea
of what the final size is likely to be.

I wouldn't want the implementation to allocate 50-100% additional space
just in case the vector would continue to grow. Presumably, when calling
reserve() I know that it will not.

[Paavo Helde]

10.06.2021 13:18 Bonita Montero kirjutas:
> vector is specified to have a amortized constant overhead for inserting
> new elements. Because of that ::emplace_back() et al grow the capacity
> exponentiallly if necessarsy (2x for libstdc++, 1.5x for MSVC). But why
> does this not apply for vector::reserve() ?

Because reserve() is only needed for the case when the default
exponential growth is not appropriate for some reason. If so, only the
programmer can know how it's not appropriate and how the buffer should
grow. So there would be little point to double-guess it and do something
else automatically.

> It could simply handle the
> reservations in a way that the increase which should be made is below
> the next exponential step, the given size doesn't count but the next
> anticipated step.

I'm not sure I understand this sentence.

> That would be the most logical way for me to handle
> this issue.

What issue?

[Bonita Montero]

> Because reserve() is only needed for the case when the default

> exponential growth is not appropriate for some reason. ...

The standard says:
"After reserve(), capacity() is _greater or equal_
to the argumentof reserve if reallocation happens ..."
So the standard gives the vector-implementation the freedom to grow
beyond the size you supply with resize(). I think that's because the
vector has to satisfy the amortized constant inserts.

[David Brown]

No, that would make no sense. It is simply to allow the implementation
to round up the capacity a bit if that suits the memory allocator -
perhaps it allocates in lumps of 4K, or cache aligned sizes, or
something else that means when you ask for space for 19 elements it
might give you 24 elements.

You use "reserve" when you know how your vector will grow, because it is
more efficient to jump to the right size than grow exponentially. If
you know you are going to store 1000 elements, you reserve space for
1000 (and don't care if the implementation sets the actual capacity to
1024). That is far faster than starting with 1 element and doubling 10
times, or scaling by 1.5 in 17 steps.

[Bonita Montero]

> No, that would make no sense. It is simply to allow the implementation

> to round up the capacity a bit if that suits the memory allocator - ...

There are no rounding memory-allocators. You say the allocator you
want size = n * sizeof(type) memory and it gives you the memory and
the allocator-API doesn't give you the opportunity to get the size
actually allocated. So you're wrong.

[Bonita Montero]

That's the API:
https://en.cppreference.com/w/cpp/memory/allocator/allocate
Where do you get the opportunity to get the size of the
actually logically or physically allocated memory ?

[MrSpo...@08_cl170xu11o4f8xcg45.co.uk]

On Thu, 10 Jun 2021 16:39:13 +0200
David Brown <david...@hesbynett.no> wrote:
>On 10/06/2021 15:44, Bonita Montero wrote:
>>> Because reserve() is only needed for the case when the default
>>> exponential growth is not appropriate for some reason. ...
>>
>> The standard says:
>>  "After reserve(), capacity() is _greater or equal_
>>   to the argumentof reserve if reallocation happens ..."
>> So the standard gives the vector-implementation the freedom to grow
>> beyond the size you supply with resize(). I think that's because the
>> vector has to satisfy the amortized constant inserts.
>
>No, that would make no sense. It is simply to allow the implementation
>to round up the capacity a bit if that suits the memory allocator -
>perhaps it allocates in lumps of 4K, or cache aligned sizes, or
>something else that means when you ask for space for 19 elements it
>might give you 24 elements.

I always thought vector was a bit of a mess with reserve(), resize(),
capacity() and size(). Having reserve() that allocates the array slots but
not the objects in them so allowing a valid [] access into the reserved but
uninitialised indexes which then gives indefined behaviour with non simple
types is IMO something that should be flagged as Use With Extreme Caution.

[Bonita Montero]

> I always thought vector was a bit of a mess with reserve(), resize(),
> capacity() and size(). Having reserve() that allocates the array slots but
> not the objects in them so allowing a valid [] access into the reserved but
> uninitialised indexes which then gives indefined behaviour with non simple
> types is IMO something that should be flagged as Use With Extreme Caution.

That's not what we're talking about. The discussion is about how much
reserve() actually allocates, not whether you can access objects behind
size() but within capacity().

[Paavo Helde]

10.06.2021 18:25 MrSpook_sw@08_cl170xu11o4f8xcg45.co.uk kirjutas:

> I always thought vector was a bit of a mess with reserve(), resize(),
> capacity() and size(). Having reserve() that allocates the array slots but
> not the objects in them so allowing a valid [] access into the reserved but
> uninitialised indexes which then gives indefined behaviour with non simple
> types is IMO something that should be flagged as Use With Extreme Caution.

Do you realize that calling reserve() and capacity() is fully optional?
If you do not like them, just don't use these functions.

And from where did you get the idea that accessing the vector beyond its
size is valid for POD types? It's definitely UB and I bet there are
debugging implementations which abort the program when they detect this
(aborting the program is a perfect example of UB).

[Bo Persson]

A standard library for a specific system will just *know* that the
memory allocator is pooled and works in certain chunks.

For example, if you ask for size = 1 * sizeof(char), you will never get
a single byte. You will get 16 bytes.

It is then just rational for reserve(1) to result in capacity == 16.

[Bonita Montero]

> A standard library for a specific system will just *know* that the
> memory allocator is pooled and works in certain chunks.

This is the requirement for a container-compliant allocator:
https://en.cppreference.com/w/cpp/named_req/Allocator
Where's the interface that supplies the container the real
size of an allocated memory-block ?

[Alf P. Steinbach]

Depends what the guy meant.

After a `.reserve` there is a guaranteed contiguous buffer of
`.capacity` size. With a vector size of at least 1 one can obtain a raw
pointer to it via `data`, and index that pointer.

You'd need the legendary perverse implementation with phat pointers, to
detect that.


- Alf

[Chris M. Thomasson]

Fwiw, I have created efficient pooled multi-threaded memory allocators
in the past where an allocation of a single char returns the user a
block of memory that is equal to the size of a pointer. So it over
allocates on anything requested that is less than the size of a pointer.
I can show examples if you are interested... If the user request memory
that is equal to the size of a pointer or greater, then there is no over
allocation....

[Paavo Helde]

Mr Spook wrote: "allowing a valid [] access into the reserved but
uninitialised indexes".

The operator[] is easy to check for an implementation. Indeed, VS2019 in
Debug mode with default options pops up a "Debug assertion failed"
dialog with choices to abort the program or attach a debugger, when
running this program:

#include <vector>

int main() {
std::vector<int> vv;
vv.resize(10);
vv.reserve(20);
vv[15] = 43;

}

[David Brown]

The allocator API may not tell you when an allocator actually gets more
memory than you ask for. But containers like std::vector are part of
the standard library - they are not restricted to the public API. A C++
standard library implementation can quite happily have undocumented
features that allow std::vector to see how much memory it has /actually/
been allocated, and let it set "capacity" a little higher.

Equally, there may be no such extra information available, and no way
for the vector to learn of extra memory.

Or when you call "reserve" for a size "x", the implementation could
round "x" up to the nearest multiple of 16 - or whatever it likes. The
implementation has a lot of freedom here.

[MrSpoo...@5ooodqy.co.uk]

On Thu, 10 Jun 2021 22:40:03 +0300
Paavo Helde <myfir...@osa.pri.ee> wrote:
>10.06.2021 18:25 MrSpook_sw@08_cl170xu11o4f8xcg45.co.uk kirjutas:
>
>> I always thought vector was a bit of a mess with reserve(), resize(),
>> capacity() and size(). Having reserve() that allocates the array slots but
>> not the objects in them so allowing a valid [] access into the reserved but
>> uninitialised indexes which then gives indefined behaviour with non simple
>> types is IMO something that should be flagged as Use With Extreme Caution.
>
>Do you realize that calling reserve() and capacity() is fully optional?
>If you do not like them, just don't use these functions.

Thanks for the heads. My point however is that the difference is confusing
to new devs and frankly a lot of older devs who don't use them very often.
I don't see the point of having an allocated array with no objects in it
anyway unless memory is really tight because what else will you do with it
other than use the objects?

>And from where did you get the idea that accessing the vector beyond its
>size is valid for POD types? It's definitely UB and I bet there are

If I reserve 10 integers and try and access one why would it crash? Its simply
an area of memory defined as an integer, unlike an object that will have
complex interactions with default or user methods that could easily cause a
crash if you try and use any of them when uninitialised. Yes, it'll probably
be some random value but it won't crash.

[MrSpook...@b1km5k73i1.edu]

On Fri, 11 Jun 2021 09:23:54 +0300
Paavo Helde <myfir...@osa.pri.ee> wrote:
>Mr Spook wrote: "allowing a valid [] access into the reserved but
>uninitialised indexes".
>
>The operator[] is easy to check for an implementation. Indeed, VS2019 in
>Debug mode with default options pops up a "Debug assertion failed"
>dialog with choices to abort the program or attach a debugger, when
>running this program:
>
>#include <vector>
>
>int main() {
> std::vector<int> vv;
> vv.resize(10);
> vv.reserve(20);
> vv[15] = 43;
>
>}

I have no idea why VS thinks thats a reason to assert. This works fine with
gcc:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
vector<int> v;
v.reserve(100000);
for(int i=0;i < v.capacity();++i)
{
v[i] = i;
cout << v[i] << endl;
}
return 0;
}

[Bo Persson]

If you want to access the values, you could just do resize(10) instead
of reserve(10).

What is the problem?

[Bo Persson]

You mean "seems to work", which is one possible effect of UB.

[Chris M. Thomasson]

Knock on wood!

https://youtu.be/XKuJUxGntRI?list=RDGMEMQ1dJ7wXfLlqCjwV0xfSNbA

;^)

[MrSpook_...@aw55u6.gov]

Why does it need both? What is the point of reserve() is my point.

[MrSpook_...@tu45utvus6nuc.tv]

Does work. There's no reason why it wouldn't unless you can think of one.

[MrSpook...@cns8.net]

Sadly not all of us have an insight into the subtext of 1970s disco tracks.
Care to explain?

[Chris M. Thomasson]

If your software is infested with UB, better knock on wood!

[Alf P. Steinbach]

My favourite song of this kind for playing on the guitar (in A with one
note on open B string) is the Beatles' "Norwegian wood".

Then there is, of course, ZZ Top's "Woke up with wood", which makes it
rather explicit what it's all about.

Except, I don't understand why Amii Stewart was /knocking/ on it.


- Alf (baffled)

[Chris M. Thomasson]

size vs capacity...

[Sam]

Memory allocators are written by smart people. They have tons of use data
that documents optimal allocations strategy. That data would show that even
if you request to reserve 8388492 bytes of memory, it's better to allocate
an even 8388608 bytes. If so, it makes perfect sense to adjust the number of
reserved values to reflect reality.

[Sam]

Just because something isn't specified for a library class, doesn't mean
that the implementation is prohibited from having it.

If you look at your header files for the methods of, say,
std::unordered_map, you will recoil in horror at seeing all sorts of class
methods that are nowhere to be found in the C++ specification.

[Bonita Montero]

> Just because something isn't specified for a library class, doesn't mean
> that the implementation is prohibited from having it.

The containers _always_ use allocators that provide the allocatotor
-interface which is specified under the link I've shown you. And
with this there is no opportunity to get the size of the memory
actually allocated.

[Bonita Montero]

> The allocator API may not tell you when an allocator actually gets more
> memory than you ask for. But containers like std::vector are part of

> the standard library - they are not restricted to the public API. ...

They are because they're restricted to the specified behaviour of the
allocator template-parameter.

[Paavo Helde]

It definitely does not work fine with gcc:

> g++ test1.cpp -D_GLIBCXX_DEBUG
> ./a.exe
/usr/lib/gcc/x86_64-pc-cygwin/10/include/c++/debug/vector:427:
In function:
std::__debug::vector<_Tp, _Allocator>::reference
std::__debug::vector<_Tp,
_Allocator>::operator[](std::__debug::vector<_Tp,
_Allocator>::size_type) [with _Tp = int; _Allocator =
std::allocator<int>; std::__debug::vector<_Tp, _Allocator>::reference =
int&; std::__debug::vector<_Tp, _Allocator>::size_type = long unsigned
int]

Error: attempt to subscript container with out-of-bounds index 0, but
container only holds 0 elements.

Objects involved in the operation:
sequence "this" @ 0x0xffffcbf0 {
type = std::__debug::vector<int, std::allocator<int> >;
}
Aborted (core dumped)


Note: the -D_GLIBCXX_DEBUG flag is what you want to use to check that
your code is correct.

[Bonita Montero]

> Memory allocators are written by smart people. They have tons of use
> data that documents optimal allocations strategy. That data would show
> that even if you request to reserve 8388492 bytes of memory, it's better
> to allocate an even 8388608 bytes. If so, it makes perfect sense to
> adjust the number of reserved values to reflect reality.

That's not what we're talking about. We're talking about if
any container can notice the size actually allocated by an
allocator - it can't.
Even with the malloc()-API there's no opportunity to get the
real size of the block.

[Manfred]

Memory allocated via resize() involves /construction/ of the required
objects - i.e. invocation of their constructor via e.g. placement new.
On the contrary, reserve() allocates memory but does /not/ construct the
objects. It is UB to access objects before their construction.

>> If you want to access the values, you could just do resize(10) instead
>> of reserve(10).
>>
>> What is the problem?
>
> Why does it need both? What is the point of reserve() is my point.
>

See above.

[Paavo Helde]

Yet another flat-earther who thinks his beliefs somehow prescribe the
world how to behave.

Just compile your program in MSVC Debug mode or with g++
-D_GLIBCXX_DEBUG and witness by your own eyes it is crashing! What else
do you want?

And this is not a fault of those compilers, the fault is in your code.
This is why you need to change your code and not claim that the whole
world is wrong and only your ideas are right.

[Bo Persson]

The library implementor knows how std::allocator gets its memory,
because he wrote that earlier.

So he can predict what the underlying memory manager will actually
return when you ask for 7, or 53, bytes. The container can make use of
that knowledge, for example by asking the allocator for 64 bytes instead
of 53. And now reserve(53) can result in capacity() == 64.

[MrSpo...@p900whw6_n8r7ovwuul.ac.uk]

On Fri, 11 Jun 2021 13:22:37 +0200
Manfred <non...@add.invalid> wrote:
>On 6/11/2021 12:17 PM, MrSpook_...@tu45utvus6nuc.tv wrote:
>> Does work. There's no reason why it wouldn't unless you can think of one.
>>
>
>Memory allocated via resize() involves /construction/ of the required
>objects - i.e. invocation of their constructor via e.g. placement new.
>On the contrary, reserve() allocates memory but does /not/ construct the
>objects. It is UB to access objects before their construction.

POD types do not need to be constructed. As long as the memory is addressable
thats all that matters. Why do you think I used ints as an example?

[MrSpo...@s879vvmwpgee7rpqv.net]

Thats not a crash, thats a compiler runtime warning. If it accessed OOB memory
then the OS would segfault it.

>And this is not a fault of those compilers, the fault is in your code.
>This is why you need to change your code and not claim that the whole
>world is wrong and only your ideas are right.

Absolutely none of you seem to understand the what reserve() is doing.

Reserve() for vector<int> v is equivalent to:

int v[10000];

Resize() would be:

int v[10000];
bzero(v,sizeof(v));

Either way you can access the memory up to the array size except in the first
case the value is undefined.

[MrSpook_...@fceufv2.ac.uk]

Knocking on wood is superstitious drivel in the english speaking world.
You do it to ward off bad luck.

[David Brown]

No, they are not.

They need to be able to work with allocators that provide nothing beyond
the specified API. But that does not mean that they can use more
information and more methods when dealing with standard library allocators.

(You snipped my other points - is that because you don't understand
them, or because you know they show you are wrong but won't admit it?)

[Bonita Montero]

> The library implementor knows how std::allocator gets its memory,
> because he wrote that earlier.

The allocator template-parameter is replaceable, so the code calling
it has to adhere to its interface. So there's no opportunity to get
the size actually physically allocated.

[Bonita Montero]

> They need to be able to work with allocators that provide nothing beyond
> the specified API. But that does not mean that they can use more
> information and more methods when dealing with standard library allocators.

The allocator template-parameter is replaceable, so the code has to
content itself with the API a allocator provides.

[Manfred]

You also asked why there is a need for both reserve() and resize(),
which is another formulation of the same question.
I gave the answer and the rationale for it.

If you want to try and find an exception for a special case of some
specifically qualified clause of some sort (and if you are willing to
bet your job on it), go ahead and have fun diving into the 1800+ pages
of legalese of the standard.

A word of advise: a quick look at [intro.object] shows:

1. An object is created by a definition (6.2), by a new-expression
(7.6.2.7), by an operation that implicitly creates objects (see below),
when implicitly changing the active member of a union (11.5), or when a
temporary object is created (7.3.4, 6.7.7)

Now you may want to look into "implicitly created objects":
13. "[Note: Some functions in the C++ standard library implicitly create
objects (20.10.9.2, 20.10.12, 21.5.3, 26.5.3). —end note]"

Then you are referenced a.o. to 20.10.9.2 [allocator.traits.members]
[[nodiscard]] static constexpr pointer allocate(Alloc& a, size_type n);
1. Returns: a.allocate(n).

Which redirects you to Allocator::allocate; for the default allocator
you have [allocator.members]:

[[nodiscard]] constexpr T* allocate(size_t n);
2 Mandates: T is not an incomplete type (6.8).
3 Returns: A pointer to the initial element of an array of n T.
4 Remarks: The storage for the array is obtained by calling
::operator new (17.6.2), but it is unspecified when or how often this
function is called. This function starts the lifetime of the array
object, but not that of any of the array elements.

Note the last sentence: "This function starts the lifetime of the array
object, but not that of any of the array elements"

Obviously it's perfectly possible that that's not the end of it.
Have fun!

[Paavo Helde]

11.06.2021 14:38 MrSpo...@s879vvmwpgee7rpqv.net kirjutas:
> On Fri, 11 Jun 2021 14:26:18 +0300
> Paavo Helde <myfir...@osa.pri.ee> wrote:
>> 11.06.2021 12:19 MrSpoo...@5ooodqy.co.uk kirjutas:
>>> an area of memory defined as an integer, unlike an object that will have
>>> complex interactions with default or user methods that could easily cause a
>>> crash if you try and use any of them when uninitialised. Yes, it'll probably
>>> be some random value but it won't crash.
>>
>> Yet another flat-earther who thinks his beliefs somehow prescribe the
>> world how to behave.
>>
>> Just compile your program in MSVC Debug mode or with g++
>> -D_GLIBCXX_DEBUG and witness by your own eyes it is crashing! What else
>> do you want?
>
> Thats not a crash, thats a compiler runtime warning. If it accessed OOB memory
> then the OS would segfault it.
>

Explain that to the customer who is complaining that your program
crashes when she compiles it with a mainstream compiler with her
favorite settings.

[MrSpook...@21yhpi_n4fck_wfz.org]

On Fri, 11 Jun 2021 14:14:53 +0200

Manfred <non...@add.invalid> wrote:
>On 6/11/2021 1:34 PM, MrSpook_0nG@p900whw6_n8r7ovwuul.ac.uk wrote:
>> On Fri, 11 Jun 2021 13:22:37 +0200
>> Manfred <non...@add.invalid> wrote:
>>> On 6/11/2021 12:17 PM, MrSpook_...@tu45utvus6nuc.tv wrote:
>>>> Does work. There's no reason why it wouldn't unless you can think of one.
>>>>
>>>
>>> Memory allocated via resize() involves /construction/ of the required
>>> objects - i.e. invocation of their constructor via e.g. placement new.
>>> On the contrary, reserve() allocates memory but does /not/ construct the
>>> objects. It is UB to access objects before their construction.
>>
>> POD types do not need to be constructed. As long as the memory is addressable
>
>> thats all that matters. Why do you think I used ints as an example?
>>
>
>You also asked why there is a need for both reserve() and resize(),

And I haven't had a proper answer yet. I see zero reason for reserve() existing.

>If you want to try and find an exception for a special case of some
>specifically qualified clause of some sort (and if you are willing to

I was making a point about reserve() allocating memory, nothing more.

>bet your job on it), go ahead and have fun diving into the 1800+ pages
>of legalese of the standard.

I'll leave that to the aspies.

tl;dr

[MrSpook...@5szcyauh_pjzi228wvwn.info]

On Fri, 11 Jun 2021 15:14:57 +0300

More likely his unless you live in a parallel woke universe. I'm simply
pointing out that reserve() reserves memory that allows PODs to be used
which leads on to my point as to whats the point of it when resize() should
always be used.

[Paavo Helde]

11.06.2021 15:52 MrSpook_uQjuVe@5szcyauh_pjzi228wvwn.info kirjutas:
> On Fri, 11 Jun 2021 15:14:57 +0300
> Paavo Helde <myfir...@osa.pri.ee> wrote:
>> 11.06.2021 14:38 MrSpo...@s879vvmwpgee7rpqv.net kirjutas:
>>> On Fri, 11 Jun 2021 14:26:18 +0300
>>> Paavo Helde <myfir...@osa.pri.ee> wrote:
>>>> 11.06.2021 12:19 MrSpoo...@5ooodqy.co.uk kirjutas:
>>>>> an area of memory defined as an integer, unlike an object that will have
>>>>> complex interactions with default or user methods that could easily cause a
>>
>>>>> crash if you try and use any of them when uninitialised. Yes, it'll
>> probably
>>>>> be some random value but it won't crash.
>>>>
>>>> Yet another flat-earther who thinks his beliefs somehow prescribe the
>>>> world how to behave.
>>>>
>>>> Just compile your program in MSVC Debug mode or with g++
>>>> -D_GLIBCXX_DEBUG and witness by your own eyes it is crashing! What else
>>>> do you want?
>>>
>>> Thats not a crash, thats a compiler runtime warning. If it accessed OOB
>> memory
>>> then the OS would segfault it.
>>>
>>
>> Explain that to the customer who is complaining that your program
>> crashes when she compiles it with a mainstream compiler with her
>> favorite settings.
>
> More likely his unless you live in a parallel woke universe.

Obviously you missed the point why I used "her" here :-) I conclude you
are living alone.

> I'm simply
> pointing out that reserve() reserves memory that allows PODs to be used
> which leads on to my point as to whats the point of it when resize() should
> always be used.

Reserve() is an optimization feature which can increase the speed and
reduce the memory usage of the program when used properly. As such, it
is not necessary to use it, as these potential performance improvements
are modest and do not make big-O difference.

However, reserve() might also be necessary in the case when the objects
placed in the container cannot have working copy or move constructors,
or they are extremely expensive. If you have reserved enough memory in
the vector, then emplace_back() et al are guaranteed to not reallocate
the buffer, so no copy or move constructor is called.

Now one could argue that it would be almost always possible to provide a
cheap move constructor, and therefore there is no inherent need for
reserve(). There might be some truth in it, but the thing is that we
didn't have move constructors before 2011, and vector::reserve() was
there beforehand, as a way to partially compensate for this lack.

[David Brown]

Sometimes this is like talking to a brick wall. You are so convinced
that you know /everything/ that you won't try to read, and you certainly
won't try to /think/.

You asked a question in this thread. I gave you the answer. You reject
that because of your incorrect preconceptions. You can go back to being
ignorant - I'm done trying to help.

If you decide to read what other people post and perhaps even rub a
couple of brain cells together to understand the help you are given, let
us know.

Oh, and /please/ do us the courtesy of learning how to quote properly
with attributions.

[Bonita Montero]

You say:

> A C++ standard library implementation can quite happily have
> undocumented features that allow std::vector to see how much
> memory it has /actually/ een allocated, and let it set "capacity"
> a little higher.

And this can't be true since the container-implementation has
to stick with what an allocator provides. Otherwise it wouldn't
be replaceable.

[MrSpook...@i1z834r.net]

On Fri, 11 Jun 2021 16:37:36 +0300
Paavo Helde <myfir...@osa.pri.ee> wrote:

>11.06.2021 15:52 MrSpook_uQjuVe@5szcyauh_pjzi228wvwn.info kirjutas:
>>> Explain that to the customer who is complaining that your program
>>> crashes when she compiles it with a mainstream compiler with her
>>> favorite settings.
>>
>> More likely his unless you live in a parallel woke universe.
>
>Obviously you missed the point why I used "her" here :-) I conclude you
>are living alone.

Obviously I did. And you're wrong.

>However, reserve() might also be necessary in the case when the objects
>placed in the container cannot have working copy or move constructors,

OK, that is a good reason for it.

[Manfred]

On 6/11/2021 3:37 PM, Paavo Helde wrote:
> 11.06.2021 15:52 MrSpook_uQjuVe@5szcyauh_pjzi228wvwn.info kirjutas:
>> On Fri, 11 Jun 2021 15:14:57 +0300
>> Paavo Helde <myfir...@osa.pri.ee> wrote:
>>> 11.06.2021 14:38 MrSpo...@s879vvmwpgee7rpqv.net kirjutas:

[...]

>> I'm simply
>> pointing out that reserve() reserves memory that allows PODs to be used
>> which leads on to my point as to whats the point of it when resize()
>> should
>> always be used.
>
> Reserve() is an optimization feature which can increase the speed and
> reduce the memory usage of the program when used properly. As such, it
> is not necessary to use it, as these potential performance improvements
> are modest and do not make big-O difference.
>
> However, reserve() might also be necessary in the case when the objects
> placed in the container cannot have working copy or move constructors,
> or they are extremely expensive. If you have reserved enough memory in
> the vector, then emplace_back() et al are guaranteed to not reallocate
> the buffer, so no copy or move constructor is called.
>
> Now one could argue that it would be almost always possible to provide a
> cheap move constructor, and therefore there is no inherent need for
> reserve(). There might be some truth in it, but the thing is that we
> didn't have move constructors before 2011, and vector::reserve() was
> there beforehand, as a way to partially compensate for this lack.

but emplace_back was first standardized in 2011 too, which would make it
hard to construct an object in-place before then anyway.
The argument is still valid though.

[Manfred]

On 6/11/2021 4:35 PM, Bonita Montero wrote:
> You say:
>
> ...
Her interpretation of proper attribution - lol.

[Bonita Montero]

>> You say:
>>  ...

> Her interpretation of proper attribution - lol.

If there's nothing more to say I'm satisfied. ;-)

[Christian Gollwitzer]

Am 11.06.21 um 16:35 schrieb Bonita Montero:

By replaceable you mean that the template for, say, std::vector uses the
same code reagrdles off the allocator. Can this not be circumvented by
partial specialization on the allocator template argument?

Christian

[Bo Persson]

So you don't think it is possible to do something like:

if constexpr (is_same_v<_Alloc, std::allocator<_Ty>>)
// use special knowledge
else
// fall-back for user defined allocator

[Sam]

Bonita Montero writes:

>> Just because something isn't specified for a library class, doesn't mean
>> that the implementation is prohibited from having it.
>
> The containers _always_ use allocators that provide the allocatotor
> -interface which is specified under the link I've shown you. And
> with this there is no opportunity to get the size of the memory
> actually allocated.

C++ library allocators are free to export additional, implementation-
specific interfaces that C++ library container templates can check for and
use, if available.

The C++ standard does not require allocators to provide ONLY the interfaces
that are specified in the standard. They are free to have implementation-
specific interfaces too, that other templates in the C++ library know how to
use, and will use them when instantiated with a standard allocator, from the
C++ library.

Of course, those C++ container templates cannot require the allocator they
use to implement these non-standard interfaces. The C++ standard reserves
certain symbol names for implementation-specific usage. If an allocator
implements the implementation-specific interface (using symbol names that
are reserved for the implementation's use), then the C++ template can take
advantage of it; otherwise the template will fall back to the interface
that's specified in the C++ standard. This is fairly simple to do using
SFINAE or concepts.

[Sam]

SFINAE, or concepts, can be used to determine whether the allocator
implements an extended interface that's supported by the library and then
use it, if it exists. Otherwise the container template will use only the
standard-specified interface.

[Bonita Montero]

> SFINAE, or concepts, can be used to determine whether the allocator
> implements an extended interface that's supported by the library and
> then use it, if it exists. Otherwise the container template will use
> only the standard-specified interface.

Extremely unlikely.

[Bonita Montero]

Extremely unlikely that there's a specializartion for std::allocator
and a specific std::allocator has that behaviour without exposing it
to other users.

[Bonita Montero]

> So you don't think it is possible to do something like:
> if constexpr (is_same_v<_Alloc, std::allocator<_Ty>>)
>     // use special knowledge
> else
>    // fall-back for user defined allocator

Extremly unlikely that such a container-behaviour exists.

[Öö Tiib]

But no one discussed what there exists? How it is argument what
the libraries implement? The C++ standard is not meant to be reactive
to what libraries implement. It is specification that tries to be visionary
and so to allow things that (people keep telling to you) are possible
and potentially profitable.

So stop arguing with what no one has claimed, and better go fix your
garbage code that trashed its performance with misuse of features
that you do not understand like reserve and/or shrink_to_fit. Do not
use features that you do not understand.

[Bonita Montero]

> But no one discussed what there exists? How it is argument what
> the libraries implement? The C++ standard is not meant to be reactive
> to what libraries implement. It is specification that tries to be visionary
> and so to allow things that (people keep telling to you) are possible
> and potentially profitable.

C++ standard-libraries are designed that they indirectly use malloc().
That's while you can replace malloc and change all the allocations in
you program. Having such a special allocator that returns the size
actually allocated would break that.

[Öö Tiib]

You seem like neither reading what others write nor knowing what you
talk about. In what implementation and what calls malloc? Can't it (that
what) be replaced globally by programmer? Where did anyone suggest
to return size? What it was that was supposed to return size?

[Bo Persson]

Not really.

It is true that std::allocator has to use operator new, but this is what
the standard says about that operator:

"Executes a loop: Within the loop, the function first attempts to
allocate the requested storage. Whether the attempt involves a call to
the C standard library functions malloc or aligned_­alloc is unspecified."

http://eel.is/c++draft/new.delete#single-4.1

[Bonita Montero]

> You seem like neither reading what others write nor knowing what you

> talk about. ...

I said that it "indirectly" calls malloc.
It calls it via std::allocator.

[Bonita Montero]

> It is true that std::allocator has to use operator new, but this is what
> the standard says about that operator:
> "Executes a loop: Within the loop, the function first attempts to
> allocate the requested storage. Whether the attempt involves a call to
> the C standard library functions malloc or aligned_­alloc is unspecified."

Can't you read, moron ? I said that it "indirectly calls malloc",
i.e. everything is built on top of malloc(). I.e. new calls malloc,
std::allocator<> calls new and the container calls std:allocator.
That's what the user expects because in this way you could replace
the whole C++ memory-alloction by replacing malloc() like a few
memory-allocators like mimalloc, jemalloc, tcmallog e.g. do it.

[Öö Tiib]

What is it? Where and when is std::allocator required to call what?
You continue not knowing what you talk about.

[Bonita Montero]

>> I said that it "indirectly" calls malloc.
>> It calls it via std::allocator.

> What is it? Where and when is std::allocator required to call what?
> You continue not knowing what you talk about.

std::allocator isn't required to do that, but at last everyone expects
it to call malloc() in some way; it doesn't matter if it does this via
new or directly. This is to meet the expectations that the
memory-allo-ocator is globally replaceable.

[Öö Tiib]

Continuing to prove that you do not know what you talk about? The
std::allocator::allocate is required to get the memory from operator
new that programmer can globally replace. And it is specially said
in standard that it is unspecified when and how operator new is
called for acquiring that memory. AFAIK libc++ even uses that
freedom. But default operator new may call HeapAlloc() of
Windows if it so wants, that is no way regulated.

[Bonita Montero]

> But default operator new may call HeapAlloc() of
> Windows if it so wants, that is no way regulated.

It's not specified how I described it, but it's expected that
the containers _indirectly_ allocate via malloc() so that the
memory-manamgement is replaceable. There are a lot of malloc()
-replacemnt like jemalloc, mimalloc, Hoard, tcmalloc or what-
ever and to work with these a standard-libary has to work in
that way I described - there are a lot of people that expect
that so that the writers of the standard-libaries imeplement
them in an expectable behaviour.

[Alf P. Steinbach]

C and C++ are two different languages.

- Alf

[Bo Persson]

So where does the standard say that "involves a call" only means a
direct call? And that an indirect call is still required even when a
direct call is not?

[Bonita Montero]

But a lot of people still expect that C++ memory-allocation indirectly
bases on malloc() and is thereby replaceable.

[Bonita Montero]

> So where does the standard say that "involves a call" only means a
> direct call? And that an indirect call is still required even when a
> direct call is not?

The standard doesn't guarantee that, but the standard libary implemen-
tors don't use sth. different than indirectly malloc() to make the whole
memory-allocation of the code replaceable. If a sandard libary wouldn't
be implemented in that way mimalloc, jemalloc, tcmalloc, Hoard ...
woudln't work.

[Bonita Montero]

> C and C++ are two different languages.

And this isn't absolutely true since most about 95% of the things
you can do in C you can do also in C++. And it is very common to
use C-code from C++-code with small adaptions.

[Alf P. Steinbach]

Yes, maybe they do. I expected that somewhere in the late 1990's, after
I'd started working as a consultant. I'd inadvertently used `free` to
deallocate something POD-ish allocated with `new`, it worked, and when
someone remarked on it I argued about the same as you do now. I was
ashamed when I, much later, understood that I was in the wrong, entirely
wrong, that it was not just a formal rule or convention I'd broken.

In my defense, I learned C++ from Bjarne's original "The C++ Programming
Language", and things were very much more C-ish at that time.

- Alf

[Bonita Montero]

> Yes, maybe they do. I expected that somewhere in the late 1990's, after
> I'd started working as a consultant. I'd inadvertently used `free` to
> deallocate something POD-ish allocated with `new`, it worked, and when

> someone remarked on it I argued about the same as you do now. ...

That's not what I meant.

[David Brown]

And there is, of course, no requirement that things end up as a call to
"malloc" here. In particular, since C++14 (IIRC) there are sized
overloads of delete which open the possibility of having more efficient
memory allocation systems than traditional malloc/free as the heap no
longer has to track the sizes of the allocated objects. (That has
always struck me as a poorly considered aspect of C's malloc/free,
leading to significant inefficiencies.)

And even if Bonita was right that everything ends up in a call to
malloc, she would /still/ be wrong. Malloc is part of the
implementation - the implementation can have a way to find out the size
of the memory actually allocated (since it knows all the details of the
heap implementation), and make that available to other implementation
code such as the C++ container library.

[David Brown]

You have already established that what /you/ personally expect is a
different thing from what languages, compilers and tools document that
they do, and what other programmers expect. This is just another one of
your unjustified assumptions based on nothing but your own lack of
imagination and inability or unwillingness to learn how C++ and the
tools are actually specified.

[Sam]

Whether it is unlikely or not, it's perfectly doable.

[Sam]

I just explained how this can be done. Nobody has to replace malloc. Just
because you are incapable of wrapping your brain around this concept doesn't
mean that it cannot be done.

[Sam]

Bonita Montero writes:

>> But default operator new may call HeapAlloc() of
>> Windows if it so wants, that is no way regulated.
>
> It's not specified how I described it, but it's expected that
> the containers _indirectly_ allocate via malloc() so that the

Maybe you expect that, but not anyone who actually understands C++.

[Bonita Montero]

> You have already established that what /you/ personally expect is a
> different thing from what languages, compilers and tools document that

> they do, ...

No, because of what I said you can rely on this.

[Bonita Montero]

>> It's not specified how I described it, but it's expected that
>> the containers _indirectly_ allocate via malloc() so that the

> Maybe you expect that, but not anyone who actually understands C++.

That's not a matter of how C++ is defined but how its actually
imple- mented. As many people expect the whole memory-allocatoin
to be replaceable via exchanging malloc() and free() the major
C++-runtimes are all implemented in that way.

[Bonita Montero]

> And there is, of course, no requirement that things end up as a call
> to "malloc" here. In particular, since C++14 (IIRC) there are sized
> overloads of delete which open the possibility of having more efficient
> memory allocation systems than traditional malloc/free as the heap no

> longer has to track the sizes of the allocated objects. ..

There aren't no such special implementations since the allocations only
have to adhere to maxalign_t.

> And even if Bonita was right that everything ends up in a call
> to malloc, she would /still/ be wrong. Malloc is part of the
> implementation - the implementation can have a way to find out the size
> of the memory actually allocated (since it knows all the details of the
> heap implementation), and make that available to other implementation
> code such as the C++ container library.

malloc() has to be replaceable - that's what a lot of developers expect
because they want to exchange the memory-allocators to faster implemen-
tations. Because of that the major C++ runtimes are all built on top of
malloc().

[Bonita Montero]

>> Extremely unlikely.

> Whether it is unlikely or not, it's perfectly doable.

A lot of people expect the C++-container indirectly base on malloc()
to have replaceable memory-allocation to install a faster allocator
like mimalloc. Therefore it's the most realistic assumption to say
that everything in the standard-library indirectly bases on malloc().

[Sam]

What "many people expect" is immaterial. As long as an implementation is in
compliance with the C++ standard, if it goes against their expectations,
well, too bad so sad.

[Sam]

Once more: what "people expect" is immaterial. As long as a particular
implementation is in compliance with the C++ standard, then that's the end
of it. And I'm afraid that is not the case. The C++ standard explicitly
states that it does not specify whether operator new uses malloc.

# 17.6.2.1 Single-object forms [new.delete.single]
#
# [[nodiscard]] void* operator new(std::size_t size);
#
# [[nodiscard]] void* operator new(std::size_t size, std::align_val_t alignment);
#
# …
#
# Whether the attempt involves a call to the C standard library functions
# malloc or aligned_alloc is unspecified.

The C++ standard authoritatively asserts that it's unspecified whether new
is implemented in terms of malloc. Too bad if someone's expectations were
otherwise.

Now, I don't actually see what that has to do with the original proposition
of std::vector::reserve()'s optimization, but since (for some odd reason)
you chose to sidetrack into your expectations of new's behavior, I have to
set the record straight:

The C++ standard does not require that operator new must be implemented in
terms of malloc. Feel free to "expect" otherwise. Your expectations may not
be realized, unfortunately.

The End.

[Ian Collins]

On 12/06/2021 21:24, Öö Tiib wrote:
> On Saturday, 12 June 2021 at 12:15:53 UTC+3, Bonita Montero wrote:
>>>> I said that it "indirectly" calls malloc.
>>>> It calls it via std::allocator.
>>
>>> What is it? Where and when is std::allocator required to call what?
>>> You continue not knowing what you talk about.
>> std::allocator isn't required to do that, but at last everyone expects
>> it to call malloc() in some way; it doesn't matter if it does this via
>> new or directly. This is to meet the expectations that the
>> memory-allo-ocator is globally replaceable.
>
> Continuing to prove that you do not know what you talk about?

You do realise that you are arguing with someone who can't even learn to
quote?

--
Ian.

[Bonita Montero]

> Once more: what "people expect" is immaterial. ...

It's realistisc.

Rest of your stupid stuff unread.

[Bonita Montero]

> What "many people expect" is immaterial. ...

It's the most realistic assumption.

[MrSpook_...@3dryi7no.gov]

On Sat, 12 Jun 2021 18:59:38 -0400
Sam <s...@email-scan.com> wrote:
>This is a MIME GnuPG-signed message. If you see this text, it means that
>your E-mail or Usenet software does not support MIME signed messages.
>The Internet standard for MIME PGP messages, RFC 2015, was published in 1996.
>To open this message correctly you will need to install E-mail or Usenet
>software that supports modern Internet standards.

Or not. Anyway...

>The C++ standard authoritatively asserts that it's unspecified whether ne=
>w =20
>is implemented in terms of malloc. Too bad if someone's expectations were =20
>otherwise.

Hardly surprising given that C++ might us used on systems where malloc() doesn't
exist. Some people forget there are more platforms in the programming world
than just Windows or *nix.

[Richard Damon]

On 6/13/21 1:31 AM, Bonita Montero wrote:
>> What "many people expect" is immaterial. ...
>
> It's the most realistic assumption.
>
>

Maybe a reasonable assumption on many platforms, but an incorrect one,
and one that can lead to hard to find bugs when it isn't true.

[Bonita Montero]

> Maybe a reasonable assumption on many platforms, but an incorrect
> one, and one that can lead to hard to find bugs when it isn't true.

No, this doesn't imply any possible bugs.

[Sam]

Bonita Montero writes:

>> Once more: what "people expect" is immaterial. ...
>
> It's realistisc.

Realistically, people are also always going to whine when they relied on
unspecified behavior, and their code breaks.

Also realistically: nobody will care.

> Rest of your stupid stuff unread.

I believe you 100%, just like I believe that you will not read every
character of this post.

[Sam]

Bonita Montero writes:

>> What "many people expect" is immaterial. ...
>
> It's the most realistic assumption.

Has anyone happen to mention what happens when you assume, all the time?

[Sam]

Ok, you go ahead and write some code that depends on it, then wait when it
breaks, inevitably, after a compiler/library upgrade, then get back to us.

We'll figure out whether it's a bug, or not, at that time.

[Bonita Montero]

>>> Once more: what "people expect" is immaterial. ...

>> It's realistisc.

> Realistically, people are also always going to whine when
> they relied on unspecified behavior, and their code breaks.

That's sth. totally different here and I told whether it's the most
reasonable assumption: there are many people that expect their alloca-
tions to be globally replaceable. Because of that C++ memory-allcoation
also indiretly bases on malloc() in some way.

[Bonita Montero]

>>> Maybe a reasonable assumption on many platforms, but an incorrect
>>> one, and one that can lead to hard to find bugs when it isn't true.

>> No, this doesn't imply any possible bugs.

> Ok, you go ahead and write some code that depends on it, then wait when
> it breaks, inevitably, after a compiler/library upgrade, then get back
> to us.

Tell me the bug when you install a malloc()-replacement ...

[Sam]

Those expectations are based on overriding operator new and delete. Both
must be overridden, otherwise the behavior is unspecified.

As I've documented: the C++ standard does not require operator new to use
malloc. Therefore, if an application wants to use custom memory allocation
and wants to be portable it must override both new and delete.

If someone's expecting to be able to override only operator new, then use
the default operator delete, then since the default operator delete is
"expected" to use free, the overridden operator new has no choice but to use
malloc too. Wonderful, but then what? What possible value-added can operator
new, in addition to mallocing? There's nothing else to do.

Perhaps one wants to override malloc in order to simply log memory
allocations in order to detect leaks. But then you have no choice but to
override operator delete and log it too.

So, no matter which way you turn, any kind of "expectations" must override
both. But then, whether new/delete uses malloc/free becomes a moot point,
and the default implementation does not need to use it, because anyone woh
overrides them will, by necessity, have to override both.

And that's why you're wrong.

You are welcome to prove me wrong by offering your own example of a
practical override of operator new, and operator new only, and actually
doing something useful, "expecting" that delete will simply call free.

But you will probably just not read any of this, right?