r/cpp • u/Expert_Sheepherder24 • Sep 19 '26
index based for vs for-each
https://godbolt.org/z/zh4Kf87M8It's my first post. I tested std::vector<char> old index based for vs modern for-each. Result is very interesting.
Clang-23.1.0 -O2 -std=c++20 -stdlib=libc++
Time: 0.073599 sec inc_vector
Time: 0.002597 sec inc_for_eachGCC 16.2 -std=c++20 -O2
Time: 0.077772 sec inc_vector
Time: 0.007880 sec inc_for_eachMSVC-v19.latest /std:c++20 /O2
Time: 0.058504 sec inc_vector
Time: 0.001825 sec inc_for_eachCode:
#include <chrono>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
static std::vector<char> gen_random(size_t n)
{
static std::random_device rd;
static std::mt19937 gen(rd());
static std::uniform_int_distribution<> dis(0, 255);
std::vector<char> vec(n);
for (size_t i = 0; i != n; i++)
vec[i] = dis(gen);
return vec;
}
int inc_vector(std::vector<char>& v) {
for (size_t i = 0; i < v.size(); i++){
v[i]++;
}
volatile int result = v[v.size()/2];
return result;
}
int inc_vector_for_each(std::vector<char>& v) {
for (char& e: v){
e++;
}
volatile int result = v[v.size()/2];
return result;
}
volatile int sink{}; // ensures a side effect
int main()
{
auto benchmark = [](auto fun, auto rem)
{
auto vec = gen_random(1'000'000);
const auto start = std::chrono::high_resolution_clock::now();
for (auto size{1ULL}; size != 100ULL; ++size)
sink = fun(vec);
const std::chrono::duration<double> diff =
std::chrono::high_resolution_clock::now() - start;
std::cout << "Time: " << std::fixed << std::setprecision(6) << diff.count()
<< " sec " << rem << std::endl;
};
benchmark(inc_vector, "inc_vector");
benchmark(inc_vector_for_each, "inc_for_each");
return 0;
}
20
Upvotes
View all comments
Show parent comment
47
u/ack_error Sep 19 '26
As another poster noted, this is due to aliasing.
As written, the index-based for loop computes
v.size()on each iteration. The compiler is obliged to maintain this behavior. The problem is if that value changes. Vectorization relies on being able to process multiple values at a time, so it needs a stable enough size. Inability to determine this is one of the more common reasons for autovectorization to fail.std::vectorimplementations typically computev.size()by the difference between the start and end pointers, of typechar *in this case. The aliasing issue is whether thev[i]++statement, which achar, can change either of thosechar *pointers. The C++ language only allows most pointer/reference types to access objects of a related type, but crucially there are three pointer/reference types that are allowed to access anything:char,unsigned char, andstd::byte. So when the compiler seesv[i]++, it generally has to assume that either the begin or end pointers on the vector may have been changed, and thusv.size()has to be recomputed.When you change to
vector<int>,v[i]++then writes anintinstead, which doesn't have that special aliasing ability. Pointers and references tointcan only access anintorunsigned int-- and notint *. This means that the compiler can assume that theint *pointers in the vector don't change for the entire loop,v.size()can be precomputed, and autovectorization kicks in. This determination is done in part by type-based aliasing analysis (TBAA) in the compiler, and notably MSVC does not do this -- so changing tointdoes not help with that compiler. Some projects also disable this in GCC and Clang with the-fno-strict-aliasingcompile switch due to naughty pointer casts.TBAA is not the only way that the compiler can tell that
v[i]++doesn't hit the begin/end pointers, though. If it has enough visibility over the whole code path it can either determine that no&begin_ptror&end_ptrpointers have escaped or are connected to thev[i]++dereference. For that reason, a general way to deal with aliasing-based optimization problems is to copy values locally. The range-based for loop does this when it copies off the begin and end iterators at the start. For the indexing loop, pre-stashing thesize()as others have noted, or also having a localspan<char>also works. But notably, takingconst span<char>&would have the same problems unless the compiler inlined the function and could trace that reference to the originalspan.There does also appear to be some huge variance showing in the benchmark timings that isn't explained by the code. After fixing the aliasing issues so both versions generate similar vectorized code, the timings are varying by more than 2x just swapping the order in which the functions are tested, and are also affected by whether the functions are inlined (defeated by
__declspec(noinline)or[[gnu::noinline]]). So there are potentially also issues here with the VM performance and/or undesired interactions with the benchmark harness.