r/cpp_questions • u/MillenniumDev • 1d ago
SOLVED Performance of std::vector
In the university we had to implement quicksort, the unsigned ints are stored in std::vector. I have accidentally discovered, that all algorithms, despite how students implemented them, are much faster when instead of directly accessing data from the vector like that:
arr[n]
we write:
unsigned int *a = arr.data()
and access that data by writing:
a[n]
But I can't understand why is that, in both cases it translates to one and the same: *(a + n)
The code is compiled on Clion IDE if that changes anything, no custom settings for compilation are used.
I can't directly share the algorithms for copyright reasons as they are not mine.
8
u/nickwebha 22h ago
Am I living in a world where someone can copyright an std::vector sort? For a student in a school doing school work?
72
u/No_Engineering_1155 1d ago
If you would turn up the optimizations, there shouldn't be any difference. You could also take a look in compiler explorer, whether there is a difference in compiled assembly code.
30
u/meancoot 1d ago
Outside of the optimizer not being enabled there is no reason they should perform differently.
14
u/Alzurana 1d ago
I have the suspicion that you're just building with default settings?
Those builds would be not optimized. Accessing the internal array is simply more direct than using the overload [] as that entails a function call (jump plus consuming a stack frame and maybe even some register saving) which wasn't inlined and therefor takes more time.
This is a nice example of what compiler optimizations do, they remove fluff like function calls on small operators, for example which is highly effective for very frequently called overloads like [] on your container in a quicksort, for example.
If you build with -O2 flags you will see that both versions will take the same time.
27
u/QuentinUK 1d ago
arr[n] for a vector calls a subroutine int std::vector<int>::operator[](size_t index); which can be optimised away to *(a+n) but in Debug mode that isn’t done so will be slower. In debug mode there are also checks that the index does not go out of bounds for the array which slow things down.
24
u/manni66 1d ago
Enable the optimizer!
Wasn’t you supposed to implement one yourself?
14
u/Total-Box-5169 1d ago
Probably because optimizations are not enabled. Also instead a std::vector you should take a std::span so that function is not tied to a very specific type used to store data.
8
u/kevinossia 1d ago
You must be compiling in debug mode or something. With optimization turned on, there's no way those two accessor methods would have a performance difference. Try it out on godbolt.org; they should compile to exactly the same machine code.
1
u/ConstructionLost4861 1d ago
Woah a teacher who can't tell the difference between optimized build and debug build? Sounds about right.
3
u/SelectAd8810 13h ago
Most likely you used Debug configuration, as STL is atrocious slow in debug builds. Even on debug, you have the options to disable validations which improves speed like 2 times. With the optimizations on you shouldn’t see any performances penalty, the exception being some custom implementations, like EASTL (which actually is good).
2
u/MyTinyHappyPlace 1d ago
If all else fails, have a look at the assembler output. Make a minimum viable test. Try out both ways with different level of compiler optimizations.
2
u/frnxt 1d ago
IME it's pretty common to use vectors exactly like this : most of the C++ code just uses methods/accessors from the STL, and a few very optimized algorithms (as small as possible and wrapped so they're safe to call from the rest of the code) manipulate data() pointers directly.
Even if release builds optimize the C++ methods out, in some cases this can make debug builds slower and therefore more difficult to work with, and sometimes the safety-speed tradeoff would rather go the "speed" direction for legitimate reasons.
2
u/WikiBox 1d ago
I would assume that there are range checks for vector[n]. That can significantly slow down access. You should be able to examine the code generated and/or the library, and figure it out.
1
u/StaticCoder 1d ago
No one else seems to have pointed it out, but if your vector is a reference (it's difficult to tell), then,
v[n], if inlined, is stillv->buf[n]. The extra indirection is expensive if it cannot be optimized out. Generally I'd recommend using iterators rather than direct pointers.1
u/Raknarg 23h ago edited 23h ago
Can you share the compiler settings and the compiler being used? We can use godbolt and take a look at the assembly to see whats going on. My guess though is just that you haven't enabled optimizations and one of these forms has some default optimizations that are better. If you enable -O3 or whatever the max optimization is for your compiler I would be surprised if there was a difference.
I tested it myself in godbolt but the assembly doesn't give any hint why one would be slower, they both invoke a function call with similar operations in gcc trunk and clang. So I'd need whatever compiler you're using.
edit: Another thing I thought of, are you only calling data() once and reusing that result? Because that would mean in a loop with 100 elements the data() version would be calling the function just once, while the operator[] version would be calling a function every time.
1
u/mredding 19h ago
You have to look at A) your compiler settings and B) your compiler output.
vec[n]is a function call for each index access, whereas you're caching a raw pointer to memory locally, and then amortizing the cost of of calling.data()once by computing simpler, cheaper pointer offsets.Turn up your optimizations, the problem goes away. Let the compiler do what it does best, otherwise you're measuring a hamstrung solution that isn't fair.
1
u/AndriesG04 1d ago
Like the other dude said, compile with optimisations turned on. I also discovered this in my Performance Engineering class and was like, why would anyone use this it’s like 3 times as slow (for mat-mat multiply). But std::vector has been built in such a way that compilers can heavily optimise your code when you use it. I also think, but don’t quote me on this, that compilers also optimise certain stuff when they recognise you use std::vector
0
u/Discordbothost 1d ago
Since it's quicksort, I'd give each timed run a fresh copy of the same unsorted vector. Make the copy before starting the timer. Reusing the vector can feed one version the other version's sorted output, which can change how much partitioning work it does.
-5
u/vyuniverse 19h ago
Using the `[]` operator on a vector performs bounds checking; i.e. a check is done to see if you’re accessing an element within the size of the vector.
Try using `.at(n)` instead; this method doesn’t enforce bounds checking and should be equivalent to your workaround