为什么Haskell的“偶数”函数会减慢我的程序速度？

Question

我有以下代码。使用参数1000000运行需要花费1秒，但如果使用标准even函数替换myEven，则运行需要5秒的时间。我检查了代码，标准，甚至函数与* myEven *完全一样。

import Data.Word 
import Data.List 
import System.Environment 

collatzNext :: Word32 -> Word32 
collatzNext a = (if myEven a then a else 3*a+1) `div` 2 

myEven :: (Integral a) => a -> Bool 
myEven a = (a `rem` 2) == 0 

collatzLen :: Word32 -> Int 
collatzLen a0 = length $ takeWhile (/= 1) $ iterate collatzNext a0 

main = do 
    [a0] <- getArgs 
    let max_a0 = (read a0)::Word32 
    print $ maximum $ map (\a0 -> (collatzLen a0, a0)) [1..max_a0] 

Answer 1

如果您添加{-# NOINLINE myEven #-}，您将获得相同的减速。问题是myEven在本地定义，所以它的源代码可用于编译器，并且它是内联的。所有的分配和函数调用本身被淘汰：

Main.$wgo1 [InlPrag=[0], Occ=LoopBreaker] 
    :: GHC.Prim.Word# -> GHC.Prim.Int# -> GHC.Prim.Int# 
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType <S,1*U><L,U>] 
Main.$wgo1 = 
    \ (ww_s6n0 :: GHC.Prim.Word#) (ww1_s6n4 :: GHC.Prim.Int#) -> 
    case ww_s6n0 of wild_X2j { 
     __DEFAULT -> 
     case GHC.Prim.remWord# wild_X2j (__word 2) of _ [Occ=Dead] { 
      __DEFAULT -> 
      Main.$wgo1 
       (GHC.Prim.quotWord# 
       (GHC.Prim.narrow32Word# 
        (GHC.Prim.plusWord# 
         (GHC.Prim.narrow32Word# (GHC.Prim.timesWord# (__word 3) wild_X2j)) 
         (__word 1))) 
       (__word 2)) 
       (GHC.Prim.+# ww1_s6n4 1); 
      __word 0 -> 
      Main.$wgo1 
       (GHC.Prim.quotWord# wild_X2j (__word 2)) (GHC.Prim.+# ww1_s6n4 1) 
     }; 
     __word 1 -> ww1_s6n4 
    } 

但even被其他模块定义，它没有被标记为INLINE或INLINEABLE。因此，它不是内联，每次调用even分配盒装Word32：

Main.$wgo1 [InlPrag=[0], Occ=LoopBreaker] 
    :: GHC.Prim.Word# -> GHC.Prim.Int# -> GHC.Prim.Int# 
[GblId, Arity=2, Str=DmdType <S,U><L,U>] 
Main.$wgo1 = 
    \ (ww_s6mz :: GHC.Prim.Word#) (ww1_s6mD :: GHC.Prim.Int#) -> 
    case ww_s6mz of wild_X1W { 
     __DEFAULT -> 
     case even 
       @ Word32 GHC.Word.$fIntegralWord32 (GHC.Word.W32# wild_X1W) 
     of _ [Occ=Dead] { 
      False -> 
      Main.$wgo1 
       (GHC.Prim.quotWord# 
       (GHC.Prim.narrow32Word# 
        (GHC.Prim.plusWord# 
         (GHC.Prim.narrow32Word# (GHC.Prim.timesWord# (__word 3) wild_X1W)) 
         (__word 1))) 
       (__word 2)) 
       (GHC.Prim.+# ww1_s6mD 1); 
      True -> 
      Main.$wgo1 
       (GHC.Prim.quotWord# wild_X1W (__word 2)) (GHC.Prim.+# ww1_s6mD 1) 
     }; 
     __word 1 -> ww1_s6mD 
    } 

注意evenis specialized为Int和Integer，但不能用于Word32，所以如果你使用Int不会出现问题。