为什么Haskell的"偶数"功能会减慢我的程序速度？

Question

我有以下代码.使用参数1000000运行需要花费1秒,但如果使用标准偶函数替换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
    }

请注意,even 是专门为Int和Integer,但不适合Word32,所以如果你使用不出现问题Int.