[GHC] #10944: powModInteger slower than computing pow and mod separately
#10944: powModInteger slower than computing pow and mod separately -------------------------------------+------------------------------------- Reporter: iago | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Core | Version: 7.8.3 Libraries | 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): | -------------------------------------+------------------------------------- {{{#!hs module Foo where import GHC.Integer.GMP.Internals ( powModInteger ) test1, test2 :: Integer -> Integer -> Int -> Integer test1 a b c = (a ^ b) `mod` (2^c) test2 a b c = powModInteger a b (2^c) }}} I was expecting `test2` to perform better than `test1`, but I'm getting quite the opposite: the use of `powModInteger` seems to be several orders of magnitude slower. I have tested this with GHC 7.10.2 and integer-gmp 1.0.0.0 too, with similar results. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10944 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#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 bgamari): I'm afraid I am unable to reproduce this. Could you provide a concrete test case which quantitatively demonstrates the difference? For the record, I my attempt was, {{{#!hs import GHC.Integer.GMP.Internals ( powModInteger ) main = defaultMain [ bench "test1" $ whnf (\(a,b,c) -> test1 a b c) (5,76,2) , bench "powModInteger" $ whnf (\(a,b,c) -> test2 a b c) (5,76,2) , bench "list test1" $ whnf (sum . map (\(a,b,c) -> test1 a b c)) xs , bench "list test2" $ whnf (sum . map (\(a,b,c) -> test2 a b c)) xs ] xs :: [(Integer, Integer, Int)] xs = do a <- [1..5] b <- [50..60] c <- [2..4] 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) }}} which resulted in, {{{ $ ghc -V The Glorious Glasgow Haskell Compilation System, version 7.10.2 $ ghc -O Hi.hs [1 of 1] Compiling Main ( Hi.hs, Hi.o ) Linking Hi ... $ ./Hi benchmarking test1 time 567.7 ns (562.9 ns .. 571.6 ns) 1.000 R² (0.999 R² .. 1.000 R²) mean 566.7 ns (562.5 ns .. 571.9 ns) std dev 15.85 ns (12.92 ns .. 19.35 ns) variance introduced by outliers: 39% (moderately inflated) benchmarking powModInteger time 440.7 ns (438.4 ns .. 443.3 ns) 1.000 R² (1.000 R² .. 1.000 R²) mean 443.6 ns (440.8 ns .. 446.9 ns) std dev 9.862 ns (8.180 ns .. 12.19 ns) variance introduced by outliers: 29% (moderately inflated) benchmarking list test1 time 97.44 μs (96.68 μs .. 98.31 μs) 0.999 R² (0.999 R² .. 0.999 R²) mean 97.59 μs (96.58 μs .. 98.57 μs) std dev 3.431 μs (2.833 μs .. 4.300 μs) variance introduced by outliers: 35% (moderately inflated) benchmarking list test2 time 76.43 μs (75.85 μs .. 76.92 μs) 0.999 R² (0.999 R² .. 1.000 R²) mean 76.55 μs (76.08 μs .. 77.11 μs) std dev 1.698 μs (1.412 μs .. 2.126 μs) variance introduced by outliers: 18% (moderately inflated) }}} This is the sort of modest speed-up that I would have expected from `powModInteger`. I found similar results with 7.8.4. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10944#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#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
participants (1)
-
GHC