performance - X86 64 位模式下的索引分支开销

Question

这是对先前线程中的一些评论的跟进:

Recursive fibonacci Assembly

以下代码片段计算斐波那契，第一个示例使用循环，第二个示例使用计算跳转(索引分支)进入展开循环。这是在带有 Intel 3770K 3.5ghz 处理器的 Windows 7 Pro 64 位模式下使用 Visual Studio 2015 Desktop Express 测试的。通过单循环测试 fib(0) 到 fib(93)，我得到的循环版本的最佳时间是 ~1.901 微秒，计算跳转是 ~1.324 微秒。使用外循环重复此过程 1,048,576 次，循环版本大约需要 1.44 秒，计算跳转大约需要 1.04 秒。在两组测试中，循环版本比计算跳转版本慢约 40%。

问题:为什么循环版本比计算跳转版本对代码位置更敏感？在之前的测试中，一些代码位置组合导致循环版本时间从大约 1.44 秒增加到 1.93 秒，但我从未发现显着影响计算的跳转版本时间的组合。

部分答案:计算的跳转版本分支到 280 字节范围内的 94 个可能的目标位置，显然分支目标缓冲区(缓存)在优化这一点方面做得很好。对于循环版本，使用 align 16 将基于程序集的 fib() 函数放在 16 字节边界上解决了大多数情况下的循环版本时间问题，但对 main() 的一些更改仍然会影响时间。我需要找到一个相当小且可重复的测试用例。

循环版本(注意我读过 | dec | jnz | 比 | loop | 快):

        align   16
fib     proc                            ;rcx == n
        mov     rax,rcx                 ;br if < 2
        cmp     rax,2
        jb      fib1
        mov     rdx,1                   ;set rax, rdx
        and     rax,rdx
        sub     rdx,rax
        shr     rcx,1
fib0:   add     rdx,rax
        add     rax,rdx
        dec     rcx
        jnz     fib0
fib1:   ret     
fib     endp

计算跳转(索引分支)到展开循环版本:

        align   16
fib     proc                            ;rcx == n
        mov     r8,rcx                  ;set jmp adr
        mov     r9,offset fib0+279
        lea     r8,[r8+r8*2]
        neg     r8
        add     r8,r9
        mov     rax,rcx                 ;set rax,rdx
        mov     rdx,1
        and     rax,rdx
        sub     rdx,rax
        jmp     r8
fib0:   ; assumes add xxx,xxx takes 3 bytes
        rept    46
        add     rax,rdx
        add     rdx,rax
        endm
        add     rax,rdx
        ret
fib     endp

运行 100 万次 (1048576) 循环以计算 fib(0) 的测试代码至 fib(93)使用 37%93 的倍数，因此顺序不是连续的。在我的系统上，循环版本大约需要 1.44 秒，索引分支版本大约需要 1.04 秒。

#include <stdio.h>
#include <time.h>

typedef unsigned int uint32_t;
typedef unsigned long long uint64_t;

extern "C" uint64_t fib(uint64_t);

/* multiples of 37 mod 93 + 93 at end */
static uint64_t a[94] = 
     {0,37,74,18,55,92,36,73,17,54,
     91,35,72,16,53,90,34,71,15,52,
     89,33,70,14,51,88,32,69,13,50,
     87,31,68,12,49,86,30,67,11,48,
     85,29,66,10,47,84,28,65, 9,46,
     83,27,64, 8,45,82,26,63, 7,44,
     81,25,62, 6,43,80,24,61, 5,42,
     79,23,60, 4,41,78,22,59, 3,40,
     77,21,58, 2,39,76,20,57, 1,38,
     75,19,56,93};

/* x used to avoid compiler optimizing out result of fib() */
int main()
{
size_t i, j;
clock_t cbeg, cend;
uint64_t x = 0;
    cbeg = clock();
    for(j = 0; j < 0x100000; j++)
        for(i = 0; i < 94; i++)
            x += fib(a[i]);
    cend = clock();
    printf("%llx\n", x);
    printf("# ticks = %u\n", (uint32_t)(cend-cbeg));
    return 0;
}

