在此 C++ 代碼中，對(duì)數(shù)據(jù)進(jìn)行排序（在定時(shí)區(qū)域之前）使主循環(huán)速度加快約 6 倍：
#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';}
文章來(lái)源地址http://www.zghlxwxcb.cn/article/276.html
如果沒(méi)有std::sort(data, data + arraySize);，代碼運(yùn)行時(shí)間為 11.54 秒。
使用排序后的數(shù)據(jù)，代碼運(yùn)行時(shí)間為 1.93 秒。
（排序本身比遍歷數(shù)組需要更多時(shí)間，因此如果我們需要為未知數(shù)組計(jì)算排序，那么實(shí)際上不值得這樣做。）
最初，我認(rèn)為這可能只是一種語(yǔ)言或編譯器異常，所以我嘗試了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);
}}具有類(lèi)似但不那么極端的結(jié)果。
文章來(lái)源：http://www.zghlxwxcb.cn/article/276.html
我的第一個(gè)想法是排序?qū)?shù)據(jù)帶入緩存，但這很愚蠢，因?yàn)閿?shù)組剛剛生成。
到底是怎么回事？
為什么處理已排序的數(shù)組比處理未排序的數(shù)組更快？
該代碼總結(jié)了一些獨(dú)立的術(shù)語(yǔ)，因此順序并不重要。
什么是分支預(yù)測(cè)？
考慮一個(gè)鐵路樞紐：
現(xiàn)在為了便于討論，假設(shè)現(xiàn)在是 1800 年代——遠(yuǎn)距離或無(wú)線電通信出現(xiàn)之前。
你是路口的盲人操作員，你聽(tīng)到火車(chē)駛來(lái)。你不知道它應(yīng)該走哪條路。你停下火車(chē)詢問(wèn)司機(jī)他們想要哪個(gè)方向。然后你適當(dāng)?shù)卦O(shè)置開(kāi)關(guān)。
火車(chē)很重并且有很大的慣性，因此它們需要很長(zhǎng)時(shí)間才能啟動(dòng)和減速。
有沒(méi)有更好的辦法？你猜火車(chē)會(huì)開(kāi)往哪個(gè)方向！
如果你猜對(duì)了，就繼續(xù)。
如果你猜錯(cuò)了，船長(zhǎng)會(huì)停下來(lái)，后退，并對(duì)你大喊，要求你打開(kāi)開(kāi)關(guān)。然后它可以沿著另一條路徑重新啟動(dòng)。
如果你每次都猜對(duì)了，火車(chē)就永遠(yuǎn)不會(huì)停下來(lái)。
如果您經(jīng)常猜錯(cuò)，火車(chē)將花費(fèi)大量時(shí)間停車(chē)、倒車(chē)和重新啟動(dòng)。
考慮一個(gè) if 語(yǔ)句：在處理器級(jí)別，它是一條分支指令：
你是一個(gè)處理器，你看到一個(gè)分支。你不知道它會(huì)走向何方。你做什么工作？您停止執(zhí)行并等待前面的指令完成。然后你繼續(xù)沿著正確的道路前進(jìn)。
現(xiàn)代處理器很復(fù)雜并且管道很長(zhǎng)。這意味著他們需要永遠(yuǎn)“熱身”和“放慢速度”。
有沒(méi)有更好的辦法？你猜分支會(huì)走向哪個(gè)方向！
如果你猜對(duì)了，你就繼續(xù)執(zhí)行。
如果你猜錯(cuò)了，你需要刷新管道并回滾到分支。然后您可以沿著另一條路徑重新啟動(dòng)。
如果你每次都猜對(duì)了，執(zhí)行就永遠(yuǎn)不必停止。
如果你經(jīng)常猜錯(cuò)，你就會(huì)花費(fèi)大量時(shí)間停頓、回滾和重新啟動(dòng)。
這就是分支預(yù)測(cè)。我承認(rèn)這不是最好的類(lèi)比，因?yàn)榛疖?chē)可以用旗幟來(lái)指示方向。但在計(jì)算機(jī)中，處理器直到最后一刻才知道分支將走向哪個(gè)方向。
您如何從策略上猜測(cè)以盡量減少火車(chē)必須倒車(chē)并沿另一條路線行駛的次數(shù)？你看看過(guò)去的歷史吧！如果火車(chē) 99% 的時(shí)間都是向左行駛，那么你猜是向左行駛。如果它交替，那么你就會(huì)改變你的猜測(cè)。如果每三次走一個(gè)方向，你猜的都是一樣的......
換句話說(shuō)，你嘗試識(shí)別一種模式并遵循它。這或多或少就是分支預(yù)測(cè)器的工作原理。
大多數(shù)應(yīng)用程序都有行為良好的分支。因此，現(xiàn)代分支預(yù)測(cè)器通常會(huì)實(shí)現(xiàn) >90% 的命中率。但是，當(dāng)面對(duì)沒(méi)有可識(shí)別模式的不可預(yù)測(cè)的分支時(shí)，分支預(yù)測(cè)器實(shí)際上毫無(wú)用處。
正如上面所暗示的，罪魁禍?zhǔn)资沁@個(gè) if 語(yǔ)句：
if (data[c] >= 128) sum += data[c];
請(qǐng)注意，數(shù)據(jù)均勻分布在 0 到 255 之間。當(dāng)數(shù)據(jù)排序時(shí)，大約前一半的迭代不會(huì)進(jìn)入 if 語(yǔ)句。之后，都會(huì)進(jìn)入if語(yǔ)句。
這對(duì)于分支預(yù)測(cè)器非常友好，因?yàn)榉种нB續(xù)多次走向同一方向。即使是簡(jiǎn)單的飽和計(jì)數(shù)器也能正確預(yù)測(cè)分支，除了切換方向后的幾次迭代之外。
快速可視化：
T = branch taken N = branch not taken data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... branch = N N N N N ... N N T T T ... T T T ... = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
然而，當(dāng)數(shù)據(jù)完全隨機(jī)時(shí)，分支預(yù)測(cè)器就變得毫無(wú)用處，因?yàn)樗鼰o(wú)法預(yù)測(cè)隨機(jī)數(shù)據(jù)。因此，可能會(huì)有大約 50% 的錯(cuò)誤預(yù)測(cè)（并不比隨機(jī)猜測(cè)更好）。
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, ... branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T ... = TTNTTTTNTNNTTT ... (completely random - impossible to predict)
可以做什么？
如果編譯器無(wú)法將分支優(yōu)化為條件移動(dòng)，并且愿意犧牲可讀性來(lái)提高性能，則可以嘗試一些技巧。
代替：
if (data[c] >= 128) sum += data[c];
和：
int t = (data[c] - 128) >> 31;sum += ~t & data[c];
這消除了分支并用一些按位運(yùn)算代替它。
（請(qǐng)注意，此 hack 并不嚴(yán)格等同于原始 if 語(yǔ)句。但在這種情況下，它對(duì) 的所有輸入值都有效data[]。）
基準(zhǔn)測(cè)試：酷睿 i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 版本
| 設(shè)想 | 時(shí)間（秒） |
|---|---|
| 分支 - 隨機(jī)數(shù)據(jù) | 11.777 |
| 分支 - 排序數(shù)據(jù) | 2.352 |
| 無(wú)分支 - 隨機(jī)數(shù)據(jù) | 2.564 |
| Branchless - 排序數(shù)據(jù) | 2.587 |
Java - NetBeans 7.1.1 JDK 7 - x64
| 設(shè)想 | 時(shí)間（秒） |
|---|---|
| 分支 - 隨機(jī)數(shù)據(jù) | 10.93293813 |
| 分支 - 排序數(shù)據(jù) | 5.643797077 |
| 無(wú)分支 - 隨機(jī)數(shù)據(jù) | 3.113581453 |
| Branchless - 排序數(shù)據(jù) | 3.186068823 |
觀察結(jié)果：
使用分支：排序數(shù)據(jù)和未排序數(shù)據(jù)之間存在巨大差異。
使用 Hack：排序數(shù)據(jù)和未排序數(shù)據(jù)之間沒(méi)有區(qū)別。
在 C++ 情況下，當(dāng)數(shù)據(jù)排序時(shí)， hack 實(shí)際上比分支慢一點(diǎn)。
一般的經(jīng)驗(yàn)法則是避免關(guān)鍵循環(huán)中的數(shù)據(jù)相關(guān)分支（例如本例中）。
更新：
-O3x64上的 GCC 4.6.1-ftree-vectorize能夠生成條件移動(dòng)，因此排序數(shù)據(jù)和未排序數(shù)據(jù)之間沒(méi)有區(qū)別 - 兩者都很快。
（或者有點(diǎn)快：對(duì)于已經(jīng)排序的情況，cmov可能會(huì)更慢，特別是如果 GCC 將其放在關(guān)鍵路徑上而不只是add，特別是在 Broadwell 之前的 Intel 上，其中cmov有 2 個(gè)周期延遲：gcc 優(yōu)化標(biāo)志 -O3 使代碼比 -O2 慢）
即使在/Ox.
英特爾 C++ 編譯器(ICC) 11 創(chuàng)造了奇跡。它交換兩個(gè)循環(huán)，從而將不可預(yù)測(cè)的分支提升到外循環(huán)。它不僅不受錯(cuò)誤預(yù)測(cè)的影響，而且速度是 VC++ 和 GCC 生成速度的兩倍！換句話說(shuō)，ICC 利用測(cè)試循環(huán)擊敗了基準(zhǔn)測(cè)試......
如果您為英特爾編譯器提供無(wú)分支代碼，它會(huì)直接對(duì)其進(jìn)行矢量化......并且與分支（使用循環(huán)交換）一樣快。
這表明即使是成熟的現(xiàn)代編譯器優(yōu)化代碼的能力也可能有很大差異......
到此這篇關(guān)于為什么處理已排序的數(shù)組比處理未排序的數(shù)組更快？的文章就介紹到這了,更多相關(guān)內(nèi)容可以在右上角搜索或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
