這些矩陣換位時間爲什麼如此違反直覺？

以下示例代碼生成大小N的矩陣，並且調換它SAMPLES的次數。當N = 512轉置運算的平均執行時間是2144 μs（coliru link）。第一眼看上去沒有什麼特別的，對不對？......這些矩陣換位時間爲什麼如此違反直覺？

嗯，這裏是

N = 513→1451 μs
N = 519→600 μs
N = 530→486 μs
N = 540結果→492 μs（最後！理論開始工作:)。

那麼，爲什麼在實踐中這些簡單的計算，從理論上如此不同？這種行爲與CPU緩存一致性或緩存未命中有關嗎？如果是這樣，請解釋。

#include <algorithm> 
#include <iostream> 
#include <chrono> 

constexpr int N  = 512; // Why is 512 specifically slower (as of 2016) 
constexpr int SAMPLES = 1000; 
using us = std::chrono::microseconds; 

int A[N][N]; 

void transpose() 
{ 
    for (int i = 0 ; i < N ; i++) 
    for (int j = 0 ; j < i ; j++) 
     std::swap(A[i][j], A[j][i]); 
} 

int main() 
{ 
    // initialize matrix 
    for (int i = 0 ; i < N ; i++) 
    for (int j = 0 ; j < N ; j++) 
     A[i][j] = i+j; 

    auto t1 = std::chrono::system_clock::now(); 
    for (int i = 0 ; i < SAMPLES ; i++) 
     transpose(); 
    auto t2 = std::chrono::system_clock::now(); 

    std::cout << "Average for size " << N << ": " << std::chrono::duration_cast<us>(t2 - t1).count()/SAMPLES << " (us)"; 
}

來源

2017-03-02 Narek Atayan

你運行過這段代碼多少次？根據您的系統可能做多少其他事情，運行時可能會因運行而異。這些是大約10或20次運行的平均時間，還是單次運行的時間？ – JGroven

可能512是一個魔術般的大小，可以適應緩存可怕，所以你會得到很多緩存未命中。其他尺寸適合更好，所以你得到更少的失誤。 – NathanOliver

錯誤的方式@NathanOliver - 512比* 513慢* * –

這是由於緩存未命中所致。您可以使用valgrind --tool=cachegrind查看未命中數量。使用N = 512你得到了以下的輸出：

Average for size 512: 13052 (us)==21803== 
==21803== I refs:  1,054,721,935 
==21803== I1 misses:   1,640 
==21803== LLi misses:   1,550 
==21803== I1 miss rate:   0.00% 
==21803== LLi miss rate:   0.00% 
==21803== 
==21803== D refs:  524,278,606 (262,185,156 rd + 262,093,450 wr) 
==21803== D1 misses:  139,388,226 (139,369,492 rd +  18,734 wr) 
==21803== LLd misses:   25,828 (  7,959 rd +  17,869 wr) 
==21803== D1 miss rate:   26.6% (  53.2%  +   0.0% ) 
==21803== LLd miss rate:   0.0% (  0.0%  +   0.0% ) 
==21803== 
==21803== LL refs:   139,389,866 (139,371,132 rd +  18,734 wr) 
==21803== LL misses:   27,378 (  9,509 rd +  17,869 wr) 
==21803== LL miss rate:   0.0% (  0.0%  +   0.0% )

雖然使用N=530你得到了以下的輸出：

Average for size 530: 13264 (us)==22783== 
==22783== I refs:  1,129,929,859 
==22783== I1 misses:   1,640 
==22783== LLi misses:   1,550 
==22783== I1 miss rate:   0.00% 
==22783== LLi miss rate:   0.00% 
==22783== 
==22783== D refs:  561,773,362 (280,923,156 rd + 280,850,206 wr) 
==22783== D1 misses:  32,899,398 (32,879,492 rd +  19,906 wr) 
==22783== LLd misses:   26,999 (  7,958 rd +  19,041 wr) 
==22783== D1 miss rate:   5.9% (  11.7%  +   0.0% ) 
==22783== LLd miss rate:   0.0% (  0.0%  +   0.0% ) 
==22783== 
==22783== LL refs:   32,901,038 (32,881,132 rd +  19,906 wr) 
==22783== LL misses:   28,549 (  9,508 rd +  19,041 wr) 
==22783== LL miss rate:   0.0% (  0.0%  +   0.0% )

正如你所看到的，D1在512惦記比530大約3.5倍

來源

2017-03-02 20:56:23 Amadeus

所以一個解決方法是使用下一個較大的矩陣作爲「緩存友好」矩陣，留下一些未使用的列（可能是行），但它應該更快。 – rcgldr

是的，高失誤率是因爲在某些內存訪問模式下，關聯性只允許使用總緩存的一小部分。 –

@rcgldr：更好的解決方案是更改內存訪問順序。而不是交換單個元素，交換一個4x4塊，這樣您可以訪問交換兩端的同一緩存行中的所有元素。 –

這些矩陣換位時間爲什麼如此違反直覺？

回答

相關問題