在某些情况下，在x86-64 Intel / AMD CPU上，128bit / 64bit硬件无符号除法能否比64bit / 32bit除法更快？

Question

可以通过硬件128bit / 64bit除法指令执行缩放的64bit / 32bit除法，例如：

; Entry arguments: Dividend in EAX, Divisor in EBX
shl rax, 32  ;Scale up the Dividend by 2^32
xor rdx,rdx
and rbx, 0xFFFFFFFF  ;Clear any garbage that might have been in the upper half of RBX
div rbx  ; RAX = RDX:RAX / RBX

...在某些特殊情况下，比硬件64位/ 32位除法指令执行的缩放64位/ 32位除法更快，例如：

; Entry arguments: Dividend in EAX, Divisor in EBX
mov edx,eax  ;Scale up the Dividend by 2^32
xor eax,eax
div ebx  ; EAX = EDX:EAX / EBX

“某些特殊情况”是指异常的红利和除数。我只想比较div说明。

Answer 1

您要问的uint64_t / uint64_t是，当除数已知为32位时，将C除法优化为64b / 32b => 32b x86 asm除法。当然，编译器必须避免在#DE完全有效的（在C中）64位除法中出现异常的可能性，否则编译器将不会遵循as-if规则。因此，只有在商数可以容纳32位的情况下，它才能执行此操作。

是的，那是一场胜利，或者至少是收支平衡。在某些CPU上，甚至值得在运行时检查这种可能性，因为64位除法速度要慢得多。 但不幸的是当前的x86编译器不具有优化通寻找这个优化，即使你设法给他们足够的信息，他们可以证明它是安全的。例如，if (edx >= ebx) __builtin_unreachable();对我上次尝试没有帮助。

对于相同的输入，32位操作数大小将始终至少与之一样快

16或8位可能比32慢，因为它们可能会有错误的依赖性来写入输出，但是为了避免这种情况，写入32位寄存器零扩展到64。（这就是为什么mov ecx, ebx将ebx零扩展到64位的一种好方法，好于andharx指出的值，该值不能编码为32位符号扩展的立即数）。但是，除了部分寄存器的恶作剧外，16位和8位除法运算速度通常也与32位一样快，甚至还不差。

在AMD CPU上，除法性能不取决于操作数大小，而仅取决于数据。 0 / 1128/64位的数据应该比任何较小的操作数大小的最坏情况都要快。AMD的整数除法指令只有2微秒（大概是因为它必须写入2个寄存器），所有逻辑都在执行单元中完成。

Ryzen上的16位/ 8位=> 8位除法是单个uop（因为它只需要写AH：AL = AX）。

在Intel CPU上，div/ idiv被微编码为尽可能多的uops。对于最大32位（Skylake = 10）的所有操作数大小，大约相同的uops数量，但是64位要慢得多。（Skylake div r64是36 uops，Skylake idiv r64是57 uops）。请参阅Agner Fog的说明表：https：//agner.org/optimize/

在Skylake上，最大32位操作数大小的div / idiv吞吐量固定为每6个周期1个。但是div/idiv r64吞吐量是每24-90周期一次。

也参见试验分割代码运行快两倍作为Windows的32位比在Linux 64位用于特定性能实验，其中修改所述REX.W前缀在现有的二进制变化div r64成div r32吞吐量〜3差制成的因素。

而为什么只有锵从Sandy Bridge的起这样做的优化技巧？显示了当英特尔CPU进行调整时，当股息较小时，机会性地使用32位除法的clang。但是您有一个大红利和一个足够大的除数，这是一个更复杂的情况。那种clang优化仍然使asm的上半部分清零，从不使用非零或非符号扩展的EDX。

当将一个无符号的32位整数（左移32位）除以另一个32位整数时，我未能使流行的C编译器生成后者的代码。

我假设您将32位整数强制转换为uint64_t first，以避免UB并uint64_t / uint64_t在C抽象机中获得正常值。

那是有道理的： 您的方式将不安全，它将在#DEwhen出现错误edx >= ebx。 当商溢出AL / AX / EAX / RAX而不是默默截断时，x86除法会发生故障。无法禁用它。

因此，编译器通常仅idiv在cdq或之后cqo，以及div仅在将上半部分归零之后才使用，除非您使用内部或内联汇编程序使自己对代码出错的可能性有所了解。在C语言中，x / y只有y = 0（如果是带符号的，INT_MIN / -1也允许故障¹）发生故障。

GNU C没有内在的宽除法，但MSVC有_udiv64。（对于gcc / clang，大于1的寄存器除法使用辅助函数，该函数会尝试针对少量输入进行优化。但是，这对于64位计算机上的64/32除法没有帮助，其中GCC和clang仅使用128 / 64位除法指令。）

即使有某种方法可以向编译器保证您的除数足够大，以使商适合32位，但根据我的经验，当前的gcc和clang不会寻求这种优化。对于您的情况而言，这将是一个有用的优化（如果总是安全的话），但是编译器不会寻找它。

脚注1：更具体地说，ISO C将这些情况描述为“未定义的行为”。一些ISA（如ARM）具有无故障的划分指令。C UB表示可能发生任何事情，包括仅截断为0或其他整数结果。请参见为什么将-1除以整数（负数）会导致FPE？有关AArch64与x86代码生成和结果的示例。 允许故障并不意味着需要故障。