Haskell 运算斐波那契数列怎么这么慢，比 JS 慢多了。。

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 985 天前的主题，其中的信息可能已经有所发展或是发生改变。

Haskell 代码

fib :: (Integral a) => a -> a
fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

main :: IO()

main = do
  print (fib 40)

M1 Max CPU 上足足跑了 25 秒

JS 代码

function fib(n){
    switch(n) {
        case 0: return 0;
        case 1: return 1;
        default: return fib(n-1) + fib(n-2);
    }
}

console.time('fib'); fib(40); console.timeEnd('fib');

JS 里只需要 1 秒

12 条回复 • 2022-03-13 08:31:25 +08:00

Buges

2022-03-12 20:50:11 +08:00 via Android

你这个 fib 是个纯函数，结果又忽略了，估计直接被优化没了。

mofe

2022-03-12 20:57:41 +08:00

![]( https://mofe.io/2022/0312/MgeZTedJUJry-HSCmIfjm.png)

测试过了，加了 `console.log` 速度没差别

xiaopc

2022-03-12 21:06:47 +08:00 via iPhone

ghc 开优化呢

mofe

2022-03-12 21:44:11 +08:00

![]( https://mofe.io/2022/0312/zyom0llV0weKRYKiyAH0R.png)

@xiaopc 开了优化之后 3.4 秒，的确快了很多，但还是比 nodejs 慢

![]( https://mofe.io/2022/0312/5ZhTUUyerKhkk51-pV5kt.png)

mofe

2022-03-12 21:44:58 +08:00

使用 `ghc -O2 --make fib.hs`这个参数，还有什么优化方法吗？
@xiaopc

secondwtq

2022-03-12 21:48:35 +08:00

GHC 默认的 class constraint 实现是传一个类似于 vtable 的东西进去，相当于 Java 泛型（真不是黑 Java ...
并且默认所有的值都是 boxed
就是说你每加一次都是调个函数

你可以把 class constraint 去掉改成 Int 加优化，或者直接用 unboxed 不开优化也可以。离 C 差点，干掉 JS 还是问题不大的

wlh233

2022-03-12 21:49:38 +08:00

类型写成 fib :: Int -> Int 就快了

mofe

2022-03-12 21:56:47 +08:00

```haskell
fib :: Int -> Int
fib n =
if n < 2 then
n
else
fib (n - 1) + fib (n - 2)

main :: IO()
main = do
print (fib 40)
```

@wlh233
@secondwtq

真的是，代码改成这样只需要 0.46s 就运行完了。。。果然 haskell 更快些。。。

```haskell
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

main :: IO()
main = do
print (fib 40)
```
这个版本和上面慢一丢丢。。0.48s 左右

wlh233

2022-03-12 22:01:59 +08:00

我觉得是因为 haskell 里有 Int 和 Integer 两种整数类型，你那么写它用的类型应该是 Integer ，相当于用了个大数类

mofe

2022-03-12 22:47:41 +08:00

@wlh233 的确是 Integer 的锅，
```haskell
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

main :: IO()
main = do
print (fib 40)
```

这段代码跑了 3.33 秒
![]( https://mofe.io/2022/0312/FX3bYI2n2il4K7HD515rj.png)

7S5cVx

2022-03-12 22:50:05 +08:00

歪个楼，不想开 `O2` 的可以这么写

```haskell
{-# LANGUAGE MagicHash #-}

import GHC.Exts

fib' :: Int# -> Int#
fib' 0# = 0#
fib' 1# = 1#
fib' n = fib' (n -# 1#) +# fib' (n -# 2#)
{-# INLINE fib' #-}

main :: IO ()
main = print $ I# (fib' 40#)
```

换个形式写可能还会更快（ :doge:

mofe

2022-03-13 08:31:25 +08:00

@7S5cVx 这啥编程语言啊，还有魔法。。。