default initialization when creating a new entry in a container

[Bonita Montero]

Does anyone know an easy way to prevent default-initialization of
new elements in a container? I.e. if we'd have a vecor<int>, when
I do a .resize( s ), the new elements would become initalized with
int(), meaning zero. Of course I could create a class containing an
int which isn't initialized in the constructor, but this is rather
unhandy.

[Thiago Adams]

Check if 'reserve' solves your problem.

https://en.cppreference.com/w/cpp/container/vector/reserve

[Bonita Montero]

>> Does anyone know an easy way to prevent default-initialization of
>> new elements in a container? I.e. if we'd have a vecor<int>, when
>> I do a .resize( s ), the new elements would become initalized with
>> int(), meaning zero. Of course I could create a class containing an
>> int which isn't initialized in the constructor, but this is rather
>> unhandy.

> Check if 'reserve' solves your problem.
> https://en.cppreference.com/w/cpp/container/vector/reserve

.reserve() doesn't grow the vector so that .end() is adjusted propery.
And with debug-builds the []-operator and the iterators might be bounds
-checking so that a debugger might break if you access the vector beyond
.end(). And I'm even mot sure if .reserve() is oblgated to really grow
the capacity; I think it could do nothing in every case in an unopti-
mized implementation.

[Paavo Helde]

On 25.03.2019 12:57, Bonita Montero wrote:
> Does anyone know an easy way to prevent default-initialization of
> new elements in a container? I.e. if we'd have a vecor<int>, when
> I do a .resize( s ), the new elements would become initalized with
> int(), meaning zero.

So do not use resize(). Use push_back(), emplace_back() or range
insert(), possibly after a suitable reserve().

What's your motivation to avoid zero initialization? If performance,
then you should first profile your app to see if it's really a problem.

[Öö Tiib]

Why we need uninitialized elements? Do we want to initialize those
in random order? In what situation we need that?
Only std::array (as aggregate) can be made with elements in
uninitialized state. With std::vector it can't be done so the valid
pattern is that we first reserve() and then emplace_back() the
elements to it.

[Bonita Montero]

> Why we need uninitialized elements?

If you overwrite the elements later the first initialization isn't
necessary. And compilers are not smart enough to optimize away the
zero-initialization.

[Öö Tiib]

The implied question (by parts of my answer that you erased) is why
not to first reserve() and later emplace_back()?

[Alf P. Steinbach]

Probably because the array is filled by someone else's C style API.

One can

* take the performance hit and copy the raw array used for the API, or

* make one's own little array wrapper to automate the lifetime
management, e.g. based on `unique_ptr`, and pass that around, or

* do a really hacky thing like defining an `int` wrapper as item type
for a `vector` and then reinterpreting the buffer pointers (hi ho hi ho,
off to that faraway land we go, oh oh oh).


Anyway I think it helps to define a span type to use for formal argument.

That way one can remove much of the dependency on a particular array
representation.


Cheers!,

- Alf

[Bonita Montero]

>> If you overwrite the elements later the first initialization isn't
>> necessary. And compilers are not smart enough to optimize away the
>> zero-initialization.

> The implied question (by parts of my answer that you erased) is why
> not to first reserve() and later emplace_back()?

Because this isn't that efficient like growing the vecor in one
step with uninitialized values and then initializing the values.

[Öö Tiib]

Why? This is doing exactly that. The reserve() allocates
uninitialized buffer and emplace_back()s initialize values in it.
With what platform the difference in efficiency was measured?
It sounds pretty much like an issue of quality of implementation.

[Paavo Helde]

Note that reserve() + emplace_back() is exactly that: growing the vector

in one step with uninitialized values and then initializing the values.

It might indeed be that using raw allocation plus assignment would be
slightly faster. If the profiler really shows there is a problem, you
can just use array new as at this optimization level you cannot use most
of std::vector functionality anyway:

std::unique_ptr<int[]> buffer(new int[n]);

AFAIK this is the last use case for 'new' and even this will be replaced
in C++20 with:

auto buffer = std::make_unique_default_init<int[]>(n);

[Bonita Montero]

> Why? This is doing exactly that. The reserve() allocates
> uninitialized buffer and emplace_back()s initialize values
> in it.

emplace_back increases the size for each enlargement.

[Bonita Montero]

> Note that reserve() + emplace_back() is exactly that: growing the vector
> in one step with uninitialized values and then initializing the values.

