Почему использование третьей переменной быстрее, чем трюк сложения? - PullRequest
Новая
       14

Почему использование третьей переменной быстрее, чем трюк сложения?

0 голосов
/ 28 июня 2018

При вычислении чисел Фибоначчи распространенным методом является сопоставление пары чисел от (a, b) до (b, a + b) несколько раз. Обычно это можно сделать, определив третью переменную c и выполнив обмен. Однако я понял, что вы можете сделать следующее, избегая использования третьей целочисленной переменной: 

b = a + b;  // b2 = a1 + b1
a = b - a;  // a2 = b2 - a1 = b1, Ta-da!

Я ожидал, что это будет быстрее, чем использование третьей переменной, поскольку, по моему мнению, этот новый метод должен учитывать только две области памяти.

Итак, я написал следующие программы на C, сравнивающие процессы. Они имитируют вычисление чисел Фибоначчи, но будьте уверены, я знаю, что они не будут вычислять правильные значения из-за ограничений размера.

(Примечание: теперь я понимаю, что было необязательно делать n a long int, но я буду сохранять его таким, как есть, потому что именно так я его сначала скомпилировал)

Файл: PlusMinus.c 

// Using the 'b=a+b;a=b-a;' method.
#include <stdio.h>

int main() {
    long int n = 1000000; // Number of iterations.
    long int a,b;

    a = 0; b = 1;
    while (n--) {
        b = a + b;
        a = b - a;
    }

    printf("%lu\n", a);
}

Файл: ThirdVar.c 

// Using the third-variable method.
#include <stdio.h>

int main() {
    long int n = 1000000; // Number of iterations.
    long int a,b,c;

    a = 0; b = 1;
    while (n--) {
        c = a;
        a = b;
        b = b + c;
    }

    printf("%lu\n", a);
}

Когда я запускаю их с GCC (оптимизация не включена), я замечаю постоянную разницу в скорости: 

$ time ./PlusMinus
14197223477820724411

real    0m0.014s
user    0m0.009s
sys     0m0.002s

$ time ./ThirdVar
14197223477820724411

real    0m0.012s
user    0m0.008s
sys     0m0.002s

Когда я запускаю два с GCC с -O3, выходные данные сборки равны. (Я подозреваю, что у меня было смещение подтверждения, когда я утверждал, что один из них превосходил другой в предыдущих изменениях.)

Проверяя сборку для каждого, я вижу, что PlusMinus.s на самом деле имеет на одну инструкцию меньше, чем ThirdVar.s, но работает стабильно медленнее.

Вопрос

Почему возникает эта разница во времени? Не только вообще, но и почему мой метод сложения / вычитания медленнее вопреки моим ожиданиям?

1 Ответ

0 голосов
/ 28 июня 2018

Почему возникает такая разница во времени?

Нет разницы во времени при компиляции с оптимизацией (в последних версиях gcc и clang). Например, gcc 8.1 для x86_64 компилирует оба:

Live at Godbolt 

.LC0:
        .string "%lu\n"
main:
        sub     rsp, 8
        mov     eax, 1000000
        mov     esi, 1
        mov     edx, 0
        jmp     .L2
.L3:
        mov     rsi, rcx
.L2:
        lea     rcx, [rdx+rsi]
        mov     rdx, rsi
        sub     rax, 1
        jne     .L3
        mov     edi, OFFSET FLAT:.LC0
        mov     eax, 0
        call    printf
        mov     eax, 0
        add     rsp, 8
        ret

Не только вообще, но и почему мой метод сложения / вычитания медленнее, чем мои ожидания?

Сложение и вычитание могут быть медленнее, чем просто перемещение. Однако в большинстве архитектур (например, процессор x86) он в основном одинаков (1 цикл плюс задержка памяти); так что это не объясняет.

Настоящая проблема, скорее всего, заключается в зависимости между данными. См: 

b = a + b;
a = b - a;

Чтобы вычислить вторую строку, вы должны закончить вычисление значения первой. Если компилятор использует выражения такими, как они есть (как в случае -O0), это то, что увидит процессор.

В вашем втором примере, однако: 

c = a;
a = b;
b = b + c;

Вы можете вычислять как новые a, так и b одновременно, поскольку они не зависят друг от друга. И в современном процессоре эти операции могут фактически вычисляться параллельно. Или, говоря иначе, вы не «останавливаете» процессор, заставляя его ждать предыдущего результата. Это называется параллелизм на уровне инструкций .

...