爲什麼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不會出現問題。