以下示例代码生成一个大小为 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)";
}
最佳答案
这是由于缓存未命中。您可以使用 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% )
如您所见,512 中的 D1 未命中大约是 530 中的 3.5 倍
关于c++ - 为什么这些矩阵转置时间如此违反直觉?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42564866/