6 ms·

Because people tend to write c++ for performance reasons and the perf profiles of std::vector are not always sufficient

jeffbee 3y ago
The only thing you can really quibble about with std::vector is whether your library has made an optimal choice of growth strategy, which you can often hack around by reserving. Aside from that, access via `operator[]` and growth via `emplace_back` will compile down to optimal code that is going to be close to impossible to beat. After the compiler gets done with it, it looks the same as if you had hand-coded it with arrays in a C-style, but without the plethora of bugs that often results from that approach.
- jsheard 3y ago
  There's also the issue that std::vector<bool> is required by the standard to be specialized as a bitset, which is a footgun in generic code since you can normally take the address of a vector element but not if it's a vector of bool. Having a bitset in the standard library is fine but it should have been a seperate type. Admittedly that's not a performance issue, but it's annoying.
  - jeffbee 3y ago
    That's true but I think everyone knows about vector<bool> being quirky. By the way, the standard does not require vector<bool> to be implemented as a bitset. Instead, it relaxes some of the details of vector, in a way that allows the implementation to do it that way. But these choices are implementation details. Vector<bool> is a little weird if you are just starting with C++, but it does have major performance benefits in its niche, and it came from the 1990s so we can be generous in overlooking its rough edges.
    - HelloNurse 3y ago
      It came from the 1990s, but it overstayed its welcome. I remember seeing proposals to remove the vector<bool> special case, what is the situation?
- dataflow 3y ago
  > The only thing you can really quibble about with std::vector is [...] That's actually not true, though I certainly don't fault you for believing it :-) but there are definitely more things to quibble about around vector if you're serious about performance. As an example, try writing a can_fit(n) function, which tells you whether the vector can fit n elements without reallocating. Observe the performance difference between (a) a smart manual version, (b) a naive manual version, and (c) the only STL version: https://godbolt.org/z/88sfM1sxW https://godbolt.org/z/88sfM1sxW #include <vector> template<class T> struct Vec { T *b, *e, *f; }; template<class T> bool can_fit_fast(Vec<T> const &v, size_t n) { return reinterpret_cast<char*>(v.f) - reinterpret_cast<char*>(v.e) >= n * sizeof(T); } template<class T> bool can_fit(Vec<T> const &v, size_t n) { return v.f - v.e >= n; } template<class T> bool can_fit(std::vector<T> const &v, size_t n) { return v.capacity() - v.size() >= n; } struct S { size_t a[3]; }; template bool can_fit_fast(Vec<S> const &, size_t); template bool can_fit(Vec<S> const &, size_t); template bool can_fit(std::vector<S> const &, size_t);
  - CyberDildonics 3y ago
    Why would that be faster? Those function calls are going to be inlined.
    - jeffbee 3y ago
      It's not the function calls they are alluding to, it's the way the compiler generates a bunch of shifts and multiplies except in the can_fit_2 case.
      - dataflow 3y ago
        Turns out GCC is more clever than Clang here, and MSVC is just horrendous. (See update, I posted a link.)
        jeffbee 3y ago
        I somewhat agree with your point (esp. that MSVC is hideous) but I also stand by mine. I don't feel that checking the capacity is something that would be in my tight loop, because checking for capacity to hold N is something you do before adding N items, which amortizes the cost, meaning the capacity check is just off the real hot path. So it doesn't feel like a realistic use case. Speaking of realism, putting these in quickbench seems to confirm that the differences between them are not material, and that the STL version is in fact the quickest, but they are all essentially free. There's not a way to make a realistic microbenchmark for this, for the same reason that it doesn't feel like a real-world performance issue. By the way clang does a much better job here: https://quick-bench.com/q/XcKK782d-7A6YHbiBRTlOnIRnPY https://quick-bench.com/q/XcKK782d-7A6YHbiBRTlOnIRnPY
CyberDildonics 3y ago
What specifically is wrong with vector? There have been a lot of hash maps done with flat memory to minimize allocations and pointer hopping over the STL but vector doesn't have those problems.

