我如何指示 MSVC 编译器使用 64 位/32 位除法而不是较慢的 128 位/64 位除法?

How can I instruct the MSVC compiler to use a 64bit/32bit division instead of the slower 128bit/64bit division?

我如何告诉 MSVC 编译器使用 64 位/32 位 division 操作为 x86-64 目标计算以下函数的结果:

#include <stdint.h> 

uint32_t ScaledDiv(uint32_t a, uint32_t b) 
{
  if (a > b)
        return ((uint64_t)b<<32) / a;   //Yes, this must be casted because the result of b<<32 is undefined
  else
        return uint32_t(-1);
}

我希望代码在 if 语句为真时编译为使用 64 位/32 位 division 操作,例如像这样:

; Assume arguments on entry are: Dividend in EDX, Divisor in ECX
mov edx, edx  ;A dummy instruction to indicate that the dividend is already where it is supposed to be
xor eax,eax
div ecx   ; EAX = EDX:EAX / ECX

...然而x64 MSVC编译器坚持使用128bit/64bit div指令,如:

mov     eax, edx
xor     edx, edx
shl     rax, 32                             ; Scale up the dividend
mov     ecx, ecx
div rcx   ;RAX = RDX:RAX / RCX

参见:https://www.godbolt.org/z/VBK4R71

根据的回答,128位/64位div指令并不比64位/32位div指令快 .

这是一个问题,因为它不必要地减慢了我的 DSP 算法,该算法产生了数百万个这样的缩放 divisions。

我通过修补可执行文件以使用 64 位/32 位 div 指令来测试此优化:性能提高了 28% 根据 rdtsc说明。

(编者注:大概是在最近的一些英特尔 CPU 上。AMD CPU 不需要这种微优化,如链接的问答中所述。)

当前的编译器 (gcc/clang/ICC/MSVC) 不会从可移植的 ISO C 源代码进行这种优化,即使您让它们证明 b < a 因此商将适合 32 位。 (例如 GNU C if(b>=a) __builtin_unreachable(); on Godbolt)。这是一个错过的优化;在解决这个问题之前,您必须使用内部函数或内联 asm 来解决它。

