performance - 涉及英特尔SnB系列CPU上涉及微编码指令的循环的分支对齐

Question

这与以下问题相关，但不相同：Performance optimisations of x86-64 assembly - Alignment and branch prediction，并且与我之前的问题：Unsigned 64-bit to double conversion: why this algorithm from g++略有相关

以下是非真实的测试案例。此素数测试算法不明智。我怀疑任何现实世界的算法都不会执行这么小的内循环那么多次（num是大约2 ** 50的素数）。在C ++ 11中：

using nt = unsigned long long;
bool is_prime_float(nt num)
{
   for (nt n=2; n<=sqrt(num); ++n) {
      if ( (num%n)==0 ) { return false; }
   }
   return true;
}

然后 g++ -std=c++11 -O3 -S产生以下内容，其中RCX包含 n，XMM6包含 sqrt(num)。请参阅我以前的文章以获取剩余的代码（由于RCX不会变得足够大而不能被视为带负号的负号，因此在此示例中不会执行）。

jmp .L20
.p2align 4,,10
.L37:
pxor    %xmm0, %xmm0
cvtsi2sdq   %rcx, %xmm0
ucomisd %xmm0, %xmm6
jb  .L36   // Exit the loop
.L20:
xorl    %edx, %edx
movq    %rbx, %rax
divq    %rcx
testq   %rdx, %rdx
je  .L30   // Failed divisibility test
addq    $1, %rcx
jns .L37
// Further code to deal with case when ucomisd can't be used

我用 std::chrono::steady_clock计时。我一直在获得怪异的性能更改：仅添加或删除其他代码。我最终将其归结为对齐问题。命令 .p2align 4,,10尝试对齐2 ** 4 = 16字节边界，但最多仅使用10个字节的填充来对齐，我想在对齐和代码大小之间取得平衡。

我编写了一个Python脚本，用手动控制的 .p2align 4,,10条指令替换 nop。以下散点图显示了20次运行中最快的15次，以秒为单位的时间，x轴上的填充字节数：



从 objdump开始，无填充，pxor指令将出现在偏移量0x402f5f处。在笔记本电脑上运行，Sandybridge i5-3210m，禁用涡轮增压，我发现


对于0字节填充，性能降低（0.42秒）
对于1-4个字节的填充（偏移量0x402f60至0x402f63），效果会稍好一些（0.41s，在图中可见）。
对于5-20字节填充（偏移量0x402f64至0x402f73）获得快速性能（0.37s）
对于21-32字节填充（偏移量0x402f74至0x402f7f）较慢的性能（0.42秒）
然后以32字节样本循环


因此16字节对齐方式并不能提供最佳性能-它使我们处于稍微好一点（或从散点图来看变化较小）的区域。对齐32加4到19可提供最佳性能。


为什么我会看到这种性能差异？为什么这似乎违反了将分支目标对齐到16字节边界的规则（请参阅例如英特尔优化手册）


我看不到任何分支预测问题。这可能是uop缓存怪癖吗？

通过更改C ++算法以将 sqrt(num)缓存在64位整数中，然后使循环完全基于整数，我消除了问题-对齐现在完全没有区别。

Answer 1

这是我在Skylake上找到的相同循环的内容。用于在硬件is on github上重现我的测试的所有代码。

我根据对齐方式观察到三个不同的性能级别，而OP实际只看到了两个主要性能级别。级别非常独特且可重复2：



我们在这里看到三个不同的性能级别（该模式从偏移32开始重复），我们将其称为区域1、2和3，从左到右（区域2分成横跨区域3的两部分）。最快的区域（1）从偏移量0到8，中间的区域（2）从9-18和28-31，最慢的区域（3）从19-27。每个区域之间的差异接近或正好是1个循环/迭代。

根据性能计数器，最快的区域与其他两个区域有很大的不同：


所有指令均从传统解码器而不是DSB1传递。
对于循环的每次迭代，正好有2个解码器<->微码开关（idq_ms_switches）。


另一方面，两个较慢的区域非常相似：


所有指令都是从DSB（uop缓存）传递的，而不是从旧式解码器传递的。
循环的每次迭代恰好有3个解码器<->微码开关。


