在Stackoverflow看到這串討論很有意思。
以下的Code，雖然時間複雜度都一樣O(n)，不過排序過後的速度遠遠超過沒排序，將sort註解掉之後可以看出很明顯的差異。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #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)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
|
其中指出關鍵在於
1
2
| if (data[c] >= 128)
sum += data[c];
|
說穿了就是CPU會預測下一步可能的走向，如果對了，就能夠順利執行，不行的話會產生嚴重的stall。而排序過後的情形就不會有這情形產收。
所有的最佳化指南都明確指出要將Branch從Loop中移除，不是沒有道理的。