[GHC] #15327: Optimize remainders by powers of two for Integer and Natural

[GHC]

#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