родолжение некоторых комментариев, сделанных в этой предыдущей теме:

Рекурсивная сборка Фибоначчи

Следующие фрагменты кода вычисляют Фибоначчи, первый пример с циклом, второй пример с вычисленным переходом (индексированная ветвь) в развернутый цикл. Это было протестировано с использованием Visual Studio 2015 Desktop Express в 64-битном режиме Windows 7 Pro с процессором Intel 3770K 3,5 ГГц. С тестом с одной петлей от fib (0) до fib (93) наилучшее время, которое я получаю для версии цикла, составляет ~ 1,901 микросекунды, а для вычисленного скачка - ~ 1,324 микросекунды. Используя внешний цикл, чтобы повторить этот процесс 1 048 576 раз, версия цикла занимает около 1,44 секунды, вычисленный переход занимает около 1,04 секунды. В обоих наборах тестов версия цикла примерно на 40% медленнее, чем версия с вычисленным переходом.

Вопрос: Почему версия цикла гораздо более чувствительна к расположению кода, чем версия вычисленного перехода? В предыдущих тестах некоторые комбинации местоположений кода вызывали увеличение времени версии цикла с примерно 1,44 до 1,93 секунды, но я никогда не находил комбинацию, которая бы существенно повлияла на вычисленное время перехода.

Частичный ответ: вычисленная версия перехода переходит в 94 возможных целевых местоположения в пределах диапазона 280 байт, и, очевидно, целевой буфер ветвления (кэш) хорошо справляется с оптимизацией этого. Для версии цикла использование выравнивания 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

Тестовый код, который выполняет 1 миллион (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) в hex равна 0x1bb433812a62b1dc0, и добавьте еще 5 нулей для цикла 0x100000 раз: 0x1bb433812a62b1dc000000. Верхние 6 полубайнов усечены из-за 64-битной математики.

Я сделал полностью сборочную версию, чтобы лучше контролировать местоположение кода. «If 1» изменяется на «if 0» для версии цикла. Версия цикла занимает от 1,465 до 2000 секунд в зависимости от заполнения nop, используемого для размещения ключевых позиций на четных или нечетных 16-байтовых границах (см. Комментарии ниже). Вычисленная версия скачка занимает около 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