那些遇到过的问题

为什么 AMD Zen 上较大值的整数除法吞吐量差异很小？

Bon*_*ero 3 performance x86 assembly cpu-architecture integer-division

我很好奇将两个值除以不同数量的值位但操作数（寄存器）位不变时的性能差异。我预计性能取决于被除数的最高设置位，因为我假设 CPU 内部的迭代减法和移位“算法”可能在一个时钟周期内进行多次迭代。

所以我写了一个 C++20 程序来测试这个：

#include <iostream>
#include <iostream>
#include <type_traits>
#include <cstdint>
#include <random>
#include <limits>
#include <atomic>
#include <chrono>
#include <vector>
#include <sstream>

using namespace std;
using namespace chrono;

int main()
{
    constexpr size_t ROUNDS = 100'000'000;
    auto ssp = []<typename TOp, typename TValue>() -> double
        requires is_unsigned_v<TOp> && is_unsigned_v<TValue> && (sizeof(TOp) >= sizeof(TValue))
    {
        constexpr size_t N = 0x1000;
        vector<TOp> vDividends( N ), vDivisors( N );
        mt19937_64 mt;
        uniform_int_distribution<unsigned> uidBits( 0, sizeof(TValue) * CHAR_BIT - 1 );
        uniform_int_distribution<uint64_t> uidValue( 0, numeric_limits<TValue>::max() );
        auto getMaxBitsValue = [&]() -> TOp
        {
            for( TValue value; ; )
                if( (make_signed_t<TValue>)(value = (TValue)uidValue( mt )) < 0 )
                    return value;
        };
        auto getDividend = [&]() -> TOp
        {
            return getMaxBitsValue() >> uidBits( mt );
        };
        auto getDivisor = [&]( TOp dividend ) -> TOp
        {
            for( TOp divisor; ; )
                if( (divisor = getMaxBitsValue() >> uidBits( mt )) <= dividend )
                    return divisor;
        };
        for( size_t i = 0; i != N; ++i )
            vDivisors[i] = getDivisor( (vDividends[i] = getDividend()) );
        auto start = high_resolution_clock::now();
        for( size_t r = ROUNDS; r--; )
            sum += vDividends[r % N] / vDivisors[r % N];
        double ns = (int64_t)duration_cast<nanoseconds>( high_resolution_clock::now() - start ).count() / (double)ROUNDS;
        return ns;
    };
    auto results = []( double ns, double nsRef )
    {
        ostringstream oss;
        oss << ns;
        if( nsRef > 0.0 )
            oss << " (" << (int)(ns / nsRef * 100.0 + 0.5) << "%)";
        return oss.str();
    };
    double nsRef;
    cout << "8v, 8op: " << results( (nsRef = ssp.template operator ()<uint8_t, uint8_t>()), 0.0 ) << endl;
    cout << "8v, 16op: " << results( ssp.template operator ()<uint16_t, uint8_t>(), nsRef ) << endl;
    cout << "8v, 32op: " << results( ssp.template operator ()<uint32_t, uint8_t>(), nsRef ) << endl;
    cout << "8v, 64op: " << results( ssp.template operator ()<uint64_t, uint8_t>(), nsRef ) << endl;
    cout << "16v, 16op: " << results( ssp.template operator ()<uint16_t, uint16_t>(), nsRef ) << endl;
    cout << "16v, 32op: " << results( ssp.template operator ()<uint32_t, uint16_t>(), nsRef ) << endl;
    cout << "16v, 64op: " << results( ssp.template operator ()<uint64_t, uint16_t>(), nsRef ) << endl;
    cout << "32v, 32op: " << results( ssp.template operator ()<uint32_t, uint32_t>(), nsRef ) << endl;
    cout << "32v, 64op: " << results( ssp.template operator ()<uint64_t, uint32_t>(), nsRef ) << endl;
    cout << "64v, 64op: " << results( ssp.template operator ()<uint64_t, uint64_t>(), nsRef ) << endl;
}
Run Code Online (Sandbox Code Playgroud)

对于具有不同操作数位且具有轻微测量误差的相同数量的值位，结果是相同的。但是，在我的计算机上，将一个 64 位值除以另一个 64 位值只比将一个 8 位值除以另一个 8 位值多花费大约 50% 的时间（Ryzen螺纹撕裂者 3990X）？即使在我配备 Ryzen 7 1800X 的 Linux 计算机上，百分比关系也大致相同。

我将其发布在“x86”、“x86-64”和“程序集”中，而不是在 C++ 中，因为我问的不是 C++ 问题，而是机器级问题。

[编辑]：这是 MSVC++ 代码的较新版本，带有一些序列化汇编代码（MASM）：

#include <iostream>
#include <iostream>
#include <type_traits>
#include <cstdint>
#include <random>
#include <limits>
#include <atomic>
#include <chrono>
#include <vector>
#include <sstream>

using namespace std;
using namespace chrono;

uint64_t divLoop( uint64_t *dividends, uint64_t *divisors, size_t n, size_t rounds );
uint32_t divLoop( uint32_t *dividends, uint32_t *divisors, size_t n, size_t rounds );
uint16_t divLoop( uint16_t *dividends, uint16_t *divisors, size_t n, size_t rounds );
uint8_t divLoop( uint8_t *dividends, uint8_t *divisors, size_t n, size_t rounds );

int main()
{
    constexpr size_t ROUNDS = 100'000'000;
    auto ssp = []<typename TOp, typename TValue>( TOp const &, TValue const & ) -> double
        requires is_unsigned_v<TOp> && is_unsigned_v<TValue> && (sizeof(TOp) >= sizeof(TValue))
    {
        constexpr size_t N = 0x1000;
        vector<TOp> vDividends( N ), vDivisors( N );
        mt19937_64 mt;
        uniform_int_distribution<unsigned> uidBits( 0, sizeof(TValue) * CHAR_BIT - 1 );
        uniform_int_distribution<uint64_t> uidValue( 0, numeric_limits<TValue>::max() );
        auto getMaxBitsValue = [&]() -> TOp
        {
            for( TValue value; ; )
                if( (make_signed_t<TValue>)(value = (TValue)uidValue( mt )) < 0 )
                    return value;
        };
        auto getDividend = [&]() -> TOp
        {
            return getMaxBitsValue() >> uidBits( mt );
        };
        auto getDivisor = [&]( TOp dividend ) -> TOp
        {
            for( TOp divisor; ; )
                if( (divisor = getMaxBitsValue() >> uidBits( mt )) <= dividend )
                    return divisor;
        };
        for( size_t i = 0; i != N; ++i )
            vDivisors[i] = getDivisor( (vDividends[i] = getDividend()) );
        TOp sum = 0;
        atomic<TOp> aSum( 0 );
        auto start = high_resolution_clock::now();
        divLoop( &vDividends[0], &vDivisors[0], N, ROUNDS );
        double ns = (int64_t)duration_cast<nanoseconds>( high_resolution_clock::now() - start ).count() / (double)ROUNDS;
        aSum = sum;
        return ns;
    };
    auto results = []( double ns, double nsRef )
    {
        ostringstream oss;
        oss << ns;
        if( nsRef > 0.0 )
            oss << " (" << (int)(ns / nsRef * 100.0 + 0.5) << "%)";
        return oss.str();
    };
    double nsRef;
    cout << "8v, 8op: " << results( (nsRef = ssp( uint8_t(), uint8_t() )), 0.0 ) << endl;
    cout << "8v, 16op: " << results( ssp( uint16_t(), uint8_t() ), nsRef ) << endl;
    cout << "8v, 32op: " << results( ssp( uint32_t(), uint8_t() ), nsRef ) << endl;
    cout << "8v, 64op: " << results( ssp( uint64_t(), uint8_t() ), nsRef ) << endl;
    cout << "16v, 16op: " << results( ssp( uint16_t(), uint16_t() ), nsRef ) << endl;
    cout << "16v, 32op: " << results( ssp( uint32_t(), uint16_t() ), nsRef ) << endl;
    cout << "16v, 64op: " << results( ssp( uint64_t(), uint16_t() ), nsRef ) << endl;
    cout << "32v, 32op: " << results( ssp( uint32_t(), uint32_t() ), nsRef ) << endl;
    cout << "32v, 64op: " << results( ssp( uint64_t(), uint32_t() ), nsRef ) << endl;
    cout << "64v, 64op: " << results( ssp( uint64_t(), uint64_t()  ), nsRef ) << endl;
}
Run Code Online (Sandbox Code Playgroud)

