构建更快的AMD64 Memset例程

在过去几年中，Microsoft推出了多项更改，导致更多内存被清零。这些缓解措施包括：

• InitAll缓解措施，它清零大多数栈变量
• 将大多数Microsoft内核代码切换到ExAllocatePool2/ExAllocatePool3 API，这些API默认清零内存

在可能的情况下，编译器会展开对memset的调用。这意味着生成的代码将直接执行存储操作，而不是调用memset。这比调用memset快得多，因为它消除了调用指令的开销以及memset本身的开销（分支、支持设置任意值等）。这只有在编译器可以静态确定memset的大小且大小相对较小时才可能实现。对于大型memset，我们更倾向于调用memset函数以减少代码大小。对于大型或未知大小的memset，我们更倾向于调用memset函数，因为它可以查询各种CPU功能，从而比展开的实现表现更好。池分配器执行的所有清零操作以及InitAll执行的许多结构/数组初始化最终都会通过memset函数。

Memset是操作系统上最热门的函数之一，因此已经相当优化。在分析memset实现时，我意识到仍有改进空间，本博客详细介绍了优化该函数的方法和结果。

本文档中记录的实现已被许多Windows组件使用（所有内核模式组件以及许多用户模式组件）。任何使用最新WDK构建的第三方驱动程序也将使用此实现。它目前未被Visual Studio附带的用户模式CRT（UCRT.dll）使用。

关于性能数字的免责声明

本博客包含我对表现良好/不良好的观察以及我进行的一些基准测试。

性能测试是在广泛的AMD和Intel CPU上进行的，从10年以上的旧CPU到Kaby Lake和Ryzen 2。博客中分享的数字和观察结果不一定适用于每一代CPU。它们是我对所有测试的汇总观察。

Memset性能在以下方面可能有很大差异：

• 不同的CPU代际
• 不同的CPU供应商
• 同一代但针对不同平台（笔记本电脑、台式机、服务器芯片）的不同CPU

如果您正在构建自己的memset，请务必在尽可能多的CPU上进行测试。

Memset入门知识

在深入优化之前，了解一些基础知识很有帮助。

• 每个CPU核心有多个“端口”，可以同时执行不同的操作。虽然您的眼睛一次读取一条汇编指令，但CPU同时处理多条指令。具体细节因CPU代际而异。
• 现代CPU是乱序执行的，这意味着它们不一定按照读取的顺序执行指令，尽管必须遵守某些规则以确保正确性。
• CPU使用流水线，其中流水线的每个部分处理执行指令的某个部分。流水线的深度取决于CPU代际。
• CPU使用分支预测和推测执行来预测分支的方向，并开始沿该路径推测执行。如果CPU预测错误，它必须丢弃所有已完成的工作并开始沿正确路径执行。这将暂时停滞CPU，同时重新填充其流水线，并导致性能不佳。CPU流水线越深，这种回归可能越严重。
• 当前的Intel/AMD CPU每个时钟周期可以退休一条存储指令。假设对齐没问题，CPU可以每个周期退休一条16字节存储，就像它可以每个周期退休一条1字节存储一样；为了获得最佳性能，您应该使用尽可能大的存储。
• 跨越缓存行的未对齐存储指令会产生一定的性能损失。跨越页面边界的未对齐存储指令要慢得多（执行时间大约长4倍）。不跨越这两种边界的未对齐存储指令在现代CPU上几乎是免费的。

Memset完全是关于设置内存，这意味着使其表现良好本质上归结为每个时钟周期退休一条存储指令，并尽可能使用大存储（以减少需要退休的存储总数）。Memset有多个因素 actively 使这项任务变得困难：

