gpt4 book ai didi

performance - 两个看似等效的汇编代码之间的性能差异

转载 作者:行者123 更新时间:2023-12-01 09:44:43 26 4
gpt4 key购买 nike

tl; dr :我有两个用Clang编译的功能等效的C代码(事实是C代码并不重要;我认为只是汇编很有趣),而IACA告诉我,应该更快一些,但我不明白为什么,我的基准测试显示这两个代码具有相同的性能。

我有以下C代码(暂时忽略#include "iacaMarks.h"IACA_STARTIACA_END):

参考c:

#include "iacaMarks.h"
#include <x86intrin.h>

#define AND(a,b) _mm_and_si128(a,b)
#define OR(a,b) _mm_or_si128(a,b)
#define XOR(a,b) _mm_xor_si128(a,b)
#define NOT(a) _mm_andnot_si128(a,_mm_set1_epi32(-1))

void sbox_ref (__m128i r0,__m128i r1,__m128i r2,__m128i r3,
__m128i* r5,__m128i* r6,__m128i* r7,__m128i* r8) {
__m128i r4;

IACA_START
r3 = XOR(r3,r0);
r4 = r1;
r1 = AND(r1,r3);
r4 = XOR(r4,r2);
r1 = XOR(r1,r0);
r0 = OR(r0,r3);
r0 = XOR(r0,r4);
r4 = XOR(r4,r3);
r3 = XOR(r3,r2);
r2 = OR(r2,r1);
r2 = XOR(r2,r4);
r4 = NOT(r4);
r4 = OR(r4,r1);
r1 = XOR(r1,r3);
r1 = XOR(r1,r4);
r3 = OR(r3,r0);
r1 = XOR(r1,r3);
r4 = XOR(r4,r3);
*r5 = r1;
*r6 = r4;
*r7 = r2;
*r8 = r0;
IACA_END

}

我想知道是否可以通过手动重新调度一些指令来优化它(我很清楚C编译器应该产生有效的调度,但是我的实验表明情况并非总是如此)。在某个时候,我尝试了以下代码(与上面的代码相同,除了不使用临时变量来存储稍后被分配给 *r5*r6的XOR的结果):

resched.c:
#include "iacaMarks.h"
#include <x86intrin.h>

#define AND(a,b) _mm_and_si128(a,b)
#define OR(a,b) _mm_or_si128(a,b)
#define XOR(a,b) _mm_xor_si128(a,b)
#define NOT(a) _mm_andnot_si128(a,_mm_set1_epi32(-1))

void sbox_resched (__m128i r0,__m128i r1,__m128i r2,__m128i r3,
__m128i* r5,__m128i* r6,__m128i* r7,__m128i* r8) {
__m128i r4;

IACA_START
r3 = XOR(r3,r0);
r4 = r1;
r1 = AND(r1,r3);
r4 = XOR(r4,r2);
r1 = XOR(r1,r0);
r0 = OR(r0,r3);
r0 = XOR(r0,r4);
r4 = XOR(r4,r3);
r3 = XOR(r3,r2);
r2 = OR(r2,r1);
r2 = XOR(r2,r4);
r4 = NOT(r4);
r4 = OR(r4,r1);
r1 = XOR(r1,r3);
r1 = XOR(r1,r4);
r3 = OR(r3,r0);
*r7 = r2;
*r8 = r0;
*r5 = XOR(r1,r3); // This two lines are different
*r6 = XOR(r4,r3); // (no more temporary variables)
IACA_END
}

我正在使用针对我的i5-6500(Skylake)的Clang 5.0.0编译这些代码,并带有 -O3 -march=native标志(我省略了生成的汇编代码,因为它们可以在下面的IACA输出中找到,但是如果希望直接将它们放在这里,问我,我将其添加)。我对这两个代码进行了基准测试,发现它们之间没有任何性能差异。出于好奇,我对它们执行了IACA,而令我惊讶的是,它说第一个版本需要6个周期才能运行,第二个版本需要7个周期。
这是IACA产生的输出:

对于第一个版本:
dada@dada-ubuntu ~/perf % clang -O3 -march=native -c ref.c && ./iaca -arch SKL ref.o        
Intel(R) Architecture Code Analyzer Version - v3.0-28-g1ba2cbb build date: 2017-10-23;16:42:45
Analyzed File - ref_iaca.o
Binary Format - 64Bit
Architecture - SKL
Analysis Type - Throughput

Throughput Analysis Report
--------------------------
Block Throughput: 6.00 Cycles Throughput Bottleneck: FrontEnd
Loop Count: 23
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
--------------------------------------------------------------------------------------------------
| Cycles | 6.0 0.0 | 6.0 | 1.3 0.0 | 1.4 0.0 | 4.0 | 6.0 | 0.0 | 1.4 |
--------------------------------------------------------------------------------------------------

DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis

| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
-----------------------------------------------------------------------------------------
| 1 | 1.0 | | | | | | | | vpxor xmm4, xmm3, xmm0
| 1 | | 1.0 | | | | | | | vpand xmm5, xmm4, xmm1
| 1 | | | | | | 1.0 | | | vpxor xmm1, xmm2, xmm1
| 1 | 1.0 | | | | | | | | vpxor xmm5, xmm5, xmm0
| 1 | | 1.0 | | | | | | | vpor xmm0, xmm3, xmm0
| 1 | | | | | | 1.0 | | | vpxor xmm0, xmm0, xmm1
| 1 | 1.0 | | | | | | | | vpxor xmm1, xmm4, xmm1
| 1 | | 1.0 | | | | | | | vpxor xmm3, xmm4, xmm2
| 1 | | | | | | 1.0 | | | vpor xmm2, xmm5, xmm2
| 1 | 1.0 | | | | | | | | vpxor xmm2, xmm2, xmm1
| 1 | | 1.0 | | | | | | | vpcmpeqd xmm4, xmm4, xmm4
| 1 | | | | | | 1.0 | | | vpxor xmm1, xmm1, xmm4
| 1 | 1.0 | | | | | | | | vpor xmm1, xmm5, xmm1
| 1 | | 1.0 | | | | | | | vpxor xmm4, xmm5, xmm3
| 1 | | | | | | 1.0 | | | vpor xmm3, xmm0, xmm3
| 1 | 1.0 | | | | | | | | vpxor xmm4, xmm4, xmm3
| 1 | | 1.0 | | | | | | | vpxor xmm4, xmm4, xmm1
| 1 | | | | | | 1.0 | | | vpxor xmm1, xmm1, xmm3
| 2^ | | | 0.3 | 0.3 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rdi], xmm4
| 2^ | | | 0.3 | 0.3 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rsi], xmm1
| 2^ | | | 0.3 | 0.3 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rdx], xmm2
| 2^ | | | 0.3 | 0.3 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rcx], xmm0
Total Num Of Uops: 26