由于偏移问题，当偏移量从8变为9时，从最快的区域过渡到中间区域的过程恰好与循环开始适合uop缓冲区的时间相对应。您用与彼得回答中完全相同的方式来计算：

偏移量8：

  LSD? <_start.L37>:
  ab 1 4000a8:  66 0f ef c0             pxor   xmm0,xmm0
  ab 1 4000ac:  f2 48 0f 2a c1          cvtsi2sd xmm0,rcx
  ab 1 4000b1:  66 0f 2e f0             ucomisd xmm6,xmm0
  ab 1 4000b5:  72 21                   jb     4000d8 <_start.L36>
  ab 2 4000b7:  31 d2                   xor    edx,edx
  ab 2 4000b9:  48 89 d8                mov    rax,rbx
  ab 3 4000bc:  48 f7 f1                div    rcx
  !!!! 4000bf:  48 85 d2                test   rdx,rdx
       4000c2:  74 0d                   je     4000d1 <_start.L30>
       4000c4:  48 83 c1 01             add    rcx,0x1
       4000c8:  79 de                   jns    4000a8 <_start.L37>

在第一列中，我已注释了每条指令的uops如何在uop缓存中结束。 “ ab 1”表示它们进入与地址相关的集合，例如 ...???a?或 ...???b?（每个集合覆盖32个字节，又称为 0x20），而1表示方式1（最多3个）。

在这一点上！因为 test指令无处可去，所以这会从uop缓存中消失，这3种方式都用光了。

另一方面，让我们看一下偏移量9：

00000000004000a9 <_start.L37>:
  ab 1 4000a9:  66 0f ef c0             pxor   xmm0,xmm0
  ab 1 4000ad:  f2 48 0f 2a c1          cvtsi2sd xmm0,rcx
  ab 1 4000b2:  66 0f 2e f0             ucomisd xmm6,xmm0
  ab 1 4000b6:  72 21                   jb     4000d9 <_start.L36>
  ab 2 4000b8:  31 d2                   xor    edx,edx
  ab 2 4000ba:  48 89 d8                mov    rax,rbx
  ab 3 4000bd:  48 f7 f1                div    rcx
  cd 1 4000c0:  48 85 d2                test   rdx,rdx
  cd 1 4000c3:  74 0d                   je     4000d2 <_start.L30>
  cd 1 4000c5:  48 83 c1 01             add    rcx,0x1
  cd 1 4000c9:  79 de                   jns    4000a9 <_start.L37>

现在没有问题！ test指令已滑入下一个32B行（ cd行），因此所有内容都适合uop缓存。

因此，这说明了为什么此时MITE和DSB之间的内容会发生变化。但是，它没有解释为什么MITE路径更快。我在循环中使用 div尝试了一些更简单的测试，您可以使用更简单的循环来重现此内容，而无需任何浮点数。它对您放入循环中的其他随机变量很奇怪并且很敏感。

例如，与DSB相比，此循环在旧版解码器中的执行速度也更快：

ALIGN 32
    <add some nops here to swtich between DSB and MITE>
.top:
    add r8, r9
    xor eax, eax
    div rbx
    xor edx, edx
    times 5 add eax, eax
    dec rcx
    jnz .top

在该循环中，添加了没有意义的 add r8, r9指令，该指令实际上并未与循环的其余部分进行交互，从而加快了MITE版本（但没有DSB版本）的工作。

因此，我认为区域1与区域2和3之间的差异是由于前者在传统解码器之外执行（奇怪的是，它使速度更快）。



我们还要看一下从偏移量18到偏移量19的过渡（region2结束而3开始）：

偏移18：

00000000004000b2 <_start.L37>:
  ab 1 4000b2:  66 0f ef c0             pxor   xmm0,xmm0
  ab 1  4000b6: f2 48 0f 2a c1          cvtsi2sd xmm0,rcx
  ab 1  4000bb: 66 0f 2e f0             ucomisd xmm6,xmm0
  ab 1  4000bf: 72 21                   jb     4000e2 <_start.L36>
  cd 1  4000c1: 31 d2                   xor    edx,edx
  cd 1  4000c3: 48 89 d8                mov    rax,rbx
  cd 2  4000c6: 48 f7 f1                div    rcx
  cd 3  4000c9: 48 85 d2                test   rdx,rdx
  cd 3  4000cc: 74 0d                   je     4000db <_start.L30>
  cd 3  4000ce: 48 83 c1 01             add    rcx,0x1
  cd 3  4000d2: 79 de                   jns    4000b2 <_start.L37>

