Why does Haskell's 'even' function slow my program down? [duplicate]

Question

I have following code. It costs 1s to run with argument 1000000, but it costs 5s to run if replace myEven with standard even function. I checked the code, the standard even function does exactly the same as * 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

If you add {-# NOINLINE myEven #-}, you'll get the same slowdown. The issue is that myEven is defined locally, so it's source is available to compiler, and it is inlined. All allocations and function call itself are eliminated:

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
    }

But even is defined in other module and it is not marked as INLINE or INLINEABLE. As a result it is not inlined, and each call to even allocates boxed 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
    }

Note that even is specialized for Int and Integer, but not for Word32, so the issue doesn't occurs if you use Int.