No, emplace_back increases the size of the container for each call
whereas the solution I'm thinking about increases the size in one
step.

[Martijn van Buul]

* Paavo Helde:

> std::unique_ptr<int[]> buffer(new int[n]);
>
> AFAIK this is the last use case for 'new'

... that you're willing to consider.

Please show me an implementation of any of the containers, or any of the
"smart" pointers that does not rely on 'new'.

--
Martijn van Buul - pi...@dohd.org

[leigh.v....@googlemail.com]

On Tuesday, March 26, 2019 at 2:53:51 PM UTC, Martijn van Buul wrote:
> * Paavo Helde:
> > std::unique_ptr<int[]> buffer(new int[n]);
> >
> > AFAIK this is the last use case for 'new'
>
> ... that you're willing to consider.
>
> Please show me an implementation of any of the containers, or any of the
> "smart" pointers that does not rely on 'new'.

Are you being deliberately obtuse? Obviously Paavo wasn't thinking about implementers of the Standard Library because, like, 0.0000001% of the programmer population are Standard Library implementers.

/Leigh

[Bonita Montero]

>> std::unique_ptr<int[]> buffer(new int[n]);
>> AFAIK this is the last use case for 'new'

> Please show me an implementation of any of the containers,
> or any of the "smart" pointers that does not rely on 'new'.

The difference here is that the above solution doesn't initialize
the ints.

[guinne...@gmail.com]

emplace_back() increases the /logical/ size (as reported by size()) of the
container for each emplacement. It only increases the /physical/ allocation
(as reported by capacity()) if size() == capacity().

By first using reserve(), you can increase the physical allocation (but not
the logical size), ready to accept a number of emplacements:

std::vector< int > container; // capacity() == 0, size() == 0
container.reserve( 3 ); // capacity() == 3, size() == 0

// no re-allocations will occur during the execution of the following lines:

container.emplace_back( 42 ); // capacity() == 3, size() == 1
container.emplace_back( 42 ); // capacity() == 3, size() == 2
container.emplace_back( 42 ); // capacity() == 3, size() == 3

// now size() == capacity(), so re-allocation will occur on the next line:

container.emplace_back( 42 ); // capacity() == 4 or more, size() == 4

[james...@alumni.caltech.edu]

True, but increasing the size isn't an expensive operation. It's
increasing the capacity that's expensive, and when you call reserve(),
it increases the capacity in a single step, which is what you really
should be concerned about.

[Bonita Montero]

>> emplace_back increases the size for each enlargement.

> emplace_back() increases the /logical/ size (as reported by size()) of the
> container for each emplacement.

I didn't say anything different. The term "size" here means the
logical aize because if you call .size(), you get the logical size.

The issue here is that the container either has a size-member internally
(rather unlikely) or a begin- and an end-pointer (very likely). The lat-
ter is usually adjustet for each emplace_back or push_back; that's not
very efficient compared to growing the size of the container with its
elements not initialized in one step.

[Bonita Montero]

>> No, emplace_back increases the size of the container for each call
>> whereas the solution I'm thinking about increases the size in one
>> step.

> True, but increasing the size isn't an expensive operation.

If you have a expensive initialization of the elemens increasing
the size puts not much weight on that. But if you have a cheap
initialization, growing the size might have an essential share.

[Paavo Helde]

On 26.03.2019 16:53, Martijn van Buul wrote:
> * Paavo Helde:
>> std::unique_ptr<int[]> buffer(new int[n]);
>>
>> AFAIK this is the last use case for 'new'
>
> ... that you're willing to consider.

Yes, I should have clarified I meant application level programming.

>
> Please show me an implementation of any of the containers, or any of the
> "smart" pointers that does not rely on 'new'.

Indeed, containers may use 'new' a lot, but this would then be placement
new and not memory allocation. Memory is typically allocated through
special allocator classes.

Smartpointers don't allocate anything at all, they just encapsulate
already allocated objects.

[Bonita Montero]

> Please show me an implementation of any of the containers,
> or any of the "smart" pointers that does not rely on 'new'.