对于第二个版本:
dada@dada-ubuntu ~/perf % clang -O3 -march=native -c resched.c && ./iaca -arch SKL resched.o
Intel(R) Architecture Code Analyzer Version - v3.0-28-g1ba2cbb build date: 2017-10-23;16:42:45
Analyzed File - resched_iaca.o
Binary Format - 64Bit
Architecture - SKL
Analysis Type - Throughput

Throughput Analysis Report
--------------------------
Block Throughput: 7.00 Cycles Throughput Bottleneck: Backend
Loop Count: 22
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
--------------------------------------------------------------------------------------------------
| Cycles | 6.0 0.0 | 6.0 | 1.3 0.0 | 1.4 0.0 | 4.0 | 6.0 | 0.0 | 1.3 |
--------------------------------------------------------------------------------------------------

DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis

| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
-----------------------------------------------------------------------------------------
| 1 | 1.0 | | | | | | | | vpxor xmm4, xmm3, xmm0
| 1 | | 1.0 | | | | | | | vpand xmm5, xmm4, xmm1
| 1 | | | | | | 1.0 | | | vpxor xmm1, xmm2, xmm1
| 1 | 1.0 | | | | | | | | vpxor xmm5, xmm5, xmm0
| 1 | | 1.0 | | | | | | | vpor xmm0, xmm3, xmm0
| 1 | | | | | | 1.0 | | | vpxor xmm0, xmm0, xmm1
| 1 | 1.0 | | | | | | | | vpxor xmm1, xmm4, xmm1
| 1 | | 1.0 | | | | | | | vpxor xmm3, xmm4, xmm2
| 1 | | | | | | 1.0 | | | vpor xmm2, xmm5, xmm2
| 1 | 1.0 | | | | | | | | vpxor xmm2, xmm2, xmm1
| 1 | | 1.0 | | | | | | | vpcmpeqd xmm4, xmm4, xmm4
| 1 | | | | | | 1.0 | | | vpxor xmm1, xmm1, xmm4
| 1 | 1.0 | | | | | | | | vpor xmm1, xmm5, xmm1
| 1 | | 1.0 | | | | | | | vpxor xmm4, xmm5, xmm3
| 1 | | | | | | 1.0 | | | vpor xmm3, xmm0, xmm3
| 2^ | | | 0.3 | 0.4 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rdx], xmm2
| 2^ | | | 0.3 | 0.3 | 1.0 | | | 0.4 | vmovdqa xmmword ptr [rcx], xmm0
| 1 | 1.0 | | | | | | | | vpxor xmm0, xmm4, xmm3
| 1 | | 1.0 | | | | | | | vpxor xmm0, xmm0, xmm1
| 2^ | | | 0.4 | 0.3 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rdi], xmm0
| 1 | | | | | | 1.0 | | | vpxor xmm0, xmm1, xmm3
| 2^ | | | 0.3 | 0.4 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rsi], xmm0
Total Num Of Uops: 26
Analysis Notes:
Backend allocation was stalled due to unavailable allocation resources.

