为简单的斐波纳契,为什么Haskell比C++更快

Question

通常Haskell标签中的问题是为什么haskell与X相比如此之慢.大多数情况下,你可以将它与使用String而不是Text或用来联系起来ByteString.非严格评估或缺乏类型签名.

但是在这里,我有一个简单的斐波那契计算器,其性能优于C++约2倍.这可能是缺乏c ++知识 - 但我从一位朋友那里得到了代码,他过去常常用这种语言编写代码.

? g++ -O3 fib2.cc -o cc-fib -lgmpxx -lgmp 
? time ./cc-fib > /dev/null
./cc-fib > /dev/null  8,23s user 0,00s system 100% cpu 8,234 total

? ghc -O3 --make -o hs-fib fib1.hs
[1 of 1] Compiling Main             ( fib1.hs, fib1.o )
Linking hs-fib ...
? time ./hs-fib > /dev/null
./hs-fib > /dev/null  4,36s user 0,03s system 99% cpu 4,403 total

在haskell文件中,我只使用了strict zipWith'和strict add'函数(这是使用扩展的地方BangPatterns- 它只是告诉编译器在执行添加之前评估参数x/ y)以及添加显式类型签名.

两个版本都使用bigint,所以这看起来与我相当,c ++代码也没有使用具有指数运行时的"标准"递归,但是应该表现得很好的备忘版本(或者至少是我认为的那样 - 请更正我,如果我错了).

使用的设置是:

• Linux 64位(Mint)在一台相当新的笔记本电脑上
• GHC-7.10.3
• g ++ 4.8.4 + libgmp-dev 2:5.1.3 + dfsg-1ubuntu1

fib.cc

#include <iostream>
#include <gmpxx.h>

mpz_class fib(int n) {
    mpz_class p1 = 0;
    mpz_class p2 = 1;
    mpz_class result;
    if ( n == 0 ) return 0;
    if ( n == 1 ) return 1;
    for(int i = 2; i <= n ; i ++ ) {
        result = p1 + p2;
        p1 = p2;
        p2 = result;
    }
    return result;
}

int main () {
    std::cout<<fib(1000000)<<std::endl;
    return 0;
}

fib.hs

{-# LANGUAGE BangPatterns -#}
module Main where

fib1 :: [Integer]
fib1 = 0:1:zipWith' (add') fib1 (tail fib1)
     where zipWith' :: (Integer -> Integer -> Integer) -> [Integer] -> [Integer] -> [Integer]
           zipWith' _ [] _ = []
           zipWith' _ _ [] = []
           zipWith' f (x:xs) (y:ys) = let z = f x y in z:zipWith' f xs ys
           add' :: Integer -> Integer -> Integer
           add' !x !y = let z = x + y in z `seq` z

fib4 :: [Integer]
fib4 = 0:1:zipWith (+) fib4 (tail fib4)

main :: IO ()
main = print $ fib1 !! 1000000

Answer 1

鉴于您打印的数量非常庞大,iostream的默认性能较差可能与它有关.确实,在我的系统上,推杆

 std::ios_base::sync_with_stdio(false);

在开始main时稍微改善了时间(从20秒到18).

而且,如此大量地复制庞大的数字必然会减慢它的速度.相反,如果你同时更新p1,并p2在每一个步骤,没有必要复制它们身边.你在循环中只需要一半的步骤.像这样:

mpz_class fib(int n) {
    mpz_class p1 = 0;
    mpz_class p2 = 1;
    for(int i = 1; i <= n/2 ; i ++ ) {
        p1 += p2;
        p2 += p1;
    }
    return (n % 2) ? p2 : p1;
}

这大大加快了我的系统速度(从18秒到8秒).

当然,要真正了解使用GMP可以做多快,您应该只使用这样做的功能:

mpz_class fib(int n) {
    mpz_class result;
    mpz_fib_ui(result.get_mpz_t(), n);
    return result;
}

这在我的机器上实际上是瞬时的(是的,它打印的是与其他两种方法相同的208,989位数字).