The only thing you can really quibble about with std::vector is whether your library has made an optimal choice of growth strategy, which you can often hack around by reserving. Aside from that, access via `operator[]` and growth via `emplace_back` will compile down to optimal code that is going to be close to impossible to beat. After the compiler gets done with it, it looks the same as if you had hand-coded it with arrays in a C-style, but without the plethora of bugs that often results from that approach.

jsheard 3y ago
There's also the issue that std::vector<bool> is required by the standard to be specialized as a bitset, which is a footgun in generic code since you can normally take the address of a vector element but not if it's a vector of bool. Having a bitset in the standard library is fine but it should have been a seperate type. Admittedly that's not a performance issue, but it's annoying.
- jeffbee 3y ago
  That's true but I think everyone knows about vector<bool> being quirky. By the way, the standard does not require vector<bool> to be implemented as a bitset. Instead, it relaxes some of the details of vector, in a way that allows the implementation to do it that way. But these choices are implementation details. Vector<bool> is a little weird if you are just starting with C++, but it does have major performance benefits in its niche, and it came from the 1990s so we can be generous in overlooking its rough edges.
  - HelloNurse 3y ago
    It came from the 1990s, but it overstayed its welcome. I remember seeing proposals to remove the vector<bool> special case, what is the situation?
dataflow 3y ago
> The only thing you can really quibble about with std::vector is [...] That's actually not true, though I certainly don't fault you for believing it :-) but there are definitely more things to quibble about around vector if you're serious about performance. As an example, try writing a can_fit(n) function, which tells you whether the vector can fit n elements without reallocating. Observe the performance difference between (a) a smart manual version, (b) a naive manual version, and (c) the only STL version: https://godbolt.org/z/88sfM1sxW https://godbolt.org/z/88sfM1sxW #include <vector> template<class T> struct Vec { T *b, *e, *f; }; template<class T> bool can_fit_fast(Vec<T> const &v, size_t n) { return reinterpret_cast<char*>(v.f) - reinterpret_cast<char*>(v.e) >= n * sizeof(T); } template<class T> bool can_fit(Vec<T> const &v, size_t n) { return v.f - v.e >= n; } template<class T> bool can_fit(std::vector<T> const &v, size_t n) { return v.capacity() - v.size() >= n; } struct S { size_t a[3]; }; template bool can_fit_fast(Vec<S> const &, size_t); template bool can_fit(Vec<S> const &, size_t); template bool can_fit(std::vector<S> const &, size_t);
- CyberDildonics 3y ago
  Why would that be faster? Those function calls are going to be inlined.
  - jeffbee 3y ago
    It's not the function calls they are alluding to, it's the way the compiler generates a bunch of shifts and multiplies except in the can_fit_2 case.
    - dataflow 3y ago
      Turns out GCC is more clever than Clang here, and MSVC is just horrendous. (See update, I posted a link.)
      - jeffbee 3y ago
        I somewhat agree with your point (esp. that MSVC is hideous) but I also stand by mine. I don't feel that checking the capacity is something that would be in my tight loop, because checking for capacity to hold N is something you do before adding N items, which amortizes the cost, meaning the capacity check is just off the real hot path. So it doesn't feel like a realistic use case. Speaking of realism, putting these in quickbench seems to confirm that the differences between them are not material, and that the STL version is in fact the quickest, but they are all essentially free. There's not a way to make a realistic microbenchmark for this, for the same reason that it doesn't feel like a real-world performance issue. By the way clang does a much better job here: https://quick-bench.com/q/XcKK782d-7A6YHbiBRTlOnIRnPY https://quick-bench.com/q/XcKK782d-7A6YHbiBRTlOnIRnPY

CyberDildonics 3y ago

What specifically is wrong with vector? There have been a lot of hash maps done with flat memory to minimize allocations and pointer hopping over the STL but vector doesn't have those problems.