Haskellの 'even'関数がプログラムを遅くするのはなぜですか？

Question

次のコードがあります。引数1000000で実行するには1を要しますが、myEvenを標準evenと置き換えた場合、実行には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箱入り：あなたはIntを使用している場合IntとIntegerのためではなくWord32ためevenis specializedので、問題が発生しないことを

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 
    } 

注意を。