Jay*_* Yi 5 c++ performance assembly g++
我有两段 C++ 代码，它们执行相同的计算。与代码 A 相比，代码 B 确实减少了大约 33% 的指令，大约减少了 17% 的内存访问，但运行速度是代码 A 的四倍（而不是两倍）。会是什么原因呢？此外，我们如何才能确认您的回答所提供的主张？
在这两个代码中，
howmany是 20 000 000testees有 20 000 000 个元素，mt19937在启动时（在这些片段之前）为代码 A 和代码 B 随机生成 ( )。-O1代码 A - 运行时间约为。95 至 110 毫秒
GF2 sum {GF2(1)};
auto a = system_clock::now();
for(size_t i=0;i<howmany;i++){
sum *= testees[i];
}
auto b = system_clock::now();
代码 B - 运行时间约为。25 至 30 毫秒
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<howmany;i+=4){
sum1 *= testees[i]; // runs sum1.rep = multTable[sum1.rep][testees[i].rep]
sum2 *= testees[i+1]; // GF2::rep is of type std::uint8_t
sum3 *= testees[i+2]; // multTable is a std::uint8_t array of size 256 * 256; 64KB in total.
sum4 *= testees[i+3];
}
sum1 = sum1*sum2*sum3*sum4;
auto bb = system_clock::now();
testees是一个充满 20M 随机 GF2 实例的 std::vector。5_3_betterbenchmark.cpp在运行时随机生成它们，因此代码 A 和 B 以相同的testees.
代码 A，主循环（运行 20M 次，总共 20M * 9 = 180M 条指令）
01 .L170:
02 movzbl 15(%rsp), %eax # on 15(%rsp) is sum.rep -> mem access #1
03 salq $8, %rax # left shift sum.rep(in %rax) by 8 bits
04 addq %rsi, %rax # on %rsi is the address for multTable
05 movzbl (%rdx), %ecx # on (%rdx) is testees[i].rep -> mem access #2
06 movzbl (%rax,%rcx), %eax # (%rax,%rcx) is multTable[sum.rep][testees[i].rep] -> mem access #3
07 movb %al, 15(%rsp) # moves this to sum.rep -> mem access #4
08 addq $1, %rdx # i+=1 but in pointers
09 cmpq %rdi, %rdx # loop condition check
10 jne .L170
代码 B，主循环（运行 5M 次，总共 5M * 24 = 120M 条指令）
01 .L171:
02 movzbl 14(%rsp), %r8d # sum1, -> mem access #1
03 salq $8, %r8
04 addq %rdi, %r8
05 movzbl (%rsi), %r10d # -> mem access #2
06 movzbl (%r8,%r10), %r8d # -> mem access #3
07 movb %r8b, 14(%rsp) # -> mem access #4
08 movzbl %cl, %ecx # sum2 is already in register for some reason
09 salq $8, %rcx
10 addq %rdi, %rcx
11 movzbl 1(%rsi), %r10d # -> mem access #5
12 movzbl (%rcx,%r10), %ecx# -> mem access #6
13 movzbl %dl, %edx # sum3 is also already in register for some reason
14 salq $8, %rdx
15 addq %rdi, %rdx
16 movzbl 2(%rsi), %r10d # -> mem access #7
17 movzbl (%rdx,%r10), %edx# -> mem access #8
18 movzbl %al, %eax # sum4 is also already in register for some reason
19 salq $8, %rax
20 addq %rdi, %rax
21 movzbl 3(%rsi), %r10d # -> mem access #9
22 movzbl (%rax,%r10), %eax# -> mem access #10
23 addq $4, %rsi # i+=4 (in pointers)
24 cmpq %r9, %rsi # decide if we should terminate loop
25 jne .L171
以下是我和我的同事在谷歌搜索和认真思考后提出的一些假设：但我很难相信。
std::chrono::system_clock()编译器优化导致调用错误
sudo perf stat两者进行了检查），并且上下文切换次数对测量时间几乎没有影响。testees在两个代码中以完全相同的顺序访问，并且multTable在两个代码中以随机顺序访问 20M 次 - 这意味着两个代码中的缓存未命中数量应该大致相同sum.rep/sum1.rep的访问非常频繁，任何合理的缓存策略都会将它们保留在 L1 缓存上 - 从而导致访问 时很少出现缓存未命中sum.rep。这很大程度上是在检查了评论中建议的内容后的报告。
用户Aki Suihkonen在评论中指出，这个测试本质上是有偏见的，因为我可能没有阻止GF2(0)被混入。事实上，我从一开始就阻止了这种情况（更多细节请参见下面我的评论） 。我相信我的问题是一个完全有效的问题，也许除了它在网站其他地方有答案这一事实之外。
我的问题实际上是两个问题合二为一。
解决第二个问题的唯一评论是用户 mattlangford 的评论。mattlangford 建议我查看llvm-mca，这是一个很酷的工具，它还可以让我以时间线方式可视化执行（从调度到退出）。然而，直到出现一些不尽如人意的结果后，我才注意到指南上的这些句子：
- LSUnit 不知道何时可能发生存储到加载转发。
- LSUnit对缓存层次结构和内存类型一无所知。
- LSUnit 不知道如何识别序列化操作和内存栅栏。
另外，代码 A 的 llvm-mca 结果看起来像这样（使用的命令是llvm-mca (input) -iterations=200 -timeline -o 630_llvmmca.txt）：
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
等等。至少根据该图，已经并行调度了四个指令。我还检查了代码 B 的 llvm-mca 输出：
[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
[0,7] .D=eE----------R . . . . . . . . . . . . . shlq $8, %rcx
[0,8] . D=eE---------R . . . . . . . . . . . . . addq %rdi, %rcx
[0,9] . DeeeeeE------R . . . . . . . . . . . . . movzbl 1(%rsi), %r10d
[0,10] . D=====eeeeeE-R . . . . . . . . . . . . . movzbl (%rcx,%r10), %ecx
[0,11] . DeE----------R . . . . . . . . . . . . . movzbl %dl, %edx
[0,12] . DeE---------R . . . . . . . . . . . . . shlq $8, %rdx
[0,13] . D=eE--------R . . . . . . . . . . . . . addq %rdi, %rdx
[0,14] . DeeeeeE-----R . . . . . . . . . . . . . movzbl 2(%rsi), %r10d
[0,15] . D=====eeeeeER . . . . . . . . . . . . . movzbl (%rdx,%r10), %edx
[0,16] . DeE--------R . . . . . . . . . . . . . movzbl %al, %eax
[0,17] . D=eE-------R . . . . . . . . . . . . . shlq $8, %rax
[0,18] . D==eE------R . . . . . . . . . . . . . addq %rdi, %rax
[0,19] . DeeeeeE----R . . . . . . . . . . . . . movzbl 3(%rsi), %r10d
[0,20] . D====eeeeeER . . . . . . . . . . . . . movzbl (%rax,%r10), %eax
[0,21] . DeE--------R . . . . . . . . . . . . . addq $4, %rsi
[0,22] . D=eE-------R . . . . . . . . . . . . . cmpq %r9, %rsi
[0,23] . D==eE------R . . . . . . . . . . . . . jne .L171
[1,0] . .DeeeeeE---R . . . . . . . . . . . . . movzbl 14(%rsp), %r8d
[1,1] . .D=====eE--R . . . . . . . . . . . . . shlq $8, %r8
[1,2] . .D======eE-R . . . . . . . . . . . . . addq %rdi, %r8
[1,3] . .DeeeeeE---R . . . . . . . . . . . . . movzbl (%rsi), %r10d
[1,4] . . D======eeeeeER . . . . . . . . . . . . movzbl (%r8,%r10), %r8d
[1,5] . . D===========eER . . . . . . . . . . . . movb %r8b, 14(%rsp)
[1,6] . . D=====eE------R . . . . . . . . . . . . movzbl %cl, %ecx
坦率地说，与代码 A 没有任何不同，只是现在对内存的写入减少了 4 倍 - 这实际上并不重要，因为任何理智的缓存策略都应该保留14(%rbx)L1 缓存上的所有内容。（据我所知，过去几十年所有兼容intel的CPU都采用了回写式缓存）
用户玛格丽特·布鲁姆声称
如果展开的越来越多，您会看到性能的增量越来越少。
事实证明这一说法是正确的。我将代码 B 进一步展开 2 倍，发现速度进一步提高了 2 倍。在此之后，我未能获得任何进一步的加速。
代码C
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<howmany;i+=8){
sum1 *= testees[i];
sum2 *= testees[i+1];
sum3 *= testees[i+2];
sum4 *= testees[i+3];
sum5 *= testees[i+4];
sum6 *= testees[i+5];
sum7 *= testees[i+6];
sum8 *= testees[i+7];
}
代码 C - 主循环的程序集
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
将所有信息收集到一处，这就是我可以得出的结论。
llvm-mca可能是严重错误的，因为它“不知道缓存结构或内存类型” - 正如上面引用的。llvm-mca将是严重错误的- 如果我的缓存是正常的，所有其他人都应该在缓存上。在许多情况下，这些将导致缓存未命中 - 并且可能需要数百个周期。movzblmultTable[sum.rep][other.rep]movzblcode B通过编写四次汇编循环code A并重命名一些寄存器/存储器，消除了一些依赖性 - 又名危险。| 归档时间： |
|
| 查看次数： |
260 次 |
| 最近记录： |