ski*_*mon 5 c++ performance caching
我读了一篇文章(1.5岁http://www.drdobbs.com/parallel/cache-friendly-code-solving-manycores-ne/240012736),其中讨论了缓存性能和数据大小.他们展示了以下代码,他们说这些代码是在i7(沙桥)上运行的
static volatile int array[Size];
static void test_function(void)
{
for (int i = 0; i < Iterations; i++)
for (int x = 0; x < Size; x++)
array[x]++;
}
他们声称如果他们保持Size*Iterations不变,增加Size,当数组内存中的大小增加超过L2缓存大小时,他们会观察到执行时间(10x)的巨大峰值.
作为我自己的练习,我想尝试一下,看看我是否可以为我的机器重现他们的结果.(i7 3770k,win7,visual c ++ 2012编译器,Win32调试模式,未启用优化).令我惊讶的是,我无法看到执行所花费的时间增加(甚至超过L3缓存大小),这让我觉得编译器在某种程度上优化了这段代码.但我也没有看到任何优化.我看到的唯一的速度变化是,在我的机器的字大小以下,它需要稍长.以下是我的时间,代码清单和相关的反汇编.
有谁知道原因:
1)为什么不管阵列的大小如何,所用的时间都不会增加？或者我怎么能找到？
2)为什么所花费的时间从高处开始然后减小直到达到缓存行大小,如果数据小于行大小,是否应该在没有从缓存读取的情况下处理更多迭代？
时序:
Size=1,Iterations=1073741824, Time=3829
Size=2,Iterations=536870912, Time=2625
Size=4,Iterations=268435456, Time=2563
Size=16,Iterations=67108864, Time=2906
Size=32,Iterations=33554432, Time=3469
Size=64,Iterations=16777216, Time=3250
Size=256,Iterations=4194304, Time=3140
Size=1024,Iterations=1048576, Time=3110
Size=2048,Iterations=524288, Time=3187
Size=4096,Iterations=262144, Time=3078
Size=8192,Iterations=131072, Time=3125
Size=16384,Iterations=65536, Time=3109
Size=32768,Iterations=32768, Time=3078
Size=65536,Iterations=16384, Time=3078
Size=262144,Iterations=4096, Time=3172
Size=524288,Iterations=2048, Time=3109
Size=1048576,Iterations=1024, Time=3094
Size=2097152,Iterations=512, Time=3313
Size=4194304,Iterations=256, Time=3391
Size=8388608,Iterations=128, Time=3312
Size=33554432,Iterations=32, Time=3109
Size=134217728,Iterations=8, Time=3515
Size=536870912,Iterations=2, Time=3532
码:
#include <string>
#include <cassert>
#include <windows.h>
template <unsigned int SIZE, unsigned int ITERATIONS>
static void test_body(volatile char* array)
{
for (unsigned int i = 0; i < ITERATIONS; i++)
{
for (unsigned int x = 0; x < SIZE; x++)
{
array[x]++;
}
}
}
template <unsigned int SIZE, unsigned int ITERATIONS>
static void test_function()
{
assert(SIZE*ITERATIONS == 1024*1024*1024);
static volatile char array[SIZE];
test_body<SIZE, 1>(array); //warmup
DWORD beginTime = GetTickCount();
test_body<SIZE, ITERATIONS>(array);
DWORD endTime= GetTickCount();
printf("Size=%u,Iterations=%u, Time=%d\n", SIZE,ITERATIONS, endTime-beginTime);
}
int main()
{
enum { eIterations= 1024*1024*1024};
test_function<1, eIterations>();
test_function<2, eIterations/2>();
test_function<4, eIterations/4>();
test_function<16, eIterations/16>();
test_function<32, eIterations/ 32>();
test_function<64, eIterations/ 64>();
test_function<256, eIterations/ 256>();
test_function<1024, eIterations/ 1024>();
test_function<2048, eIterations/ 2048>();
test_function<4096, eIterations/ 4096>();
test_function<8192, eIterations/ 8192>();
test_function<16384, eIterations/ 16384>();
test_function<32768, eIterations/ 32768>();
test_function<65536, eIterations/ 65536>();
test_function<262144, eIterations/ 262144>();
test_function<524288, eIterations/ 524288>();
test_function<1048576, eIterations/ 1048576>();
test_function<2097152, eIterations/ 2097152>();
test_function<4194304, eIterations/ 4194304>();
test_function<8388608, eIterations/ 8388608>();
test_function<33554432, eIterations/ 33554432>();
test_function<134217728, eIterations/ 134217728>();
test_function<536870912, eIterations/ 536870912>();
}
拆卸
for (unsigned int i = 0; i < ITERATIONS; i++)
00281A59 mov dword ptr [ebp-4],0
00281A60 jmp test_body<536870912,2>+1Bh (0281A6Bh)
00281A62 mov eax,dword ptr [ebp-4]
00281A65 add eax,1
00281A68 mov dword ptr [ebp-4],eax
00281A6B cmp dword ptr [ebp-4],2
00281A6F jae test_body<536870912,2>+53h (0281AA3h)
{
for (unsigned int x = 0; x < SIZE; x++)
00281A71 mov dword ptr [ebp-8],0
00281A78 jmp test_body<536870912,2>+33h (0281A83h)
00281A7A mov eax,dword ptr [ebp-8]
{
for (unsigned int x = 0; x < SIZE; x++)
00281A7D add eax,1
00281A80 mov dword ptr [ebp-8],eax
00281A83 cmp dword ptr [ebp-8],20000000h
00281A8A jae test_body<536870912,2>+51h (0281AA1h)
{
array[x]++;
00281A8C mov eax,dword ptr [array]
00281A8F add eax,dword ptr [ebp-8]
00281A92 mov cl,byte ptr [eax]
00281A94 add cl,1
00281A97 mov edx,dword ptr [array]
00281A9A add edx,dword ptr [ebp-8]
00281A9D mov byte ptr [edx],cl
}
00281A9F jmp test_body<536870912,2>+2Ah (0281A7Ah)
}
00281AA1 jmp test_body<536870912,2>+12h (0281A62h)
TL; DR:您的测试不正确测试缓存延迟或速度.相反,它测量了通过OoO CPU管道斩波复杂代码的一些问题.
使用正确的测试来测量缓存和内存延迟:来自lmbench的lat_mem_rd ; 和速度(带宽)测量的正确测试:STREAM内存速度基准测试 ; 从memtest86测试缓存速度与rep movsl主操作)
此外,在现代(2010年及更新版本)桌面/服务器CPU 中,在L1和L2高速缓存附近内置了硬件预取逻辑,它将检测线性访问模式,并在您要求此数据之前将数据从外部高速缓存预加载到内部:英特尔优化手册- 7.2数据的硬件预取,第365页; intel.com博客,2009年.很难禁用所有硬件预取(SO Q/A 1,SO Q/A 2)
很长的故事:
我将尝试使用perfLinux(aka perf_events)中的性能监视工具对类似测试进行多次测量.代码基于Joky的程序(32位整数数组,而不是字符数组),并被分成几个二进制文件:a5大小为2 ^ 5 = 32; a10=> 2 ^ 10 = 1024(4 KB); a15=> 2 ^ 15 = 32768,a20(1百万英寸= 4 MB)和a25(32百万英寸= 128 MB ).cpu是i7-2600四核Sandy Bridge 3.4 GHz.
让我们从基本perf stat的默认事件集开始(跳过一些行).我选择了2 ^ 10(4 KB)和2 ^ 20(4 MB)
$ perf stat ./a10
Size=1024 ITERATIONS=1048576, TIME=2372.09 ms
Performance counter stats for './a10':
276 page-faults # 0,000 M/sec
8 238 473 169 cycles # 3,499 GHz
4 936 244 310 stalled-cycles-frontend # 59,92% frontend cycles idle
415 849 629 stalled-cycles-backend # 5,05% backend cycles idle
11 832 421 238 instructions # 1,44 insns per cycle
# 0,42 stalled cycles per insn
1 078 974 782 branches # 458,274 M/sec
1 080 091 branch-misses # 0,10% of all branches
$ perf stat ./a20
Size=1048576 ITERATIONS=1024, TIME=2432.4 ms
Performance counter stats for './a20':
2 321 page-faults # 0,001 M/sec
8 487 656 735 cycles # 3,499 GHz
5 184 295 720 stalled-cycles-frontend # 61,08% frontend cycles idle
663 245 253 stalled-cycles-backend # 7,81% backend cycles idle
11 836 712 988 instructions # 1,39 insns per cycle
# 0,44 stalled cycles per insn
1 077 257 745 branches # 444,104 M/sec
30 601 branch-misses # 0,00% of all branches
我们在这里能看到什么？指令计数非常接近(因为大小*迭代是常数),循环计数和时间也很接近.两个例子都有10亿个分支,99%的预测良好.但是前端有60%的失速计数,后端有5-8%的失速计数.前端档位是指令提取和解码中的停顿,很难说明原因,但是对于你的代码前端不能解码每个时钟4个指令(英特尔优化手册第B-41页,B.3节 - "性能调整") ...... Sandy Bridge的技术",B.3.2小节自上而下的性能表征......
$ perf record -e stalled-cycles-frontend ./a20
Size=1048576 ITERATIONS=1024, TIME=2477.65 ms
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.097 MB perf.data (~4245 samples) ]
$ perf annotate -d a20|cat
Percent | Source code & Disassembly of a20
------------------------------------------------
: 08048e6f <void test_body<1048576u, 1024u>(int volatile*)>:
10.43 : 8048e87: mov -0x8(%ebp),%eax
1.10 : 8048e8a: lea 0x0(,%eax,4),%edx
0.16 : 8048e91: mov 0x8(%ebp),%eax
0.78 : 8048e94: add %edx,%eax
6.87 : 8048e96: mov (%eax),%edx
52.53 : 8048e98: add $0x1,%edx
9.89 : 8048e9b: mov %edx,(%eax)
14.15 : 8048e9d: addl $0x1,-0x8(%ebp)
2.66 : 8048ea1: mov -0x8(%ebp),%eax
1.39 : 8048ea4: cmp $0xfffff,%eax
或者在这里使用原始操作码(objdump -d),有些具有相当复杂的索引,因此有可能它们无法由3个简单的解码器处理并等待唯一复杂的解码器(图像在那里:http://www.realworldtech.com/sandy-桥/ 4 /)
8048e87: 8b 45 f8 mov -0x8(%ebp),%eax
8048e8a: 8d 14 85 00 00 00 00 lea 0x0(,%eax,4),%edx
8048e91: 8b 45 08 mov 0x8(%ebp),%eax
8048e94: 01 d0 add %edx,%eax
8048e96: 8b 10 mov (%eax),%edx
8048e98: 83 c2 01 add $0x1,%edx
8048e9b: 89 10 mov %edx,(%eax)
8048e9d: 83 45 f8 01 addl $0x1,-0x8(%ebp)
8048ea1: 8b 45 f8 mov -0x8(%ebp),%eax
8048ea4: 3d ff ff 0f 00 cmp $0xfffff,%eax
后端停顿是通过等待内存或缓存(测量缓存时感兴趣的东西)和内部执行核心停顿创建的停顿:
$ perf record -e stalled-cycles-backend ./a20
Size=1048576 ITERATIONS=1024, TIME=2480.09 ms
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.095 MB perf.data (~4149 samples) ]
$ perf annotate -d a20|cat
4.25 : 8048e96: mov (%eax),%edx
58.68 : 8048e98: add $0x1,%edx
8.86 : 8048e9b: mov %edx,(%eax)
3.94 : 8048e9d: addl $0x1,-0x8(%ebp)
7.66 : 8048ea1: mov -0x8(%ebp),%eax
7.40 : 8048ea4: cmp $0xfffff,%eax
报告的大多数后端停顿是add 0x1,%edx因为它是数据的使用者,从上一个命令中的数组加载.对于存储到数组,它们占后端档位的70%,或者如果我们将程序中的后端档位部分(7%)乘以5%的所有档位.或者换句话说,缓存比程序更快.现在我们可以回答您的第一个问题:
无论阵列的大小如何,为什么所用的时间都没有增加？
您测试是如此糟糕(未优化),您正在尝试测量缓存,但它们的总运行时间仅减慢了5%.你的测试是如此不稳定(嘈杂),你不会看到这5%的效果.
通过自定义perf stat运行,我们还可以测量缓存请求丢失率.对于4 KB程序,L1数据缓存服务于99,99%的所有负载和99,999%的所有存储.我们可以注意到,您的不正确测试产生的缓存请求数量要多于在数组上行走和增加每个元素(10亿次加载+ 10亿次存储)所需的数量.其他访问用于处理局部变量,例如x,它们总是由缓存服务,因为它们的地址是常量)
$ perf stat -e 'L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses' ./a10
Size=1024 ITERATIONS=1048576, TIME=2412.25 ms
Performance counter stats for './a10':
5 375 195 765 L1-dcache-loads
364 140 L1-dcache-load-misses # 0,01% of all L1-dcache hits
2 151 408 053 L1-dcache-stores
13 350 L1-dcache-store-misses
对于4 MB程序,命中率要差很多倍.失误多100倍!现在1.2%的内存请求不是由L1提供,而是由L2提供.
$ perf stat -e 'L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses' ./a20
Size=1048576 ITERATIONS=1024, TIME=2443.92 ms
Performance counter stats for './a20':
5 378 035 007 L1-dcache-loads
67 725 008 L1-dcache-load-misses # 1,26% of all L1-dcache hits
2 152 183 588 L1-dcache-stores
67 266 426 L1-dcache-store-misses
当我们想要注意缓存延迟从4个cpu滴答到12个(3倍长),并且此更改仅影响1.2%的缓存请求,以及当我们的程序只有7%的减速敏感时,是不是这种情况到缓存延迟???
如果我们将使用更大的数据集怎么办？好的,这是a25(2 ^ 25的4字节整数= 128 MB,是缓存大小的几倍):
$ perf stat ./a25
Size=134217728 ITERATIONS=8, TIME=2437.25 ms
Performance counter stats for './a25':
262 417 page-faults # 0,090 M/sec
10 214 588 827 cycles # 3,499 GHz
6 272 114 853 stalled-cycles-frontend # 61,40% frontend cycles idle
1 098 632 880 stalled-cycles-backend # 10,76% backend cycles idle
13 683 671 982 instructions # 1,34 insns per cycle
# 0,46 stalled cycles per insn
1 274 410 549 branches # 436,519 M/sec
315 656 branch-misses # 0,02% of all branches
$ perf stat -e 'L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses' ./a25
Size=134217728 ITERATIONS=8, TIME=2444.13 ms
Performance counter stats for './a25':
6 138 410 226 L1-dcache-loads
77 025 747 L1-dcache-load-misses # 1,25% of all L1-dcache hits
2 515 141 824 L1-dcache-stores
76 320 695 L1-dcache-store-misses
几乎相同的L1未命中率,以及更多的后端档位.我能够获得关于"缓存引用,缓存未命中"事件的统计信息,我建议它们是关于L3缓存的(对L2的请求有几倍):
$ perf stat -e 'cache-references,cache-misses' ./a25
Size=134217728 ITERATIONS=8, TIME=2440.71 ms
Performance counter stats for './a25':
17 053 482 cache-references
11 829 118 cache-misses # 69,365 % of all cache refs
因此,未命中率很高,但是测试会产生10亿(有用)负载,其中只有0.08亿缺少L1.内存提供了10亿个请求.内存延迟大约为230 cpu时钟,而不是4个时钟L1延迟.测试能看到这个吗？可能是,如果噪音很低.
| 归档时间： |
|
| 查看次数： |
1413 次 |
| 最近记录： |