#15327: Optimize remainders by powers of two for Integer and Natural -------------------------------------+------------------------------------- Reporter: Bodigrim | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: 8.6.1 Component: Core | Version: 8.4.3 Libraries | Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: #14437 Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- It appears that GHC does not optimise `even (n :: Integer)` to a bitwise check, as it does for `Int` and `Word` (#14437). Here is a benchmark: {{{#!hs import Data.Time.Clock evenRem :: Integer -> Bool evenRem n = fromIntegral n `rem` 2 == (0 :: Word) lim :: Integer lim = 100000000 main :: IO () main = do t0 <- getCurrentTime print $ maximum $ filter even [1..lim] t1 <- getCurrentTime putStrLn "even" print $ diffUTCTime t1 t0 t0 <- getCurrentTime print $ maximum $ filter evenRem [1..lim] t1 <- getCurrentTime putStrLn "evenRem" print $ diffUTCTime t1 t0 }}} {{{ $ ghc -O2 Even.hs [1 of 1] Compiling Main ( Even.hs, Even.o ) Linking Even ... $ ./Even 100000000 even 6.367393s 100000000 evenRem 4.35664s }}} The reason is that `even (n :: Integer)` results in `remInteger` call in CMM, which remains unoptimized. One possible solution is to add a special case of divisor 2 to `GHC.Integer.Type.remInteger`. Or perhaps even something like {{{#!hs remInteger n (S# d#) | isPowerOfTwo (I# d#) = fromIntegral (fromIntegral n `rem` I# d#) isPowerOfTwo :: Int -> Bool isPowerOfTwo d = d /= 0 && d .&. (complement d + 1) == d }}} Since `remInteger` is not inlined during Core pipeline, such implementation of `even` will pattern-match in runtime, which is a bit suboptimal. On my machine it benchmarks halfway between `even` and `evenRem` above. Alternative approach is to add new rules to `PrelRules.builtinIntegerRules` to avoid any possible runtime slowdown. Is is appropriate? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15327 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler