r/cpp_questions • • 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.

26 Upvotes

51 comments sorted by

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?

0

u/MillenniumDev 20h ago

They are being salty after I pointed out that it is possible to make their algorithms 10-13 times faster. Barred me not only from sharing their code, but also from questioning it or directly mentioning that it is slow. While it is unlikely for them to find me on Reddit, I am still avoiding breaking their "kind request" to avoid drama. Legally they can't claim shit, it is quicksort, they are not inventors of it.

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.

6

u/TimelyTraffic8003 23h ago

This may come off as a stupid question, but here goes. I often hear people suggest using compiler explorer to read assembly output, but why not just use your installed C++ compiler?

20

u/AKostur 22h ago

Convenience. As I recall, the early compiler-explorer was just a quick webpage slapped on top of feeding the code through g++ to get the assembly.

Edit: and I get access to compilers from a large number of different versions, different compilers, different platforms.

10

u/No_Engineering_1155 23h ago

I think the main reason is, that you only want to see a short snippet of your code in assembly and the convenience is there, copy-pasta your code and see what comes out as assembly. You can easily swap between compilers without installing them. But maybe there are other folks with better explanation.

5

u/Selbstdenker 22h ago

You can certainly do that. Compiler explorer is just a very easy way to do that. You do not have to figure out how to call your compiler to get the assembly instead of binary output or which tiny part of the executable is the part which comes from your code and not the cruft the compiler adds to get you an executable program. It also helps you to understand the instructions and aligns your code with the resulting instructions.

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.

•

u/KingAggressive1498 2h ago

yep. way way back before I got pretty good at debugging optimized builds I used to do hacks like this instead of using the std algorithms all the time because "iterators are slow".

-4

u/Raknarg 23h ago

but data() is also a subroutine, so both versions should be invoking a subroutine call.

13

u/WhiteEvilBro 22h ago

.data() needs to be invoked once, while operator[] is invoked on every read and write (therefore O(nlogn) times)

24

u/manni66 1d ago

Enable the optimizer!

I can't directly share the algorithms for copyright reasons as they are not mine

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/AndriesG04 1d ago

I think using std::span is only preferable if they know that they want the exact same function to be usable with the different storage type, otherwise using std::vector or a plain pointer is definitely fine. No need to overcomplicate the code when not needed

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/MillenniumDev 1d ago

Where did I say that I am a teacher?

1

u/ConstructionLost4861 1d ago

despite how students implemented them

Are you referring to yourself as "students"?

2

u/MillenniumDev 1d ago

I am refering to my group. My whole job was to manipulate algorithms of other students to find as many things as I can related to optimisation.

7

u/ConstructionLost4861 1d ago

Oh sorry for my confusion, I thought you mean "my students". Yeah look for the word "Debug" on your IDE's GUI and change it to "Release", or add -O2 to your build flags if you're compiling using make, or add --config Release to your cmake --build command.

2

u/I__Know__Stuff 1d ago

That's what I thought it meant, too.

1

u/AKostur 1d ago

Themselves plus their cohort.  They’re noting that it’s not just themselves, but other students saw the same results.

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.

3

u/ItWasMyWifesIdea 1d ago

FWIW I've never seen people write code that way in 25 years as a C++ professional. May be specific to your experience or domain.

2

u/frnxt 1d ago

Signal processing, often with vectors of simple types such as std::vector<float>.

To be honest this is not something I would recommend unconditionally (notably because if I can afford a proper "safe" design, a specialized data structure with control over its allocations is often a better choice), but it's a pattern I found used by multiple people over around 10 years I've been programming C++ so it looks pervasive enough.

2

u/frnxt 1d ago

(Also : we often deal with other external C/C++ libraries for performance, which take pointers, and std::vectors are a very quick way to initialize a pointer to an array containing all the data we might need!)

2

u/ItWasMyWifesIdea 1d ago

Oh yeah, when working with external libraries it makes sense for sure. The idea of using data() to speed up debug builds is the surprising one. I'd use a release build with debug symbols first.

2

u/frnxt 1d ago

