Is branch prediction still significantly speeding up array processing?

Question

I was reading a interesting post about why is it faster to process a sorted array than an unsorted array? and saw a comment made by @mp31415 that said:

Just for the record. On Windows / VS2017 / i7-6700K 4GHz there is NO difference between two versions. It takes 0.6s for both cases. If number of iterations in the external loop is increased 10 times the execution time increases 10 times too to 6s in both cases

So I tried it on a online c/c++ compiler (with, I suppose, modern server architecture), I get, for the sorted and unsorted, respectively, ~1.9s and ~1.85s, not so much different but repeatable.

So I wonder if it is still true for modern architectures? Question was from 2012, not so far from now... Or where am I wrong?

---

Question precision for reopening:

• Please forget about me adding the C code as example. This was a terrible mistake. Not only erroneous was the code, posting it misled people who were focusing on the code itself, rather than on the question.

• When I tried first the C++ code used in the link above and got only 2% difference (1.9s & 1.85s).

• My first question and intent was about the previous post, its c++ code and the comment of @mp31415.

• @rustyx made an interesting comment, and I wondered if it could explain what I observed.

  Interestingly, a debug build exhibits 400% difference between sorted/unsorted, and a release build at most 5% difference (i7-7700).

In other words, my question is:

• Why does the c++ code in the previous post did not worked with as good performances as those claimed by the previous OP?

precised by:

• Does the timing difference between the release build and debug build could explain it?

Answer 1

You're a victim of the as-if rule:

... conforming implementations are required to emulate (only) the observable behavior of the abstract machine ...

Consider the function under test ...

const size_t arraySize = 32768;
int *data;

long long test()
{
    long long sum = 0;
    for (size_t i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (size_t c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }
    return sum;
}

And the generated assembly (VS 2017, x86_64 /O2 mode)

The machine does not execute your loops, instead it executes a similar program that does this:

long long test()
{
    long long sum = 0;
    // Primary loop
    for (size_t c = 0; c < arraySize; ++c)
    {
        for (size_t i = 0; i < 20000; ++i)
        {
            if (data[c] >= 128)
                sum += data[c] * 5;
        }
    }
    return sum;
}

Observe how the optimizer reversed the order of the loops and defeated your benchmark.

Obviously the latter version is much more branch-predictor-friendly.

You can in turn defeat the loop hoisting optimization by introducing a dependency in the outer loop:

long long test()
{
    long long sum = 0;
    for (size_t i = 0; i < 100000; ++i)
    {
        sum += data[sum % 15];  // <== dependency!
        // Primary loop
        for (size_t c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }
    return sum;
}

Now this version again exhibits a massive difference between sorted/unsorted data. On my system (i7-7700) 1.6s vs 11s (or 700%).

Conclusion: branch predictor is more important than ever these days when we are facing unprecedented pipeline depths and instruction-level parallelism.