Optimizing the usage of std::vector in C++
Вставка
- Опубліковано 21 вер 2017
- Patreon ► / thecherno
Twitter ► / thecherno
Instagram ► / thecherno
Discord ► thecherno.com/discord
Series Playlist ► thecherno.com/cpp
Thank you to the following Patreon supporters:
- Samuel Egger
- Dominic Pace
Gear I use:
-----------------
BEST laptop for programming! ► geni.us/pakTES
My FAVOURITE keyboard for programming! ► geni.us/zNhB
FAVOURITE monitors for programming! ► geni.us/Ig6KBq
MAIN Camera ► geni.us/t6xyDRO
MAIN Lens ► geni.us/xGoDWT
Second Camera ► geni.us/CYUQ
Microphone ► geni.us/wqO6g7K
I really like C++. Many languages will abstract such things away, which can be very useful but I very often come back to C++ because I want that level of control.
I miss real languages... Been in LabVIEW world for a while. The idea of "optimizing" there would be laughable. Talk about abstraction ...
I'd like to see a language that aims to do what C++ does but without keeping all the old C legacy stuff. Clean the language up a bit and make it less of a mess. Some of the standard library features should be language features and vice versa... and we'd have a really solid language for developing high performance applications using modern abstraction. Which is what C++ wanted to be from the beginning but got held down with trying to keep compatibility with C.
@@nexusclarum8000 I think that's what C# was supposed to be wasn't it? I've been wanting to learn that a little better.
@@nexusclarum8000 You really should take a look at Rust. Just as close to the metal as C/C++ without all the baggage and some really good approaches to classic problems. It takes some getting used to, especially if you aren't over OOP yet, but I it's well worth it IMHO.
JK W no, that is not C#. C# is managed and abstracts everything, you have no control over anything.
Optimization Strategy 1: (4:20)
--> Construct the vertex in the same place as it will be stored. Rather than constructing it in the current method and then copying it to the vertex location.
--> use emplace_back rather than push_back and only pass the parameter list for the constructor
Ex. vertices.emplace_back(1, 2, 3);
Optimization Strategy 2: (5:55)
-->Remember to “know your environment”.
--> If you know that you will need an array to store 3 vertex objects, define it as such so that it is not dynamically resized everytime it runs out of space.
Ex. First define the vector, then use vertices.reserve(3); (on separate lines)
Please do more! This is probably THE best series for c++ on youtube right now. Thanks a lot!!
Not only on UA-cam, even paid courses are not even close to this tutorial
The std::vector also has a built in memory allocator that you can implement to get even more optimization. For instance, creating objects which are automatically aligned on the native CPUs cache line.
For CPU intensive work, ensuring objects are cache aligned can gain HUGE benefits because the CPU can fetch data for processing more quickly if that data respects the cache line.
So yeah, std::vector has plenty of nice features!
Probably late, but do you have any examples of how I could try to ensure cache optimization? Or sources to reference/learn?
I've done a very simple test a long time ago and saw the time to complete the test reduce extremely thanks to a basic cache optimization, but not sure how to deal with more complex situations.
Thanks, good to know!
I think the biggest takeaway here is that you should ALWAYS try to reserve before you start pushing back elements into the container. Even if using emplace_back, the elements would be copied over in the case of a reallocation. So always call reserve before starting to push back. Even if you don't know exactly how many elements you will push back, a guesstimate is always better than not calling reserve at all.
This is gold for embedded systems!! Thank you so much!
What a great video! Loved the way you showed how to optimize a vectors memory footprint. These are the types of details that I have not yet seen in any other c++ videos on UA-cam. Wonderful job. Thanks a lot!
Clear, precise, and super useful! Thanks, Cherno
Super cool! I hope there is a lot more stuff like this later on in this series. Thanks Cherno.
I love your tutorials :d you explain it perfectly. helped me a lot. i plan to watch the whole series to understand cpp better.
This was very informative. Awesome. I'd love to watch more optimization videos for general and often used c++ stdlib functions.
Good optimisations and clear show of how it helps in running fast, keep going.
This is really great! Thank you! Can you please make additional optimization videos? Possibly even how to write a class with optimization in mind.
This rules. Thank you for showing clearly how you can look for ways to optimize and for giving such an easy to follow example, and thank you for all your videos in general. Trying really hard to learn C++ on my own and your content is more helpful than the MIT classes that are online. It's easy to follow, easy to digest, assumes that the viewer is competent, isn't condescending at all to people who are new to C++, all while explaining everything clearly.
That was beautiful, thanks!
Cool :) Thank you for the video, that actually was really helpful, learned something new.
Nice video. A couple of really easy and effective tips there. Thanks.
Very nice taste of optimizations to come. Can't wait for the game engine series!
Sick video - thanks Cherno!
Thanks. Helpful. Scott Meyer further elaborates by exploring when it's reasonable to expect emplacement to be better than insertion in his talk: "Scott Meyers - The evolving search for effective C++ - Keynote @ Meeting C++ 2014", at around the 20 minute mark.
My man your channel is a blessing from c++ gods. My c++ code runs like a rocket now thx bro
incredible video, it s really teaching a lot!
Man this was great. Thanks dude.
So much quality in this video
This C++ series is so great. Its free, to point and easy to understand.
Thank you so much for the helpful video!
Great, mate!
You go to details bro.
Thank you so much.
This video is gold! More optimization videos pls
you're really good at this!
Thanks man!!!! This is one of the best...
The best tutorials ever. Thank you!
This was BY FAR one of the most awesome things I've learned this month regarding std lib optimization in C++! You're a LEGEND
This is by far the best cpp tutorial video, made by Cherno.
La mejor serie de c++ que vi :)
Best C++ tutorial video ever!
It's amazing to see when cpu copies the members in the memory. And seeing that we reduce the amount of times we need to copy, it is soo nice.
as clean as a whistle!!
You're the best C++ teacher I've found in my life!
never seen this detail anywhere. sweet.
I love optimizations, nice! :)
Your videos are gold!
clear as crystal
Great! Thanks!
This is gold.
bro... that's PURE *GOLD*
Wow, I had no idea that it worked like this!
Wow.. please make more of this kind of optimization videos and I'll make sure that whole of my class in tel aviv university computer science course will be happy to subscribe to your channel!!
Im talking about the std:vector video ofc!
Technion will too :)
Outstanding
this is better than my uni programming course by far.
simple and great example!
your hair is goals 😂
superb!
Thanks!!
that guitar is going to topple anytime now
I like the speed of these talks. I put them in the background and set the speed to about 1.5 or 1.25, but once in a while when it gets to something that causes a double take or that I want to pay specific attention to, I'll back it up a short bit and set the speed to normal. So for people who aren't already familiar, I bet it's about the right speed.
Dude I don’t know why but read countless books but I learned so much more from how you explain things great job
The push_back() method actually has O(1) time complexity. For larger sizes of the array, it will always double the size, or make it proportionally larger by some constant multiplier. So even if you can't reserve the space beforehand, it won't be as bad an issue, it won't cause any exponential time complexity. (It would, if it resized the vector before every insertion.)
thenks
that's was a good episode.
I didn't want to wink even once , but i had to . Thanks man , thanks for this wonderful content
Thx!
Thanks
ty good man
Optimization
This is the best explanation I have seen! I have also realized that watching videos teaches (me) much better than books.
One of the reason I don't like Bjarne Stroustrup's books, because it's like he's talking an alien language.
Hello, nice videos on your channel, what´s are the tools that you use to indicate the elapsed time in line, or is your IDE or any plug-in ?? I use Eclipse for c++, can you recommend any tool for optimize the code ?? Thanks
This is by far the best video I've ever seen
I love C/C++ , they r just mindblowing
Great!
Cool!
optimising like a boss
I'm emplaced with this c++ series.
That's fucking amazing.
I asked my uni professor the difference between push_back and emplace_back and he told me they are basically the same, and didn't explain any further. Thank you Cherno
If I could like this video more than once, I would!!
Great video! Thanks for this series! One question, how much should you reserve if you don't know the exact number? Let's say my vector might range between at least 16 and at max 128. Would it be better to reserve 16, or 128? Or would some where in the middle be better?
Do you know the answer to this question yet? I want to know the same thing.
One thing I'd suggest if you have a really critical path (ideally measured) and it resembles something like this:
for (int j=0; j < some_huge_number; ++j)
{
vector v;
v.reserve(???);
// do something with v
}
If that's really critical I'd recommend instead to just hoist the vector out of the loop.
vector v;
v.reserve(some_large_size);
for (int j=0; j < some_huge_number; ++j)
{
// do something with v
v.clear();
}
In this case, you can more confidently reserve a larger capacity for the vector if you even reserve at all, because you are only paying for the heap allocation involved with reserving once for the entire massive loop. The 'clear' method of vector doesn't free its underlying dynamic array. It keeps whatever capacity it had before clear was called. That'll wipe out almost the entirety of both the linear-time copies or moves involved with reallocating along with the heap allocations involved with reallocating and you don't have to spend so much time guessing and fiddling around with some optimal capacity for reserve.
Or you can even avoid reserving once you have things this way, reusing the same vector for each loop iteration, and the cost of not reserving in advance will probably be negligible since the vector's capacity will quickly start to fit the common case requirements of each loop iteration.
If you're not worried about memory consumption (do the math) then just reserve 128. Otherwise be aware that most implementations of vector increase their reserve length by 50% (rounded up) each time they reallocate. So the question becomes how many reallocations you're prepared to tolerate vs how much unused memory you're prepared to tolerate.
In the 16 to 128 case, if you start at 16 then 128 would need 6 reallocations. If you start at 38 then it's only 3.
The case that you really need to worry about is when you have a vector that can become arbitrarily large very quickly, since that's the worst for performance. In that case it's best to experiment a little to try and determine the average peak size under normal use and just reserve that amount.
All that having been said, this is generally only a significant issue in code that is handling massive sets of complex data or in code that is simply malformed and should be refactored rather than optimized. (Lack of move-constructors can be a culprit here.)
Remember to avoid premature optimization: don't spend more time optimizing than time you're saving unless there's a systematic reason for it.
A bit late but...
Nobody can really say. Khatarr already gave some good information as well.
Anyways.
you have anywhere from 16 to 128 Elements? Are the big? how often do you get 16, 64, 128 or any other number of elements? Are you constraint by memory or CPU-time? Is performance in that actually critical or would it just be a nice to have?
If performance is not critical then just don't. Things like printing out the elements the the console are so much slower that any change you do to the reservation become irrelevant. If you are constraint by memory then you also do not want to reserve more than you need.
If you know that most of the time it will be, say for example, less than 50 elements and you need that performance - than reserve it for a bit more than that so that 90% of the time it is fine. Or if you objects are expensive to construct, copy and delete.
It is also mostly the case that when you feel the need to ask such a question there are 3 things at play: You do not know the exact situation your program is in, you do not really need any higher performance, and the things you are using are so simply that just reserving even 500 Elements is no problem.
ily cherno
In fact the Cherno forgot an important point. Until 03:07, the Vertex pushed back in the container is an rvalue, and therefore will be moved (not copied), since the move constructor is implicitly defined.
Upon redefining the copy constructor however, the implicit move constructor is deleted by the compiler.
By wanting to see where the copy constructor is called, we cause our code to copy the Vertex instead of moving it(until we redefine the move constructor ourselves).
thank you. That saved for me an very important ms. speed up 2x
awesome^^
Such a great video!! So why shouldn't I use emplace all the time?
I've using vectors for 1 year without knowing this, Thanks Cherno
So is emplace_back now always the better option to push_back?
This was very useful, but how do you do strategy #1 (size the vector beforehand) if you don't know how much memory/what size you need? A typical case i run into is reading in a file. Often the file has an unknown number of lines (ie vector size needed unknown) or the file has variable line lengths (ie size of each vector element unknown)
Absolutely superb!!
Additionally you talk like Brüno...
This must be the best c++ series in all German spoken countries except Germany!!
I'll make an echo of something that you already said...
Get this into your head.
YOU ARE THE BEEESSSTTTT.
With you, everything is like a walk in the park.
Thanks
I am a C# programmer trying to understand C++ and it seems Lists in C# are exactly vectors as I understand it from this video. Cool!
Warning C4244 ('argument' conversion from _Ty to float possible loss of data).
changed ->
vertices.emplace_back(1, 2, 3);
to ->
vertices.emplace_back(1.0f, 2.0f, 3.0f);
I got the same thing. Didn't remember that I needed .0 at the end of my values for it to register my f properly. Thanks for your help
My favorite part of this guy's videos : ) (9:26)
My main reason to learn C/CPP is actually be able to control that precisely what I want my computer to do
you blew my mind in a way i felt like i'm a nerd
Super useful. I'm impressed with your grasp and ability to teach
c pillow like channel logo impressing
In my personal test in which I compared the usage of reserve() and resize(), it turned out that reserve() was indeed slower than resize() and also I had overloaded the new operator and from there I came to know that the reserve() method was allocating twice on the heap whereas the resize() method hit the heap only once. Why is this so? The compiler I used was g++ (MinGW) and compiled using std=c++17.
As Ilari Vallivaara has said, the time of copying N elements in a vector is no where near exponential. It's linear. You will find that if you do the amortized analysis which he has explained in his comments. I would like to give a practical proof for it.
Lets see how much time it takes to push 100M elements in a vector without reserving the space versus reserving the space.
First, without reserving the space.
#include
#include
using namespace std;
#define MAX 100000000
int main()
{
vector subject;
for(int i=1; i
Now try to do the same with a proper struct/class. It's misleading if you just use int ... the difference will be much bigger.
Please make an episode on templates as well
what happens to the vertex made in the stack in the push_back method?
Is it deleted after the push_back or does it remain in the stack?
When we use emplace_back, does the vector object get constructed in heap?
"a professional knows what he is doing"