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

Question

这是对前一篇文章中的一些评论的跟进：

递归斐波那契汇编

以下代码片段计算Fibonacci，第一个示例使用循环，第二个示例使用计算跳转(索引分支)到展开的循环。这是在采用英特尔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（） 的一些更改仍然会影响时间。我需要找到一个相当小且可重复的测试用例。

循环版本(注意我已经读到| < code > dec | < code > 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

#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）之和为0x1bb433812a62b1 dc0，再加5个零，循环0x100000次：0x1bb43 3812a62 b1dc1000000。由于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确切地解释了为什么用一个循环add循环携带的依赖链来累加结果会产生如此大的差异。有趣的事情可以尝试：将它存储到内存中（例如，将其分配给volatile int discard），这样asm-dep链就不会只以一个被破坏的寄存器结束。HW可能会对此进行优化（例如，一旦确定结果无效，就丢弃uop）。英特尔表示，Sandybridge系列可以为shl-reg，cl中的一个标志结果uops做到这一点。

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

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

乱序执行隐藏了延迟，因为一个调用的结果不是 arg 对下一个调用的输入依赖项。IvyBridge 的无序窗口足够大，在这里很有用：168 个条目的 ROB（从发出到停用），54 个条目的调度程序（从发出到执行），以及一个 160 个条目的物理寄存器文件。另请参阅 OOO 窗口大小的 PRF 与 ROB 限制。

OOO执行还隐藏了在任何Fib工作完成之前分支预测失误的成本。最后一个fib（n）dep链的工作仍在运行中，并在预测失误期间进行。（现代Intel CPU仅回滚到预测失误的分支，并且在解决预测失误的过程中，可以从分支之前继续执行uop。）

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

我认为在大多数真实的用例中，延迟可能是相关的。也许吞吐量仍然是最重要的，但除此之外的任何事情都会使延迟变得更重要，因为这甚至根本没有使用结果。当然，在间接分支预测失误恢复时，管道中通常会有先前的工作可以处理，但这将延迟结果准备就绪，这可能意味着如果< code>fib()返回后的大多数指令都依赖于结果，则可能会延迟。但是如果不是这样(例如，大量的重新加载和计算结果的地址)，让前端在< code>fib()之后更快地开始发出微操作是一件好事。

我认为一个好的中景应该是4或8的展开，在展开循环之前检查以确保它应该运行一次。（例如sub rcx，8/jb。清理）。

另请注意，循环版本的数据依赖于 n 作为初始值。在我们之前的讨论中，我指出避免这种情况对于无序执行会更好，因为它允许添加链在 n 准备就绪之前开始工作。我认为这不是一个重要因素，因为调用方对 n 的延迟很低。但它确实将循环分支错误地预测在退出循环的末尾 -