(或者改用 GPU 或 SIMD;如果您对许多元素有相同的 divisor,请参阅 https://libdivide.com/ for SIMD 计算乘法逆一次并重复应用它。)


_udiv64 is available 从 Visual Studio 2019 RTM 开始。

在 C 模式 (-TC) 中,它显然总是被定义的。根据 Microsoft 文档,在 C++ 模式下,您需要 #include <immintrin.h>。或 intrin.h.

https://godbolt.org/z/vVZ25L (Or on Godbolt.ms 因为最近 Godbolt 主站点上的 MSVC 不工作1.)

#include <stdint.h>
#include <immintrin.h>       // defines the prototype

// pre-condition: a > b else 64/32-bit division overflows
uint32_t ScaledDiv(uint32_t a, uint32_t b) 
{
    uint32_t remainder;
    uint64_t d = ((uint64_t) b) << 32;
    return _udiv64(d, a, &remainder);
}

int main() {
    uint32_t c = ScaledDiv(5, 4);
    return c;
}

_udiv64 将产生 64/32 div。左右两个shift是漏优化

;; MSVC 19.20 -O2 -TC
a$ = 8
b$ = 16
ScaledDiv PROC                                      ; COMDAT
        mov     edx, edx
        shl     rdx, 32                             ; 00000020H
        mov     rax, rdx
        shr     rdx, 32                             ; 00000020H
        div     ecx
        ret     0
ScaledDiv ENDP

main    PROC                                            ; COMDAT
        xor     eax, eax
        mov     edx, 4
        mov     ecx, 5
        div     ecx
        ret     0
main    ENDP

所以我们可以看到 MSVC 不会通过 _udiv64 执行 constant-propagation,即使在这种情况下它不会溢出并且它可以将 main 编译为 [= =21=] / ret.


更新#2 https://godbolt.org/z/n3Dyp- 添加了一个使用 Intel C++ 编译器的解决方案,但这效率较低并且会打败 constant-propagation 因为它是内联 asm.

#include <stdio.h>
#include <stdint.h>

__declspec(regcall, naked) uint32_t ScaledDiv(uint32_t a, uint32_t b) 
{
    __asm mov edx, eax
    __asm xor eax, eax
    __asm div ecx
    __asm ret
    // implicit return of EAX is supported by MSVC, and hopefully ICC
    // even when inlining + optimizing
}

int main()
{
    uint32_t a = 3 , b = 4, c = ScaledDiv(a, b);
    printf( "(%u << 32) / %u = %u\n", a, b, c);
    uint32_t d = ((uint64_t)a << 32) / b;
    printf( "(%u << 32) / %u = %u\n", a, b, d);
    return c != d;
}

脚注 1:Matt Godbolt 的主站点的 non-WINE MSVC 编译器暂时(?)消失了。 Microsoft 运行 https://www.godbolt.ms/ 以在真正的 Windows 上托管最新的 MSVC 编译器,并且通常主要 Godbolt.org 站点中继到 MSVC 的主站点。)

好像godbolt.ms会生成短链接,但不会再展开!无论如何,完整链接更好,因为它们可以抵抗 link-rot.

@Alex Lopatin 的回答显示了如何使用 _udiv64 获得 non-terrible 标量代码(尽管 MSVC 愚蠢的错过了优化转移 left/right)。

对于支持 GNU C 内联 asm(包括 ICC)的编译器,您可以使用它来代替低效的 MSVC 内联 asm 语法,后者在包装单个指令时会产生大量开销。有关包装 64 位/32 位 => 32 位 idiv 的示例,请参阅 What is the difference between 'asm', '__asm' and '__asm__'?。 (只需将助记符和类型更改为无符号即可将其用于 div。)GNU C 没有 64 / 32 或 128 / 64 除法的内在函数;它应该优化纯 C。但不幸的是,即使使用 if(a<=b) __builtin_unreachable(); 来承诺 a>b.

,GCC / Clang / ICC 也没有针对这种情况进行优化

但这仍然是标量除法,吞吐量很差。

也许您可以为您的 DSP 任务配备 GPU?如果您有足够大的批量工作(并且您的算法的其余部分是 GPU-friendly),那么与 GPU 的通信往返开销可能是值得的。

如果您使用的是 CPU,那么我们的任何建议都将从多核并行化中获益,因此请这样做以获得更高的吞吐量。


x86 SIMD (SSE4/AVX2/AVX512*) 在硬件中没有 SIMD 整数除法。英特尔 SVML 函数 _mm_div_epu64 and _mm256_div_epu64 而不是 真实指令的内在函数,它们是可能解包为标量或计算乘法逆函数的慢函数。或者他们使用的任何其他技巧;可能 32 位除法函数转换为 double 的 SIMD 向量,尤其是在 AVX512 可用的情况下。 (英特尔仍然称它们为 "intrinsics" 可能是因为它们就像 built-in 函数,它可以理解并可以完成 constant-propagation 。它们可能尽可能高效,但那是 "not very",他们需要处理一般情况,而不仅仅是你的特殊情况,即一个除数的低半部分全为零且商拟合为 32 位。)

如果许多元素具有相同的除数,请参阅 https://libdivide.com/ SIMD 计算一次乘法逆元并重复应用它。 (你应该采用这种技术来烘烤股息的转移而不实际这样做,留下 all-zero 低半隐式。)

如果你的除数总是变化的,并且这不是一些更大的 SIMD-friendly 算法的中间步骤,如果你需要精确的结果,标量除法可能是你最好的选择。


如果 24 位尾数精度足够,您可以通过使用 SIMD float 获得很大的加速

uint32_t ScaledDiv(uint32_t a, uint32_t b) 
{
    return ((1ULL<<32) * (float)b) / a;
}

(float)(1ULL<<32) 是一个 compile-time 常量 4294967296.0f.

即使没有 -ffast-math(但不是 MSVC),这也会 auto-vectorize 在数组 上使用 gcc 和 clang。 See it on Godbolt。您可以将 gcc 或 clang 的 asm 移植回 MSVC 的内在函数;他们使用一些 FP 技巧来 packed-conversion 无符号整数 to/from 浮点数而不使用 AVX512。 Non-vectorized 标量 FP 可能会比 MSVC 上的普通整数慢,而且不太准确。

例如,Skylake 的 div r32 吞吐量是每 6 个周期 1 个。但是它的 AVX vdivps ymm 吞吐量是每 5 个周期一条指令(8 floats)。或者对于 128 位 SSE2,divps xmm 每 3 个周期有一个吞吐量。 因此您从 Skylake 上的 AVX 获得大约 10 倍的除法吞吐量。 (8 * 6/5 = 9.6) 较旧的微体系结构的 SIMD FP 除法要慢得多,但整数除法也稍微慢一些。一般来说,比率较小,因为较旧的 CPU 没有那么宽的 SIMD 分频器,因此 256 位 vdivps 必须分别 运行 128 位的一半。但是仍然有很多收获,比如比 Haswell 的 4 倍更好。 Ryzen 具有 vdivps ymm 6c 的吞吐量,但 div 32 14-30 个周期的吞吐量。所以这是比 Skylake 更大的加速。

如果您的 DSP 任务的其余部分可以从 SIMD 中受益,则整体加速应该非常好。 float 操作具有更高的延迟,因此 out-of-order 执行必须更加努力地工作以隐藏独立循环迭代的延迟和重叠执行。因此,IDK 是否更好地为您转换为 float 并返回此操作,或者更改您的算法以在任何地方使用 float。这取决于您还需要用您的号码做什么。


如果您的无符号数实际上适合 有符号 32 位整数,您可以使用直接硬件支持来打包 SIMD int32 -> 浮点数转换.否则,您需要 AVX512F 来打包 uint32 -> 单条指令浮点数,但可以通过一些效率损失来模拟。这就是当 auto-vectorizing 使用 AVX2 时 gcc/clang 所做的,以及为什么 MSVC auto-vectorize.

MSVC 用 int32_t 而不是 uint32_t 做 auto-vectorize(并且 gcc/clang 可以使代码更高效),所以如果你的整数输入的最高位and/or 无法设置输出。 (即他们的 bit-patterns 的 2 的补码解释将是 non-negative。)

特别是AVX,vdivps 足够慢,几乎可以隐藏从整数转换回来的吞吐量成本,除非有其他有用的工作可以重叠。


浮点精度:

A float 将数字存储为 significand * 2^exp,其中有效数字在 [1.0, 2.0) 范围内。 (或 [0, 1.0) 次正规)。 single-precision float 具有 24 位有效数字精度,包括 1 个隐式位。

https://en.wikipedia.org/wiki/Single-precision_floating-point_format

所以一个整数的24 most-significant 位可以表示,其余的因舍入误差而丢失。 (uint64_t)b << 32 这样的整数对 float 来说没有问题;那只是意味着更大的指数。低位全为零。

例如,b = 123105810b64 << 32 提供了 528735427897589760。将其直接从 64 位整数转换为 float 得到 528735419307655168,舍入误差为 0.0000016%,或大约 2^-25.8。这不足为奇:最大舍入误差为 0.5ulp(最后一位的单位),或 2^-25,而且这个数字是偶数,所以无论如何它都有 1 个尾随零。这与我们从转换 123105810; 得到的相对误差相同。结果 float 也相同,除了它的指数字段(高 32)。

(我用 https://www.h-schmidt.net/FloatConverter/IEEE754.html 来检查这个。)

float 的最大指数足以容纳 INT64_MININT64_MAX 范围之外的整数。 float 可以表示的大整数的低位全为零,但这正是 b<<32 所具有的。因此,在 full-range 和奇数的最坏情况下,您只会丢失 b 的低 9 位。

如果结果的重要部分是 most-significant 位,并且在转换回整数后具有低 ~9 整数位 = 舍入误差是可以的,那么 float 非常适合你。

如果 float 不起作用,double 可能是一个选项。

divpd 在许多 CPU 上大约是 divps 的两倍,并且只做了一半的工作(2 double 元素而不是 4 float).因此,您以这种方式损失了 4 倍的吞吐量。

但是 每个 32 位整数都可以精确地表示为 double. 并且通过将 t运行cation 转换回零,我认为你得到所有输入对的精确整数除法,除非 double-rounding is a problem (first to nearest double, then truncation)。您可以使用

进行测试
// exactly correct for most inputs at least, maybe all.
uint32_t quotient = ((1ULL<<32) * (double)b) / a;

unsigned long long 常量 (1ULL<<32) 被转换为 double,所以你有 2x u32 -> double 转换(ab),一个 double乘法、双除法和 double -> u32 转换。 x86-64 可以通过标量转换(通过将 uint32_t 零扩展到 int64_t 或忽略双精度转换的高位 ->int64_t 来有效地完成所有这些操作,但它可能会仍然比 div r32.

转换 u32 -> double 和返回(没有 AVX512)可能比转换 u32 -> float 更昂贵,但 clang 确实 auto-vectorize 它。 (只需将上面的神栓 link 中的 float 更改为 double 即可。同样,如果您的输入都是 <= INT32_MAX,那么它们会被视为用于 FP 转换的带符号整数。

如果 double-rounding 有问题,您可以将 FP 舍入模式设置为 t运行cation 而不是默认的 round-to-nearest,如果您不使用 FP 进行任何操作else 在您的 DSP 代码为 运行ning.

的线程中