No, the containers rely on std::allocator and how this works is
exchangeable.
Unfortunately std::allocator works with new and not with some other kind
of memory-allocation. The thing is simply that when you have very large
allocations, the're not backed up by the internal heap but by contignous
pages of the OS (i.e. allocated through mmap() or VirtualAlloc(). And
when new indirectly allocates its memory with this means, you could
often grow an allocation in-place without allocation a new memory-block
at another location. If std::allocator would have a function that would
enable f.e. vector to ask if a block could be grown in-place before
moving it to another location a lot of overhead would be saved.

[James Kuyper]

I recommend doing careful profiling to confirm that this is a
significant problem before expending a lot of effort to avoid it. I
think you'll be surprised at just how little difference it makes - you
might even find that it's infinitesimally faster doing it the way that
seems like it should be slower.

[Mr Flibble]

On 26/03/2019 16:32, Paavo Helde wrote:
> Smartpointers don't allocate anything at all, they just encapsulate
> already allocated objects.

Not true: std::shared_ptr may allocate a control block.

/Flibble

--
“You won’t burn in hell. But be nice anyway.” – Ricky Gervais

“I see Atheists are fighting and killing each other again, over who
doesn’t believe in any God the most. Oh, no..wait.. that never happens.” –
Ricky Gervais

"Suppose it's all true, and you walk up to the pearly gates, and are
confronted by God," Bryne asked on his show The Meaning of Life. "What
will Stephen Fry say to him, her, or it?"
"I'd say, bone cancer in children? What's that about?" Fry replied.
"How dare you? How dare you create a world to which there is such misery
that is not our fault. It's not right, it's utterly, utterly evil."
"Why should I respect a capricious, mean-minded, stupid God who creates a
world that is so full of injustice and pain. That's what I would say."

[james...@alumni.caltech.edu]

Either way, it's a single increment of either a counter or a pointer per
element. Such an imcrement will also occur, not necessarily in the same
variable, during the loop that executes when you initialize the array
with a large number of elements at once, so you don't actually save
anything by doing it all at once.

It's a very minor cost compared to all the other things that need to be
done, and not easily avoided. You should concentrate on thinking about
how many memory allocations occur, because they're fairly expensive, and
how many constructor calls occur, because they, depending upon the type,
they might be expensive.

[Bonita Montero]

> It's a very minor cost compared to all the other things that need to be

> done, ...

That depends on what you write.

[Ian Collins]

Can you cite an example and in doing so, quote correctly?

--
Ian.

[Bonita Montero]

>>> It's a very minor cost compared to all the other things that need to be
>>> done, ...

>> That depends on what you write.

> Can you cite an example and in doing so, quote correctly?

No, but I can not safely rule out cases I indicated.

[Ian Collins]

So you can't quote properly or cite an example where incrementing a
pointer is excessively expensive?

One is just plain rude, the other an inability to back your argument.

--
Ian.

[Vir Campestris]

No.

Or not in any way that matters.

It's technically implementation dependent, but in all the ones I've
looked at:

reserve() calls new() which calls malloc() and gives you a load of
memory. If it's big enough that comes from the operating system directly
not the process local heap, and the OS may well zero all the pages it
gives out for security between processes.

You now have this big lump of memory. Each time you call emplace_back
you construct a new object in the memory you already allocated.

Even if you _don't_ call reserve the implementations tend not to grow
the space by just one unit. They'll allocate a bunch - and the size of
the bunch grows as the array grows. It might go 16,32, 64....1MB, 2MB,
3MB, 4MB.

Andy

[james...@alumni.caltech.edu]

On Tuesday, March 26, 2019 at 5:26:38 PM UTC-4, Vir Campestris wrote:
> On 26/03/2019 14:35, Bonita Montero wrote:
> >> Why? This is doing exactly that. The reserve() allocates
> >> uninitialized  buffer and emplace_back()s initialize values
> > > in it.
> >
> > emplace_back increases the size for each enlargement.
>
> No.

I think it does.

> Or not in any way that matters.

But I agree that it doesn't matter.

> It's technically implementation dependent, but in all the ones I've
> looked at:
>
> reserve() calls new() which calls malloc() and gives you a load of
> memory. If it's big enough that comes from the operating system directly
> not the process local heap, and the OS may well zero all the pages it
> gives out for security between processes.
>
> You now have this big lump of memory. Each time you call emplace_back
> you construct a new object in the memory you already allocated.

Which requires increasing the size.

> Even if you _don't_ call reserve the implementations tend not to grow
> the space by just one unit. They'll allocate a bunch - and the size of
> the bunch grows as the array grows. It might go 16,32, 64....1MB, 2MB,
> 3MB, 4MB.

He said that it increases the size by 1. You're talking about
increasing the capacity, which is a much more important issue. You're
right - that issue is resolved by using reserve(). But he's convinced,
in conflict with expert opinion and without any supporting evidence,
that increasing the size by 1 for each emplaced object will have a
significant detrimental effect on the speed.

[Chris Vine]

The contest is between (a) unnecessarily incrementing the size integer
or end pointer on each emplace_back() or (b) unnecessarily initializing
each element to 0 at the outset.

As she has said, the last is likely to be faster than the first. That
seems like backing her argument to me.

[Chris Vine]

On Tue, 26 Mar 2019 14:51:41 -0700 (PDT)
james...@alumni.caltech.edu wrote:
> He said ...

Have you consider that Bonita may be a woman? Women can code as well.

[Ian Collins]

But they not to be rude..

--
Ian.

[Ian Collins]

On 27/03/2019 11:21, Chris Vine wrote:

Okay, I concede growing the size of the container with its
elements uninitialised in one step would be faster, but it would also be
an impractical thing to standardise given objects may not have a valid
uninitialised state.

So within the confines of standard C++, reserve() and emplace_back() is
the optimal solution.

--
Ian.

[Chris Vine]

Could you recast that, as I can't parse it? (And if you are saying
Bonita has been rude, can you reference the post in question? I didn't
see it but it is possible I have missed it. But as I say I can't
parse your sentence and you may have meant something else.)