如您所见,在第二个版本中,IACA表示瓶颈是后端,并且“后端分配由于分配资源不可用而停顿了”。

两种汇编代码都包含相同的指令,唯一的区别是最后7条指令的调度以及它们使用的寄存器。

我唯一能想到的就是可以解释第二个代码为什么要慢的事实,因为它在最后4条指令中写了两次 xmm0,从而引入了依赖性。但是由于这些写操作是独立的,所以我希望CPU为它们使用不同的物理寄存器。但是,我无法真正证明这一理论。另外,如果像这样使用两次 xmm0是一个问题,我希望Clang对其中一条指令使用不同的寄存器(特别是因为这里的寄存器压力很低)。

我的问题:第二个代码应该慢一些吗(基于汇编代码),为什么?

编辑:IACA跟踪:

第一版: https://pastebin.com/qGXHVW6a
第二版: https://pastebin.com/dbBNWsc2

注意:C代码是由Osvik here计算的蛇密码第一个S-box的实现。

最佳答案

弄清楚为什么第二个代码是后端绑定的,需要大量的手动分析,因为IACA发出的输出太原始了,尽管信息非常丰富。请注意,IACA发出的迹线对于分析循环特别有用,它们对于理解如何执行直线指令序列(这没有用)也很有用,但是发出的迹线需要进行不同的解释。贯穿此答案的其余部分,我将介绍我对循环场景的分析,这比较困难。