偏移19：

00000000004000b3 <_start.L37>:
  ab 1 4000b3:  66 0f ef c0             pxor   xmm0,xmm0
  ab 1 4000b7:  f2 48 0f 2a c1          cvtsi2sd xmm0,rcx
  ab 1 4000bc:  66 0f 2e f0             ucomisd xmm6,xmm0
  cd 1 4000c0:  72 21                   jb     4000e3 <_start.L36>
  cd 1 4000c2:  31 d2                   xor    edx,edx
  cd 1 4000c4:  48 89 d8                mov    rax,rbx
  cd 2 4000c7:  48 f7 f1                div    rcx
  cd 3 4000ca:  48 85 d2                test   rdx,rdx
  cd 3 4000cd:  74 0d                   je     4000dc <_start.L30>
  cd 3 4000cf:  48 83 c1 01             add    rcx,0x1
  cd 3 4000d3:  79 de                   jns    4000b3 <_start.L37>

我在这里看到的唯一区别是，偏移量为18的情况下的前4条指令适合 ab高速缓存行，但偏移量为19的情况下只有3条指令。如果我们假设DSB只能从一个缓存集中将uops传递到IDQ，则这意味着在偏移18场景中某个时刻可以比在19场景中更早地发出并执行一个uop（例如， IDQ为空）。具体取决于uop在周围uop流中所连接的端口，这可能会使环路延迟一个周期。实际上，区域2和3之间的差约为1个周期（在误差范围内）。

因此，我认为我们可以说2与3之间的差异可能是由于uop缓存对齐方式所致-就早于一个周期发布一个额外的uop而言，区域2的对齐方式比3稍好。



一些我检查过的东西的补充说明未能成功，这可能是造成速度下降的原因：


尽管DSB模式（区域2和3）相对于MITE路径的2（区域1）具有3个微码开关，但这似乎并没有直接导致速度下降。特别是，带有 div的简单循环以相同的周期计数执行，但仍分别显示DSB和MITE路径的3和2开关。因此，这是正常现象，并不直接意味着经济放缓。
两条路径执行基本相同数量的微指令，尤其是具有由微码定序器生成的相同数量的微指令。因此，这好像并没有在不同地区进行更多的总体工作。
在各个级别的缓存未命中（如预期的那样非常低），分支错误预测（基本上为03）或我检查的任何其他类型的惩罚或异常情况方面，都没有真正的区别。


取得成果的是查看各个区域中执行单元使用的模式。以下是每个周期执行的uops的分布情况和一些停顿指标：

+----------------------------+----------+----------+----------+
|                            | Region 1 | Region 2 | Region 3 |
+----------------------------+----------+----------+----------+
| cycles:                    | 7.7e8    | 8.0e8    | 8.3e8    |
| uops_executed_stall_cycles | 18%      | 24%      | 23%      |
| exe_activity_1_ports_util  | 31%      | 22%      | 27%      |
| exe_activity_2_ports_util  | 29%      | 31%      | 28%      |
| exe_activity_3_ports_util  | 12%      | 19%      | 19%      |
| exe_activity_4_ports_util  | 10%      | 4%       | 3%       |
+----------------------------+----------+----------+----------+

我对几个不同的偏移值进行了采样，结果在每个区域内都是一致的，但是在两个区域之间，结果却大不相同。特别是在区域1中，停顿周期（没有执行uop的周期）较少。尽管没有明显的“好”或“差”趋势，但非停顿周期也有很大的变化。例如，区域1具有更多的周期（执行4 uop）（10％比3％或4％），但是其他区域在执行3 uop的情况下有更多的周期，而执行1 uop的周期却很少。

上面的执行分布所暗示的UPC4的差异充分说明了性能的差异（这可能是重言式，因为我们已经确认它们之间的uop计数相同）。