[Chris Vine]

On Wed, 27 Mar 2019 11:34:31 +1300

Actually, the optimal solution if using std::vector is probably to size
it at the outset and take the hit of the unnecessary initialization, as
I have said. I think that (b) is likely to be faster than (a). But
measurement will reveal all.

The optimum solution if not using std::vector where the size is fixed is
probably to allocate a C array on the heap or use std::array. This of
course is also "within the confines of standard C++.

[Ian Collins]

Deliberately sipping attributions despite being asked not to do so.
Sipping attributions has always been a no-no on Usenet.

--
Ian.

[Chris Vine]

On Wed, 27 Mar 2019 11:42:37 +1300

What are you talking about? Firstly, snipping redundant material as
here is entirely proper, and secondly no one has asked me to do
anything.

You attempt to imply Bonita is rude (I think) and then you attempt to
imply something else in relation to me which seems unintelligible.

[Ian Collins]

Yep, measure... If default initialisation is non-trivial, sizing at the
outset wouldn't be a good idea.

I probably should have said in the general case, reserve() and
emplace_back() is the optimal solution. This is "fix" the clang-tidy
performance-inefficient-vector-operation will perform when it detects
default constructed vectors being filled with [push/emplace]_back().

--
Ian.

[Ian Collins]

I did no such thing, it is Bonita who snips attributions.

--
Ian.

[Chris Vine]

On Wed, 27 Mar 2019 11:51:55 +1300

Sure, but option (b) would not involve filling with push_back/emplace_back().

Yes, option (a) - reserve/emplace_back() - would be better with element
types with non-trivial default constructors. However, subject to
measurement, I strongly suspect that is not the case with ints.

[James Kuyper]

On 3/26/19 18:21, Chris Vine wrote:
> On Tue, 26 Mar 2019 14:51:41 -0700 (PDT)
> james...@alumni.caltech.edu wrote:
>> He said ...
>

> Have you consider that Bonita may be a woman? ...

No, for some reason I never noticed that she was using a feminine name.

> ... Women can code as well.

Oh yes, I've worked with many female programmers. However, this
newsgroup is disproportionately male, and that may have influenced my
failure to notice.

[James Kuyper]

On 3/26/19 18:35, Chris Vine wrote:
> On Wed, 27 Mar 2019 11:26:56 +1300
> Ian Collins <ian-...@hotmail.com> wrote:
>> On 27/03/2019 11:21, Chris Vine wrote:
>>> On Tue, 26 Mar 2019 14:51:41 -0700 (PDT)
>>> james...@alumni.caltech.edu wrote:
>>>> He said ...
>>>
>>> Have you consider that Bonita may be a woman? Women can code as well.
>>
>> But they not to be rude..
>
> Could you recast that, as I can't parse it?

I think there's a "tend" missing between "they" and "not".

[Jorgen Grahn]

I have (as usual) not kept track of this thread, but I think the main
idea with std::vector is to keep properly constructed objects in a
safe and convenient way. I don't think you can expect it to give
maximum performance in all corner cases.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Paavo Helde]

