128 位/64 位硬件无符号除法在某些情况下是否比 x86-64 Intel/AMD CPU 上的 64 位/32 位除法更快？
Can 128bit/64bit hardware unsigned division be faster in some cases than 64bit/32bit division on x86-64 Intel/AMD CPUs?
能否通过硬件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
...在某些特殊情况下比硬件64bit/32bit除法指令执行的缩放64bit/32bit除法更快，例如：
; 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
"some special cases" 我的意思是不寻常的股息和除数。
我只对比较 div 指令感兴趣。
Can 128bit/64bit hardware unsigned division be faster in some cases than 64bit/32bit division on x86-64 Intel/AMD CPUs?
理论上，一切皆有可能（例如，也许在 50 年后 Nvidia 会创造出 80x86 CPU ...）。
但是，我想不出一个合理的理由来解释为什么 128 位/64 位除法比 x86-64 上的 64 位/32 位除法更快（而不仅仅是等同于）。
I suspect this because I assume that the C compiler authors are very smart and so far I have failed to make the popular C compilers generate the latter code when dividing an unsigned 32-bit integer (shifted left 32 bits) by another 32-bit integer. It always compiles to the128bit/64bit div instruction. P.S. The left shift compiles fine to shl.
编译器开发人员很聪明，但编译器很复杂，而且 C 语言规则妨碍了他们。例如，如果您只执行 a = b/c;（b 是 64 位，c 是 32 位）语言的规则是 c 被提升为 64 位在除法发生之前，所以它最终成为某种中间语言的 64 位除数，这使得 back-end 翻译（从中间语言到汇编语言）很难分辨出 64 位除数可以是 32 位除数。
你问的是将 uint64_t / uint64_t C 除法优化为 64b / 32b => 32b x86 asm 除法，此时已知除数是 32 位。编译器当然必须避免在完全有效（在 C 中）64 位除法上出现 #DE 异常的可能性，否则它不会遵循 as-if 规则。所以它只能在可以证明商适合 32 位的情况下执行此操作。
是的，这是一场胜利，或者至少 break-even。在某些 CPU 上，甚至值得在运行时检查可能性，因为 64 位除法要慢得多。 但不幸的是，当前的 x86 编译器没有优化器通道来寻找这种优化，即使您设法给它们足够的信息，它们可以证明它是安全的。例如if (edx >= ebx) __builtin_unreachable(); 我上次试过没有用。
对于相同的输入，32 位 operand-size 将始终至少与
一样快
16 位或 8 位可能比 32 位慢，因为它们可能有错误的依赖写入输出，但将 32 位寄存器 zero-extends 写入 64 以避免这种情况。 （这就是为什么 mov ecx, ebx 是 zero-extend ebx 到 64 位的好方法，优于 and 一个不可编码为 32 位 sign-extended 立即数的值，例如 harold指出）。但除了partial-register恶作剧外，16位和8位除法一般也和32位一样快，或者不差。
在 AMD CPU 上，除法性能不取决于 operand-size，仅取决于数据。 128/64 位的 0 / 1 应该比任何更小的 operand-size 的 worst-case 更快。 AMD的integer-division指令只有2微秒（估计是因为要写2个寄存器），所有的逻辑都在执行单元完成。
16-bit / 8-bit => Ryzen上的8位除法是一个uop（因为它只需要写AH:AL = AX）。
在 Intel CPU 上，div/idiv 被微编码为 uops。对于所有 operand-size 的 32 位（Skylake = 10），大约相同数量的 uops，但是 64 位要慢很多很多。 （Skylake div r64 是 36 微指令，Skylake idiv r64 是 57 微指令）。查看 Agner Fog 的指令表：https://agner.org/optimize/
div/idiv operand-size 高达 32 位的吞吐量在 Skylake 上固定为每 6 个周期 1 个。但是 div/idiv r64 吞吐量是每 24-90 个周期一个。
另请参阅 div r64 更改为 div r32 在吞吐量上产生了大约 3 倍的差异。
并且 在为英特尔 CPU 进行调优时，当被除数较小时， 显示 clang 机会主义地使用 32 位除法。但是你有一个很大的红利和一个 large-enough 除数，这是一个更复杂的情况。该 clang 优化仍在将 asm 中的红利的上半部分归零，从不使用 non-zero 或非 sign-extended EDX。
I have failed to make the popular C compilers generate the latter code when dividing an unsigned 32-bit integer (shifted left 32 bits) by another 32-bit integer.
我假设你将那个 32 位整数转换为 uint64_tfirst，以避免 UB 并在 C 摘要中获得正常的 uint64_t / uint64_t机.
这是有道理的：你的方法不安全，它会在 edx >= ebx 时出现 #DE 故障。 x86 除法在商溢出时出现故障AL / AX / EAX / RAX，而不是静默截断。没有办法禁用它。
所以编译器通常只在 cdq 或 cqo 之后使用 idiv，而 div 只有在将高半部分置零之后，除非你使用内部或内联 asm 来敞开心扉面对代码错误的可能性。在 C 中，x / y 仅在 y = 0 时出错（或者对于有符号，INT_MIN / -1 也允许出错 1）。
GNU C 没有宽除法的内在函数，但 MSVC 有 _udiv64。 （对于 gcc/clang，比 1 寄存器宽的除法使用了一个辅助函数，该函数确实尝试针对小输入进行优化。但这对 64 位机器上的 64/32 除法没有帮助，其中 GCC 和 clang 仅使用128/64 位除法指令。)
即使有一些方法可以向编译器保证您的除数足够大，使商适合 32 位，但根据我的经验，当前的 gcc 和 clang 不会寻求这种优化。这对你的情况来说是一个有用的优化（如果它总是安全的），但编译器不会寻找它。
脚注 1：更具体地说，ISO C 将这些情况描述为“未定义的行为”；一些像 ARM 这样的 ISA 有 non-faulting 除法指令。 C UB 意味着 任何事情 都可能发生，包括截断为 0 或其他一些整数结果。有关 AArch64 与 x86 code-gen 和结果的示例，请参阅 。 允许犯错并不意味着需要犯错。
能否通过硬件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
...在某些特殊情况下比硬件64bit/32bit除法指令执行的缩放64bit/32bit除法更快，例如：
; 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
"some special cases" 我的意思是不寻常的股息和除数。
我只对比较 div 指令感兴趣。
Can 128bit/64bit hardware unsigned division be faster in some cases than 64bit/32bit division on x86-64 Intel/AMD CPUs?
理论上，一切皆有可能（例如，也许在 50 年后 Nvidia 会创造出 80x86 CPU ...）。
但是，我想不出一个合理的理由来解释为什么 128 位/64 位除法比 x86-64 上的 64 位/32 位除法更快（而不仅仅是等同于）。
I suspect this because I assume that the C compiler authors are very smart and so far I have failed to make the popular C compilers generate the latter code when dividing an unsigned 32-bit integer (shifted left 32 bits) by another 32-bit integer. It always compiles to the128bit/64bit div instruction. P.S. The left shift compiles fine to
shl.
编译器开发人员很聪明，但编译器很复杂，而且 C 语言规则妨碍了他们。例如，如果您只执行 a = b/c;（b 是 64 位，c 是 32 位）语言的规则是 c 被提升为 64 位在除法发生之前，所以它最终成为某种中间语言的 64 位除数，这使得 back-end 翻译（从中间语言到汇编语言）很难分辨出 64 位除数可以是 32 位除数。
你问的是将 uint64_t / uint64_t C 除法优化为 64b / 32b => 32b x86 asm 除法，此时已知除数是 32 位。编译器当然必须避免在完全有效（在 C 中）64 位除法上出现 #DE 异常的可能性，否则它不会遵循 as-if 规则。所以它只能在可以证明商适合 32 位的情况下执行此操作。
是的，这是一场胜利，或者至少 break-even。在某些 CPU 上，甚至值得在运行时检查可能性，因为 64 位除法要慢得多。 但不幸的是，当前的 x86 编译器没有优化器通道来寻找这种优化，即使您设法给它们足够的信息，它们可以证明它是安全的。例如if (edx >= ebx) __builtin_unreachable(); 我上次试过没有用。
对于相同的输入，32 位 operand-size 将始终至少与
一样快16 位或 8 位可能比 32 位慢，因为它们可能有错误的依赖写入输出，但将 32 位寄存器 zero-extends 写入 64 以避免这种情况。 （这就是为什么 mov ecx, ebx 是 zero-extend ebx 到 64 位的好方法，优于 and 一个不可编码为 32 位 sign-extended 立即数的值，例如 harold指出）。但除了partial-register恶作剧外，16位和8位除法一般也和32位一样快，或者不差。
在 AMD CPU 上，除法性能不取决于 operand-size，仅取决于数据。 128/64 位的 0 / 1 应该比任何更小的 operand-size 的 worst-case 更快。 AMD的integer-division指令只有2微秒（估计是因为要写2个寄存器），所有的逻辑都在执行单元完成。
16-bit / 8-bit => Ryzen上的8位除法是一个uop（因为它只需要写AH:AL = AX）。
在 Intel CPU 上，div/idiv 被微编码为 uops。对于所有 operand-size 的 32 位（Skylake = 10），大约相同数量的 uops，但是 64 位要慢很多很多。 （Skylake div r64 是 36 微指令，Skylake idiv r64 是 57 微指令）。查看 Agner Fog 的指令表：https://agner.org/optimize/
div/idiv operand-size 高达 32 位的吞吐量在 Skylake 上固定为每 6 个周期 1 个。但是 div/idiv r64 吞吐量是每 24-90 个周期一个。
另请参阅 div r64 更改为 div r32 在吞吐量上产生了大约 3 倍的差异。
并且
I have failed to make the popular C compilers generate the latter code when dividing an unsigned 32-bit integer (shifted left 32 bits) by another 32-bit integer.
我假设你将那个 32 位整数转换为 uint64_tfirst，以避免 UB 并在 C 摘要中获得正常的 uint64_t / uint64_t机.
这是有道理的：你的方法不安全，它会在 edx >= ebx 时出现 #DE 故障。 x86 除法在商溢出时出现故障AL / AX / EAX / RAX，而不是静默截断。没有办法禁用它。
所以编译器通常只在 cdq 或 cqo 之后使用 idiv，而 div 只有在将高半部分置零之后，除非你使用内部或内联 asm 来敞开心扉面对代码错误的可能性。在 C 中，x / y 仅在 y = 0 时出错（或者对于有符号，INT_MIN / -1 也允许出错 1）。
GNU C 没有宽除法的内在函数，但 MSVC 有 _udiv64。 （对于 gcc/clang，比 1 寄存器宽的除法使用了一个辅助函数，该函数确实尝试针对小输入进行优化。但这对 64 位机器上的 64/32 除法没有帮助，其中 GCC 和 clang 仅使用128/64 位除法指令。)
即使有一些方法可以向编译器保证您的除数足够大，使商适合 32 位，但根据我的经验，当前的 gcc 和 clang 不会寻求这种优化。这对你的情况来说是一个有用的优化（如果它总是安全的），但编译器不会寻找它。
脚注 1：更具体地说，ISO C 将这些情况描述为“未定义的行为”；一些像 ARM 这样的 ISA 有 non-faulting 除法指令。 C UB 意味着 任何事情 都可能发生，包括截断为 0 或其他一些整数结果。有关 AArch64 与 x86 code-gen 和结果的示例，请参阅