让我们看看 toplev.py关于它的话……（省略结果）。

好吧，toplev建议主要瓶颈是前端（50％以上）。我认为您不能相信这一点，因为在长串的微代码指令的情况下，它计算有限元绑定的方法似乎被破坏了。有限元绑定基于 frontend_retired.latency_ge_8，它定义为：


在以下时间间隔后获取的退休指令：
前端在8个周期内没有传递任何信息
被后端停顿中断。 （支持PEBS）


通常这是有道理的。您正在计算由于前端未交付周期而被延迟的指令。 “不被后端停顿打断”条件可确保当前端不提供uops时（仅因为后端无法接受它们）（例如，当RS满时，因为后端正在执行一些低吞吐量指令）。

div指令似乎有点象-甚至一个只有一个 div的简单循环显示：

FE      Frontend_Bound:                57.59 %           [100.00%]
BAD     Bad_Speculation:                0.01 %below      [100.00%]
BE      Backend_Bound:                  0.11 %below      [100.00%]
RET     Retiring:                      42.28 %below      [100.00%]

也就是说，唯一的瓶颈是前端（“退休”不是瓶颈，它代表着有用的工作）。显然，这样的循环是由前端处理的，而受后端咀嚼掉 div操作生成的所有微指令的能力的限制。 Toplev可能会弄错这个真正的错误，因为（1）可能是微码定序器传递的微指令未在 frontend_retired.latency...计数器中计数，因此每个 div操作都会导致该事件对所有后续指令进行计数（即使是尽管在此期间CPU处于忙碌状态-没有真正的停顿），或者（2）微代码定序器可能实质上将所有ups都“提前”交付，向IDQ猛击约36 oups，此时它没有交付直到 div完成为止。

不过，我们可以查看较低级别的 toplev以获得提示：

toplev在区域1与区域2和3之间的主要区别是后两个区域 ms_switches的惩罚增加（因为它们每次迭代产生3，而传统路径产生2；在内部， toplev估计为2这样的开关在前端的循环惩罚，当然，这些惩罚是否真的减慢了速度，这取决于指令队列和其他因素的复杂方式，如上所述，使用 div的简单循环不会显示任何区别在DSB和MITE路径之间，需要执行带有附加指令的循环，因此，可能是多余的开关气泡被更简单的循环吸收了（其中，由 div生成的所有uops的后端处理是主要因素），但是一旦您在循环中添加其他工作，开关至少会成为 div和non-div`工作之间过渡期间的一个因素。

所以我想我的结论是，div指令与前端uop流的其余部分以及后端执行的交互方式尚不完全清楚。我们知道，这涉及大量的uops，既从MITE / DSB（似乎每个 div 4 uops）还是从微码定序器（似乎每个 div 32 uops）传递，尽管它随输入值的变化而变化。 div操作）-但我们不知道这些uops是什么（尽管我们可以看到它们的端口分布）。所有这些使行为变得相当不透明，但是我认为这可能归结于MS交换机前端拥塞，或者uop交付流程中的细微差异导致了不同的调度决策，最终使MITE订单成为了主订单。



1当然，大多数微码根本不是从传统解码器或DSB传递的，而是由微码定序器（ms）传递的。因此，我们不拘一格地谈论交付的说明，而不是讨论。

2请注意，此处的x轴是“距32B对齐的偏移字节”。也就是说，0表示循环的顶部（标签.L37）与32B边界对齐，而5表示循环从32B边界以下开始五个字节（使用nop进行填充），依此类推。所以我的填充字节和偏移量是相同的。如果我正确理解的话，OP对偏移使用了不同的含义：他的1个字节的填充导致0偏移。因此，您可以从OP填充值中减去1，以获得我的偏移值。

3实际上，使用 prime=1000000000000037进行的典型测试的分支预测率为〜99.999997％，在整个运行过程中仅反映了3个错误预测的分支（可能在第一次遍历循环和最后一次迭代时）。

4 UPC，即每个周期uops-一种与IPC密切相关的类似程序的度量，当我们详细查看uop流量时，该度量更为精确。在这种情况下，我们已经知道所有对齐方式的uop计数都相同，因此UPC和IPC将成正比。