Pau*_*zak 28 c++ benchmarking simd avx2 vector-class-library
我在 Intel i3-N305 3.8GHz 和 AMD Ryzen 7 3800X 3.9GHz PC 上运行了使用 gcc-13 ( https://godbolt.org/z/qq5WrE8qx )编译的相同二进制文件。此代码使用 VCL 库（https://github.com/vectorclass/version2）：
int loop_vc_nested(const array<uint8_t, H*W> &img, const array<Vec32uc, 8> &idx) {
int sum = 0;
Vec32uc vMax, iMax, vCurr, iCurr;
for (int i=0; i<H*W; i+=W) {
iMax.load(&idx[0]);
vMax.load(&img[i]);
for (int j=1; j<8; j++) {
iCurr.load(&idx[j]);
vCurr.load(&img[i+j*32]);
iMax = select(vCurr > vMax, iCurr, iMax);
vMax = max(vMax, vCurr);
}
Vec32uc vMaxAll{horizontal_max(vMax)};
sum += iMax[horizontal_find_first(vMax == vMaxAll)];
}
return sum;
}
完整的基准源位于：https://github.com/pauljurczak/simd-benchmarks/blob/main/main-5-vcl-eve.cpp。这是时间安排：
int loop_vc_nested(const array<uint8_t, H*W> &img, const array<Vec32uc, 8> &idx) {
int sum = 0;
Vec32uc vMax, iMax, vCurr, iCurr;
for (int i=0; i<H*W; i+=W) {
iMax.load(&idx[0]);
vMax.load(&img[i]);
for (int j=1; j<8; j++) {
iCurr.load(&idx[j]);
vCurr.load(&img[i+j*32]);
iMax = select(vCurr > vMax, iCurr, iMax);
vMax = max(vMax, vCurr);
}
Vec32uc vMaxAll{horizontal_max(vMax)};
sum += iMax[horizontal_find_first(vMax == vMaxAll)];
}
return sum;
}
出现了 3.2 倍的意外减速。AFAIK，这些 CPU 对于单线程程序具有类似的 SIMD 功能。7-zip 基准测试的性能非常接近。为什么差距这么大？
这是 的输出perf。AMD 锐龙 7 3800X：
Ubuntu 22.04.3 LTS on AMD Ryzen 7 3800X 8-Core Processor
gcc v13.1 __cplusplus=202100
loop_vc_nested(): 3.597 3.777 [us] 108834
Ubuntu 23.10 on Intel(R) Core(TM) i3-N305
gcc v13.1 __cplusplus=202100
loop_vc_nested(): 11.804 11.922 [us] 108834
英特尔 i3-N305：
3,841.61 msec task-clock # 1.000 CPUs utilized
20 context-switches # 5.206 /sec
0 cpu-migrations # 0.000 /sec
2,191 page-faults # 570.333 /sec
14,909,837,582 cycles # 3.881 GHz (83.34%)
3,509,824 stalled-cycles-frontend # 0.02% frontend cycles idle (83.34%)
9,865,497,290 stalled-cycles-backend # 66.17% backend cycles idle (83.34%)
42,856,816,868 instructions # 2.87 insn per cycle
# 0.23 stalled cycles per insn (83.34%)
1,718,672,677 branches # 447.383 M/sec (83.34%)
2,409,251 branch-misses # 0.14% of all branches (83.29%)
编译器选项：-O3 -Wno-narrowing -ffast-math -fno-trapping-math -fno-math-errno -ffinite-math-only -march=alderlake
i3-N305 上的其他缓存使用信息perf stat -d：
12,015.18 msec task-clock # 1.000 CPUs utilized
57 context-switches # 4.744 /sec
0 cpu-migrations # 0.000 /sec
2,196 page-faults # 182.769 /sec
45,432,594,158 cycles # 3.781 GHz (74.97%)
42,847,054,707 instructions # 0.94 insn per cycle (87.48%)
1,714,003,765 branches # 142.653 M/sec (87.48%)
4,254,872 branch-misses # 0.25% of all branches (87.51%)
TopdownL1 # 0.2 % tma_bad_speculation
# 45.5 % tma_retiring (87.52%)
# 53.8 % tma_backend_bound
# 53.8 % tma_backend_bound_aux
# 0.5 % tma_frontend_bound (87.52%)
我安装了最新的英特尔 C++ 编译器，以便开始-march=gracemont工作。性能没有提高，因为英特尔编译器是基于 clang 的，在这个基准测试中它的性能比 gcc 差。以下是时间安排：
15,615,324,576 L1-dcache-loads # 1.294 G/sec (54.50%)
<not supported> L1-dcache-load-misses
60,909 LLC-loads # 5.048 K/sec (54.50%)
5,231 LLC-load-misses # 8.59% of all L1-icache accesses (54.50%)
Pet*_*des 43
AVX 编码vpblendvb有 4 个操作数（3 个源和一个单独的目标），即使在 Intel P 核上也是多微指令（与传统 SSE 128 位编码不同），但在 Zen 上是单微指令。不同的算法可以避免它。
Alder Lake E-cores (Gracemont) 是 5 宽乱序，具有合理的乱序执行能力，但它们一般在 256 位 SIMD 上表现不佳，特别是在 8-uop 上严重vpblendvb ymm阻塞，包括看起来像的前端瓶颈。但是你的内部循环在依赖链中每第四条指令就使用它（足够短，以至于 OoO exec 可能部分隐藏，所以我们可能只是得到后端吞吐量或前端瓶颈的影响）。
您的实施策略/算法是 Zen 2 所擅长的，但这对 Gracemont 来说是一个绊脚石，放大了 256 位与 128 位 SIMD 执行单元之间的差异。
您的i3-N305是Alder Lake-N系列。与型号中带有 N 的早期 Celeron/Pentium CPU 一样，这些内核都是低功耗 Silvermont 系列。在本例中，Gracemont 是完整 Alder Lake 芯片中的 E 核。（它比 Tremont 或尤其是像 Goldmont Plus 这样的前代产品要强大得多。）而且它有 AVX2+FMA，我想这就是它作为 i3 出售的理由。
https://chipsandcheese.com/2021/12/21/gracemont-revenge-of-the-atom-cores/深入探讨了 CPU 微架构，与 Zen 2 进行了一些比较，以及缓存带宽和性能的微基准测试延迟（作为 i9-12900k 的一部分，IDK 如果互连或 L3 在 i3-N 系列中不同，但您的基准测试适合其 2M L2 缓存；在单个核心处于活动状态时，L2 的读取带宽大约相同作为顺序访问的 L1d。）没有提及解码器如何处理超过 3 uop 的指令，但它确实有一个图表显示了一对 3 宽解码簇。（如果像以前的 Intel 一样，任何超过 1 uop 的指令只能在集群的第一个解码器中解码，因此这可能会将前端吞吐量限制为每个时钟两个 YMM 向量指令，即使它们是最小 2 uop。）
您的 Ryzen 3800X 是 Zen 2，一个成熟的大核心，具有良好的 256 位 SIMD 负载和 ALU 吞吐量（Zen 1、Ryzen 1xxx 和 2xxx 系列中为 128 位）。和单微操作vpblendvb。
最重要的因素是：
向量 ALU 和内存端口为 128 位宽，每个 256 位指令解码为（至少）2 uops，除了少数类似vextracti128和vpmovmskb。（所以它就像 Zen 1 和 Bulldozer 系列）。因此，当运行主要是带有一点标量开销的向量指令的代码时，每个时钟的 uops 大约是 IPC 的两倍。当每个负载仅为 128 位时，2/时钟负载带宽仅达到一半。
编译select为vpblendvb. 不幸的是，Gracemont 上的速度非常慢，请参阅https://uops.info/ - 变量混合的 VEX 编码为每 128 位通道 4 uops，因此 YMM 版本为 8 uops，测量吞吐量为每 3.86 个周期 1 个。（令人惊讶的是，内存源需要 3.2 个周期而不是寄存器。）Zen 系列将 4 操作数vpblendvb作为单个 uop 运行（甚至可以选择端口）。
传统的 SSE 编码只有 3 个操作数，其中一个是隐式 XMM0，Gracemont 将其作为单个 uop 运行。即使 Alder Lake P 核也vpblendvb x/ymm以 3 个微指令运行，而 Ice Lake 中为 2 个微指令，而 SSE4.1pblendvb xmm, xmm在现代英特尔 P 核上也是单微指令。
Gracemontvpblendvb ymm还具有 6 到 7 个周期延迟，或者 XMM 版本为 5c（P 核上为 2 到 3 个），具体取决于作为关键路径的数据与控制输入，而 Zen 上为 1 个周期。即使存在前端瓶颈，其吞吐量甚至更差。无序执行缓冲区（调度程序和 ROB）可能足够大，可以将其隐藏在 7 个缓冲区的链上，因为您每 256 字节启动一个新的 dep 链，但这不是很好，并且会成为循环中的瓶颈运行更多迭代。
英特尔在设计它的 AVX1 编码时似乎犯了错误（在立即字节中包含第四个寄存器号！），而 Sandybridge 系列仍在设计中，没有预料到他们后来的 CPU 能够将 3 操作数指令作为单个指令处理uop。（受 Haswell 中的 FMA 启发，但使 Broadwell 及更高版本中的其他人受益。）并且如果在指令之后需要原始值（与此处不同），则 mov 消除将消除在需要时复制寄存器的后端执行端口成本就地修改 R+W 目标。FMA3 和更高版本的 3 输入指令（如 AVX-512）vpternlogd具有vpermi/t2dR+W 源/目标作为第一个操作数。（kAVX-512 指令的掩码输入是一个单独的转发网络和一个单独的域来跟踪依赖项，因此它们不算在内。）
对于相同的 uops/时钟吞吐量，8 uops 本质上会导致 IPC 较低，但也可能会导致前端停顿一些，从而减少 uops/时钟。如果连续运行，即使 Gracemont 的 4-uop 也有大约vpblendvb xmm相同的糟糕吞吐量，这与某种解码停顿或必须在 > 3 uop 指令上切换到微代码 ROM 一致。
您可以尝试与_mm256_and_si256/ andnot/手动混合or，这将是 6 uop，但避免前端停顿，矢量 ALU 端口上的总吞吐量成本为 1.33 个周期。但是 clang 会将这些内在函数“优化”为 a vpblendvb，因为它知道混合控制是比较结果，所有位都与符号位匹配。
Clang trunk 的-mtune=gracemont或-march=gracemont不知道它在那个 uarch 上很慢，至少没有分裂select成那些。MSVC，或者经典的 ICC，对于内在函数来说更加字面化。GCC 确实优化了一些，但在这种情况下，它确实使用实际的vpand//指令（https://godbolt.org/z/3fc1jo9r4vpandn ），因此您可以制作一个在 Ryzen 上更差、在 Gracemont 上不那么糟糕的版本，但在任何地方都不是最佳的。我认为 Gracemont 的版本仍然比下面的版本更糟糕。vpornoselect
您的原始版本对于 Ryzen 来说相当不错，但在清理方面还有改进的空间，并且可能向后扫描以避免反转比较以提供混合。或者，如果最大元素的实例经常出现在前 64 个字节内，那么分支策略可能是最好的，因此它是可预测的。只需加载 + 7x vpmaxub ymm, mem，然后缩小并扫描。
您的实际问题可以通过其他方式完成，例如，按照 chtz 在使用库寻找有效函数来查找 SIMD 向量中最大元素的索引中建议的那样使用索引解包数据，因此最大u16元素包含数据和索引。（索引可以来自 ，而不是加载idx = _mm256_add_epi8(idx, _mm256_set1_epi8(32));。也许超过 256 个字节的内部循环可以完全展开，因此您有 8 个寄存器保存索引数据。）
由于您可能无论如何都想使用改进的缩减，因此更早地解包可以节省一些清理工作，并且您的循环只有 8 个向量。
对于索引的总和，我想获得匹配项的第一次出现很重要？因此，您需要反转索引，以便在相等数据的平局时，打包为 u16 的 data:index 的最大值会选择较早的索引。无论如何，这就是我们想要使用的清理工作vphminposuw。
这就是它可能的样子，如果对索引不聪明，那么它可能会采用最后一个。
int loop_vc_nested_noselect(const std::array<uint8_t, H*W> &img, const std::array<Vec32uc, 8> &idx) {
int sum = 0;
for (int i=0; i<H*W; i+=W) {
__m256i tmpidx = _mm256_loadu_si256((__m256i*)&idx[0]);
__m256i tmp = _mm256_loadu_si256((__m256i*)&img[i]);
Vec16us vMaxlo = _mm256_unpacklo_epi8(tmpidx, tmp);
Vec16us vMaxhi = _mm256_unpackhi_epi8(tmpidx, tmp);
for (int j=1; j<8; j++) {
Vec32uc vCurr, iCurr;
iCurr.load(&idx[j]); // these get hoisted out of the outer loop and reused across img iters
vCurr.load(&img[i+j*32]);
Vec16us lo = _mm256_unpacklo_epi8(iCurr, vCurr);
Vec16us hi = _mm256_unpackhi_epi8(iCurr, vCurr);
vMaxlo = max(vMaxlo, lo);
vMaxhi = max(vMaxhi, hi);
// vMax = max(vMax, max(lo,hi)); // GCC was optimizing to two dep chains anyway, and that's better on big-cores that can do more than 1 load+shuffle+max per clock
}
Vec16us vMax = max(vMaxlo, vMaxhi);
// silly GCC uses vpextrw even though we're already truncating narrower
auto maxidx = (uint8_t)horizontal_max(vMax); // retrieve the payload from the bottom of the max
// TODO: use phminposuw like the last part of maxpos_u8_noscan_unpack
// with indices loaded and inverted once, outside the outer loop. (Manually unrolled if compilers don't do that for you)
sum += maxidx;
}
return sum;
}
您可以不加载索引，而只是计算它们_mm256_sub_epi8(idx, _mm256_set1_epi8(-1))（或add从 255 开始按降序排列），尽管编译器可能会通过它进行常量传播并生成 8 个常量向量，并使用 RIP 相对寻址模式来加载该索引比[rsi+disp8]前 5 次加载的代码大小更大，但这只是启动代码。编译器完成展开后，您肯定希望它具有在循环之前生成的 8 个索引向量。
神箭。GCC-O3 -march=alderlake完全展开，index在外循环之前加载所有 8 个向量并从寄存器中使用它们。（与原始版本相同。）
内循环看起来像这样；请注意，它两次使用相同的内存源操作数以节省前端带宽，但代价是增加后端微指令。事实上，这在 Gracemont 和 Alder Lake 上都是可以的；vpunpckl/hbw是 2 个前端微指令，有或没有内存源操作数。对于 1.0 与 0.66 周期吞吐量，但对于单独的负载，我认为前端将是一个更糟糕的瓶颈，具体取决于它解码 2-uop 指令的速度。每次vpmaxuw解包都是额外的向量 ALU 工作，以保持端口繁忙，因此不会成为负载瓶颈。
Clang-mtune=gracemont选择不同，但即使针对 Alder Lake / Ice Lake 进行调整，它也不会加载两次。
.L7:
vpunpcklbw ymm11, ymm7, YMMWORD PTR [rax+32]
vpunpckhbw ymm10, ymm7, YMMWORD PTR [rax+32]
add rax, 256
vpunpcklbw ymm0, ymm8, YMMWORD PTR [rax-256]
vpunpckhbw ymm9, ymm8, YMMWORD PTR [rax-256]
vpmaxuw ymm0, ymm0, ymm11
vpmaxuw ymm9, ymm9, ymm10
vpunpcklbw ymm11, ymm6, YMMWORD PTR [rax-192]
vpunpckhbw ymm10, ymm6, YMMWORD PTR [rax-192]
vpmaxuw ymm0, ymm0, ymm11
vpunpcklbw ymm11, ymm5, YMMWORD PTR [rax-160]
vpmaxuw ymm9, ymm9, ymm10
vpunpckhbw ymm10, ymm5, YMMWORD PTR [rax-160]
vpmaxuw ymm0, ymm0, ymm11
...
https://uica.uops.info/预测 Ice Lake 每次迭代可以运行 14 个周期，而该vpblendvb版本为 17 个周期。这在矢量 ALU 端口上几乎遇到瓶颈，因此 Alder Lake 的版本会更糟vpblendvb。
我还没有对 Gracemont 进行手工分析，也没有尝试过可能有 Gracemont 模型的 LLVM-MCA。
我也没有考虑过优化它以用作vphminposuw清理的一部分，这会节省更多，有助于支付我们为每个向量所做的额外洗牌工作。
或者考虑一个分支策略，比如找到最大值，然后在数组中搜索第一个匹配项。（比较/移动掩码又名to_bits(curr == bcast_max)，如果非零，则返回tzcnt(mask)）。您永远不需要加载索引数据向量，并且早期匹配可以减少工作量。（但它可能会错误地预测哪个可能更糟糕；仍然值得一试。但是，对依赖于正确分支预测的有用的微基准测试非常困难 - 微基准可以学习一种模式。或者，如果你让它完全随机，它的预测会比真实数据更糟糕分布。）
只需 8 个数据向量，第二遍循环就可以在没有负载的情况下完全展开。第一遍可以将数据留在寄存器中。（但它也必须完全展开，也许一次检查一对 ymm 寄存器是否匹配，使用 Shift/or 和 64 位 tzcnt。 vpmovmskb r32, ymm在 Gracemont 上是单 uop。）这意味着单独的第一遍加载 + max 指令，而不是内存源。Gracemont 没有 uop 缓存，但显然它的解码器可以很好地处理吞吐量。对于连续的 2-uop 指令来说，也许效果并不好。
（这与当前清理使用的策略基本相同，找到最大值，然后搜索其位置，但跨越整个 8 向量数组。允许将第一遍和第二遍之间的大部分水平最大工作减少到 128 位很好。）
int loop_vc_nested(const std::array<uint8_t, H*W> &img, const std::array<Vec32uc, 8> &idx) {
int sum = 0;
Vec32uc vMax, iMax, vCurr, iCurr;
for (int i=0; i<H*W; i+=W) {
iMax.load(&idx[0]);
vMax.load(&img[i]);
for (int j=1; j<8; j++) {
iCurr.load(&idx[j]); // these get hoisted out of the outer loop and reused across img iters
vCurr.load(&img[i+j*32]);
// unsigned > isn't available until AVX-512. VCL uses !(a == max(a,b))
// GCC XORs the compare result, clang uses max and a==min(a,b)
iMax = select(vCurr > vMax, iCurr, iMax);
// scanning backwards from the end with a==max(a,b), we could still find the earliest max
vMax = max(vMax, vCurr);
}
#if 1
Vec32uc vMaxAll{horizontal_max(vMax)};
//size_t maxidx = horizontal_find_first(vMax == vMaxAll); // total disaster on clang: non-inlined BSF wrapper forces vector spill/reload of the idx vectors
size_t maxidx = _tzcnt_u32(to_bits(vMax == vMaxAll));
#else
size_t maxidx = maxpos_u8_noscan_unpack(vMax);
#endif
sum += iMax[maxidx];
}
return sum;
}
它编译为提前加载前 4 个向量的代码，进行一些处理，然后加载更多向量。ymm1 = set1(-1)，与它进行异或，对比较结果进行非运算。
# GCC13.2 -O3 -march=alderlake for the version of your source above
loop_vc_nested(std::array<unsigned char, 208896ul> const&, std::array<Vec32uc, 8ul> const&):
push rbp
mov rax, rdi
xor ecx, ecx
vpcmpeqd ymm1, ymm1, ymm1 # set1(-1)
mov rbp, rsp
and rsp, -32 # align the stack for the store that we index with movzx
vmovdqu ymm9, YMMWORD PTR [rsi+32] # idx[32..63]
vmovdqu ymm8, YMMWORD PTR [rsi] # idx[0..31]
... # and all 8 vectors of idx
lea rsi, [rdi+208896] # img.end()
.L2:
vmovdqu ymm0, YMMWORD PTR [rax+32]
vpmaxub ymm11, ymm0, YMMWORD PTR [rax]
add rax, 256
vpmaxub ymm10, ymm11, YMMWORD PTR [rax-192]
vpcmpeqb ymm0, ymm11, YMMWORD PTR [rax-256]
vpcmpeqb ymm11, ymm11, ymm10
vpxor ymm0, ymm0, ymm1
vpxor ymm11, ymm11, ymm1
vpblendvb ymm0, ymm8, ymm9, ymm0
vpblendvb ymm0, ymm0, ymm7, ymm11
vpmaxub ymm11, ymm10, YMMWORD PTR [rax-160]
vpcmpeqb ymm10, ymm10, ymm11
vpxor ymm10, ymm10, ymm1
vpblendvb ymm0, ymm0, ymm6, ymm10
vpmaxub ymm10, ymm11, YMMWORD PTR [rax-128]
vpcmpeqb ymm11, ymm11, ymm10
vpxor ymm11, ymm11, ymm1
vpblendvb ymm0, ymm0, ymm5, ymm11
vpmaxub ymm11, ymm10, YMMWORD PTR [rax-96]
vpcmpeqb ymm10, ymm10, ymm11
vpxor ymm10, ymm10, ymm1
vpblendvb ymm0, ymm0, ymm4, ymm10
vpmaxub ymm10, ymm11, YMMWORD PTR [rax-64]
vpcmpeqb ymm11, ymm11, ymm10
vpxor ymm11, ymm11, ymm1
vpblendvb ymm0, ymm0, ymm3, ymm11
vpmaxub ymm11, ymm10, YMMWORD PTR [rax-32]
vpcmpeqb ymm10, ymm10, ymm11
vpxor ymm10, ymm10, ymm1
vpblendvb ymm0, ymm0, ymm2, ymm10
## end of unrolled inner loop
vextracti128 xmm10, ymm11, 0x1 # start of horizontal_max
vpmaxub xmm12, xmm11, xmm10
vmovdqa YMMWORD PTR [rsp-32], ymm0 # store iMax
vpunpckhqdq xmm10, xmm12, xmm12
...
vpmaxub xmm10, xmm10, xmm12 # end of horizontal_max
vpbroadcastb ymm10, xmm10
vpcmpeqb ymm10, ymm10, ymm11
vpmovmskb edx, ymm10
tzcnt edx, edx # your actual original used BSF, much worse on AMD
and edx, 31 # this isn't in the source anywhere!
movzx edx, BYTE PTR [rsp-32+rdx]
add ecx, edx # sum +=
cmp rsi, rax
jne .L2 }while(ptr != endptr);
mov eax, ecx
vzeroupper
ret
正如我添加的评论中提到的，可以使用 保存围绕混合的指令（以获得相反的条件）curr == max(vmax, curr)，但当您的条件不是时，在领带上也是如此。向后循环可以解决这个问题，但对于预取器来说可能会更困难。
（至少在 asm 中，您可以按正向顺序加载所有 8 个向量，或者从每个缓存行加载一个向量，但向后处理它们。假设预取保持按顺序流式传输，这使得乱序 exec 更难隐藏加载延迟.)