#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