On 26.03.2019 23:51, james...@alumni.caltech.edu wrote:
>
> He said that it increases the size by 1. You're talking about
> increasing the capacity, which is a much more important issue. You're
> right - that issue is resolved by using reserve(). But he's convinced,
> in conflict with expert opinion and without any supporting evidence,
> that increasing the size by 1 for each emplaced object will have a
> significant detrimental effect on the speed.

Bonita is right in that there is a detrimental effect. I just measured
it. The initialization of a 800 million element unsigned int vector
takes ca 1.3 s with reserve() and emplace_back() and ca 0.9 s with new[]
and assignment. This makes ca half of a nanosecond per element.

If this detrimental effect is significant is another topic and depends
on what this array is used for. If it is not used for anything it can be
just deleted and 100% efficiency gained ;-). If it used for anything
substantial then the initialization overhead will likely turn insignificant.

[Juha Nieminen]

Paavo Helde <myfir...@osa.pri.ee> wrote:
> On 25.03.2019 12:57, Bonita Montero wrote:
>> Does anyone know an easy way to prevent default-initialization of
>> new elements in a container? I.e. if we'd have a vecor<int>, when
>> I do a .resize( s ), the new elements would become initalized with
>> int(), meaning zero.
>
> So do not use resize(). Use push_back(), emplace_back() or range
> insert(), possibly after a suitable reserve().

One thing I very often do is resolve the size of a file, create a
std::vector<unsigned char> of that size, and then std::fread() the
file into the vector.

The zero-initialization of the vector is completely unnecessary and
a complete waste of time.

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Juha Nieminen]

Öö Tiib <oot...@hot.ee> wrote:
> The implied question (by parts of my answer that you erased) is why
> not to first reserve() and later emplace_back()?

Because functions like std::fread() do not emplace_back().

And yes, it's much more efficient to create a vector of the size of the
data being read and then read all the data into it with one single
std::fread() call, than to do anything more complicated.

In this case, the zero-initialization of the vector is a completely
useless waste of time.

[Paavo Helde]

On 27.03.2019 11:17, Juha Nieminen wrote:
> Öö Tiib <oot...@hot.ee> wrote:
>> The implied question (by parts of my answer that you erased) is why
>> not to first reserve() and later emplace_back()?
>
> Because functions like std::fread() do not emplace_back().
>
> And yes, it's much more efficient to create a vector of the size of the
> data being read and then read all the data into it with one single
> std::fread() call, than to do anything more complicated.
>
> In this case, the zero-initialization of the vector is a completely
> useless waste of time.

And this waste is completely insignificant in this case because file
access takes orders of magnitudes more time.

[Paavo Helde]

Have you measured how much time you lose this way? 0.01%?

If file reading is a performance bottleneck then one should use mmap
instead. By using fread() you already say you don't care so much about
performance.

[Bonita Montero]

>> In this case, the zero-initialization of the vector is a completely
>> useless waste of time.

> And this waste is completely insignificant in this case because file
> access takes orders of magnitudes more time.

That depends on the block-size you read at once.

[Paavo Helde]

Right, if you read the file by blocks then you can reuse the same
std::vector buffer and its initialization overhead becomes even more
insignificant.

[Bonita Montero]

>>> And this waste is completely insignificant in this case because file
>>> access takes orders of magnitudes more time.

>> That depends on the block-size you read at once.

> Right, if you read the file by blocks then you can reuse the same
> std::vector buffer and its initialization overhead becomes even more
> insignificant.

Then it might be so small that you have a lot of kernel-calls for
small blocks which slow down the operation.

[Paavo Helde]

Sure, in file I/O there are lots of potential performance issues. But
these are not related to std::vector initialization.

[Jorgen Grahn]

On Wed, 2019-03-27, Paavo Helde wrote:
> On 27.03.2019 11:13, Juha Nieminen wrote:
>> Paavo Helde <myfir...@osa.pri.ee> wrote:
>>> On 25.03.2019 12:57, Bonita Montero wrote:
>>>> Does anyone know an easy way to prevent default-initialization of
>>>> new elements in a container? I.e. if we'd have a vecor<int>, when
>>>> I do a .resize( s ), the new elements would become initalized with
>>>> int(), meaning zero.
>>>
>>> So do not use resize(). Use push_back(), emplace_back() or range
>>> insert(), possibly after a suitable reserve().
>>
>> One thing I very often do is resolve the size of a file, create a
>> std::vector<unsigned char> of that size, and then std::fread() the
>> file into the vector.

Presumably with an extra step for when the file grew or shrunk
just after you determineed its size.

