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

This topic created in 1526 days ago, the information mentioned may be changed or developed.

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 replies 2022-03-13 08:31:25 +08:00

Buges

Mar 12, 2022 via Android

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

mofe

Mar 12, 2022

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

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

xiaopc

Mar 12, 2022 via iPhone

ghc 开优化呢

mofe

Mar 12, 2022

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

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

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

mofe

Mar 12, 2022

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

secondwtq

Mar 12, 2022

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

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

wlh233

Mar 12, 2022 2

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

mofe

Mar 12, 2022

```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

Mar 12, 2022

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

mofe

Mar 12, 2022

@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

Mar 12, 2022

歪个楼，不想开 `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

Mar 13, 2022

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