33%的指令减少，17%的内存访问减少，但速度提高了4倍？
33%的指令减少，17%的内存访问减少，但速度提高了4倍？
摘要
\n我有两段C++代码进行相同的计算。代码B的指令数量约比代码A少33％，内存访问量约少17％，但运行速度却是后者的四倍。这是什么原因？此外，我们如何验证你们答案中提供的声明？\n在两段代码中，\n
- \n
howmany为20,000,000testees有20,000,000个元素，在代码A和代码B的代码片段之前使用随机生成器(mt19937)在启动时生成。- 乘法通过单次内存访问进行处理(如后续的汇编代码中所见)
- 两段代码都使用了优化标志
-O1进行编译
\n
\n
\n
\n
\n
一些代码
\n代码A-运行时间约为95到110毫秒\n
GF2 sum {GF2(1)};
auto a = system_clock::now();
for(size_t i=0;i
\n代码B-运行时间约为25到30毫秒\n
GF2 sum1 {GF2(1)};
GF2 sum2 {GF2(1)};
GF2 sum3 {GF2(1)};
GF2 sum4 {GF2(1)};
auto aa = system_clock::now();
for(size_t i=0;i
\ntestees是一个填充了20M个随机GF2实例的std::vector。5_3_betterbenchmark.cpp在运行时随机生成它们，所以代码A和B都使用相同的testees。\n代码A，主循环（循环运行20M次，总共执行了20M * 9 = 180M条指令）\n
01 .L170:
02 movzbl 15(%rsp), %eax # sum.rep在15(%rsp)上->内存访问#1
03 salq $8, %rax # 将sum.rep（在%rax中）左移8位
04 addq %rsi, %rax # %rsi是multTable的地址
05 movzbl (%rdx), %ecx # testees[i].rep在（%rdx）上->内存访问#2
06 movzbl (%rax,%rcx), %eax # （%rax,%rcx）是multTable[sum.rep][testees[i].rep]->内存访问#3
07 movb %al, 15(%rsp) # 将其移到sum.rep->内存访问#4
08 addq $1, %rdx # i+=1，但是这里是指针操作
09 cmpq %rdi, %rdx # 循环条件检查
10 jne .L170
\n代码B，主循环（循环运行5M次，总共执行了5M * 24 = 120M条指令）\n
01 .L171:
02 movzbl 14(%rsp), %r8d # sum1->内存访问#1
03 salq $8, %r8
04 addq %rdi, %r8
05 movzbl (%rsi), %r10d # ->内存访问#2
06 movzbl (%r8,%r10), %r8d # ->内存访问#3
07 movb %r8b, 14(%rsp) # ->内存访问#4
08 movzbl %cl, %ecx # sum2已在寄存器中
09 salq $8, %rcx
10 addq %rdi, %rcx
11 movzbl 1(%rsi), %r10d # ->内存访问#5
12 movzbl (%rcx,%r10), %ecx# ->内存访问#6
13 movzbl %dl, %edx # sum3也已在寄存器中
14 salq $8, %rdx
15 addq %rdi, %rdx
16 movzbl 2(%rsi), %r10d # ->内存访问#7
17 movzbl (%rdx,%r10), %edx# ->内存访问#8
18 movzbl %al, %eax # sum4也已在寄存器中
19 salq $8, %rax
20 addq %rdi, %rax
21 movzbl 3(%rsi), %r10d # ->内存访问#9
22 movzbl (%rax,%r10), %eax# ->内存访问#10
23 addq $4, %rsi # i+=4（在指针中）
24 cmpq %r9, %rsi # 决定是否终止循环
25 jne .L171
\n
假设
\n以下是我和同事在谷歌搜索和深思后提出的一些假设，但我并不完全相信。\n
\n
- 声明：编译器优化将
std::chrono::system_clock()的调用位置放错了\n
\n
- 在查看整个汇编代码后，我们确认这并不是事实
\n
\n
\n
- 声明：当发生进程切换并且TLB被清除时，代码A更容易发生TLB缺失（根据Linux内核的实现方式）\n
\n
- 然而，在两次运行期间的上下文切换次数几乎相同，大多数情况下只有6次（使用
sudo perf stat进行检查），并且上下文切换次数对测量时间几乎没有影响。
\n
\n
\n
- 声明：代码B导致更少的缓存缺失\n
\n
- 然而，在这两段代码中，
testees以完全相同的顺序访问，并且multTable在两段代码中以随机顺序访问20M次-这意味着两段代码中的缓存缺失数量应该大致相同
\n
- 此外，由于非常频繁地访问
sum.rep/sum1.rep，任何合理的缓存策略都将将它们保留在L1缓存中-从而从访问sum.rep中产生很少的缓存缺失。
\n
\n
\n
\n
问题关闭后进行编辑
\n这在很大程度上是进行评论建议后的一份报告。\n
一些澄清
\n用户Aki Suihkonen在评论中指出，此测试本质上是有偏见的，因为我可能没有防止GF2(0)混入。实际上，我从一开始就防止了这种情况（有关更多详细信息，请参见我的下面的评论）。我相信我的问题是完全有效的，也许除了它在网站上已经有答案。\n
后续
\n我的问题实际上有两个问题。\n
\n
- 为什么代码B（4倍）比代码A快
\n
- 如何验证你提供的声明是真实的？
\n
\n唯一回答第二个问题的评论是用户mattlangford的。mattlangford建议我查看llvm-mca，这是一个很棒的工具，可以让我以时间线的方式可视化执行过程（从调度到退休）。然而，只有在得到一些不令人满意的结果之后，我才注意到指南中的以下几句话：\n
\n
\n
- LSUnit不知道何时可能发生存储到加载的转发
\n
- LSUnit不知道关于缓存层次结构和内存类型的任何信息。
\n
- LSUnit不知道如何识别序列化操作和内存屏障。
\n
\n
\n此外，代码A的llvm-mca结果看起来像这样（使用的命令是llvm-mca（输入）-iterations=200 -timeline -o 630_llvmmca.txt）：\n
Timeline view:
0123456789 012345
Index 0123456789 0123456789
[0,0] DeeeeeER . . . . . . movzbl 14(%rsp), %eax
[0,1] D=====eER . . . . . . shlq $8, %rax
[0,2] D======eER. . . . . . addq %rsi, %rax
[0,3] DeeeeeE--R. . . . . . movzbl (%rdx), %ecx
[0,4] .D======eeeeeER. . . . . movzbl (%rax,%rcx), %eax
[0,5] .D===========eER . . . . . movb %al, 14(%rsp)
[0,6] .DeE-----------R . . . . . addq $1, %rdx
[0,7] .D=eE----------R . . . . . cmpq %rdi, %rdx
[0,8] . D=eE---------R . . . . . jne .L171
[1,0] . DeeeeeE------R . . . . . movzbl 14(%rsp), %eax
[1,1] . D=====eE-----R . . . . . shlq $8, %rax
[1,2] . D======eE----R . . . . . addq %rsi, %rax
[1,3] . DeeeeeE-----R . . . . . movzbl (%rdx), %ecx
[1,4] . D======eeeeeER . . . . . movzbl (%rax,%rcx), %eax
[1,5] . D===========eER . . . . . movb %al, 14(%rsp)
[1,6] . DeE-----------R . . . . . addq $1, %rdx
[1,7] . DeE----------R . . . . . cmpq %rdi, %rdx
[1,8] . D=eE---------R . . . . . jne .L171
[2,0] . DeeeeeE------R . . . . . movzbl 14(%rsp), %eax
[2,1] . D=====eE-----R . . . . . shlq $8, %rax
[2,2] . D=====eE----R . . . . . addq %rsi, %rax
[2,3] . DeeeeeE-----R . . . . . movzbl (%rdx), %ecx
\n以此类推。至少根据这个图表，每次同时调度四条指令。我也检查了代码B的llvm-mca输出：\n
[0,0] DeeeeeER . . . . . . . . . . . . . . . movzbl 14(%rsp), %r8d
[0,1] D=====eER . . . . . . . . . . . . . . . shlq $8, %r8
[0,2] D======eER. . . . . . . . . . . . . . . addq %rdi, %r8
[0,3] DeeeeeE--R. . . . . . . . . . . . . . . movzbl (%rsi), %r10d
[0,4] .D======eeeeeER. . . . . . . . . . . . . . movzbl (%r8,%r10), %r8d
[0,5] .D===========eER . . . . . . . . . . . . . movb %r8b, 14(%rsp)
[0,6] .DeE-----------R . . . . . . . . . . . . . movzbl %cl, %ecx
\n坦率地说，与代码A没有什么不同，只是现在对内存的写入减少了4倍-这实际上不应该有什么影响，因为对于任何合理的缓存策略，无论14(%rbx)上是什么，都应该保留在L1缓存中。（据我所知，过去几十年来，所有兼容英特尔的CPU都采用了写回缓存）\n
更多测试
\nMargaret Bloom用户声称：\n
\n如果你展开得越多，你会看到性能的增长越少。\n
\n这个说法被证明是正确的。我将代码B展开了2倍，并看到了2倍的速度增长。在这之后，我无法获得进一步的加速。\n代码C\n
GF2 sum1 {GF2(1)};
GF2 sum2 {GF2(1)};
GF2 sum3 {GF2(1)};
GF2 sum4 {GF2(1)};
GF2 sum5 {GF2(1)};
GF2 sum6 {GF2(1)};
GF2 sum7 {GF2(1)};
GF2 sum8 {GF2(1)};
auto aa = system_clock::now();
for(size_t i=0;i
\n代码C-主循环的汇编代码\n
1532 movzbl 14(%rsp), %ebp
1533 salq $8, %rbp
1534 addq %r11, %rbp
1535 movzbl (%rax), %r13d
1536 movzbl 0(%rbp,%r13), %ebp
1537 movb %bpl, 14(%rsp)
1538 movzbl %r10b, %r10d
1539 salq $8, %r10
1540 addq %r11, %r10
1541 movzbl 1(%rax), %r13d
1542 movzbl (%r10,%r13), %r10d
1543 movzbl %r9b, %r9d
1544 salq $8, %r9
1545 addq %r11, %r9
1546 movzbl 2(%rax), %r13d
1547 movzbl (%r9,%r13), %r9d
1548 movzbl %r8b, %r8d
1549 salq $8, %r8
1550 addq %r11, %r8
1551 movzbl 3(%rax), %r13d
1552 movzbl (%r8,%r13), %r8d
1553 movzbl %dil, %edi
1554 salq $8, %rdi
1555 addq %r11, %rdi
1556 movzbl 4(%rax), %r13d
1557 movzbl (%rdi,%r13), %edi
1558 movzbl %sil, %esi
1559 salq $8, %rsi
1560 addq %r11, %rsi
1561 movzbl 5(%rax), %r13d
1562 movzbl (%rsi,%r13), %esi
1563 movzbl %cl, %ecx
1564 salq $8, %rcx
1565 addq %r11, %rcx
1566 movzbl 6(%rax), %r13d
1567 movzbl (%rcx,%r13), %ecx
1568 movzbl %dl, %edx
1569 salq $8, %rdx
1570 addq %r11, %rdx
1571 movzbl 7(%rax), %r13d
1572 movzbl (%rdx,%r13), %edx
1573 addq $8, %rax
1574 cmpq %r12, %rax
1575 jne .L171
\n
初步结论和一些问题
\n将所有信息汇集在一起，这是我能得出的结论。\n
\n
- 根据llvm-mca的说法，如果内存延迟实际上像上面的图表中显示的那样短，每个周期可以同时调度四条指令，甚至对于代码A也是如此。
\n
- 然而，由于“llvm-mca对缓存结构或内存类型没有任何了解”，因此它提供的任何关于内存延迟的信息可能是严重错误的。
\n
- 现在，当真正考虑内存层次结构时，
llvm-mca提供的内存延迟预测对于从multTable[sum.rep][other.rep]获取的movzbl来说可能是严重错误的-在许多情况下可能需要数百个周期。
\n
代码B通过将代码A的汇编循环写入四次并重命名一些寄存器/内存来消除了一些依赖关系-也就是所谓的冒险。\n
- 如果我尝试绘制类似于上面由llvm-mca生成的图表，但这次考虑到缓存缺失，我应该得到总运行时间的粗略估计...？
\n
\n
我仍然困惑
\n
\n
- 如果我的CPU一次只能调度四条指令，那么是什么原因解释了代码C相对于代码A的8倍加速？
\n
\n
未来计划
\n
\n
- 现在，这显然是一个不适合在stackoverflow上提问的问题-我将在其他地方提问-或者再进行更多的查找。
\n
\n
非常感谢您提供宝贵的见解！