玛斯姆：

; uint64_t divLoop( uint64_t *dividends, uint64_t *divisors, size_t n, size_t rounds );
PUBLIC ?divLoop@@YA_KPEA_K0_K1@Z
; uint32_t divLoop( uint32_t *dividends, uint32_t *divisors, size_t n, size_t rounds );
PUBLIC ?divLoop@@YAIPEAI0_K1@Z
; uint16_t divLoop( uint16_t *dividends, uint16_t *divisors, size_t n, size_t rounds );
PUBLIC ?divLoop@@YAGPEAG0_K1@Z
; uint8_t divLoop( uint8_t *dividends, uint8_t *divisors, size_t n, size_t rounds );
PUBLIC ?divLoop@@YAEPEAE0_K1@Z

_TEXT SEGMENT

; rcx = dividends
; rdx = divisors
; r8 = n
; r9 = rounds

?divLoop@@YA_KPEA_K0_K1@Z PROC
    push    r12
    push    r13
    mov     r10, rdx
    sub     r13, r13
outerLoop:
    mov     r11, r8
    cmp     r8, r9
    cmova   r11, r9
    sub     r11, 1
    jc      byebye
innerLoop:
    mov     rax, [rcx + r11 * 8]
    mov     r12, [r10 + r11 * 8]
    mov     rdx, r13
    div     r12
    mov     r13, rax
    and     r13, 0
    sub     r11, 1
    jnc     innerLoop
    sub     r9, r8
    ja      outerLoop
byebye:
    pop     r13
    pop     r12
    ret
?divLoop@@YA_KPEA_K0_K1@Z ENDP

?divLoop@@YAIPEAI0_K1@Z PROC
    push    r12
    push    r13
    mov     r10, rdx
    sub     r13, r13
outerLoop:
    mov     r11, r8
    cmp     r8, r9
    cmova   r11, r9
    sub     r11, 1
    jc      byebye
innerLoop:
    mov     eax, [rcx + r11 * 4]
    mov     r12d, [r10 + r11 * 4]
    mov     edx, r13d
    div     r12d
    mov     r13d, eax
    and     r13d, 0
    sub     r11, 1
    jnc     innerLoop
    sub     r9, r8
    ja      outerLoop
byebye:
    pop     r13
    pop     r12
    ret
?divLoop@@YAIPEAI0_K1@Z ENDP

?divLoop@@YAGPEAG0_K1@Z PROC
    push    r12
    push    r13
    mov     r10, rdx
    sub     r13, r13
outerLoop:
    mov     r11, r8
    cmp     r8, r9
    cmova   r11, r9
    sub     r11, 1
    jc      byebye
innerLoop:
    mov     ax, [rcx + r11 * 2]
    mov     r12w, [r10 + r11 * 2]
    mov     dx, r13w
    div     r12w
    mov     r13w, ax
    and     r13w, 0
    sub     r11, 1
    jnc     innerLoop
    sub     r9, r8
    ja      outerLoop
byebye:
    pop     r13
    pop     r12
    ret
?divLoop@@YAGPEAG0_K1@Z ENDP

?divLoop@@YAEPEAE0_K1@Z PROC
    push    r12
    push    r13
    mov     r10, rdx
    sub     r13, r13
outerLoop:
    mov     r11, r8
    cmp     r8, r9
    cmova   r11, r9
    sub     r11, 1
    jc      byebye
innerLoop:
    mov     al, [rcx + r11]
    mov     r12b, [r10 + r11]
    mov     dl, r13b
    mov     ah, dl
    div     r12b
    mov     r13b, al
    and     r13b, 0
    sub     r11, 1
    jnc     innerLoop
    sub     r9, r8
    ja      outerLoop
byebye:
    pop     r13
    pop     r12
    ret
?divLoop@@YAEPEAE0_K1@Z ENDP

_TEXT ENDS

END
Run Code Online (Sandbox Code Playgroud)

现在，这段代码完美地证明了除法不依赖于寄存器宽度，而是依赖于操作数宽度。但我仍然在问自己，为什么 64（操作数和寄存器）× 64 除法仅比 8×8 除法慢 1/3。

