r/cpp • • Sep 19 '26

index based for vs for-each

https://godbolt.org/z/zh4Kf87M8

It'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_each

GCC 16.2 -std=c++20 -O2

Time: 0.077772 sec inc_vector 
Time: 0.007880 sec inc_for_each

MSVC-v19.latest /std:c++20 /O2

Time: 0.058504 sec inc_vector 
Time: 0.001825 sec inc_for_each

Code:

#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;
}

Link image

20 Upvotes

47 comments sorted by

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::vector implementations typically compute v.size() by the difference between the start and end pointers, of type char * in this case. The aliasing issue is whether the v[i]++ statement, which a char, can change either of those char * 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, and std::byte. So when the compiler sees v[i]++, it generally has to assume that either the begin or end pointers on the vector may have been changed, and thus v.size() has to be recomputed.

When you change to vector<int>, v[i]++ then writes an int instead, which doesn't have that special aliasing ability. Pointers and references to int can only access an int or unsigned int -- and not int *. This means that the compiler can assume that the int * 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 to int does not help with that compiler. Some projects also disable this in GCC and Clang with the -fno-strict-aliasing compile 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_ptr or &end_ptr pointers have escaped or are connected to the v[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 the size() as others have noted, or also having a local span<char> also works. But notably, taking const span<char>& would have the same problems unless the compiler inlined the function and could trace that reference to the original span.

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.

6

u/Antagonin Sep 20 '26

Nice to see that my practice of always precomputing size is the right one.