• Memset处理任意大小，因此必须包含分支。分支预测错误将浪费多个CPU周期。
• Memset可以接受任意字节值进行存储。如果memset要使用一次存储超过1字节的指令，它必须将此单字节值扩展为模式（通常使用昂贵的“imul”指令）。
• 传递给memset的地址可能具有任意对齐方式，可能需要纠正才能使用最快的指令（即避免跨缓存行或跨页面边界访问）。
• 在内核模式实现中，使用AVX指令（允许一次存储32或64字节）不实用。出于效率原因，Windows内核在用户模式程序调用内核模式时不保存AVX寄存器的副本，因此如果内核模式memset尝试使用这些寄存器，它将破坏用户模式放入其中的内容。

现有的NT Memset

下图概述了现有NT memset函数的逻辑。

• 蓝色方块代表分支点。
• 橙色方块代表在低效循环中发生的存储，无法每个时钟退休1条指令。橙色方块还代表受可能预测错误的分支保护的单次存储。
• 绿色方块代表高效存储，因为它们无条件发生或在可以每个时钟退休1条存储的高效循环内。

在分析此memset实现后，我有以下担忧：

1. 对于小于80字节的大小，大部分存储是在每次迭代执行一次存储的循环中完成的。这是次优的，无法实现每个时钟退休1条存储。循环的每次迭代需要至少有4条存储指令才能每个时钟退休一条存储。这个数字是通过在各种硬件上基准测试不同存储循环发现的。
2. 有两个地方在设置尾随字节之前进行检查（分支）。几乎可以肯定，总是设置尾随字节（即使与先前的存储完全重叠）比冒险分支预测错误以节省一次存储要快。
3. 热路径代码（对于大于79字节的大小）有几个可能发生预测错误的地方。我不确定这个原始阈值是如何确定的。
4. 热路径代码有一个每次16字节的循环来设置尾随字节，无法每个时钟退休1条存储。

有趣的是，我发现当大小超过几百字节时，对第4点的担忧变得无关紧要。我相信这是因为CPU能够推测执行得足够远，以减轻低效尾随字节循环的影响。

该实现还具有一些很好的特性，例如：

• 非常小的代码大小。
• 对于256字节及更大的分配，性能极佳。执行一次16字节未对齐存储，然后目标16字节对齐，以便没有进一步的内存访问跨越缓存行或页面。
• 对于较小的分配大小，性能相当合理，特别是如果分支预测器预测正确。

该实现还有一个巧妙的技巧。在原始缓冲区足够大的情况下，缓冲区的尾随字节可以通过单次（可能未对齐）存储操作设置。计算缓冲区的结束地址，并从中减去8（或16）字节。这给出了用于最后8或16字节存储指令的地址。该指令可能与其他指令重叠，但比逐字节循环设置尾随字节要好得多。请注意，在现有的memset中，有一个分支来确定尾随存储是否必要，或者缓冲区是否已被完全填充。

这个技巧将在后面更有效地使用。

优化

Memset基本上分为两个主要部分：

1. 一个热循环，处理高于某个阈值的大小，具有极高的效率，几乎每个周期退休1条存储。
2. 处理任何太小而无法由热循环处理的代码。

Memset在以下常见场景中使用：

• 反复memset相同大小（例如在热循环中），其中函数的分支预测器在经过一定次数的循环迭代后将完美训练。
• memset各种不同大小（例如栈上的不同大小结构），其中分支预测器将无法正确预测。

我优化memset的方法是：

• 我们希望热循环对于大尺寸极其高效。
• 我们希望热循环处理尽可能多的大小，以便大多数设置沿单个分支处理。
• 我们希望最小化分支预测错误的数量，因为这可能严重损害性能。对于小的memset，单个分支预测错误可能消耗比所有存储更多的CPU周期。常见大小应以非常少的预测错误和最大每周期退休存储处理，不太常见的大小可以以更昂贵的方式处理。
• 编译器在编译大小时会展开63字节或更小的memset，在编译速度时会展开127字节或更小的memset。虽然小的可变大小memset仍将使用memset函数，但小的静态大小memset永远不会到达memset函数，因此可以稍微降低非常小尺寸的性能优先级。

有了这些，第一个分支决策被添加。

步骤1：确定热循环的最小必要大小

对于大尺寸（我们需要确定其最小大小），memset最终将循环遍历缓冲区并进行存储。

