Wrap `gmpz_fdiv_{q,r,qr}_ui` to optimize `div`/`mod`
authorHerbert Valerio Riedel <hvr@gnu.org>
Mon, 13 Jan 2014 15:13:40 +0000 (16:13 +0100)
committerHerbert Valerio Riedel <hvr@gnu.org>
Mon, 13 Jan 2014 15:13:40 +0000 (16:13 +0100)
This is similiar to what has been done in [af2ba9c8/integer-gmp] for
`gmpz_tdiv_{q,r,qr}_ui` (re #8647); However, the gain is more modest
here, as performance-conscious code tends to use `quot`/`rem` rather
than `div`/`mod`:

     Program    Size    Allocs   Runtime   Elapsed  TotalMem
 -------------------------------------------------------------
   primetest   +0.3%     -2.4%      0.06      0.06     +0.0%
         rsa   +0.2%     -3.3%      0.02      0.02     +0.0%

Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
GHC/Integer/GMP/Prim.hs
GHC/Integer/Type.lhs
cbits/gmp-wrappers.cmm

index 3790345..4137dd5 100644 (file)
@@ -24,9 +24,13 @@ module GHC.Integer.GMP.Prim (
     remIntegerWord#,
 
     divModInteger#,
+    divModIntegerWord#,
     divInteger#,
+    divIntegerWord#,
     modInteger#,
+    modIntegerWord#,
     divExactInteger#,
+    divExactIntegerWord#,
 
     gcdInteger#,
     gcdExtInteger#,
@@ -191,16 +195,25 @@ foreign import prim "integer_cmm_remIntegerWordzh" remIntegerWord#
 --
 foreign import prim "integer_cmm_divModIntegerzh" divModInteger#
   :: Int# -> ByteArray# -> Int# -> ByteArray# -> (# MPZ#, MPZ# #)
+foreign import prim "integer_cmm_divModIntegerWordzh" divModIntegerWord#
+  :: Int# -> ByteArray# -> Word# -> (# MPZ#, MPZ# #)
 foreign import prim "integer_cmm_divIntegerzh" divInteger#
   :: Int# -> ByteArray# -> Int# -> ByteArray# -> MPZ#
+foreign import prim "integer_cmm_divIntegerWordzh" divIntegerWord#
+  :: Int# -> ByteArray# -> Word# -> MPZ#
 foreign import prim "integer_cmm_modIntegerzh" modInteger#
   :: Int# -> ByteArray# -> Int# -> ByteArray# -> MPZ#
+foreign import prim "integer_cmm_modIntegerWordzh" modIntegerWord#
+  :: Int# -> ByteArray# -> Word# -> MPZ#
 
 -- | Divisor is guaranteed to be a factor of dividend.
 --
 foreign import prim "integer_cmm_divExactIntegerzh" divExactInteger#
   :: Int# -> ByteArray# -> Int# -> ByteArray# -> MPZ#
 
+foreign import prim "integer_cmm_divExactIntegerWordzh" divExactIntegerWord#
+  :: Int# -> ByteArray# -> Word# -> MPZ#
+
 -- | Greatest common divisor.
 --
 foreign import prim "integer_cmm_gcdIntegerzh" gcdInteger#
index ab4fe9d..fe4be92 100644 (file)
@@ -43,8 +43,10 @@ import GHC.Integer.GMP.Prim (
     timesInteger#, timesIntegerInt#,
     quotRemInteger#, quotRemIntegerWord#,
     quotInteger#, quotIntegerWord#, remInteger#, remIntegerWord#,
-    divModInteger#, divInteger#, modInteger#,
-    gcdInteger#, gcdExtInteger#, gcdIntegerInt#, gcdInt#, divExactInteger#,
+    divModInteger#, divModIntegerWord#,
+    divInteger#, divIntegerWord#, modInteger#, modIntegerWord#,
+    divExactInteger#, divExactIntegerWord#,
+    gcdInteger#, gcdExtInteger#, gcdIntegerInt#, gcdInt#,
     decodeDouble#,
     int2Integer#, integer2Int#, word2Integer#, integer2Word#,
     andInteger#, orInteger#, xorInteger#, complementInteger#,
@@ -278,8 +280,13 @@ divModInteger (S# i) (S# j) = (# S# d, S# m #)
       -- evaluated strictly.
       !d = i `divInt#` j
       !m = i `modInt#` j
-
-divModInteger i1@(J# _ _) i2@(S# _) = divModInteger i1 (toBig i2)
+divModInteger (J# s1 d1) (S# b) | isTrue# (b <# 0#)
+  = case divModIntegerWord# (negateInt# s1) d1 (int2Word# (negateInt# b)) of
+          (# q, r #) -> let !q' = mpzToInteger (mpzNeg q)
+                            !r' = mpzToInteger r
+                        in (# q', r' #)
+divModInteger (J# s1 d1) (S# b)
+  = mpzToInteger2(divModIntegerWord# s1 d1 (int2Word# b))
 divModInteger i1@(S# _) i2@(J# _ _) = divModInteger (toBig i1) i2
 divModInteger (J# s1 d1) (J# s2 d2) = mpzToInteger2 (divModInteger# s1 d1 s2 d2)
 
@@ -326,9 +333,10 @@ modInteger :: Integer -> Integer -> Integer
 modInteger (S# INT_MINBOUND) b = modInteger minIntAsBig b
 modInteger (S# a) (S# b) = S# (modInt# a b)
 modInteger ia@(S# _) ib@(J# _ _) = modInteger (toBig ia) ib
+modInteger (J# sa a) (S# b) | isTrue# (b <# 0#)
+  = mpzToInteger (mpzNeg (remIntegerWord# (negateInt# sa) a (int2Word# (negateInt# b))))
 modInteger (J# sa a) (S# b)
-  = case int2Integer# b of { (# sb, b' #) ->
-    mpzToInteger (modInteger# sa a sb b') }
+  = mpzToInteger (modIntegerWord# sa a (int2Word# b))
 modInteger (J# sa a) (J# sb b)
   = mpzToInteger (modInteger# sa a sb b)
 
@@ -337,8 +345,10 @@ divInteger :: Integer -> Integer -> Integer
 divInteger (S# INT_MINBOUND) b = divInteger minIntAsBig b
 divInteger (S# a) (S# b) = S# (divInt# a b)
 divInteger ia@(S# _) ib@(J# _ _) = divInteger (toBig ia) ib
+divInteger (J# sa a) (S# b) | isTrue# (b <# 0#)
+  = mpzToInteger (divIntegerWord# (negateInt# sa) a (int2Word# (negateInt# b)))
 divInteger (J# sa a) (S# b)
-  = case int2Integer# b of { (# sb, b' #) -> mpzToInteger (divInteger# sa a sb b') }
+  = mpzToInteger (divIntegerWord# sa a (int2Word# b))
 divInteger (J# sa a) (J# sb b)
   = mpzToInteger (divInteger# sa a sb b)
 \end{code}
@@ -396,9 +406,9 @@ divExact (S# INT_MINBOUND) b = divExact minIntAsBig b
 divExact (S# a) (S# b) = S# (quotInt# a b)
 divExact (S# a) (J# sb b)
   = S# (quotInt# a (integer2Int# sb b))
-divExact (J# sa a) (S# b)
-  = case int2Integer# b of
-    (# sb, b' #) -> mpzToInteger (divExactInteger# sa a sb b')
+divExact (J# sa a) (S# b) | isTrue# (b <# 0#)
+  = mpzToInteger (divExactIntegerWord# (negateInt# sa) a (int2Word# (negateInt# b)))
+divExact (J# sa a) (S# b) = mpzToInteger (divExactIntegerWord# sa a (int2Word# b))
 divExact (J# sa a) (J# sb b) = mpzToInteger (divExactInteger# sa a sb b)
 \end{code}
 
index 28c1333..88ce0d1 100644 (file)
@@ -46,11 +46,15 @@ import "integer-gmp" __gmpz_tdiv_q_ui;
 import "integer-gmp" __gmpz_tdiv_r;
 import "integer-gmp" __gmpz_tdiv_r_ui;
 import "integer-gmp" __gmpz_fdiv_q;
+import "integer-gmp" __gmpz_fdiv_q_ui;
 import "integer-gmp" __gmpz_fdiv_r;
+import "integer-gmp" __gmpz_fdiv_r_ui;
 import "integer-gmp" __gmpz_tdiv_qr;
 import "integer-gmp" __gmpz_tdiv_qr_ui;
 import "integer-gmp" __gmpz_fdiv_qr;
+import "integer-gmp" __gmpz_fdiv_qr_ui;
 import "integer-gmp" __gmpz_divexact;
+import "integer-gmp" __gmpz_divexact_ui;
 import "integer-gmp" __gmpz_and;
 import "integer-gmp" __gmpz_xor;
 import "integer-gmp" __gmpz_ior;
@@ -602,8 +606,11 @@ GMP_TAKE1_UL1_RET1(integer_cmm_quotIntegerWordzh,   __gmpz_tdiv_q_ui)
 GMP_TAKE2_RET1(integer_cmm_remIntegerzh,            __gmpz_tdiv_r)
 GMP_TAKE1_UL1_RET1(integer_cmm_remIntegerWordzh,    __gmpz_tdiv_r_ui)
 GMP_TAKE2_RET1(integer_cmm_divIntegerzh,            __gmpz_fdiv_q)
+GMP_TAKE1_UL1_RET1(integer_cmm_divIntegerWordzh,    __gmpz_fdiv_q_ui)
 GMP_TAKE2_RET1(integer_cmm_modIntegerzh,            __gmpz_fdiv_r)
+GMP_TAKE1_UL1_RET1(integer_cmm_modIntegerWordzh,    __gmpz_fdiv_r_ui)
 GMP_TAKE2_RET1(integer_cmm_divExactIntegerzh,       __gmpz_divexact)
+GMP_TAKE1_UL1_RET1(integer_cmm_divExactIntegerWordzh, __gmpz_divexact_ui)
 GMP_TAKE2_RET1(integer_cmm_andIntegerzh,            __gmpz_and)
 GMP_TAKE2_RET1(integer_cmm_orIntegerzh,             __gmpz_ior)
 GMP_TAKE2_RET1(integer_cmm_xorIntegerzh,            __gmpz_xor)
@@ -615,6 +622,7 @@ GMP_TAKE1_RET1(integer_cmm_complementIntegerzh,     __gmpz_com)
 GMP_TAKE2_RET2(integer_cmm_quotRemIntegerzh,        __gmpz_tdiv_qr)
 GMP_TAKE1_UL1_RET2(integer_cmm_quotRemIntegerWordzh,__gmpz_tdiv_qr_ui)
 GMP_TAKE2_RET2(integer_cmm_divModIntegerzh,         __gmpz_fdiv_qr)
+GMP_TAKE1_UL1_RET2(integer_cmm_divModIntegerWordzh, __gmpz_fdiv_qr_ui)
 
 GMP_TAKE3_RET1(integer_cmm_powModIntegerzh,         __gmpz_powm)
 GMP_TAKE3_RET1(integer_cmm_powModSecIntegerzh,      __gmpz_powm_sec)