x 的输出为 0x812a62b1dc000000。十六进制的 fib(0) 到 fib(93) 的总和为 0x1bb433812a62b1dc0，并添加 5 个零以循环 0x100000 次:0x1bb433812a62b1dc000000。由于 64 位数学运算，前 6 个半字节被截断。

我制作了一个全汇编版本以更好地控制代码位置。循环版本的“if 1”更改为“if 0”。循环版本大约需要 1.465 到 2.000 秒，具体取决于用于将关键位置放置在偶数或奇数 16 字节边界上的 nop 填充(请参阅下面的注释)。计算的跳跃版本大约需要 1.04 秒，并且边界在时间上的差异小于 1%。

        includelib msvcrtd
        includelib oldnames

        .data
; multiples of 37 mod 93 + 93 at the end
a       dq      0,37,74,18,55,92,36,73,17,54
        dq     91,35,72,16,53,90,34,71,15,52
        dq     89,33,70,14,51,88,32,69,13,50
        dq     87,31,68,12,49,86,30,67,11,48
        dq     85,29,66,10,47,84,28,65, 9,46
        dq     83,27,64, 8,45,82,26,63, 7,44
        dq     81,25,62, 6,43,80,24,61, 5,42
        dq     79,23,60, 4,41,78,22,59, 3,40
        dq     77,21,58, 2,39,76,20,57, 1,38
        dq     75,19,56,93
        .data?
        .code
;       parameters      rcx,rdx,r8,r9
;       not saved       rax,rcx,rdx,r8,r9,r10,r11
;       code starts on 16 byte boundary
main    proc
        push    r15
        push    r14
        push    r13
        push    r12
        push    rbp
        mov     rbp,rsp
        and     rsp,0fffffffffffffff0h
        sub     rsp,64
        mov     r15,offset a
        xor     r14,r14
        mov     r11,0100000h
;       nop padding effect on loop version (with 0 padding in padx below)
;        0 puts main2 on  odd 16 byte boundary  clk = 0131876622h => 1.465 seconds
;        9 puts main1 on  odd 16 byte boundary  clk = 01573FE951h => 1.645 seconds
        rept    0
        nop
        endm
        rdtsc
        mov     r12,rdx
        shl     r12,32
        or      r12,rax
main0:  xor     r10,r10
main1:  mov     rcx,[r10+r15]
        call    fib
main2:  add     r14,rax
        add     r10,8
        cmp     r10,8*94
        jne     main1
        dec     r11
        jnz     main0
        rdtsc
        mov     r13,rdx
        shl     r13,32
        or      r13,rax
        sub     r13,r12
        mov     rdx,r14
        xor     rax,rax
        mov     rsp,rbp
        pop     rbp
        pop     r12
        pop     r13
        pop     r14
        pop     r15
        ret
main    endp

        align   16
padx    proc
;       nop padding effect on loop version with 0 padding above
;        0 puts fib on  odd 16 byte boundary    clk = 0131876622h => 1.465 seconds
;       16 puts fib on even 16 byte boundary    clk = 01A13C8CB8h => 2.000 seconds
;       nop padding effect on computed jump version with 9 padding above
;        0 puts fib on  odd 16 byte boundary    clk = 00D979792Dh => 1.042 seconds
;       16 puts fib on even 16 byte boundary    clk = 00DA93E04Dh => 1.048 seconds
        rept    0
        nop
        endm
padx    endp

        if      1       ;0 = loop version, 1 = computed jump version

fib     proc                            ;rcx == n
        mov     r8,rcx                  ;set jmp adr
        mov     r9,offset fib0+279
        lea     r8,[r8+r8*2]
        neg     r8
        add     r8,r9
        mov     rax,rcx                 ;set rax,rdx
        mov     rdx,1
        and     rax,rdx
        sub     rdx,rax
        jmp     r8
fib0:   ; assumes add xxx,xxx takes 3 bytes
        rept    46
        add     rax,rdx
        add     rdx,rax
        endm
        add     rax,rdx
        ret
fib     endp

        else

fib     proc                            ;rcx == n
        mov     rax,rcx                 ;br if < 2
        cmp     rax,2
        jb      fib1
        mov     rdx,1                   ;set rax, rdx
        and     rax,rdx
        sub     rdx,rax
        shr     rcx,1
fib0:   add     rdx,rax
        add     rax,rdx
        dec     rcx
        jnz     fib0
fib1:   ret     
fib     endp

        endif
        end

Answer 1

这是对原始问题的回答，即当结果完全未使用时，为什么循环需要计算跳转版本的 1.4 倍时间。 IDK 正是为什么用 1 周期 add 循环携带的依赖链来累积结果会产生如此大的不同。尝试有趣的事情:将其存储到内存中(例如，将其分配给 volatile int discard )，因此 asm dep 链不会仅以损坏的寄存器结束。硬件可能会对其进行优化(例如，一旦确定结果已死，就丢弃微指令)。 Intel says Sandybridge-family can do that for one of the flag-result uops in shl reg,cl 。

旧答案: 为什么计算的跳转比循环快 1.4 倍，结果未使用

您在这里测试吞吐量，而不是延迟。在我们之前的讨论中，我主要关注延迟。那可能是一个错误；对调用者的吞吐量影响通常与延迟一样重要，这取决于调用者在执行后所做的事情对结果的数据依赖性。

乱序执行隐藏了延迟，因为一次调用的结果不是 arg 到下一次调用的输入依赖项。并且 IvyBridge 的乱序窗口足够大，可以在这里使用: 168-entry ROB (from issue to retirement), and 54-entry scheduler (from issue to execute) 和一个 160 条目的物理寄存器文件。另见 PRF vs. ROB limits for OOO window size 。

OOO 执行还隐藏了在任何 Fib 工作完成之前分支错误预测的成本。最后一个 fib(n) dep 链的工作仍在进行中，并在该错误预测期间进行处理。 (现代 Intel CPU 只回滚到错误预测的分支，并且可以在错误预测得到解决的同时继续执行分支之前的微指令。)

计算分支版本在这里很好是有道理的，因为您主要是 uop 吞吐量的瓶颈，并且循环退出分支的错误预测与进入展开版本时的间接分支错误预测的成本大致相同。 IvB 可以将 sub/jcc 宏融合到端口 5 的单个微指令中，因此 40% 的数字非常匹配。 (3 个 ALU 执行单元，因此在循环开销上花费 1/3 或 ALU 执行吞吐量说明了这一点。分支错误预测差异和 OOO 执行的限制说明了其余部分)

我认为在大多数实际用例中，延迟可能是相关的。也许吞吐量仍然是最重要的，但除此之外的任何事情都会使延迟变得更加重要，因为这甚至根本不使用结果。当然，在恢复间接分支错误预测时，流水线中可以处理以前的工作是正常的，但这会延迟结果准备就绪，这可能意味着如果 fib() 之后的大多数指令返回，则稍后会停止取决于结果。但如果不是(例如，大量重新加载和计算放置结果的地址)，让前端从 fib() 之后更快地开始发出微指令是一件好事。

我认为这里的一个很好的中间立场是展开 4 或 8，在展开循环之前进行检查以确保它应该运行一次。 (例如 sub rcx,8/jb .cleanup )。

另请注意，您的循环版本对 n 的初始值具有数据依赖性。在我们之前的讨论中，I pointed out 避免这种情况对于乱序执行会更好，因为它让 add 链在 n 准备好之前开始工作。我认为这不是一个重要因素，因为调用者对 n 的延迟很低。但它确实将循环分支错误预测置于 n -> fib(n) dep 链的末尾而不是中间退出循环。 (如果 lea 低于零而不是零，我正在描绘循环后的无分支 cmov/sub ecx, 2 进行一次迭代。)