例如，这是一个此循环的简单实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

; rcx  = 目标缓冲区
; r8   = 要存储的字节数
; xmm0 = 一个16字节模式，其中每个单独字节等于要存储的字节

    shr r8, 4             ; r8包含要设置的16字节块数

big_loop:
    movdqu [rcx], xmm0    ; 存储16字节
    add     rcx, 16       ; 递增指针
    dec     r8            ; 递减计数器
    jnz     big_loop      ; 如果计数器不为零，再次循环

; 存储尾随字节（尚未实现！）

如前所述，memset需要尽可能接近每个时钟退休1条存储。暂时忽略memset的其余部分，这里实现的循环需要每个时钟退休1条存储才能最佳执行。不幸的是，在所有测试架构（各种AMD和Intel CPU，从10年旧到Kaby Lake / Ryzen 2）和所有测试大小范围（64字节到1MB）上，每次循环迭代执行1条存储不足以使CPU饱和。

Windows使用的现有memset实现使用每次迭代执行8次XMM存储（128字节）的循环。这表现良好；它每个时钟退休1条存储指令。但是，由于循环每次迭代存储128字节，需要特殊逻辑来处理小于128字节的大小。特殊逻辑意味着额外的分支，这是我们试图最小化的。

经过一些测试，我确定每次循环迭代执行2条存储仍然不能最佳执行，但4条存储每次迭代可以。这允许我们的循环每次迭代处理64字节。这很方便，因为由于编译器将展开小于64字节的静态大小memset，所有使用memset函数的静态大小memset将在热循环代码路径中处理。

步骤2：高效设置尾随字节

我们知道缓冲区至少64字节大。有0-63个尾随字节要设置。现代CPU内部实现了存储缓冲区，允许它们高效处理对同一地址的存储，而无需多次实际写入RAM。在大多数CPU上，这需要存储直接重叠以最大化效率。

而不是使用条件分支来存储0-63字节的尾随数据，我们执行以下操作：

1. 计算目标结束后的1字节。
2. 从中减去16字节，将其（在寄存器中）保存为最后尾随存储的位置。
3. 从中减去48字节并将结果向下对齐到最近的16字节边界，将其（在寄存器中）保存为最后3个对齐存储的位置。
4. 热循环后，对步骤3中计算的对齐位置执行3次16字节存储（每次将地址递增16）。
5. 对步骤2中计算的最后16字节数据执行1次16字节存储。

在汇编中看起来像这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

; rcx  = 目标缓冲区
; r8   = 要存储的字节数
; xmm0 = 一个16字节模式，其中每个单独字节等于要存储的字节

        lea     rdx, [rcx + r8 - 16]    ; 计算最后16字节存储的位置
        lea     r9, [rcx + r8 - 48]     ; 计算第一个“尾随字节”存储的位置
        and     r9, NOT 15              ; 第一个“尾随字节”存储应为16字节对齐

        movaps  [r9], xmm0
        movaps  [r9 + 16], xmm0
        movaps  [r9 + 32], xmm0
        movups  [rdx], xmm0

请注意，如果缓冲区正好是64字节大，这将导致退休8条存储。热循环将执行4条存储，尾随字节代码也将无条件执行4条存储。退休所有这些存储需要8个CPU周期，但由于CPU的存储缓冲区，多次存储将仅每16字节位置写入CPU缓存一次。换句话说，为了退休4条额外存储指令的4个CPU周期开销，我们可以：

• 消除 previous NT memset 必须设置尾随字节的循环。
• 消除 previous NT memset 在设置最后16字节之前的0大小分支。

这可能是值得的，因为单个分支预测错误成本超过4个周期。

步骤3：高效设置少量字节

此memset现在处理所有大于或等于64字节的大小，但需要高效处理小于64字节的大小。

我们预计会很少看到超小的memset。例如，1字节memset应该相当不常见，并且相对于正在执行的操作（单字节写入）已经有很多开销。考虑到这一点，我决定优先处理此范围内的较大尺寸是可以的。

