在Stack Overflow看到這一篇,
Why is processing a sorted array faster than an unsorted array? - Stack Overflow
引起我蠻大的興趣.
以前就知道會因為CPU分支預測錯誤, 導致執行速度變慢.
(因為預測錯誤會導致所以在pipe上的指令都要重來.^#0)
但是依照這篇的說法兩者差距蠻大的,
可以高達 11.54 seconds/1.93 seconds = 6.01 倍.

那我也在我的電腦(AMD Phenom II)上試試,
用MinGW g++ 4.9.2 64bits^#1 用 -O2 來編譯,
執行完的結果是:

13.233 seconds / 4.12 seconds = 3.21 倍

看來CPU是有強弱之別的...XD
再來換用 -O3 來編譯, 差別就不大了,
結果如下:
3.988 seconds / 3.989 seconds = 0.999749 倍

後來又再試32bits的情況, 即使加了 -O3 或者是 -ftree-vectorize 也都沒有效果.
g++.exe -m32 -O3 -ftree-vectorize test.cpp
結果是 13.991 秒

因為是C++的程式, 編譯出來的執行檔有點複雜.
所以自己就寫了個C的版本來觀察不同的編譯參數所造成的影響.
============================

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void test1(int *data, int arraySize, unsigned int num)
{
    clock_t start;
    long long sum = 0;
    double elapsedTime;
    unsigned int i;
    int c;

    start = clock();

    for (i = 0; i < num; ++i) {
        // Primary loop
        for (c = 0; c < arraySize; ++c) {
            if (data[c] >= 128) {
                sum += data[c];
            }
        }
    }

    elapsedTime = (double) (clock() - start) / CLOCKS_PER_SEC;
    printf("=== %s ===\n", __FUNCTION__);
    printf("%lf\t", elapsedTime);
    printf("sum = %lld\n", sum);
}

int cmp(const void *_a, const void *_b)
{
    int a = *(int *)_a;
    int b = *(int *)_b;
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}

#define arraySize  32768
int main()
{
    int data[arraySize];
    int i;

    for (i = 0; i < arraySize; ++i) {
        data[i] = rand() % 256;
    }
    
    test1(data, arraySize, 100000);
    qsort(data, sizeof(data)/sizeof(data[0]), sizeof(data[0]),cmp);
    printf("\nAfter Sorting...\n\n");
    test1(data, arraySize, 100000);

    return 0;
}
============================

$ gcc.exe -O2 -g test1.c
$ ./a.exe
=== test1 ===
13.211000       sum = 312275400000

After Sorting...

=== test1 ===
4.115000        sum = 312275400000

=========================================================

$ gcc.exe -O3 -g test1.c
$ ./a.exe
=== test1 ===
3.988000        sum = 312275400000

After Sorted...

=== test1 ===
3.983000        sum = 312275400000

然後用objdump -d去反組譯出來,
-O2版本如下:

  401550:    4d 63 11                 movslq (%r9),%r10
  401553:    41 83 fa 7f              cmp    $0x7f,%r10d
  401557:    7e 03                    jle    40155c <test1+0x4c>
  401559:    4c 01 d3                 add    %r10,%rbx

-O3版本如下:

  401550:    4d 63 11                 movslq (%r9),%r10
  401553:    4d 89 d3                 mov    %r10,%r11
  401556:    49 01 da                 add    %rbx,%r10
  401559:    41 83 fb 7f              cmp    $0x7f,%r11d
  40155d:    49 0f 4f da              cmovg  %r10,%rbx

差別的-O3會很聰明的用CMOV指令,
而不是用條件跳躍指令Jxx.

就因為這個差別讓CPU不需要依靠分支預測,
讓整個執行效率變好.

#0: 分支預測器 - 維基百科，自由的百科全書
#1: x86_64-4.9.2-release-posix-sjlj-rt_v3-rev1 需要是 sjlj 版本才能同時支援32bits/64bits.