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

Question

我很好奇将两个具有不同数量的值位但恒定操作数(寄存器)位的值相除时的性能差异。我预计性能取决于股息的最高设置位，因为我假设 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;
}

对于具有不同操作数位的相同数量的值位，结果是相同的，具有轻微的测量误差。但是，在我的计算机上，将一个 64 位值除以另一个 64 位值所花费的时间仅比将一个 8 位值除以另一个 8 位值多花费大约 50% 的 CPU 架构原因(Ryzen Threadripper 3990X)？即使在配备 Ryzen 7 1800X 的 Linux 计算机上，百分比关系也大致相同。

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

[编辑]:这是带有一些序列化汇编代码 (MASM) 的 MSVC++ 代码的较新版本:

#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;
}

马斯克:

; 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

现在这段代码完美地展示了除法不依赖于寄存器宽度而是操作数宽度。但我仍然在问自己，为什么 64 位除法的 64(操作数和寄存器)只比 8 位除法慢 1/3。

Answer 1

我假设您的构建类似于 GCC11.2 -O3 -std=gnu++20 https://godbolt.org/z/13YnGKPq9 ，除了加载和 div 之外不需要太多工作就可以创建一个循环。所以结果是真实的，没有隐藏在循环开销背后的更大差异(div 足够慢，可能不会成为内存瓶颈)。

---

您只测量 div 吞吐量，而不是延迟。 延迟比吞吐量的可变性更大(可能是红利？)，即使在最近的 CPU 上也是如此。

现代 CPU 通常具有接近恒定的吞吐量，即使延迟仍然可变也是如此。

• https://electronics.stackexchange.com/questions/280673/why-does-hardware-division-take-much-longer-than-multiplication/280709#280709 - 现代快速除法器从初始猜测(从查找表)开始，然后用 Newton-Raphson 对其进行改进(使用硬件乘法器作为除法单元的一部分)使事情变得更快。也许在每个阶段使用乘法器单元对其进行流水线处理以提供固定的吞吐量，并提前输出以根据数据提供更低的延迟。

• 另请参阅 The integer division algorithm of Intel's x86 processors和 How sqrt() of GCC works after compiled? Which method of root is used? Newton-Raphson? (在 Ice Lake 之前，英特尔在与 FP 相同的 div/sqrt 单元上运行整数除法)。此外，与 AMD 不同，Intel before Ice Lake used many more uops对于 64 位 div r64 比对于 32 位或更小的操作数大小。如果您在 Intel 上测试了您的基准测试，您会发现 uint64_t 即使使用较小的值也会使速度变得非常慢。

另请参阅关于 What is integer division heavily used for? 的评论中的讨论随着时间的推移，关于硬件分频器的改进，尽管它主要是关于除法的用例，以及现代 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报告 14-46 的 div r64 延迟和 14-45 的吞吐量。 uops.info confirms that , 但由于某种原因没有将不同的吞吐量放入主表中。 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他们发现 div r64 的吞吐量范围为 14c 到 46c。