REP 做了什么设置?

What setup does REP do?

引用 Intel® 64 和 IA-32 架构优化参考手册, §2.4.6 "REP String Enhancement":

The performance characteristics of using REP string can be attributed to two components: startup overhead and data transfer throughput.

[...]

For REP string of larger granularity data transfer, as ECX value increases, the startup overhead of REP String exhibit step-wise increase:

  • Short string (ECX <= 12): the latency of REP MOVSW/MOVSD/MOVSQ is about 20 cycles,
  • Fast string (ECX >= 76: excluding REP MOVSB): the processor implementation provides hardware optimization by moving as many pieces of data in 16 bytes as possible. The latency of REP string latency will vary if one of the 16-byte data transfer spans across cache line boundary:

    • Split-free: the latency consists of a startup cost of about 40 cycles and each 64 bytes of data adds 4 cycles,
    • Cache splits: the latency consists of a startup cost of about 35 cycles and each 64 bytes of data adds 6 cycles.
  • Intermediate string lengths: the latency of REP MOVSW/MOVSD/MOVSQ has a startup cost of about 15 cycles plus one cycle for each iteration of the data movement in word/dword/qword.

(强调我的)

没有进一步提到这样的启动成本。它是什么?它有什么作用,为什么总是需要更多时间?

根据描述,在我看来最佳传输大小为 16 字节,因此如果您要传输 79 字节,即 4*16 + 15。所以不了解更多关于对齐的信息可能意味着是前面或末尾(或拆分)的 15 个字节的成本,而 4 个 16 字节传输比 16 的分数更快。有点像汽车中的高档与通过档位升到高档。

查看 glibc 或 gcc 或其他地方的优化 memcpy。他们最多传输几个单独的字节,然后他们可以进行 16 位传输,直到达到 32 位对齐、64 位对齐、128 位对齐地址的最佳对齐大小,然后他们可以为大部分副本,然后他们降档,可能是一个 32 位的东西,可能是一个 16 位的东西,也可能是 1 个字节,以弥补后端对齐的不足。

听起来代表做同样的事情,低效的单次传输以达到优化的对齐大小,然后进行大量传输直到接近尾声,然后可能进行一些小的单独传输以覆盖最后一部分。

请注意,只有 rep movsrep stos 速度快。当前 CPU 上的 repe/ne cmpsscas 一次只循环 1 个元素。 (https://agner.org/optimize/ 有一些性能数字,例如 repe cmpsb 每个 RCX 计数 2 个周期)。不过,它们仍然有一些微码启动开销。


rep movs微码有多种策略可供选择。 如果 src 和 dest 没有紧密重叠,微编码循环可以传输更大的 64b 块。 (这是 P6 引入的所谓“快速字符串”功能,偶尔会为支持更宽 loads/stores 的更高版本的 CPU 重新调整)。但是,如果 dest 仅来自 src 一个字节,rep movs 必须产生与从许多单独的 movs 指令中获得的完全相同的结果。

所以微代码必须检查重叠,并可能检查对齐(src 和 dest 分别,或相对对齐)。它可能还会根据 small/medium/large 计数器值选择一些东西。

根据 Andy Glew's comments on an answer to Why are complicated memcpy/memset superior?微码中的条件分支不受分支预测影响。因此,如果默认未采用的路径不是实际采用的路径,则启动周期会受到严重影响,即使对于使用相同 rep movs 且具有相同对齐方式和大小的循环也是如此。

他监督了 P6 中最初的 rep 字符串实现,所以他应该知道。 :)

REP MOVS uses a cache protocol feature that is not available to regular code. Basically like SSE streaming stores, but in a manner that is compatible with normal memory ordering rules, etc. // The "large overhead for choosing and setting up the right method" is mainly due to the lack of microcode branch prediction. I have long wished that I had implemented REP MOVS using a hardware state machine rather than microcode, which could have completely eliminated the overhead.

By the way, I have long said that one of the things that hardware can do better/faster than software is complex multiway branches.

Intel x86 have had "fast strings" since the Pentium Pro (P6) in 1996, which I supervised. The P6 fast strings took REP MOVSB and larger, and implemented them with 64 bit microcode loads and stores and a no-RFO cache protocol. They did not violate memory ordering, unlike ERMSB in iVB.

The big weakness of doing fast strings in microcode was (a) microcode branch mispredictions, and (b) the microcode fell out of tune with every generation, getting slower and slower until somebody got around to fixing it. Just like a library men copy falls out of tune. I suppose that it is possible that one of the missed opportunities was to use 128-bit loads and stores when they became available, and so on

