建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
很久以前在stackoverflow上看到下面這段代碼，今天忍不住把它摘錄過(guò)來(lái)。
成都創(chuàng)新互聯(lián)自2013年起，先為邛崍等服務(wù)建站，邛崍等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢(xún)服務(wù)。為邛崍企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。
- #include
- #include
- #include
- 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
(clock() - start) / CLOCKS_PER_SEC; - std::cout << elapsedTime << std::endl;
- std::cout << "sum = " << sum << std::endl;
- }
上面的程序在保留std::sort(data, data + arraySize);語(yǔ)句時(shí)，程序運(yùn)行時(shí)間是1.93 秒
但去掉排序語(yǔ)句后，程序運(yùn)行時(shí)間是11.54秒
問(wèn)題：為什么會(huì)出現(xiàn)這種情況？
解答：分支預(yù)測(cè)。
[[119029]]
程序分支
考慮以下if語(yǔ)句塊。對(duì)于處理器來(lái)說(shuō)，就是一個(gè)分支指令，如下：
處理器每次遇到一條分支時(shí)，它都不知道該走哪一條道。這時(shí)候該怎么辦？程序停下來(lái)，等待前面的指令執(zhí)行完，得到確切的結(jié)果后，再接著走某一條分支。
現(xiàn)代處理器都支持指令并行處理和超流水線(xiàn)作業(yè)。因此，當(dāng)處理器遇到程序分支時(shí)，都會(huì)去猜測(cè)應(yīng)該走哪一條分支。
如果猜對(duì)了，程序接著流暢運(yùn)行。如果猜錯(cuò)了，則處理器需要做一些額外的工作，再次回到那條正確的分支。
因此，如果處理器每次都猜錯(cuò)，那程序的運(yùn)行時(shí)間就會(huì)邊長(zhǎng)。
這就是上面的代碼為什么運(yùn)行時(shí)間會(huì)相差那么大的原因。
對(duì)于分支語(yǔ)句：
- if (data[c] >= 128)
- sum += data[c];
在保留std::sort(data, data + arraySize);的情況下。數(shù)組data中的內(nèi)容是這樣的：
- 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)
在未排序的情況下，數(shù)組data中的內(nèi)容是這樣的：
- data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
- branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
- = TTNTTTTNTNNTTTN ... (completely random - hard to predict)
也就是說(shuō)，在已經(jīng)排序的情況下，處理器便能更好的預(yù)測(cè)分支了。因此，程序也運(yùn)行的更快。
關(guān)于分支預(yù)測(cè)
閱讀linux源代碼時(shí)，你會(huì)發(fā)現(xiàn)if(likely( )){}或是if(unlikely( ))這樣的語(yǔ)句。對(duì)于條件選擇語(yǔ)句，gcc內(nèi)建了一條指令用于優(yōu)化，在一個(gè)條件經(jīng)常出現(xiàn)，或者該條件很少出現(xiàn)的時(shí)候，編譯器可以根據(jù)這條指令對(duì)條件分支選擇進(jìn)行優(yōu)化。而Linux內(nèi)核把這條指令封裝成了宏likely()和unlikely()。
因此，在編寫(xiě)程序時(shí)，如果一個(gè)分支條件只有在很少數(shù)的情況下才出現(xiàn)時(shí)，我們使用unlikely( )和likely( )能夠加快程序的運(yùn)行,這也是一種優(yōu)化程序的手段。
比如這樣：
- if ( unlikely(statement) ) { //這里便是告訴編譯器，這個(gè)條件只在少數(shù)情況下發(fā)生
- dosomething();
- }
標(biāo)題名稱(chēng)：CodeInside：為什么處理已排序數(shù)組比處理未排序數(shù)組更快？
網(wǎng)頁(yè)URL：http://www.5511xx.com/article/dpchssd.html
