Opened 3 years ago

Last modified 3 years ago

## #10944 new bug

# powModInteger slower than computing pow and mod separately

Reported by: | iago | Owned by: | |
---|---|---|---|

Priority: | normal | Milestone: | |

Component: | Core Libraries | Version: | 7.8.3 |

Keywords: | integer-gmp | Cc: | ekmett |

Operating System: | Linux | Architecture: | x86_64 (amd64) |

Type of failure: | Runtime performance bug | Test Case: | |

Blocked By: | Blocking: | ||

Related Tickets: | Differential Rev(s): | ||

Wiki Page: |

### Description

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.

### Change History (2)

### comment:1 Changed 3 years ago by

### comment:2 Changed 3 years ago by

My bad, I forgot to mention that I have observed this when using large `c`

s (thus very large divisors). I have updated your benchmark:

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)

**Note:**See TracTickets for help on using tickets.

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,

which resulted in,

This is the sort of modest speed-up that I would have expected from

`powModInteger`

. I found similar results with 7.8.4.