Почему моя программа на C медленнее, чем эквивалент Haskell?

Question

Я решил сравнить производительность стандартной строчной хвостовой рекурсивной версии программы Фибоначчи в Haskell с одной, написанной на C, с использованием GMP, чтобы позволить сравнения, где результат будет большим, чтобы соответствовать слову (в Haskell я использую многоточность Integer type). Я собираюсь опустить программу Haskell, потому что это вопрос о C и GMP. Реализация С заключается в следующем:

#include <stdio.h> 
#include <stdlib.h> 
#include <gmp.h> 

void fib(unsigned int n){ 
    mpz_t a, b, t; 

    mpz_init_set_ui(a, 0); 
    mpz_init_set_ui(b, 1); 
    mpz_init(t); 
    for(; n > 1; n --){ 
     mpz_add(t, a, b); 
     mpz_set(a, b); 
     mpz_set(b, t); 
    } 
    //mpz_out_str(stdout, 10, b); 
} 


int main(int argc, char **argv){ 
    unsigned long n, f; 
    if(argc != 2){ 
     printf("Usage: fibc <number>\n"); 
     return 1; 
    } 

    fib(atol(argv[1])); 

    return 0; 
} 

Заметьте, что я закомментирована линии, которая выводит значение, которое принимает около секунды (я оставил это поведение в версии Haskell).

Результаты:

time ./fibhs 1000000 
./fibhs 1000000 5.77s user 0.05s system 99% cpu 5.831 total 

time ./fibc 1000000 
./fibc 1000000 11.19s user 0.00s system 100% cpu 11.194 total 

Я полагаю, что я должен использовать GMP неправильно. Может ли кто-нибудь увидеть возможности повышения производительности в коде C?

Answer 1

Play ping-pong. У вас есть две переменные a и b и временная t. Вы добавляете и помещаете результат в t, затем копируете b в a и t в b. Вместо этого замените добавление b в a и добавление a к b. Конечным результатом является либо a, либо b, в зависимости от того, является ли n нечетным или четным.