Why a Sorted Array in C++ Processes Faster? The Secret of Branch Prediction

Introduction: One of the Most Unexpected Questions in the C++ World

Imagine a situation: you write a simple loop in C++ that sums the elements of a large array, but only those that are greater than a certain threshold. You run the code, it works... normally. Then you decide to sort the array beforehand and run it again. And suddenly you notice that the code runs 2-3 times faster! What's the trick? Compiler magic? A benchmark error?

This question, asked on Stack Overflow over ten years ago, has gathered thousands of views and still sparks heated debates. Today on PythonLib we will dissect it thoroughly, with real examples in C++ and a deep dive into the architecture of modern processors. You will learn not only why this happens, but also how to use this effect to speed up your code.

1. Reproducing the Phenomenon: Code That Surprises

Let's write a simple program that vividly demonstrates this effect. We need an array of 100,000 integers. We'll fill it with random values, then measure the time to sum all elements exceeding 128.

#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <chrono>\n#include <random>\n\nint main() {\n    const int SIZE = 100000;\n    const int THRESHOLD = 128;\n    \n    // Create an unsorted array\n    std::vector<int> data(SIZE);\n    std::mt19937 rng(42);\n    std::uniform_int_distribution<int> dist(0, 255);\n    for (auto& val : data) {\n        val = dist(rng);\n    }\n\n    // Sum for the unsorted array\n    auto start = std::chrono::high_resolution_clock::now();\n    long long sum_unsorted = 0;\n    for (int i = 0; i < SIZE; ++i) {\n        if (data[i] >= THRESHOLD) {\n            sum_unsorted += data[i];\n        }\n    }\n    auto end = std::chrono::high_resolution_clock::now();\n    auto time_unsorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n    std::cout << "Unsorted array: " << time_unsorted << " µs, sum = " << sum_unsorted << std::endl;\n\n    // Sort the array\n    std::sort(data.begin(), data.end());\n\n    // Sum for the sorted array\n    start = std::chrono::high_resolution_clock::now();\n    long long sum_sorted = 0;\n    for (int i = 0; i < SIZE; ++i) {\n        if (data[i] >= THRESHOLD) {\n            sum_sorted += data[i];\n        }\n    }\n    end = std::chrono::high_resolution_clock::now();\n    auto time_sorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n    std::cout << "Sorted array: " << time_sorted << " µs, sum = " << sum_sorted << std::endl;\n\n    std::cout << "Speedup: " << (double)time_unsorted / time_sorted << "x" << std::endl;\n    return 0;\n}

When compiled without optimizations (the -O0 flag), the difference will be small, but if you enable -O2 or -O3 in GCC/Clang, you will get an impressive result: the sorted array is processed 3-6 times faster.

2. Processor Anatomy: Where Does the Difference Come From?

The key to the puzzle is a mechanism called Branch Prediction. Modern processors are pipelined machines. They do not execute instructions one by one, but break them down into stages (fetch, decode, execute, write back). To keep the pipeline from stalling, the processor tries to guess which branch of code (if or else) will be executed next and starts loading instructions in advance.

In our example, the condition if (data[i] >= THRESHOLD) is a branching point. For a sorted array, prediction works