SSE实现Miller-Rabin素性测试（含Montgomery模乘）为何比标量版本慢？

兄弟，我太懂你这种憋屈了——明明抱着“SIMD肯定更快”的期待写完代码，结果跑起来反而比标量版慢10%，尤其是psrldq这种理论上轻量的指令居然比pmuludq还拖后腿，换谁都得挠头。结合你在Ryzen 5 3600+Visual Studio环境下的代码，咱们来拆解问题、捋优化思路。

先明确你的核心逻辑，就是实现base^d mod x的模幂运算，循环流程是：

eax = 1
esi = x
edi = bases[eax]
ebp = d
while d do
  if d & 1 then eax = (eax * edi) mod x
  edi = (edi*edi) mod x
  d >>= 1
end

为什么SIMD版本反而更慢？ #

1. 数据依赖链锁死了CPU并行能力 #

Ryzen 3000的Zen2架构对SIMD指令的调度能力很强，但你的代码里存在串行链式依赖：
比如pmuludq xmm0, xmm1 → pmuludq xmm0, xmm2 → pmuludq xmm0, xmm3，这一串乘法是严格依赖前一个结果的，每个pmuludq延迟3周期，CPU根本没法乱序执行来并行处理。反观标量版，你用了mulx这种无依赖的指令（可以同时调度到不同执行端口），CPU能并行处理多步操作，整体吞吐量反而更高。

至于你疑惑的psrldq，虽然理论延迟1周期，但它依赖前面psubd xmm1, xmm0的结果，而且在Zen2上，128位SIMD移位指令（比如psrldq）只能在Port 5执行，而pmuludq可以在Port 0/1执行，如果你的代码里psrldq和其他Port5指令挤在一起，就会产生端口瓶颈，看起来耗时就上去了。

2. SIMD的额外开销抵消了优势 #

你的SIMD代码是把标量逻辑逐行翻译成SIMD指令，但忽略了SIMD的数据重组和混合指令开销：

• 循环内的movdqa xmm4, xmm0、blendps xmm0, xmm4, 4、movddup xmm1, xmm0这些都是额外的SIMD操作，而标量版用的是mulx这种单周期吞吐量的指令，没有这些冗余开销。
• 你用blendvps、blendps来模拟标量的条件分支，但如果d & 1的分支预测命中率很高（比如Miller-Rabin里的d是固定格式的数），标量的jz @F分支预测开销其实比SIMD混合指令小——Zen2的分支预测机制非常高效，反而比SIMD的条件混合更划算。

3. 指令偏移的分析误差 #

你提到运行时分析有指令偏移1位的问题，这可能让你误以为psrldq耗时高，但实际可能是它前面的psubd延迟被算到了它头上。不过即使排除这个误差，SIMD的整体指令数和依赖链长度还是比标量版劣势明显。

SIMD代码优化方案 #

1. 真正利用SIMD的并行性：一次处理多个基 #

你的当前SIMD代码只是把单个标量操作塞进SIMD寄存器，完全没发挥SIMD“并行处理多个数据”的优势。Miller-Rabin素性测试需要测试多个基，你可以把多个基打包到SIMD寄存器里，一次处理多个base^d mod x运算，这样SIMD的开销被分摊，整体速度会远超标量版。

2. 重构Montgomery模乘的SIMD流程，打破依赖链 #

针对Montgomery模乘的步骤，重新设计SIMD逻辑：

• 把链式的pmuludq拆成无依赖的操作，比如同时计算两组乘法（比如pmuludq xmm0, xmm1和pmuludq xmm2, xmm3），让CPU能乱序执行。
• 替换psrldq为更适合32位数据的指令：你的psrldq xmm1,4是把64位结果的高32位移到低32位，改用psrld xmm1, 32（针对双字的移位）或者pextrd ecx, xmm1,1 + movd xmm1, ecx，这些指令在Zen2上的端口压力更小，执行效率更高。

3. 减少循环内的SIMD数据搬移 #

• 把循环内的movdqa xmm4, xmm0提前到循环外，或者调整寄存器分配，避免不必要的寄存器拷贝。
• 如果分支预测命中率高，把blendps替换成条件分支：比如当test ebp,1为真时跳过操作，否则直接movdqa xmm0, xmm4，这样用分支代替混合指令，能减少SIMD指令的开销。

4. 利用Zen2的256位SIMD特性 #

Zen2对256位ymm寄存器的支持很好，吞吐量比128位xmm更高。你可以尝试扩展代码到256位，用vpmludq（256位版pmuludq）来并行处理更多数据，进一步提升效率。

你的原始代码 #

标量版模幂循环 #

LOOP_MODEXP:
 push eax
 test ebp, 1
 jz @F
 mul edi
 mov ecx, edx
 imul eax, DWORD PTR [esp+16]
 mul esi
 xor ebx, ebx
 sub ecx, edx
 cmovs ebx, esi
 add ecx, ebx
 mov DWORD PTR [esp], ecx
@@:
 mov edx, edi
 mulx ecx, edx, edi
 imul edx, DWORD PTR [esp+16]
 mulx eax, ebx, esi
 xor ebx, ebx
 sub ecx, eax
 cmovs ebx, esi
 add ecx, ebx
 mov edi, ecx
 pop eax
 shr ebp, 1
 jnz LOOP_MODEXP

SIMD版模幂循环 #

movd xmm2, DWORD PTR [esp+12]
movd xmm3, esi
pshufd xmm2, xmm2, 0
pshufd xmm3, xmm3, 0
movd xmm1, edi
pshufd xmm1, xmm1, 0
movdqa xmm0, xmm1
pinsrd xmm0, eax, 2
LOOP_MODEXP:
movdqa xmm4, xmm0
pmuludq xmm0, xmm1
movdqa xmm1, xmm0
pmuludq xmm0, xmm2
pmuludq xmm0, xmm3
psubd xmm1, xmm0
psrldq xmm1, 4
pxor xmm0, xmm0
pcmpgtd xmm0, xmm1
blendvps xmm0, xmm3, xmm0
paddd xmm0, xmm1
movddup xmm1, xmm0
test ebp, 1
jnz @F
blendps xmm0, xmm4, 4
@@:
shr ebp, 1
jnz LOOP_MODEXP
pextrd eax, xmm0, 2

内容的提问来源于stack exchange，提问作者quaver