>> The zero-initialization of the vector is completely unnecessary and
>> a complete waste of time.
>
> Have you measured how much time you lose this way? 0.01%?
>
> If file reading is a performance bottleneck then one should use mmap
> instead. By using fread() you already say you don't care so much about
> performance.

And maybe he's already saying that by reading the whole file into a
std::vector. YMMV, but most files I read can be read line by line,
with only a line at a time in memory. Similarly for all compressed
files, etc.

[Martijn van Buul]

* leigh.v....@googlemail.com:
> On Tuesday, March 26, 2019 at 2:53:51 PM UTC, Martijn van Buul wrote:
>> * Paavo Helde:
>> > std::unique_ptr<int[]> buffer(new int[n]);
>> >
>> > AFAIK this is the last use case for 'new'
>>
>> ... that you're willing to consider.
>>
>> Please show me an implementation of any of the containers, or any of the
>> "smart" pointers that does not rely on 'new'.
>
> Are you being deliberately obtuse? Obviously Paavo wasn't thinking about implementers of the Standard Library because, like, 0.0000001% of the programmer population are Standard Library implementers.

Tne remaining 99.9999999% will still need a working "old-style" new, otherwise
their templates won't compile. Also, I would venture that the STL is far from
feature-complete regarding data containers. If it wasn't, boost.container
would've been out of business, for starters, and boost.intrusive wouldn't
have to exist.

The STL containers are a decent starting point, but pretending they suffice
for all applications is short-sighted at best.

--
Martijn van Buul - pi...@dohd.org

[Öö Tiib]

Are most of those (supposedly superior to STL containers) designed using
"old style" new instead of allocator::allocate() and allocator::construct()
and "old style" delete instead of allocator::deallocate() and
allocator::destroy() for resource management? Why?

[Daniel]

On Wednesday, March 27, 2019 at 9:33:20 AM UTC-4, Öö Tiib wrote:
>
> Are most of those (supposedly superior to STL containers) designed using
> "old style" new instead of allocator::allocate() and allocator::construct()
> and "old style" delete instead of allocator::deallocate() and
> allocator::destroy() for resource management?

"Supposedly superior?" What is that supposed to mean? Typical alternative
containers attempt to fill gaps that the standard library containers don't
cover, such as flat maps, btrees and n-dimensional arrays. As far as I can
tell, authors of alternative containers go to great lengths to stay as close
as possible to standard library sequence container and associative container
concepts, and of course use allocator::allocate() and allocator::destroy(),
but at times they struggle. It's not completely trivial, for example, to
support stateful allocators in heterogeneous containers with a multitude of
internal data structures.

Daniel

[Öö Tiib]

On Wednesday, 27 March 2019 16:33:22 UTC+2, Daniel wrote:
> On Wednesday, March 27, 2019 at 9:33:20 AM UTC-4, Öö Tiib wrote:
> >
> > Are most of those (supposedly superior to STL containers) designed using
> > "old style" new instead of allocator::allocate() and allocator::construct()
> > and "old style" delete instead of allocator::deallocate() and
> > allocator::destroy() for resource management?
>
> "Supposedly superior?" What is that supposed to mean?

I meant it in sense of having allegedly/probably/seemingly superior
algorithm in sense of storage usage and/or performance for particular
task type under hand.

> Typical alternative
> containers attempt to fill gaps that the standard library containers don't
> cover, such as flat maps, btrees and n-dimensional arrays. As far as I can
> tell, authors of alternative containers go to great lengths to stay as close
> as possible to standard library sequence container and associative container
> concepts, and of course use allocator::allocate() and allocator::destroy(),
> but at times they struggle. It's not completely trivial, for example, to
> support stateful allocators in heterogeneous containers with a multitude of
> internal data structures.

I did not try to imply that anything of it is trivial. I just asked two
questions. I asked because I knew that the libraries in Boost either
use other containers (as underlying containers) or use allocators instead
using new or delete directly or don't deal with management at all
(like Boost.Intrusive).

[Juha Nieminen]

Paavo Helde <myfir...@osa.pri.ee> wrote:
> If file reading is a performance bottleneck then one should use mmap
> instead.

In which version of the C++ standard was mmap introduced?

[Juha Nieminen]

Paavo Helde <myfir...@osa.pri.ee> wrote:
> And this waste is completely insignificant in this case because file
> access takes orders of magnitudes more time.

