如何优化热循环中的内存写入
How to optimize for writes to memory in hot loop
我的代码中有一个循环，我花费了大部分 CPU 时间：
%%write_to_intermediate_head:
; uint64_t count_index = (arr[i] >> (8 * cur_digit)) & (RADIX - 1);
; We will use rsi to hold the digit we're currently examining
mov rsi, [rdx + rdi * 8] ; Load arr[i] into rsi
mov r9, %1 ; Load current digit were sorting on
shl r9, 3 ; Multiply by 8
shrx rsi, rsi, r9
and rsi, 255
; intermediate_arr[--digit_counts[count_index]] = arr[i];
; rdi is the loop counter i
; rsi is the count_index
; rcx is the digit_counts array
; rax is the intermediate_arr
dec qword [rcx + rsi * 8]
mov r9, [rcx + rsi * 8] ; --digit_counts[count_index]
mov rsi, [rdx + rdi * 8] ; arr[i]
mov [rax + r9 * 8], rsi
dec rdi
jnz %%write_to_intermediate_head
变量：digit_counts、arr、intermediate_arr都在内存中（堆和bss）。 AMD 分析器显示许多周期用于读取和写入这些内存位置。有什么办法可以优化吗？
您的计数真的需要是 qwords 吗，或者您可以使用更窄的类型来将 32 位的缓存占用空间减半（或者更窄的更少）？如果您遇到缓存未命中，这将意味着如果 OoO exec 无法隐藏该延迟，则等待 loads/stores 的时间会更多。
不过，我想复制数据将是内存带宽/高速缓存未命中的大部分。这看起来像 Radix Sort，与数据相比，要管理的元数据量很小。 （但至少它命中缓存会有所帮助，使其更能抵抗您扔掉的所有其他数据的驱逐。）
无论你做什么，Radix Sort 的访问模式本质上都不是很缓存友好，尽管它并不可怕。您正在将写入分散到 256 个可能的目的地，同时更新指针。但是这 256 个目的地是顺序流，所以如果幸运的话，它们可以命中 L1d 缓存。
希望这些目的地不是 4k 的倍数（最初或大部分时间），否则它们将在 L1d 缓存中为同一行添加别名并导致冲突未命中。 （即强制驱逐您即将写入的另一个部分写入的缓存行。）
您有一些冗余加载/存储，这可能是 load/store 执行单元的瓶颈，但如果这不是瓶颈，那么缓存会很好地吸收它们。本节主要是关于调整循环以使用更少的 uops，在 no-cache-miss 最佳情况下进行改进，并为 OoO exec 提供更少的隐藏延迟。
使用内存目标 dec 然后重新加载 dec 的存储在总后端 load/store 操作和 OoO 执行延迟方面显然效率低下隐藏。 （尽管在 AMD 上，dec mem 仍然是前端的单个 uop，而在 Intel 上是 3；https://uops.info/ and https://agner.org/optimize/）。
同样，你不是用相同的 RDI 加载了两次 [rdx + rdi * 8] ; arr[i] 吗？ SHRX 可以复制和移动，因此您甚至不会通过保留该加载结果以备后用而节省微指令。 （你也可以为 arr[i] 使用简单的非索引寻址模式，通过像 add rdi,8 和 cmp rdi, endp/jne 这样的指针递增，其中 end 是你之前计算的使用 lea endp, [rdx + size*8]。在数组上循环 forward 对于某些 HW 预取器来说可能更好。）
x86-64 有 15 个寄存器，因此如果您需要更多用于此内部循环，save/restore 函数 top/bottom 处的一些调用保留寄存器（如 RBX 或 RBP）。或者在必要时将一些外循环的东西溢出到内存中。
mov r9, %1 看起来是循环不变的，因此将 shl r9, 3 计算提升到循环之外，并且不要在内循环中覆盖 R9。
您确实需要对提取的字节进行零扩展，但 and rsi, 255 不如 movzx eax, sil 有效。 （或者更好的是，选择一个像 ECX 这样的寄存器，它的低字节可以在没有 REX 前缀的情况下访问）。不过，AMD 无法像 Intel 那样在 movzx 上进行 mov-elimination，所以只是为 AMD 节省了代码大小，但如果你在 Intel CPU 上 运行 这样做，则可以优化延迟。
或者更好，AMD Zen 有单微指令BMI1 bextr r64,r64,r64，所以在寄存器的低2 字节准备一个start/length 对。如前所述，这是循环不变的。即在循环 mov ecx, %k1 / shl cl, 3 / mov ch, 0x8 之前（AMD 没有部分寄存器停顿，只有错误的依赖关系。在这种情况下是正确的，因为我们想要合并。）如果那是内联 asm 语法，%k1 指定寄存器的 32 位版本。或者是内存的话，反正你就是loading，吊起来又省了一个load！
（Intel 有 2-uop bextr，大概是 shift 和 bzhi uops。）
或者如果你真的想加载两次，movzx esi, byte [rdi + rdx] 其中 RDI 是指向你递增或递减的 arr[[i] 的指针，而 RDX 是一个字节偏移量。但 BEXTR 可能是更好的选择。
其他优化。生成计数的初始传递可以同时对所有数字完成，使用矩阵而不是数组。对于 64 位无符号整数，用 1 字节数字进行 8 次传递已经足够接近理想，因为计数 |索引将适合 L1 缓存。初始通道将计数存储在 [8][256] 矩阵中，32 位计数|索引应该足够好。
对于比缓存大得多的大数组，如果要排序的数据相当均匀，那么第一个基数排序通道可以是最高有效位通道，如果使用 1 字节数字则创建 256 个 bin，目标是适合高速缓存的 256 个箱中的每一个，并在 256 个箱中的每一个上首先对最低有效位进行基数排序，一次一个箱。如果数组更大，第一遍可以创建更多的 bins，512（9 位数字），1024（10 位数字），...，然后每个 bin 仍然可以使用 1 字节数字进行排序，最后一个数字较小通过.
我的代码中有一个循环，我花费了大部分 CPU 时间：
%%write_to_intermediate_head:
; uint64_t count_index = (arr[i] >> (8 * cur_digit)) & (RADIX - 1);
; We will use rsi to hold the digit we're currently examining
mov rsi, [rdx + rdi * 8] ; Load arr[i] into rsi
mov r9, %1 ; Load current digit were sorting on
shl r9, 3 ; Multiply by 8
shrx rsi, rsi, r9
and rsi, 255
; intermediate_arr[--digit_counts[count_index]] = arr[i];
; rdi is the loop counter i
; rsi is the count_index
; rcx is the digit_counts array
; rax is the intermediate_arr
dec qword [rcx + rsi * 8]
mov r9, [rcx + rsi * 8] ; --digit_counts[count_index]
mov rsi, [rdx + rdi * 8] ; arr[i]
mov [rax + r9 * 8], rsi
dec rdi
jnz %%write_to_intermediate_head
变量：digit_counts、arr、intermediate_arr都在内存中（堆和bss）。 AMD 分析器显示许多周期用于读取和写入这些内存位置。有什么办法可以优化吗？
您的计数真的需要是 qwords 吗，或者您可以使用更窄的类型来将 32 位的缓存占用空间减半（或者更窄的更少）？如果您遇到缓存未命中，这将意味着如果 OoO exec 无法隐藏该延迟，则等待 loads/stores 的时间会更多。
不过，我想复制数据将是内存带宽/高速缓存未命中的大部分。这看起来像 Radix Sort，与数据相比，要管理的元数据量很小。 （但至少它命中缓存会有所帮助，使其更能抵抗您扔掉的所有其他数据的驱逐。）
无论你做什么，Radix Sort 的访问模式本质上都不是很缓存友好，尽管它并不可怕。您正在将写入分散到 256 个可能的目的地，同时更新指针。但是这 256 个目的地是顺序流，所以如果幸运的话，它们可以命中 L1d 缓存。
希望这些目的地不是 4k 的倍数（最初或大部分时间），否则它们将在 L1d 缓存中为同一行添加别名并导致冲突未命中。 （即强制驱逐您即将写入的另一个部分写入的缓存行。）
您有一些冗余加载/存储，这可能是 load/store 执行单元的瓶颈，但如果这不是瓶颈，那么缓存会很好地吸收它们。本节主要是关于调整循环以使用更少的 uops，在 no-cache-miss 最佳情况下进行改进，并为 OoO exec 提供更少的隐藏延迟。
使用内存目标 dec 然后重新加载 dec 的存储在总后端 load/store 操作和 OoO 执行延迟方面显然效率低下隐藏。 （尽管在 AMD 上，dec mem 仍然是前端的单个 uop，而在 Intel 上是 3；https://uops.info/ and https://agner.org/optimize/）。
同样，你不是用相同的 RDI 加载了两次 [rdx + rdi * 8] ; arr[i] 吗？ SHRX 可以复制和移动，因此您甚至不会通过保留该加载结果以备后用而节省微指令。 （你也可以为 arr[i] 使用简单的非索引寻址模式，通过像 add rdi,8 和 cmp rdi, endp/jne 这样的指针递增，其中 end 是你之前计算的使用 lea endp, [rdx + size*8]。在数组上循环 forward 对于某些 HW 预取器来说可能更好。）
x86-64 有 15 个寄存器，因此如果您需要更多用于此内部循环，save/restore 函数 top/bottom 处的一些调用保留寄存器（如 RBX 或 RBP）。或者在必要时将一些外循环的东西溢出到内存中。
mov r9, %1 看起来是循环不变的，因此将 shl r9, 3 计算提升到循环之外，并且不要在内循环中覆盖 R9。
您确实需要对提取的字节进行零扩展，但 and rsi, 255 不如 movzx eax, sil 有效。 （或者更好的是，选择一个像 ECX 这样的寄存器，它的低字节可以在没有 REX 前缀的情况下访问）。不过，AMD 无法像 Intel 那样在 movzx 上进行 mov-elimination，所以只是为 AMD 节省了代码大小，但如果你在 Intel CPU 上 运行 这样做，则可以优化延迟。
或者更好，AMD Zen 有单微指令BMI1 bextr r64,r64,r64，所以在寄存器的低2 字节准备一个start/length 对。如前所述，这是循环不变的。即在循环 mov ecx, %k1 / shl cl, 3 / mov ch, 0x8 之前（AMD 没有部分寄存器停顿，只有错误的依赖关系。在这种情况下是正确的，因为我们想要合并。）如果那是内联 asm 语法，%k1 指定寄存器的 32 位版本。或者是内存的话，反正你就是loading，吊起来又省了一个load！
（Intel 有 2-uop bextr，大概是 shift 和 bzhi uops。）
或者如果你真的想加载两次，movzx esi, byte [rdi + rdx] 其中 RDI 是指向你递增或递减的 arr[[i] 的指针，而 RDX 是一个字节偏移量。但 BEXTR 可能是更好的选择。
其他优化。生成计数的初始传递可以同时对所有数字完成，使用矩阵而不是数组。对于 64 位无符号整数，用 1 字节数字进行 8 次传递已经足够接近理想，因为计数 |索引将适合 L1 缓存。初始通道将计数存储在 [8][256] 矩阵中，32 位计数|索引应该足够好。
对于比缓存大得多的大数组，如果要排序的数据相当均匀，那么第一个基数排序通道可以是最高有效位通道，如果使用 1 字节数字则创建 256 个 bin，目标是适合高速缓存的 256 个箱中的每一个，并在 256 个箱中的每一个上首先对最低有效位进行基数排序，一次一个箱。如果数组更大，第一遍可以创建更多的 bins，512（9 位数字），1024（10 位数字），...，然后每个 bin 仍然可以使用 1 字节数字进行排序，最后一个数字较小通过.