Edit - Stack Overflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Rev

Why is processing a sorted array faster than processing an unsorted array?

Here is a piece of C++ code that shows some very peculiar behavior. For some strange reason, sorting the data (before the timed region) miraculously makes the loop almost six times faster.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}

Without std::sort(data, data + arraySize);, the code runs in 11.54 seconds.
With the sorted data, the code runs in 1.93 seconds.

(Sorting itself takes more time than this one pass over the array, so it's not actually worth doing if we needed to calculate this for an unknown array.)

Initially, I thought this might be just a language or compiler anomaly, so I tried Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

With a similar but less extreme result.

My first thought was that sorting brings the data into the cache, but then I thought how silly that was because the array was just generated.

What is going on?
Why is processing a sorted array faster than processing an unsorted array?

The code is summing up some independent terms, so the order should not matter.

Related / followup Q&As about the same effect with different / later compilers and options:

Answer

The above behavior is happening because of Branch prediction.

To understand branch prediction one must first understand **Instruction Pipeline**:

Any instruction is broken into a sequence of steps so that different steps can be executed concurrently in parallel. This technique is known as instruction pipeline and this is used to increase throughput in modern processors. To understand this better please see this [example on Wikipedia][1].

Generally, modern processors have quite long pipelines, but for ease let's consider these 4 steps only.
<ol>  
  <li>IF -- Fetch the instruction from memory 
  <li>ID -- Decode the instruction
  <li>EX -- Execute the instruction 
  <li>WB -- Write back to CPU register
</ol>
 ***4-stage pipeline in general for 2 instructions.***
![4-stage pipeline in general][2]

Moving back to the above question let's consider the following instructions:

							A) if (data[c] >= 128)
					                /\
				                   /  \
				                  /    \
                            true /      \ false
			                    /        \
                               /          \
                              /            \
                             /              \
                  B) sum += data[c];          C) for loop or print().


Without branch prediction, the following would occur:

To execute instruction B or instruction C the processor will have to wait till the instruction A doesn't reach till EX stage in the pipeline, as the decision to go to instruction B or instruction C depends on the result of instruction A. So the pipeline will look like this.

***when if condition returns true:***
![enter image description here][3]

***When if condition returns false:***
![enter image description here][4]

As a result of waiting for the result of instruction A, the total CPU cycles spent in the above case (without branch prediction; for both true and false) is 7.

**So what is branch prediction?**

Branch predictor will try to guess which way a branch (an if-then-else structure) will go before this is known for sure. It will not wait for the instruction A to reach the EX stage of the pipeline, but it will guess the decision and go to that instruction (B or C in case of our example).

***In case of a correct guess, the pipeline looks something like this:***
![enter image description here][5]

If it is later detected that the guess was wrong then the partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay. 
The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. The longer the pipeline the greater the need for a good [branch predictor][6].

In the OP's code, the first time when the conditional, the branch predictor does not have any information to base up prediction, so the first time it will randomly choose the next instruction. Later in the for loop, it can base the prediction on the history. 
For an array sorted in ascending order, there are three possibilities:
<ol>
<li> All the elements are less than 128
<li> All the elements are greater than 128
<li> Some starting new elements are less than 128 and later it become greater than 128
</ol>

Let us assume that the predictor will always assume the true branch on the first run.

So in the first case, it will always take the true branch since historically all its predictions are correct.
In the 2nd case, initially it will predict wrong, but after a few iterations, it will predict correctly.
In the 3rd case, it will initially predict correctly till the elements are less than 128. After which it will fail for some time and the correct itself when it sees branch prediction failure in history. 
 
In all these cases the failure will be too less in number and as a result, only a few times it will need to discard the partially executed instructions and start over with the correct branch, resulting in fewer CPU cycles. 

But in case of a random unsorted array, the prediction will need to discard the partially executed instructions and start over with the correct branch most of the time and result in more CPU cycles compared to the sorted array.


  [1]: https://en.wikipedia.org/wiki/Pipeline_(computing)#Concept_and_motivation
  [2]: http://i.stack.imgur.com/PqBBR.png
  [3]: http://i.stack.imgur.com/0H4gP.png
  [4]: http://i.stack.imgur.com/APpca.png
  [5]: http://i.stack.imgur.com/ZYUbs.png
  [6]: https://en.wikipedia.org/wiki/Branch_predictor

Edit Summary

Cancel

5

how are two instructions executed together? is this done with separate cpu cores or is pipeline instruction is integrated in single cpu core?
– M.kazem Akhgary
Oct 11, 2017 at 14:49
5

@M.kazemAkhgary It's all inside one logical core. If you're interested, this is nicely described for example in Intel Software Developer Manual
– Sergey.quixoticaxis.Ivanov
Nov 3, 2017 at 7:45

Add a comment |

Correct minor typos or mistakes
Clarify meaning without changing it
Add related resources or links
Always respect the author’s intent
Don’t use edits to reply to the author

create code fences with backticks ` or tildes ~
```
like so
```
add language identifier to highlight code
```python
def function(foo):
print(foo)
```
put returns between paragraphs
for linebreak add 2 spaces at end
_italic_ or **bold**
indent code by 4 spaces
backtick escapes `like _so_`
quote by placing > at start of line
to make links (use https whenever possible)
<https://example.com>
[example](https://example.com)
<a href="https://example.com">example</a>

formatting help »
answering help »

current community

your communities

more stack exchange communities

Why is processing a sorted array faster than processing an unsorted array?

Answer