In retrospect, I should have written a self-tuning infrastructure, to get reasonably good microcode on every generation. But that would not have helped use new, wider, loads and stores, when they became available. // The Linux kernel seems to have such an autotuning infrastructure, that is run on boot. // Overall, however, I advocate hardware state machines that can smoothly transition between modes, without incurring branch mispredictions. // It is debatable whether good microcode branch prediction would obviate this.

基于此,我对特定答案的最佳猜测是:通过微码的快速路径(尽可能多的分支实际上采用默认未采用的路径)是 15 周期启动情况,对于中间长度。

由于英特尔没有公布完整的细节,我们只能对各种尺寸和排列的周期计数进行黑盒测量。 幸运的是,这就是我们做出正确选择所需的全部内容。 Intel 手册和 http://agner.org/optimize/ 提供了有关如何使用 rep movs 的详细信息。


有趣的事实:没有 ERMSB(IvB 中的新功能):rep movsb 针对小型副本进行了优化。对于大型(我认为超过几百个字节)副本,启动时间比 rep movsdrep movsq 更长,即使在那之后也可能无法达到相同的吞吐量。

没有 ERMSB 且没有 SSE/AVX(例如在内核代码中)的大型对齐副本的最佳序列可能是 rep movsq,然后用类似未对齐的东西清理 mov复制缓冲区的最后 8 个字节,可能与 rep movsq 所做的最后对齐的块重叠。 (基本上使用 glibc's small-copy memcpy strategy)。但是,如果大小可能小于 8 个字节,则您需要进行分支,除非复制比需要的字节更多的字节是安全的。或者 rep movsb 是清理的选项,如果小代码大小比性能更重要。 (如果 RCX = 0,rep 将复制 0 个字节)。

即使在具有 Enhanced Rep Move/Stos B 的 CPU 上,SIMD 向量循环通常至少比 rep movsb 快一点。尤其是在不能保证对齐的情况下。 (, and see also Intel's optimization manual. Links in the x86 tag wiki)


进一步的细节:我认为在 SO 的某个地方有一些关于测试 rep movsb 如何影响周围指令的乱序执行的讨论,稍后的 uops指令可以进入流水线。我认为我们在英特尔专利中找到了一些信息,这些信息阐明了该机制。

微码可以使用一种预测加载和存储 uop,让它在最初不知道 RCX 的值的情况下发出一堆 uops。如果事实证明 RCX 是一个小值,其中一些 uops 选择不做任何事情。

我已经在 Skylake 上对 rep movsb 进行了一些测试。它似乎与初始突发机制一致:低于某个大小阈值(如 96 字节或类似大小)时,IIRC 性能对于任何大小几乎都是恒定的。 (在 L1d 缓存中有小的对齐缓冲区热)。我在一个具有独立 imul 依赖链的循环中有 rep movs,测试它可以重叠执行。

但随后出现了超出该大小的显着下降,大概是当微码定序器发现它需要发出更多的复制微指令时。所以我认为当 rep movsb 微码 uop 到达 IDQ 的前端时,它让微码定序器发出足够的负载 + 存储一些固定大小的 uops,并检查是否足够或者是否有更多需要。

全凭记忆,更新答案时没有重新测试。如果这与其他人的实际情况不符,请告诉我,我会再次检查。

您给出的报价仅适用于 Nehalem 微架构(2009 年和 2010 年发布的 Intel Core i5、i7 和 Xeon 处理器),Intel 对此有明确说明。

在 Nehalem 之前,REP MOVSB 甚至更慢。 Intel 对后续微架构中发生的事情保持沉默,但是,随着 Ivy Bridge 微架构(2012 年和 2013 年发布的处理器),Intel 引入了 Enhanced REP MOVSB(我们仍然需要检查相应的 CPUID 位)这使我们能够快速复制内存。

后来处理器的最便宜版本 - 2017 年发布的 Kaby Lake“Celeron”和“Pentium”没有可用于快速内存复制的 AVX,但它们仍然具有增强型 REP MOVSB。这就是为什么 REP MOVSB 对 2013 年以来发布的处理器非常有利。

令人惊讶的是,Nehalem 处理器对于非常 large-sized 块具有相当快的 REP MOVSD/MOVSQ 实现(但不是 REP MOVSW/MOVSB) - 只需 4 个周期来复制每个后续的 64 字节数据(如果数据与缓存行边界对齐)在我们支付了 40 个周期的启动成本之后——当我们复制 256 字节或更多字节时这非常好,而且您不需要使用 XMM 寄存器!

因此,在 Nehalem 微架构上,REP MOVSB/MOVSW 几乎没有用,但是当我们需要复制超过 256 字节的数据并且数据与缓存行边界对齐时,REP MOVSD/MOVSQ 非常有用.

在以前的英特尔微架构(2008 年之前)上,启动成本更高。自 1996 年的 Pentium Pro (P6) 以来,英特尔 x86 处理器就拥有“快速字符串”。P6 快速字符串采用 REP MOVSB 和更大的字符串,并使用 64 位微码加载和存储以及 non-RFO(阅读所有权) 缓存协议。与 Ivy Bridge 中的 ERMSB 不同,它们没有违反内存顺序。

2019 年 9 月推出的 Ice Lake 微架构引入了 Fast Short REP MOV (FSRM)。此功能可以通过 CPUID 位进行测试。它的目的是让 128 字节或更少的字符串也很快,但实际上,64 字节之前的字符串使用 rep movsb 仍然比使用简单的 64 位寄存器复制慢。除此之外,FSRM 仅在 64 位下实现,而不是在 32 位下实现。至少在我的 i7-1065G7 CPU 上,rep movsb 仅适用于 64 位以下的小字符串,但在 32 位架构上,字符串必须至少为 4KB 才能让 rep movsb 开始优于其他字符串方法。

以下是 REP MOVS* 的测试,当源和目标位于 L1 缓存中时,块足够大,不会受到启动成本的严重影响,但不会大到超过 L1 缓存大小。资料来源:http://users.atw.hu/instlatx64/

约娜 (2006-2008)

    REP MOVSB 10.91 B/c
    REP MOVSW 10.85 B/c
    REP MOVSD 11.05 B/c

尼哈勒姆 (2009-2010)

    REP MOVSB 25.32 B/c
    REP MOVSW 19.72 B/c
    REP MOVSD 27.56 B/c
    REP MOVSQ 27.54 B/c

韦斯特米尔 (2010-2011)

    REP MOVSB 21.14 B/c
    REP MOVSW 19.11 B/c
    REP MOVSD 24.27 B/c

Ivy Bridge (2012-2013) - 增强 REP MOVSB

    REP MOVSB 28.72 B/c
    REP MOVSW 19.40 B/c
    REP MOVSD 27.96 B/c
    REP MOVSQ 27.89 B/c

SkyLake (2015-2016) - 增强 REP MOVSB

    REP MOVSB 57.59 B/c
    REP MOVSW 58.20 B/c
    REP MOVSD 58.10 B/c
    REP MOVSQ 57.59 B/c

Kaby Lake (2016-2017) - 增强 REP MOVSB

    REP MOVSB 58.00 B/c
    REP MOVSW 57.69 B/c
    REP MOVSD 58.00 B/c
    REP MOVSQ 57.89 B/c

如您所见,REP MOVS 的实现在不同微体系结构之间存在显着差异。

根据 Intel 的说法,在 Nehalem 上,大于 9 字节的字符串的 REP MOVSB 启动成本为 50 个周期,但对于 REP MOVSW/MOVSD/MOVSQ,它们为 35 到 40 个周期 - 因此 REP MOVSB 具有更大的启动成本;测试表明,REP MOVSW 的整体性能最差,而不是 Nehalem 和 Westmere 上的 REP MOVSB。

在 Ivy Bridge、SkyLake 和 Kaby Lake 上,这些指令的结果是相反的:REP MOVSB 比 REP MOVSW/MOVSD/MOVSQ 快,尽管只是稍微快一点。在 Ivy Bridge 上,REP MOVSW 仍然落后,但在 SkyLake 和 Kaby Lake 上,REP MOVSW 并不比 REP 差 MOVSD/MOVSQ.

请注意,我提供了 SkyLake 和 Kaby Lake 的测试结果,这些结果取自 instaltx64 site 只是为了确认 - 这些架构具有相同的 cycle-per-instruction 数据。

结论:您可以将 MOVSD/MOVSQ 用于非常大的内存块,因为它在从 Yohan 到 Kaby Lake 的所有英特尔微体系结构上都能产生足够的结果。虽然在 Yonan 及更早的架构上,SSE copy 可能会产生比 REP MOVSD 更好的结果,但是,为了通用性,REP MOVSD 是首选。除此之外,REP MOVS* 可能在内部使用不同的算法来处理缓存,这对于普通指令是不可用的。

关于非常小的字符串(小于 9 字节或小于 4 字节)的 REP MOVSB - 我什至不会推荐它。在 Kaby Lake 上,单个 MOVSB 即使没有 REP 也是 4 个周期,在 Yohan 上是 5 个周期。根据上下文,您可以使用普通 MOV 做得更好。

如您所写,启动成本不会随着大小的增加而增加。完成整个字节序列的整个指令的延迟增加了——这很明显——你需要复制更多的字节,需要更多的周期,即整体延迟,而不仅仅是启动成本。英特尔并没有发现丢失小字符串的启动成本,它只为 Nehalem 指定了 76 字节或更多字节的字符串。例如,获取有关 Nehalem 的数据:

  • 如果 ECX < 4,则 MOVSB 的延迟为 9 个周期。因此,这意味着只要该字符串具有 1 个字节或 2 个字节或 3 个字节,就需要 9 个周期来复制任何字符串。这并没有那么糟糕——例如,如果您需要复制一条尾巴并且您不想使用或重叠商店。只需 9 个周期来确定大小(在 1 到 3 之间)并实际复制数据——用普通指令和所有这些分支很难实现这一点——对于 3 字节的复制,如果你没有复制以前的数据,您将不得不使用 2 次加载和 2 次存储(字 + 字节),并且由于我们最多只有一个存储单元,因此我们不会用普通的 MOV 指令更快地做到这一点。
  • 如果 ECX 介于 4 和 9 之间,英特尔对 REP MOVSB 的延迟保持沉默
  • 短字符串(ECX <= 12):REP MOVSW/MOVSD/MOVSQ 的延迟大约是复制整个字符串的 20 个周期——不仅仅是 20 个周期的启动成本。因此,复制 <= 12 字节的整个字符串需要大约 20 个周期,因此与 ECX < 4 的 REP MOVSB 相比,我们的每字节输出速率更高。
  • ECX >= 76 with REP MOVSD/MOVSQ – 是的,这里我们确实有 40 个周期的启动成本,但是,这是非常合理的,因为我们稍后使用复制每 64 个字节的数据,只需 4周期。我不是授权回答为什么有启动成本的英特尔工程师,但我想这是因为对于这些字符串,REP MOVS* 使用(根据 Andy Glew 对 Why are complexity [=82= 的回答的评论) ] superior? 来自 Peter Cordes 的回答)常规代码不可用的缓存协议功能。在这句话中有一个解释:“选择和设置正确方法的巨大开销主要是由于缺乏微码分支预测”。还有一个有趣的注意事项,即 1996 年的 Pentium Pro (P6) 使用 64 位微码加载和存储以及 no-RFO 缓存协议实现了 REP MOVS* - 它们没有违反内存顺序,这与 Ivy Bridge 中的 ERMSB 不同。

这个 patent 表明解码器能够确定 rcx 的最后一步是立即移动还是以 rcx 中的值是解码器未知。它通过在将立即移动解码为 rcx 时设置一个位来实现这一点,并将其称为 'fast string bit' 并将立即值存储在寄存器中。当它解码以未知方式修改 rcx 的指令时,该位将被清除。如果该位被设置,那么它跳转到一个单独的微代码例程中的一个位置,该例程可能是 12 次重复的大小——如果 rcx = 5 它跳到重复 7,即它保留的寄存器中的立即值为 5。这是一种不包含微分支的快速实现。如果未设置,根据 SGX 论文中关于更大数组的 'microcode assist' 的讨论,那么当 [=10= 的值] 是已知的,尽管这更像是一个总是陷阱的 'trap' uop 而不是 可能 导致需要 'assist' 的 uop。或者,正如该专利所建议的那样('否则,指令翻译器 206 将控制转移到循环 REP MOVS 微指令序列')MSROM 可以立即内联执行慢速例程,它只是继续发出重复并循环直到分支预测错误并最终被更正为未被采用并且微代码结束。

我假设常规(循环)MSROM 过程主体中的微分支将由 uop 本身(在操作码中)静态预测,因为这是一个将执行多个的循环次并预测错误一次。因此,这种快速方法只会消除序列末尾的分支预测错误以及每次迭代的微分支指令,从而减少微指令数。大部分错误预测发生在 Peter 提到的设置中,这似乎是 P6 'fast strings' 的设置(显然与专利中的术语 'fast string' 无关,后者出现在 P6 之后),或者实际上是 ERMSB,我认为这只发生在专利提到的慢速(循环)例程中。在慢速例程中,如果 ecx >= 76,则可以对其进行增强并通过初始设置过程,但似乎 ecx 需要超过一定大小才能使其实际更快'fast strings' 或 ERMSB 的启动过程。这将需要知道 ecx 的值,这可能只是一个常规的 ecx 比较和可能会错误预测的跳跃。显然这个缓慢的例程增强也使用了不同的缓存协议,.

微分支错误预测代价高昂,因为它必须 ,在它可能已经完成解码并且其他 uops 在它后面解码之后返回到 MSROM 过程。 BOB 也可能与微分支错误预测一起使用,这比宏分支错误预测更有益。 RAT快照很可能与每个分支指令的ROB条目相关联。