Opened 4 years ago

Last modified 4 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 4 years ago 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,

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.

comment:2 Changed 4 years ago by iago

My bad, I forgot to mention that I have observed this when using large cs (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)
Last edited 4 years ago by iago (previous) (diff)
Note: See TracTickets for help on using tickets.