Pet*_*des 6

我假设您的构建类似于 GCC11.2 -O3 -std=gnu++20 https://godbolt.org/z/13YnGKPq9，除了 load 和 之外，无需做太多工作即可进行循环div。因此结果是现实的，而不是隐藏在循环开销后面的更大差异（div足够慢，可能不会成为内存瓶颈）。

您只测量div吞吐量，而不测量延迟。 即使在最近的 CPU 上，延迟也比吞吐量更容易随着某些东西的大小（可能是红利？）而变化。

即使延迟仍然存在变化，现代 CPU 通常也具有接近恒定的吞吐量。

另请参阅评论中的讨论：整数除法大量用于什么？关于随着时间的推移对硬件除法器的改进，尽管它主要是关于除法的用例以及现代 CPU 的晶体管预算如此之高以至于他们可能会将其中一些投入到除法单元中的事实。

您的结果也是根据其他人所做的指令吞吐量测量得出的。

  • https://uops.info/在 Zen+ 上使用 ax=0 / bl=1 和 ax=0x3301 / bl=123测试 8 位div reg8，发现吞吐量没有差异，始终约为 13 或 14 个周期。（只有延迟差异，从 8 到 25 个周期。或者对于div r64，从 8 到 41 个周期延迟，具体取决于值以及哪个输入到哪个输出）。仅当 dep 链中存在将输出连接回输入的其他指令时，才能观察到低于吞吐量的延迟，这对我来说仍然很奇怪。

  • Agner Fog报告延迟为div r6414-46，吞吐量为 14-45。uops.info证实了这一点，但由于某种原因没有将变化的吞吐量获取到主表中。“快速除法0 / 1”确实每 14 个周期运行一次，但慢速除法则0x343a9ed744556677:0000000000000085 / 0x75e6e44fccddeeff需要 43 个周期。（输入时 RDX=0 的最坏情况可能没那么糟糕；当前的 C++ 编译器从不使用div或idiv的上半部分不是零扩展的，除非它是扩展精度的一部分，例如unsigned __int128。）

    对于 AMD K10，他评论说 div/idiv 性能：“取决于除数绝对值的有效位数。请参阅 AMD 软件优化指南。 ”我不确定这是否仍然是现代 AMD 和 Intel CPU 中除法单元的扩展方式。

  • InstLatx64 还测试了一些不同的数据输入，以及哪个输入将输出耦合回延迟，例如，对于Zen1 Ryzen 7 1800X，他们发现 14c 到 46c 的吞吐量范围div r64。

归档时间：

查看次数：

537 次

最近记录：

3 年，10 月 前
快速硬件整数除法 9
英特尔x86处理器的整数除法算法 7
整数除法主要用于什么？ 7
GCC的sqrt()如何在编译后工作？使用哪种root方法？牛顿迭代？ 5
更多相关链接
相关归档
MATLAB的速度是Numpy的两倍 21
如何编写代码以提示JVM使用向量操作？ 18
如何在Android项目中使用ARM汇编代码？ 14
基于可用的免费cpu的Java并发 9
SSE 指令在实践中优化了什么，编译器如何启用和使用它们？ 6
如何在程序集中实现mod运算符 6
如何运行汇编代码。我有它在一个文本文件中，但我不知道如何运行它 6
shuffle 和 permute 有什么区别 5
为什么 mod 2^n 对有符号数使用 CLTD 指令 2
为什么default和empty构造函数在C++中生成不同的机器代码？ 0
难疑归档
撤消尚未推送的Git合并 3695
在CSS中设置cellpadding和cellspacing？ 3210
如何测试私有函数或具有私有方法,字段或内部类的类？ 2593
在JavaScript中创建多行字符串 2412
如何在不手动指定编码的情况下在C#中获得字符串的一致字节表示？ 2121
如何在Python中将字符串解析为float或int？ 2108
将字节转换为字符串？ 1968
Python join:为什么是string.join(list)而不是list.join(string)？ 1669
如何使用SSH在远程计算机上运行shell脚本？ 1164
如何使用$ scope.$ watch和$ scope.$在AngularJS中申请？ 1076