performance - 为什么 Haskell 的 'even' 函数会减慢我的程序速度？

Question

这个问题已经有答案了:

GHC 7.10 generates slower code than older versions (1 个回答)

已关闭 7 年前。

我有以下代码。使用参数 1000000 运行需要 1 秒，但如果将 myEven 替换为标准 even 则运行需要 5 秒功能。我检查了代码，标准的 even 函数与 * 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
    }

请注意，甚至 is specialized对于 Int 和 Integer，但不适用于 Word32，因此如果您使用 Int，则不会出现此问题。