您发出跟踪而没有将代码放入循环的事实会影响以下因素:

  • ,编译器无法内联并将存储优化为输出操作数。它们根本不会出现在实际循环中,或者如果将其链接到其他S-box,则根本不会出现。
  • 由于编译器使用xmm0..3准备要存储的数据而巧合地发生了从输出到输入的数据依赖关系,而不是选择选择将哪个输出反馈到同一S-box的哪个输入。
  • 内联后,将创建一个全矢量(用于NOT)的vpcmpeqd吊出循环。
  • 将存在dec/jnz或同等的循环开销(可以将其宏融合到端口6的单个uop中)。

  • 但是您已经要求IACA分析这个asm精确块,就好像它是在循环中运行一样。因此,为了解释结果,这就是我们如何看待它(即使您不是在循环中使用此函数,也不会从C编译器得到它)。

    在这种情况下,底部的 jmpdec/jnz使其成为循环不是问题:它将始终在端口6上执行,任何矢量指令都不会使用它。这意味着跳转指令将不会在端口6上争用,也不会消耗调度程序uop带宽,否则该带宽将被其他指令使用。但是,这可能会在问题/重命名阶段(每个周期不超过4个融合域uops)影响资源分配器的带宽,但这在我将要讨论的特定情况下并不重要。

    我们首先检查端口压力ASCII数字:
    | Num Of   |                    Ports pressure in cycles                         |      |
    | Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
    -----------------------------------------------------------------------------------------
    | 1 | 1.0 | | | | | | | | vpxor xmm4, xmm3, xmm0
    | 1 | | 1.0 | | | | | | | vpand xmm5, xmm4, xmm1
    | 1 | | | | | | 1.0 | | | vpxor xmm1, xmm2, xmm1
    | 1 | 1.0 | | | | | | | | vpxor xmm5, xmm5, xmm0
    | 1 | | 1.0 | | | | | | | vpor xmm0, xmm3, xmm0
    | 1 | | | | | | 1.0 | | | vpxor xmm0, xmm0, xmm1
    | 1 | 1.0 | | | | | | | | vpxor xmm1, xmm4, xmm1
    | 1 | | 1.0 | | | | | | | vpxor xmm3, xmm4, xmm2
    | 1 | | | | | | 1.0 | | | vpor xmm2, xmm5, xmm2
    | 1 | 1.0 | | | | | | | | vpxor xmm2, xmm2, xmm1
    | 1 | | 1.0 | | | | | | | vpcmpeqd xmm4, xmm4, xmm4
    | 1 | | | | | | 1.0 | | | vpxor xmm1, xmm1, xmm4
    | 1 | 1.0 | | | | | | | | vpor xmm1, xmm5, xmm1
    | 1 | | 1.0 | | | | | | | vpxor xmm4, xmm5, xmm3
    | 1 | | | | | | 1.0 | | | vpor xmm3, xmm0, xmm3
    | 2^ | | | 0.3 | 0.4 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rdx], xmm2
    | 2^ | | | 0.3 | 0.3 | 1.0 | | | 0.4 | vmovdqa xmmword ptr [rcx], xmm0
    | 1 | 1.0 | | | | | | | | vpxor xmm0, xmm4, xmm3
    | 1 | | 1.0 | | | | | | | vpxor xmm0, xmm0, xmm1
    | 2^ | | | 0.4 | 0.3 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rdi], xmm0
    | 1 | | | | | | 1.0 | | | vpxor xmm0, xmm1, xmm3
    | 2^ | | | 0.3 | 0.4 | 1.0 | | | 0.3 | vmovdqa xmmword ptr [rsi], xmm0

    融合域微指令的总数为22。6个不同的微指令已分配给端口0、1和5。每4个微指令分别由STD和STA微指令组成。 STD需要端口4。此分配是合理的。如果我们忽略所有数据依赖关系,则看来调度程序应该能够在每个周期中至少分配3个融合域uops。但是,端口4可能存在严重争用,这可能导致填满预订站。根据IACA,这不是此代码中的瓶颈。请注意,如果调度程序可以某种方式实现等于分配器最大吞吐量的吞吐量,则代码只能是前端绑定的。显然,这里不是这样。

    下一步是仔细检查IACA跟踪。我根据跟踪制作了以下数据流图,该图更易于分析。水平的黄线根据在同一周期中分配的微指令来划分图形。请注意,IACA始终假设完善的分支预测。另请注意,该划分的准确度约为99%,但并非100%。这并不重要,您可以认为它100%准确。节点表示融合的uops,箭头表示数据依赖性(其中箭头指向目标uop)。节点的颜色取决于它们所属的循环迭代。为了清楚起见,省略了图形顶部箭头的来源。右侧的绿色框包含循环编号,在该循环编号处为相应的微指令进行分配。因此,前一个周期是X,而当前周期是X + 1,无论X是多少。停止标志表示相关联的uop在其中一个端口上发生争用。所有红色停止符号代表在端口1上的争用。只有另一个不同颜色的停止符号代表在端口5上的争用。存在争用的情况,但为清楚起见,我将其省略。箭头有两种颜色:蓝色和红色。那些是关键的。注意,分配2个迭代值的指令需要11个周期,然后重复分配模式。请记住,Skylake具有97个RS整体。

    每个分区内节点的位置(“本地”位置)具有含义。如果两个节点在同一行上,并且它们的所有操作数均可用,则意味着它们可以在同一周期内分派。否则,如果节点不在同一行上,则它们可能不会在同一周期内分派。这仅适用于已一起分配为一组的动态uops,不适用于作为不同组的一部分分配的动态uops,即使它们恰好位于图中的同一划分中。

    enter image description here

    我将使用 (it, in)表示法来标识特定的融合uop,其中 it是从零开始的循环迭代数,而 in是从零开始的uop数。 IACA跟踪的最重要部分是显示(11,5)的流水线阶段的部分:
    11| 5|vpxor xmm0, xmm0, xmm1                            :          |         |         |         |         |         |         |         |         |         |         |         |         |         |         
    11| 5| TYPE_OP (1 uops) : | | | | | |_A--------------------dw----R-------p | | | | |

    这告诉我们由于资源不可用(在这种情况下,是保留站中的条目),此时分配带宽未得到充分利用。这意味着调度程序无法维持足够高的未融合微指令吞吐量,无法跟上每个周期前端4个融合微指令的速度。由于IACA已经告诉我们代码是后端绑定的,因此,这种未充分利用的原因显然不是由于较长的依赖链或特定执行单元的争用,而是更复杂的原因。因此,我们需要做更多的工作来弄清楚发生了什么。我们必须分析过去(11、5)。

    每次迭代的uops 1、4、7、10、13、18都分配给端口1。在11个周期内会发生什么?总共需要12个微指令,需要端口1,因此不可能在11个周期内分派所有微指令,因为这至少需要12个周期。不幸的是,需要相同端口的uops内部和需要其他端口的uops之间的数据依赖性大大加剧了该问题。在一个11个周期内,请考虑以下管道流量:
  • 在周期0:(0,0)和(0,1)被分配(以及我们现在不在乎的其他uops)。 (0,1)取决于(0,0)的数据。
  • 1:(0,4)和(0,7)被分配。假定没有将较旧的就绪uops分配给端口0并且(0,0)的操作数已就绪,则将(0,0)调度到端口0。端口1可能保持空闲状态,因为(0,1)尚未就绪。
  • 2:(0,0)的结果可通过旁路网络获得。此时,可以并且将调度(0,1)。但是,即使(0,4)或(0,7)准备就绪,也没有将最旧的uop分配给端口1,因此它们都会被阻塞。 (0,10)被分配。
  • 3:(0,4)被调度到端口1。(0,7)和(0,10)都被阻塞,即使它们的操作数已准备就绪。 (0,13)被分配。
  • 4:(0,7)被调度到端口1。(0,10)被阻塞。 (0,13)必须等待(0,7)。 (0,18)被分配。
  • 5:(0,10)被调度到端口1。(0,13)被阻塞。 (0,18)必须等待(0,17)取决于(0,13)。 (1,0)和(1,1)被分配。
  • 6:(0,13)被调度到端口1。(0,18)必须等待(0,17)依赖于(0,13)。 (1,1)必须等待(1,0)。无法分配(1,0),因为(1,0)与(0,7)之间的距离为3 oups,其中之一可能会发生端口冲突。 (1,4)被分配。
  • 7:由于(0,18),(1、1)和(1,4)尚未准备就绪,因此没有任何内容分配到端口1。 (1,7)被分配。
  • 8:由于(0,18),(1、1),(1、4)和(1,7)尚未准备就绪,因此没有任何内容分配到端口1。 (1,10)和(1,13)得到分配。
  • 9:(0,18)被调度到端口1。(1,10)和(1,4)准备就绪,但由于端口争用而被阻塞。 (1、1),(1、7)和(1、13)尚未准备好。
  • 10:(1,1)被调度到端口1。(1,4),(1,7)和(1,10)已准备就绪,但由于端口争用而被阻塞。 (1,13)没有准备好。 (1,18)被分配。

  • 好吧,理想情况下,我们希望在12个微指令中有11个以11个周期分配到端口1。但是,这种分析表明情况远非理想。端口1在11个周期中有4个空闲!如果我们假设前一个迭代中的一些(X,18)在周期0处调度,则端口1将空闲3个周期,这很浪费,考虑到我们每11个周期需要12个微指令。在12个微指令中,最多只有8个被调度。情况有多严重?我们可以继续分析跟踪并记录已准备好分发但由于冲突而被阻止或由于数据下降而未准备就绪的p1绑定的数量。我能够确定由于端口冲突而停滞的p1绑定的数量永远不会大于3。但是,由于数据下降而停滞的p1绑定的数量总体上会随着时间逐渐增加。我没有看到它增加的任何模式,所以我决定在跟踪的前24个周期中使用线性回归来预测在什么时候会有97个此类微指令。下图显示了这一点。

    enter image description here

    x轴表示从左到右递增的从零开始的循环。请注意,在前4个周期内,微指令的数量为零。 y轴表示在相应周期内此类微指令的数量。线性回归方程为:

    y = 0.3624x-0.6925。

    通过将y设置为97,我们得到:

    x =(97 + 0.6925)/ 0.3624 = 269.57

    也就是说,在大约第269个周期,我们期望RS中所有p1绑定到97微码,并等待它们的操作数准备就绪。此时RS已满。但是,由于其他原因,RS中可能还有其他等待的对象。因此,我们期望分配器在周期269或之前未充分利用其带宽。通过查看指令(11,5)的IACA跟踪,我们可以看到这种情况发生在周期629,这早于269。这意味着我的预测器非常乐观,或者与其他端口绑定的uops数量也表现出类似的行为。我的胆量告诉我是后者。但这足以理解IACA为什么说代码是后端绑定的。您可以对第一个代码执行类似的分析,以了解为什么它是前端绑定的。我想我只是留给读者练习。

    如果IACA不支持特定的代码段,或者对于特定的微体系结构不存在类似IACA的工具,则可以执行此手动分析。线性回归模型使您能够估计在迭代次数之后分配器未充分利用其带宽。例如,在这种情况下,周期269对应于迭代269/11/2 = 269/22 =12。因此,只要最大迭代次数不大于12,循环的后端性能就会降低问题。

    @Bee有一篇相关的文章: How are x86 uops scheduled, exactly?

    我可能会在之后的前24个周期中发布发生的情况的详细信息。

    旁注:Wikichip在 Skylake上的文章中有两个错误。首先,Broadwell的调度程序具有60个整体,而不是64个。其次,分配器的吞吐量仅高达4个融合uops。

    关于performance - 两个看似等效的汇编代码之间的性能差异,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51723837/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com