Why should I be paying that extra time, no matter how "insignificant"
it may be? I thought the design principle of C++ is that you don't have
to pay for what you don't use. In this case I'm not using, at all, the
fact that std::vector zero-initializes its contents when you resize it,
yet I'm still forced to pay for it.

[Öö Tiib]

On Thursday, 28 March 2019 11:01:16 UTC+2, Juha Nieminen wrote:
> Paavo Helde <myfir...@osa.pri.ee> wrote:
> > If file reading is a performance bottleneck then one should use mmap
> > instead.
>
> In which version of the C++ standard was mmap introduced?

It will never be. The mmap is part of other standard (POSIX) and C++
will never limit itself only to systems that comply with POSIX.
Even in POSIX the mmap is present only when platform kernel has
virtual memory system. Embedded Linuxes without virtual memory
system don't have mmap. So mmap will forever be a performance
optimization or inter-process communication measure for larger
POSIX-compliant systems.

[Öö Tiib]

On Thursday, 28 March 2019 11:03:22 UTC+2, Juha Nieminen wrote:
> Paavo Helde <myfir...@osa.pri.ee> wrote:
> > And this waste is completely insignificant in this case because file
> > access takes orders of magnitudes more time.
>
> Why should I be paying that extra time, no matter how "insignificant"
> it may be? I thought the design principle of C++ is that you don't have
> to pay for what you don't use. In this case I'm not using, at all, the
> fact that std::vector zero-initializes its contents when you resize it,
> yet I'm still forced to pay for it.

Because it is designed to provide certain guarantees that are important
for certain usages. One tool can not be exactly optimal for every usage.
It has been already said that we don't have to use std::vector where the
difference from optimal actually matters. We can us std::unique_ptr<T[]>
or std::array<T,N> for potentially uninitialized buffers if such are needed.

[Paavo Helde]

On 28.03.2019 11:01, Juha Nieminen wrote:
> Paavo Helde <myfir...@osa.pri.ee> wrote:
>> If file reading is a performance bottleneck then one should use mmap
>> instead.
>
> In which version of the C++ standard was mmap introduced?

That's what I said. You care about other things more than about the
performance. The other things appear to be standard conformance and
convenience (reading the whole file in in one go).

There is nothing wrong about these preferences, that's a perfectly fine
approach, but then it sounds a bit silly to complain about the time
wasted on std::vector initialization.

I just made a little performance test, reading a 2.3 GB file and summing
all its bytes. The results are here:

large vector: 1.55176 s
large new[] : 1.40286 s, 9.59564 % win
small vector: 0.768879 s, 50.4511 % win
small new[] : 0.759881 s, 51.031 % win
mmap : 0.46249 s, 70.1958 % win

Here, large means the whole file read into a single buffer, and small
means a 16k buffer.

IIRC your approach was "large vector" (read the whole file into a
std::vector). So, using an uninitialized buffer with new[] would win ca
10% in this task (that's much more than I expected, must be because the
file is already in OS caches). That's the overhead you complained about.

However, by using a smaller buffer and thus reducing stress on memory
allocator you can win 50% instead, fully standard-conformant.

And finally, if you care about performance more than having pure
standard-conforming code, then you can use memory mapping and win 72%.


Code follows (Windows-only, no error checks, sorry):

#include <iostream>
#include <numeric>
#include <string>
#include <functional>
#include <chrono>
#include <algorithm>
#include <io.h>
#include <Windows.h>

