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

fixed column indentation

Source Link

edited Feb 27, 2019 at 10:58

6k
5
43
66

As data is distributed between 0 and 255 when the array is sorted, around the first half of the iterations will not enter the if-statement (the if statement is shared below).

if (data[c] >= 128)
    sum += data[c];

The question is: What makes the above statement not execute in certain cases as in case of sorted data? Here comes the "branch predictor". A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!

Let's do some bench marking to understand it better

The performance of an if-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the if-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Here are the timings of the loop with different true-false patterns:

Condition            Pattern    Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

A “bad” true-false pattern can make an if-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about the impact of branch prediction on performance!

As data is distributed between 0 and 255 when the array is sorted, around the first half of the iterations will not enter the if-statement (the if statement is shared below).

if (data[c] >= 128)
    sum += data[c];

The question is: What makes the above statement not execute in certain cases as in case of sorted data? Here comes the "branch predictor". A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!

Let's do some bench marking to understand it better

The performance of an if-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the if-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Here are the timings of the loop with different true-false patterns:

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

A “bad” true-false pattern can make an if-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about the impact of branch prediction on performance!

As data is distributed between 0 and 255 when the array is sorted, around the first half of the iterations will not enter the if-statement (the if statement is shared below).

if (data[c] >= 128)
    sum += data[c];

The question is: What makes the above statement not execute in certain cases as in case of sorted data? Here comes the "branch predictor". A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!

Let's do some bench marking to understand it better

The performance of an if-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the if-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Here are the timings of the loop with different true-false patterns:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

A “bad” true-false pattern can make an if-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about the impact of branch prediction on performance!

Active reading [<https://en.wiktionary.org/wiki/let%27s#Contraction>]

Source Link

edited Mar 16, 2018 at 12:51

Peter Mortensen

31.4k
22
110
134

As data is distributed between 0 and 255 when the array is sorted, around the first half of the iterations will not enter the ifif-statement (ifthe if statement is shared below).

if (data[c] >= 128)
    sum += data[c];

QuestionThe question is what make: What makes the above statement not execute in certain casecases as in case of sorted data? Here comes the "Branch"branch predictor" a. A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-elseif-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!

LetsLet's do some bench marking to understand it better

The performance of an ifif-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the ifif-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Here are the timings of the loop with different Truetrue-Falsefalse patterns:

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

A “bad” true-false pattern can make an ifif-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about the impact of branch prediction on performance!

As data is distributed between 0 and 255 when array is sorted, around first half of the iterations will not enter the if-statement (if statement shared below).

if (data[c] >= 128)
    sum += data[c];

Question is what make the above statement not execute in certain case as in case of sorted data? Here comes the "Branch predictor" a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!

Lets do some bench marking to understand it better

The performance of an if-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the if-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++) if (condition) sum++;

Here are the timings of the loop with different True-False patterns:

Condition           Pattern              Time (ms)

(i & 0×80000000) == 0   T repeated        322

(i & 0xffffffff) == 0   F repeated        276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…         513

(i & 2) == 0            TTFFTTFF…         1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0           16T 16F 16T 16F … 490

A “bad” true-false pattern can make an if-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about impact of branch prediction on performance!

As data is distributed between 0 and 255 when the array is sorted, around the first half of the iterations will not enter the if-statement (the if statement is shared below).

if (data[c] >= 128)
    sum += data[c];

The question is: What makes the above statement not execute in certain cases as in case of sorted data? Here comes the "branch predictor". A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!

Let's do some bench marking to understand it better

The performance of an if-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the if-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Here are the timings of the loop with different true-false patterns:

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

A “bad” true-false pattern can make an if-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about the impact of branch prediction on performance!

Mod Removes Wiki by Shog9

occurred Jan 29, 2016 at 1:24

Post Made Community Wiki by George Stocker

occurred Jan 28, 2016 at 20:56

added 711 characters in body

Source Link

edited Mar 22, 2013 at 12:20

Saqlain

18k
4
31
33

As data is distributed between 0 and 255 when array is sorted, around first half of the iterations will not enter the if-statement (if statement shared below).

if (data[c] >= 128)
    sum += data[c];

Question is what make the above statement not execute in certain case as in case of sorted data? Here comes the "Branch predictor" a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!

Lets do some bench marking to understand it better

The performance of an if-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the if-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++) if (condition) sum++;

Here are the timings of the loop with different True-False patterns:

Condition           Pattern              Time (ms)

(i & 0×80000000) == 0   T repeated        322

(i & 0xffffffff) == 0   F repeated        276

(i & 1) == 0            TF alternating        760

(i & 3) == 0            TFFFTFFF…         513

(i & 2) == 0            TTFFTTFF…         1675

(i & 4) == 0            TTTTFFFFTTTTFFFF…     1275

(i & 8) == 0            8T 8F 8T 8F …         752

(i & 16) == 0           16T 16F 16T 16F …     490

A “bad” true-false pattern can make an if-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about impact of branch prediction on performance!

The performance of an if-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the if-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++) if (condition) sum++;

Here are the timings of the loop with different True-False patterns:

Condition           Pattern              Time (ms)

(i & 0×80000000) == 0   T repeated        322

(i & 0xffffffff) == 0   F repeated        276

(i & 1) == 0            TF alternating        760

(i & 3) == 0            TFFFTFFF…         513

(i & 2) == 0            TTFFTTFF…         1675

(i & 4) == 0            TTTTFFFFTTTTFFFF…     1275

(i & 8) == 0            8T 8F 8T 8F …         752

(i & 16) == 0           16T 16F 16T 16F …     490

A “bad” true-false pattern can make an if-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about impact of branch prediction on performance!

As data is distributed between 0 and 255 when array is sorted, around first half of the iterations will not enter the if-statement (if statement shared below).

if (data[c] >= 128)
    sum += data[c];

Question is what make the above statement not execute in certain case as in case of sorted data? Here comes the "Branch predictor" a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!

Lets do some bench marking to understand it better

The performance of an if-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the if-statement will be much more expensive.

Let’s measure the performance of this loop with different conditions:

for (int i = 0; i < max; i++) if (condition) sum++;

Here are the timings of the loop with different True-False patterns:

Condition           Pattern              Time (ms)

(i & 0×80000000) == 0   T repeated        322

(i & 0xffffffff) == 0   F repeated        276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…         513

(i & 2) == 0            TTFFTTFF…         1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0           16T 16F 16T 16F … 490

A “bad” true-false pattern can make an if-statement up to six times slower than a “good” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about impact of branch prediction on performance!