c++ - 为什么 Haskell 对于简单的斐波那契比 C++ 更快

Question

Haskell 标签中的通常问题是为什么 haskell 与 X 相比如此慢。大多数情况下，您可以将其与 String 而不是 Text 或 的用法联系起来字节串。评估不严格或缺少类型签名。

但是我有一个简单的斐波那契计算器，它的性能比 C++ 高出大约 2 倍。这可能是因为缺乏 C++ 知识——但我从一个 friend 那里得到了代码，他过去常常在这种语言。

★ 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 文件中，我只使用了一个严格的 zipWith' 和一个严格的 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

考虑到您正在打印的数量非常庞大，iostreams 的默认性能不佳可能与此有关。事实上，在我的系统上，把

 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 位数字)。