Три версии одной и той же программы на С, почему первая такая быстрая? - PullRequest
Новая
       35

Три версии одной и той же программы на С, почему первая такая быстрая?

1 голос
/ 22 сентября 2019

Вот очень простая программа на C: 

int main()
{
    int n = 0;

    while(n != 1000000000){
        n += 1;
    }

return n;

}

Я скомпилировал ее с помощью Clang и рассчитал время.Он работал за 4.711095243692398e-06 секунды или 0.000004711095243692398 секунды.

Далее я вывожу программу C на язык синтаксической ассемблера Intel, используя проводник компилятора Godbolt (https://godbolt.org) для удаления директив .cfi: 

.file   "Svx.c"
.intel_syntax noprefix
.text
.globl  main
.type   main, @function
main:
    push    rbp
    mov rbp, rsp
    mov DWORD PTR -4[rbp], 0
    jmp .L2
.L3:
    add DWORD PTR -4[rbp], 1
.L2:
    cmp DWORD PTR -4[rbp], 1000000000
    jne .L3
    mov eax, DWORD PTR -4[rbp]
    pop rbp
    ret
    .size   main, .-main
    .ident  "GCC: (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0"
    .section    .note.GNU-stack,"",@progbits

Я скомпилировал ее с помощьюGCC и рассчитал время. Результат составил 1.96 секунд - намного медленнее, чем версия Clang.

Наконец, я создал свою собственную версию сборки: 

[BITS 64]
[default rel]

global main:function

section .data align=16

section .text

main:
xor rax,rax
l_01:
cmp rax,1000000000
je l_02
add rax,5
jmp l_01
l_02:
ret

Я скомпилировал ее с помощью nasm и связал его с ld: 

sudo nasm -felf64 Svx.asm

sudo ld -shared Svx.o -o Svx.so

и рассчитал по времени. Он работал за 0.14707629615440965 секунд.

Почему версия C работает так быстро, если обратная компиляцияверсия работает значительно медленнее (0.0000047 секунд против 1.96 секунд), а моя версия NASM работает за 0.147 секунд? У меня такое ощущение, что результат версии C на 0.0000047 секундах неверный, он кажется невероятно быстрым.Это вывод Clang на язык ассемблера: 

    .text
    .intel_syntax noprefix
    .file   "Svx.c"
    .globl  main                     # -- Begin function main
    .p2align    4, 0x90
    .type   main,@function
main:                                    # @main
    .cfi_startproc
# %bb.0:
    push    rbp
    .cfi_def_cfa_offset 16
    .cfi_offset rbp, -16
    mov rbp, rsp
    .cfi_def_cfa_register rbp
    mov dword ptr [rbp - 4], 0
.LBB0_1:                                # =>This Inner Loop Header:     Depth=1
    cmp dword ptr [rbp - 4], 1000000000
    je  .LBB0_3
# %bb.2:                                #   in Loop: Header=BB0_1   Depth=1
    mov eax, dword ptr [rbp - 4]
    add eax, 1
    mov dword ptr [rbp - 4], eax
    jmp .LBB0_1
.LBB0_3:
    mov eax, dword ptr [rbp - 4]
    pop rbp
    .cfi_def_cfa rsp, 8
    ret
.Lfunc_end0:
    .size   main, .Lfunc_end0-main
    .cfi_endproc
                                        # -- End function
    .ident  "clang version 8.0.0-3~ubuntu18.04.1 (tags/RELEASE_800/final)"
    .section    ".note.GNU-stack","",@progbits
    .addrsig

В листинге показано, что они используют стек для переменных, а не регистр, который (обычно) медленнее.

Скорость при0.0000047 секунд, кажется невозможным быстро считатьо миллиард.Если эта скорость верна, в чем ее секрет?Обратный инжиниринг ничего не показывает, и на самом деле версия Godbolt намного медленнее.

Ответы [ 2 ]

2 голосов
/ 22 сентября 2019

У вас есть 3 случая:

  • C с включенной оптимизацией: замените цикл на результат: mov eax, 1000000000 / ret.Время, которое вы измерили, - все накладные.Компилятор может легко доказать, что n должно иметь это значение для завершения цикла, и что цикл не бесконечен.
  • C с оптимизацией отключен : хранить переменные C в памяти,включая счетчик цикла.Узкие места в цикле при задержке пересылки хранилища составляют около 6 циклов на итерацию на современных процессорах x86.(https://agner.org/optimize/)

  • Рукописный asm, который зацикливается (неэффективно), но, по крайней мере, сохраняет значения в регистрах. Таким образом, цепочка зависимостей, переносимая циклами (с приращением n), имеет только задержку в 1 цикл.

    И так как вы используете add rax,5, вы выполняете только 1/5 итераций цикла n++. Вы можете думать об этом как о развертывании на 5 с последующей оптимизацией 5x n++ в n+=5. Вы можете сделать этот коэффициент настолько большим, насколько захотите, и сделать время выполнения произвольно небольшим, пока не доберетесь до mov eax, 1000000000, как это сделал компилятор.

См. первые 2 на Godbolt , где я использовал clang -O3 и gcc -O0. Обратите внимание, что int n является 32-битной переменной в стандартных ABI x86-64, поэтому нет необходимости тратить дополнительный размер кода (префиксы REX) для 64размер бита-операнда.

См. Почему циклы всегда компилируются в стиль "do ... while" (прыжок в хвост)? , почему эффективные простые циклы имеют условную ветвь внизуи no безусловная ветвь. Обратите внимание, что это то, что gcc does даже в -O0 (вход в цикл с jmp к условию цикла внизу).

Clang делает еще более наивный код в -O0, который имеет ту же структуру, что и C сусловие прерывания вверху и безусловное jmp внизу, как у вашего написанного от руки асма.

Таким образом, ваш асм должен быть примерно в 6 * 5 раз быстрее, чем антиоптимизированныйВывод компилятора C, или половина этого , если ему не удается запустить цикл NASM с 1 тактом на одну итерацию.На практике вы измерили коэффициент 13,333, который довольно близок к 15.

Таким образом, у вас, вероятно, есть Intel до Haswell или AMD до Ryzen .Более поздние процессоры имеют пропускную способность 2 ветви в такт, если хотя бы один из них не занят.

Или Skylake (цикл-буфер отключен обновлением микрокода) и некоторый интерфейсный эффект (например, наличиецикл, разделенный по 64-байтной границе), остановил его выдачу со скоростью 1 итер / такт, поскольку он не мог прочитать из кэша UOP достаточно быстро.

2 голосов
/ 22 сентября 2019

Clang просто понимает, что этот цикл запускается 1000000000 раз и делает эквивалент return 1000000000;.

Мой вывод с -O3, как вы указали, что используете: 

        .text
        .file   "test.c"
        .globl  main                    # -- Begin function main
        .p2align        4, 0x90
        .type   main,@function
main:                                   # @main
        .cfi_startproc
# %bb.0:
        movl    $1000000000, %eax       # imm = 0x3B9ACA00
        retq
.Lfunc_end0:
        .size   main, .Lfunc_end0-main
        .cfi_endproc
                                        # -- End function

        .ident  "clang version 8.0.0 (tags/RELEASE_800/final)"
        .section        ".note.GNU-stack","",@progbits
        .addrsig

Обратите внимание на содержимое main: 

# %bb.0:
        movl    $1000000000, %eax       # imm = 0x3B9ACA00
        retq

Это полностью удаляет цикл и просто возвращает 1000000000.

Хитрость, чтобы обойти это, заключается в использовании volatile: 

int main(void)
{
    volatile int n = 0;

    while(n != 1000000000) {
        n += 1;
    }

    return n;
}

Выход (снова с -O3): 

        .text
        .file   "test.c"
        .globl  main                    # -- Begin function main
        .p2align        4, 0x90
        .type   main,@function
main:                                   # @main
        .cfi_startproc
# %bb.0:
        movl    $0, -4(%rsp)
        movl    -4(%rsp), %ecx
        movl    -4(%rsp), %eax
        cmpl    $1000000000, %ecx       # imm = 0x3B9ACA00
        je      .LBB0_3
        .p2align        4, 0x90
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        addl    $1, %eax
        movl    %eax, -4(%rsp)
        movl    -4(%rsp), %ecx
        movl    -4(%rsp), %eax
        cmpl    $1000000000, %ecx       # imm = 0x3B9ACA00
        jne     .LBB0_1
.LBB0_3:
        retq
.Lfunc_end0:
        .size   main, .Lfunc_end0-main
        .cfi_endproc
                                        # -- End function

        .ident  "clang version 8.0.0 (tags/RELEASE_800/final)"
        .section        ".note.GNU-stack","",@progbits
        .addrsig
...