Stop using std::vector wrong

🔗 LINKS

💰 Links to stuff I use:

This video is sponsored by Brilliant.

[RevolutionaryUsername]

Please don’t forget to add this to the C++ series playlist. A lot of beginners need to see this

[literallynull]

Sonic pro tip: preallocate memory beforehand

[ABaumstumpf]

6:08 - that is categorically wrong. The cost of using heap-allocation is the actual allocation. Once it is allocated there is no difference anymore.
9:57 - compile that with a not-ancient compiler and optimisation enabled: The result is most likely 0 allocations - the compiler is allowed to remove those.
16:35 - emplace_back would also be 0 allocations - that is mandated by the language.
19:05 - the reason it does not have a move-constructor is cause you disabled it by giving it a user-declared copy-constructor. had you not done that your class would be a simple aggregate-type, those operations would all be compiler-generated (with some other nice benefits) and you'd not see copies/moves either.


With vector you only want to use reserve if you either know the exact number of elements already, or you have measured that there is a performance-problem and you have also measured that you can get a good enough heuristic that your preallocation actually is significantly faster.
If you dont know then you can very easily end up with nearly the same number of allocations but a lot higher re-allocation and more memory-traffic.

[nordgaren]

Technically, std::array is stored wherever the memory you are using for it, is stored.

If you have an object that has an std::array, that array is going to be stored wherever that object is. If you put that object on the heap, then the std array is stored on the heap.

In your second example, if you make a static array to store the colors, that data would be stored in the .data section or .rdata section. (Or SOMEWHERE within the PE or ELF. I have also seen static data get stuck in the .text section. Haha)

The important part is that it's not going to create any additional memory.

Just minor nitpick though. :)

[isodoubIet]

The discussion in the second part is wrong in the sense that the only reason you got all those copies was because your instrumentation code forced them to be there -- overload resolution will prefer the manually-added copy constructor over the compiler-generated move constructor. Had you _not_ written the copy constructor, a move would've happened instead. That is, it's not true that you need to supply a move constructor yourself. In the vast majority of cases the compiler will write one for you and it'll usually be correct, particularly if what you have are just dumb structs (even if they contain more complicated types like vector).

[wissensfrosch]

A std::array is not a general replacement for std::vector. If you return a std::array from a function by value, all its elements will be copied. Returning a vector by value is a lot cheaper. (Sure, in most cases we have RVO.) Another important point, though, is that stack space is limited. Your program might work for small test examples, but will crash if you suddenly use it with larger std::arrays. This does not happen with std::vector. In certain cases it might be a lot smarter to use a vector to future proof your program for larger inputs.

I’m also not sure about performance differences in accessing arrays or vectors. This might be true if you only store 5 ints, but for larger sizes the overhead of the initial indirection is negligible. Caches don’t play much of a role for performance comparisons if you iterate over a hundred structs or more. You should only make sure that you don’t continuously resize a vector by calling push_back (like you have mentioned). But, don’t initialize the vector with a size or resize it. (Almost) always use reserve() instead because default constructing objects (not just ints which actually stay uninitialized) is a performance killer. If you always use resize() you don’t have to think twice.

And finally, only use emplace_back if you want to construct the object in place. Otherwise the general consensus is to use push_back to avoid nasty errors. If you move an already existing object into the vector with push_back it is not slower than emplace_back. But, it is safer and you actually want to push back an object in this case and cannot emplace it.

[hanspeterbestandig]

BTW In the meanwhile the owner (Adam) of this Tetris project was so kind to accept my Pull Request in which I taught him about these Issues as part of a Fork of his Project. This means that the latest version of the discussed code is now fixed in this repeating copy of the vectors. This storage then is referenced by a *const reference* that refers to these cached data when needed. Hence the code now performs lazy allocation of the Resources upon the first access and stores (caches) it *on a single point*. BTW its not only the Vector of Colors that are managed within a std::vector).

[dn]

Thank you so much for making this video! It’s super helpful for someone like myself who’s self-taught and doesn’t have a good grasp of the inner workings. I really appreciate how you explain the thought process, the different approaches, and show how you can dig in deeper to verify for yourself. You’re a great teacher!

[przemeknowak]

I think it also worth to mention that if we use vector that may be resized, it is good to mark move constructor objects that vector stores as noexcept

[master]

const std::vector<int> a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

BTW this only allocates once so immediate initializing with an initializer list is also efficient.

[tfraven]

Great video! I've known about this for a while, and it's surprising how many programmers overlook the importance of understanding how many copies and movements are happening in deep memory when using std::vector. You absolutely nailed it in explaining why this matters. It's not just about using the right tools, but knowing how they work under the hood. Thanks for shedding light on this important topic!

[rbaleksandar]

Fun fact - allocating more than you asked for also happens in other languages. I remember asking on SO why a supposedly empty dictionary has such a large size when I first discovered this.

[fbafelipe]

In the tetris code, when it iterates the vector it is also making a copy of Position. He could avoid that by changing that for to "for (const Position &item : tiles)"

[collynchristopherbrenner]

And here I am, basking in the C# bliss of using List<T> all the time with no idea of how it affects performance lol

[Bolpat]

Naive mathematician: I want to do simple vector stuff, but std::vector has no mathematical operations defined on it, so I added some operator overloads.
Me, a C++ dev: Nooo, don’t do that. You want to use a std::valarray, that already implements those.
Mathematician: Oh, okay… What is a std::vector then?
Me: An extendable array. It has zero conceptual relationship with vector spaces.
Mathematician: C++ naming is stupid.
Me: yes-meme.jpg

[MagnificentImbecil]

Thank you for the information in this video.

If I may make an observation (possibly wrong, please feel free to kindly correct me):

I think that:

Moving an `std::array` requires time approximately proportional to the number of elements (and the exception safety (error safety) level of this operation depends on the exception safety (error safety) level of the move operations for the elements).

Moving `an std::vector` only requires a fixed (very small) amount of time whatever the number of elements (and always offers the strongest possible level of exception safety (error safety): it is always a no-throw (no-fail) operation, whatever the exception safety (error safety) level of the move operations for the elements -- and in fact works even when the elements cannot be moved, e.g. mutexes and condvars).

[chickenbobbobba]

keep in mind you dont always want to stack allocate arrays, especially if they are large. you only get 1mb of stack on windows and 8mb on linux, which is fine for small stuff but past a point you want to keep it fairly freed up

[koonhanong]

💡One thing that could have been highlighted (though you have briefly mentioned it), is that moves are not free. When a move is done on a temporary, both objects need to be created first, before the temporary is moved (and also destroyed).
This is precisely why emplace_back() which forwards the arguments is good 👍

[WolfspiritMagic]

I like that video. There is one thing however that I don't get. The function that hooks into the allocation prints a message and increases the counter. But when executed it show way less messages in console than the counter. For example at 10:48 it shows 1 message printed and 5 allocations. I'd expect it to show 5 lines with "Allocated...". Is this just scrolled or what's going on?

[theobarollet]

I think their is an important idea to have because we often add elements to vectors but sometimes we need to remove them. If we don't have a LIFO or something we sometimes need to remove elements in the middle of a vector. If the order does not matter the correct way to remove elements is to swap the element to remove with the last element THEN remove the last element so it is constant time and not linear. Actually I think this kind of algorithmic optimization is more important than machinery optimization that is a super complex topic in the end.