日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
CodeInside：為什么處理已排序數(shù)組比處理未排序數(shù)組更快？

很久以前在stackoverflow上看到下面這段代碼，今天忍不住把它摘錄過來。

成都創(chuàng)新互聯(lián)自2013年起，先為邛崍等服務(wù)建站，邛崍等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為邛崍企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

 
 
    
  
  
  1. #include  
    2. 
  
  
  2. #include  
    3. 
  
  
  3. #include  
    4. 
  
  
  4.   
    5. 
  
  
  5. int main() 
    6. 
  
  
  6. { 
    7. 
  
  
  7.     // Generate data 
    8. 
  
  
  8.     const unsigned arraySize = 32768; 
    9. 
  
  
  9.     int data[arraySize]; 
    10. 
  
  
  10.   
    11. 
  
  
  11.     for (unsigned c = 0; c < arraySize; ++c) 
    12. 
  
  
  12.         data[c] = std::rand() % 256; 
    13. 
  
  
  13.   
    14. 
  
  
  14.     // !!! With this, the next loop runs faster 
    15. 
  
  
  15.     std::sort(data, data + arraySize); 
    16. 
  
  
  16.   
    17. 
  
  
  17.     // Test 
    18. 
  
  
  18.     clock_t start = clock(); 
    19. 
  
  
  19.     long long sum = 0; 
    20. 
  
  
  20.   
    21. 
  
  
  21.     for (unsigned i = 0; i < 100000; ++i) 
    22. 
  
  
  22.     { 
    23. 
  
  
  23.         // Primary loop 
    24. 
  
  
  24.         for (unsigned c = 0; c < arraySize; ++c) 
    25. 
  
  
  25.         { 
    26. 
  
  
  26.             if (data[c] >= 128) 
    27. 
  
  
  27.                 sum += data[c]; 
    28. 
  
  
  28.         } 
    29. 
  
  
  29.     } 
    30. 
  
  
  30.   
    31. 
  
  
  31.     double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC; 
    32. 
  
  
  32.   
    33. 
  
  
  33.     std::cout << elapsedTime << std::endl; 
    34. 
  
  
  34.     std::cout << "sum = " << sum << std::endl; 
    35. 
  
  
  35. }
    36.

上面的程序在保留std::sort(data, data + arraySize);語句時，程序運行時間是1.93 秒

但去掉排序語句后，程序運行時間是11.54秒

問題：為什么會出現(xiàn)這種情況？

解答：分支預(yù)測。

[[119029]]

程序分支

考慮以下if語句塊。對于處理器來說，就是一個分支指令，如下：

處理器每次遇到一條分支時，它都不知道該走哪一條道。這時候該怎么辦？程序停下來，等待前面的指令執(zhí)行完，得到確切的結(jié)果后，再接著走某一條分支。

現(xiàn)代處理器都支持指令并行處理和超流水線作業(yè)。因此，當(dāng)處理器遇到程序分支時，都會去猜測應(yīng)該走哪一條分支。

如果猜對了，程序接著流暢運行。如果猜錯了，則處理器需要做一些額外的工作，再次回到那條正確的分支。

因此，如果處理器每次都猜錯，那程序的運行時間就會邊長。

這就是上面的代碼為什么運行時間會相差那么大的原因。

對于分支語句：

 
 
    
  
  
  1. if (data[c] >= 128) 
    2. 
  
  
  2.     sum += data[c];
    3.

在保留std::sort(data, data + arraySize);的情況下。數(shù)組data中的內(nèi)容是這樣的：

 
 
    
  
  
  1. T = branch taken 
    2. 
  
  
  2. N = branch not taken 
    3. 
  
  
  3.   
    4. 
  
  
  4. data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... 
    5. 
  
  
  5. branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ... 
    6. 
  
  
  6.   
    7. 
  
  
  7.        = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)
    8.

在未排序的情況下，數(shù)組data中的內(nèi)容是這樣的：

 
 
    
  
  
  1. data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ... 
    2. 
  
  
  2. branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ... 
    3. 
  
  
  3.   
    4. 
  
  
  4.        = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)
    5.

也就是說，在已經(jīng)排序的情況下，處理器便能更好的預(yù)測分支了。因此，程序也運行的更快。

關(guān)于分支預(yù)測

閱讀linux源代碼時，你會發(fā)現(xiàn)if(likely( )){}或是if(unlikely( ))這樣的語句。對于條件選擇語句，gcc內(nèi)建了一條指令用于優(yōu)化，在一個條件經(jīng)常出現(xiàn)，或者該條件很少出現(xiàn)的時候，編譯器可以根據(jù)這條指令對條件分支選擇進(jìn)行優(yōu)化。而Linux內(nèi)核把這條指令封裝成了宏likely()和unlikely()。

因此，在編寫程序時，如果一個分支條件只有在很少數(shù)的情況下才出現(xiàn)時，我們使用unlikely( )和likely( )能夠加快程序的運行,這也是一種優(yōu)化程序的手段。

比如這樣：

 
 
    
  
  
  1. if ( unlikely(statement) ) { //這里便是告訴編譯器，這個條件只在少數(shù)情況下發(fā)生 
    2. 
  
  
  2. 
  
  
  3. dosomething(); 
    4. 
  
  
  4. 
  
  
  5. }
    6.

分享題目：CodeInside：為什么處理已排序數(shù)組比處理未排序數(shù)組更快？
本文鏈接：http://m.5511xx.com/article/dpchssd.html