可变大小无分支存储技术

我观察到前一节的尾随字节代码在这里会有用。假设大小至少为16字节，我可以无条件设置16到63字节，使用以下汇编序列：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

; rcx = 目标
; r8 = 大小
; xmm0 = 要存储的模式

        lea     r9, [r8 + rcx - 16]     ; 计算最后存储的位置，可能未对齐
        and     r8, 32                  ; 如果大小至少32字节，r8 = 32，否则 r8 = 0
        movups  [rcx], xmm0             ; 设置前16字节
        shr     r8, 1                   ; 将r8除以2，现在为16或0
        movups  [r9], xmm0              ; 设置最后位置
        movups  [rcx + r8], xmm0        ; 设置索引0或索引16，基于大小是否至少32
        neg     r8                      ; 0或-16
        movups  [r9 + r8], xmm0         ; 设置倒数第二个位置

此汇编序列可以每个CPU周期退休1条存储。类似的算术可用于然后设置4到15字节（使用4字节存储指令而不是16字节存储指令）。对于大小0、1、2和3，使用分支来确定精确的字节数。这些大小应该非常不常见，因此性能慢不是问题。

这是一个巨大的胜利，因为我们预计当memset被调用用于小于64字节的大小时，大小可能至少为16字节。我们需要一个分支来检查大小是否大于16字节，然后可以执行memset而无需额外分支。

以下是一些示例图，帮助说明如何对不同大小执行4条存储：

此图显示了处理所有小尺寸后memset的决策树：

步骤4：优化真正大的尺寸

回到负责设置大缓冲区的代码，还有一个额外的优化可以做。现代Intel CPU支持增强的“rep stosb”指令，对于大尺寸，它可以比SSE指令运行得更快（软件实现对于中小尺寸仍然更好）。“rep stosb”的一大优势，特别是在内核模式下，是它可以在底层使用32字节或64字节存储。内核可以使用如此大存储的唯一其他方法是首先保存所有AVX寄存器状态（这需要存储超过1,000字节的数据）。

在我的测试中，我确实注意到“rep stosb”的一个大缺陷，在我测试过的每个CPU上都重现：传递未对齐到32字节边界的地址将导致性能下降约50%。这可以通过使用XMM存储指令存储缓冲区的前64字节，然后将缓冲区对齐到64字节边界，调整大小，并将缓冲区的其余部分传递给“rep stosb”来修复。您可能想知道为什么我将缓冲区64字节对齐而不是32字节。我没有任何支持AVX-512的CPU来测试，我假设“rep stosb”在缓冲区未64字节对齐时性能会下降，同时执行该架构允许的64字节存储。鉴于没有真正理由不将缓冲区64字节对齐，我这样做是为了安全起见。

我还观察到，对于小于800字节的大小，通常最好只使用正常的XMM存储循环而不是使用“rep stosb”。请注意，此阈值因CPU代际而异（较新一代通常能够使用较低的阈值），但800字节阈值是所有测试CPU代际的良好整体折衷。

我们还需要一个额外的分支来检查预填充的全局变量，指示CPU是否支持“增强stosb”。如果CPU不支持，则memset将不使用“rep stosb”指令，因为它将表现极差。所有现代Intel CPU都支持“rep stosb”，希望AMD将来支持它。

乍一看，这些在热路径循环中添加的额外分支似乎是不必要的开销。“增强stosb支持检查”应该总是被CPU正确推测，因为它在启动时配置且从不更改。传递给memset的大多数大小小于800字节，因此800字节大小检查也应该总是通常推测较小尺寸。对于大于800字节的大小，分支预测错误是可接受的，因为使用“rep stosb”有如此大的性能优势。默认推测行为（如果不存在分支预测信息）是增强stosb支持且大小小于800字节。

分析理论性能

请注意，在下表中，虽然理论上循环的每次迭代都可能发生分支预测错误，但极不可能。我假设循环最大预测错误次数为1（退出循环的预测错误，某些CPU可能实际优化掉）。