In general we're not modifying the lowlevel optimized parts of our framework very often (and it's often a task in itself to validate their correctness) and we mostly use the debug builds to debug issues in layers above that (which, honestly, could be written in Python with the "small" problem that Python is absolute shit at threading). You could argue we could split the lowlevel core in a separate library and just compile that one in release, but... small team and an old historical build system and all that.

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.

4

u/Flimsy_Complaint490 1d ago

[] has no bound checks.

at() does bound checking.

5

u/didntplaymysummercar 1d ago

at() is guaranteed to throw if you're out of bounds.

[] on some standard library implementations will bounds check in debug or if you opt into it. MSVC does it out of the box in debug: "Expression: vector subscript out of range"

1

u/Normal-Narwhal0xFF 23h ago

That's true in the standard but debug builds could add vendor-specific range checks, just like optional "checked iterators". Since debug builds are for catching bugs ...

1

u/UndefFox 1d ago edited 1d ago

It doesn't do any bound checking:

      /**
       *    Subscript access to the data contained in the %vector.
       *   __n The index of the element for which data should be
       *  accessed.
       *  u/return  Read/write reference to data.
       *
       *  This operator allows for easy, array-style, data access.
       *  Note that data access with this operator is unchecked and
       *  out_of_range lookups are not defined. (For checked lookups
       *  see at().)
       */
      _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
      reference
      operator[](size_type __n) _GLIBCXX_NOEXCEPT
      {
__glibcxx_requires_subscript(__n);
return *(this->_M_impl._M_start + __n);
      }

Most likely either the call isn't inlined, or the pointer is constantly being loaded over and over if they didn't pass vector as const/

edit: it does check on debug builds:

# define __glibcxx_requires_subscript(_N)\
  __glibcxx_assert(_N < this->size())

2

u/oriolid 1d ago

This is nitpicking, but that depends on the compiler. Access outside bounds is UB so it's completely legal to check the bounds and crash the app if the check fails. This is from AppleClang:

  [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __n) _NOEXCEPT {
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds");
    return this->__begin_[__n];
  }
  [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference
  operator[](size_type __n) const _NOEXCEPT {
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds");
    return this->__begin_[__n];
  }

The assert is disabled by default. If I was writing a programming assignment checker, I would enable it.

1

u/serafean 1d ago

Invalid access through [], compiled without optimizations, gcc-16:

/usr/lib/gcc/x86_64-pc-linux-gnu/16/include/g++-v16/bits/stl_vector.h:1253: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

-O1 already disables this assert.

1

u/UndefFox 1d ago

Yeah, didn't think to check the defines...:

# define __glibcxx_requires_subscript(_N)\
  __glibcxx_assert(_N < this->size())

So yeah, it does check on debug build.

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 still v->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

5

u/Alzurana 1d ago

Just attatching to this answer because you say standard types are built to be optimized very well.

That is 100% true, I just want to attach a very good series on compiler design that also helps understanding how those optimizations take place and how you can potentially have your own code be optimized similarly well by thinking about it's structure just a little bit more:

https://www.youtube.com/watch?v=zA5iLLP9v-I&list=PL6whQ6CW68oe3tcmFcBLYFQChqwYEaG7_

It's also a good resource to realize where you can absolutely be more verbose for readability sake without losing on any performance. (For example, writing a new variable for each new value you calculate). It just all optimizes out. Or even avoiding ternary operators if an "if" block is more readable.

Similarly, the compiler will reorder instructions to promote hot paths so you do not have to do that yourself, you can think about readability first. There's ways to give hints to likely branches with the "likely" keyword, as well.

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

4

u/esspeebee 19h ago

You have those two backwards. at() performs bounds checking while [] doesn't.

0

u/jevndev 19h ago

This comment isn't correct. std::vector<T>::operator[](size_type) (cppref) is standardized to not do bounds checking1. std::vector<T>::at(size_type) (cppref) is standardized to do bounds checking and throw a std::out_of_range if out of bounds. Whether a given implementation does bounds checking is vendor defined (and in some release modes, operator[] will do so), but it's against the standard.

1 (unless you're using C++26 with contract assertions and the implementation is hardened. But that's a new and widely unsupported feature and not really relevant here. I just figured I'd mention it in case I get "whatabout"-ed)

0

u/PijanyRuski 17h ago

Do one or two most popular compilers do it?