int main() {

std::string filename = "D:/test/columbus/Case 00647038.zip";
unsigned int x1, x2, x3, x4, x5;

// put mmap first to warm caches up and still win
auto start3 = std::chrono::steady_clock::now();
{
HANDLE h = ::CreateFileA(filename.c_str(), GENERIC_READ,
FILE_SHARE_READ|FILE_SHARE_WRITE, NULL, OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL, NULL);
LARGE_INTEGER li;
::GetFileSizeEx(h, &li);
size_t n = li.QuadPart;
HANDLE m = ::CreateFileMapping(h, NULL, PAGE_READONLY, 0, 0, NULL);
unsigned char* view = static_cast<unsigned char*>(::MapViewOfFile(m,
FILE_MAP_READ, 0, 0, n));
x3 = std::accumulate(view, view+n, 0u);
::UnmapViewOfFile(view);
::CloseHandle(m);
::CloseHandle(h);
}
auto finish3 = std::chrono::steady_clock::now();

auto start1 = std::chrono::steady_clock::now();
{
FILE* f = fopen(filename.c_str(), "rb");
size_t n = _filelengthi64(fileno(f));
std::vector<unsigned char> a(n);
fread(a.data(), 1, n, f);
fclose(f);
x1 = std::accumulate(a.begin(), a.end(), 0u);

}
auto finish1 = std::chrono::steady_clock::now();

auto start2 = std::chrono::steady_clock::now();
{
FILE* f = fopen(filename.c_str(), "rb");
size_t n = _filelengthi64(fileno(f));
unsigned char* b = new unsigned char[n];
fread(b, 1, n, f);
x2 = std::accumulate(b, b+n, 0u);
delete[] b;
fclose(f);
}
auto finish2 = std::chrono::steady_clock::now();

auto start4 = std::chrono::steady_clock::now();
{
FILE* f = fopen(filename.c_str(), "rb");
size_t n = _filelengthi64(fileno(f));
const size_t bufferSize = 4*4096;
std::vector<unsigned char> a(bufferSize);
x4 = 0;
while (true) {
size_t k = fread(a.data(), 1, bufferSize, f);
x4 = std::accumulate(a.data(), a.data()+k, x4);
if (k<bufferSize) {
break;
}
}
fclose(f);
}
auto finish4 = std::chrono::steady_clock::now();

auto start5 = std::chrono::steady_clock::now();
{
FILE* f = fopen(filename.c_str(), "rb");
size_t n = _filelengthi64(fileno(f));
const size_t bufferSize = 4*4096;
unsigned char* a = new unsigned char[bufferSize];
x5 = 0;
while (true) {
size_t k = fread(a, 1, bufferSize, f);
x5 = std::accumulate(a, a+k, x5);
if (k<bufferSize) {
break;
}
}
delete[] a;
fclose(f);
}
auto finish5 = std::chrono::steady_clock::now();

auto dur1 =
std::chrono::duration_cast<std::chrono::duration<double>>(finish1-start1);
auto dur2 =
std::chrono::duration_cast<std::chrono::duration<double>>(finish2-start2);
auto dur3 =
std::chrono::duration_cast<std::chrono::duration<double>>(finish3-start3);
auto dur4 =
std::chrono::duration_cast<std::chrono::duration<double>>(finish4-start4);
auto dur5 =
std::chrono::duration_cast<std::chrono::duration<double>>(finish5-start5);

std::cout << "mmap : " << dur3.count() << " s, " <<
100.0*(dur1.count()-dur3.count())/dur1.count() << " % win\n";
std::cout << "large vector: " << dur1.count() << " s\n";
std::cout << "large new[] : " << dur2.count() << " s, " <<
100.0*(dur1.count()-dur2.count())/dur1.count() << " % win\n";
std::cout << "small vector: " << dur4.count() << " s, " <<
100.0*(dur1.count()-dur4.count())/dur1.count() << " % win\n";
std::cout << "small new[] : " << dur5.count() << " s, " <<
100.0*(dur1.count()-dur5.count())/dur1.count() << " % win\n";

if (x1!=x2 || x1!=x3 || x1!=x4 || x1!=x5) {
std::cerr << "Something wrong\n";
}
return x1-x2;
}

[leigh.v....@googlemail.com]

Nonsense. Boost provides a platform agnostic way to do this so there is no reason C++ couldn't in the future.

[Öö Tiib]

On Thursday, 28 March 2019 14:03:49 UTC+2, leigh.v...@googlemail.com wrote:
> Nonsense. Boost provides a platform agnostic way to do this so there is no reason C++ couldn't in the future.

That "magical boost" does on work embedded
Linux that does not have virtual memory system.

[Vir Campestris]

On 27/03/2019 06:15, Paavo Helde wrote:
>
> Bonita is right in that there is a detrimental effect. I just measured
> it. The initialization of a 800 million element unsigned int vector
> takes ca 1.3 s with reserve() and emplace_back() and ca 0.9 s with new[]
> and assignment. This makes ca half of a nanosecond per element.
>

I just measured it too...

reserve + emplace_back: .532
emplace_back without reserve: 1.14
push_back without reserve: 1.38

Visual Studio 2012 for vector<char> size 2^29 in _release_ mode, in
debug it's another story.

> If this detrimental effect is significant is another topic and depends
> on what this array is used for. If it is not used for anything it can be
> just deleted and 100% efficiency gained ;-). If it used for anything
> substantial then the initialization overhead will likely turn
> insignificant.

+1

Andy