如何在haskell中像c++一样快地编写sum函数？

Question

以下 2 个版本

mysum

Haskell 中的函数比 C++ 版本（带有

ghc -O

）慢 10 倍。如何进一步优化

mysum

功能？

module Main where

main :: IO ()
main = print $ mysum [1..100000000] 0

mysum ::Num a =>[a]->a->a
mysum (x:xs) !s = mysum xs (x + s)
mysum [] !s = s

module Main where

main :: IO ()
main = print $ mysum 0 100000000 0

mysum ::(Num a,Eq a) =>a->a->a->a
mysum !from !to !now | from == to = now + from
                     | otherwise = mysum (from+1) to (now+from)

#include <iostream>

int main(){
    unsigned long long a = 0;
    for(unsigned long long i =0;i<=100000000;++i){
        a+=i;
    }
    printf("%llu", a);
}

Answer 1

原始 Haskell 代码：

{-# LANGUAGE BangPatterns, NumericUnderscores #-}
module Main where

main :: IO ()
main = print $ mysum [1 .. 100_000_000] 0

mysum :: Num a => [a] -> a -> a
mysum (x:xs) !s = mysum xs (x + s)
mysum [] !s = s

用

ghc -O2

编译，我们得到：

$ time ./Sum1
5000000050000000

real    0m1,913s
user    0m1,904s
sys 0m0,008s

新代码，对您的尝试进行了微小的更改：

{-# LANGUAGE BangPatterns, NumericUnderscores #-}
module Main where

main :: IO ()
main = print $ mysum 1 100_000_000 (0 :: Int)

{-# SPECIALIZE mysum :: Int -> Int -> Int -> Int #-}
mysum ::(Num a,Eq a) =>a->a->a->a
mysum !from !to !now | from == to = now + from
                     | otherwise = mysum (from+1) to (now+from)

用

ghc -O2

编译，我们得到：

$ time ./Sum2 
5000000050000000

real    0m0,122s
user    0m0,118s
sys 0m0,004s

这是15.6 倍的加速。 C++ 仍然更快，因为它消除了循环。如果我在循环中添加

if (a == ...) printf(...);

来强制循环运行，C++ 会产生

real 0m0,108s

，这与 Haskell 相当（但是，IMO，现在的比较是不公平的，因为 C++ 有一个额外的

if

）。

无论如何，为了让 Haskell 更快，我做了以下操作：

• 对于数值，使用

  Int

  ，而不是默认的

  Integer

  。
• 将

  mysum

  函数特化为

  Int

  ，告诉 GHC 为该特殊情况生成超出标准多态代码的优化代码。多态性使得

  mysum

  变慢。

最后，请始终记住使用

ghc -O2

打开优化（并避免 GHCi）。