[GHC] #10944: powModInteger slower than computing pow and mod separately

[GHC]

#10944: powModInteger slower than computing pow and mod separately
-------------------------------------+-------------------------------------
        Reporter:  iago              |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Core Libraries    |              Version:  7.8.3
      Resolution:                    |             Keywords:  integer-gmp
Operating System:  Linux             |         Architecture:  x86_64
 Type of failure:  Runtime           |  (amd64)
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
-------------------------------------+-------------------------------------

Comment (by iago):

 My bad, I forgot to mention that I have observed this when using large
 `c`s (thus very large divisors). A simple test case would be:

 {{{#!hs
 import Criterion.Main
 import GHC.Integer.GMP.Internals ( powModInteger )

 main = defaultMain
   [ bench "test1" $ whnf (\(a,b,c) -> test1 a b c) (45,432,500000)
   , bench "powModInteger" $ whnf (\(a,b,c) -> test2 a b c) (45,432,500000)

   , bench "list test1" $ whnf (sum . map (\(a,b,c) -> test1 a b c)) xs
   , bench "list powModInteger" $ whnf (sum . map (\(a,b,c) -> test2 a b
 c)) xs
   ]

 xs :: [(Integer, Integer, Int)]
 xs = do
   a <- [45..50]
   b <- [295..300]
   c <- [299999..300000]
   return (a,b,c)

 test1, test2 :: Integer -> Integer -> Int -> Integer
 test1 a b c = (a ^ b) `mod` (2^c)
 test2 a b c = powModInteger a b (2^c)
 }}}

 On my laptop the results are:

 {{{
 benchmarking test1
 time                 9.796 ms   (9.671 ms .. 10.03 ms)
                      0.997 R²   (0.992 R² .. 1.000 R²)
 mean                 9.834 ms   (9.764 ms .. 9.977 ms)
 std dev              274.6 μs   (176.3 μs .. 443.6 μs)

 benchmarking powModInteger
 time                 118.2 ms   (117.8 ms .. 118.7 ms)
                      1.000 R²   (1.000 R² .. 1.000 R²)
 mean                 118.5 ms   (118.3 ms .. 118.7 ms)
 std dev              263.8 μs   (193.4 μs .. 350.7 μs)
 variance introduced by outliers: 11% (moderately inflated)

 benchmarking list test1
 time                 341.9 ms   (335.5 ms .. 347.6 ms)
                      1.000 R²   (NaN R² .. 1.000 R²)
 mean                 338.7 ms   (336.6 ms .. 340.1 ms)
 std dev              2.110 ms   (0.0 s .. 2.434 ms)
 variance introduced by outliers: 19% (moderately inflated)

 benchmarking list powModInteger
 time                 5.582 s    (5.559 s .. 5.622 s)
                      1.000 R²   (1.000 R² .. 1.000 R²)
 mean                 5.737 s    (5.685 s .. 5.776 s)
 std dev              60.66 ms   (0.0 s .. 68.48 ms)
 variance introduced by outliers: 19% (moderately inflated)
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/10944#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler