[Emacs-diffs] master a050cf8 4/5: Speed up % and mod with fixnum denom

[Paul Eggert]

branch: master
commit a050cf80f38e6b9b33745bc62b50dab43cac7a3a
Author: Paul Eggert <address@hidden>
Commit: Paul Eggert <address@hidden>

    Speed up % and mod with fixnum denom
    
    * src/data.c (integer_remainder): New function.  When the
    numerator is a bignum and the denominator is small, this function
    uses mpz_tdiv_ui, which should be faster than mpz_tdiv_r.
    (Frem, Fmod): Use it.
---
 src/data.c | 100 ++++++++++++++++++++++++++++++++-----------------------------
 1 file changed, 52 insertions(+), 48 deletions(-)

diff --git a/src/data.c b/src/data.c
index cb25fce..1d9222e 100644
--- a/src/data.c
+++ b/src/data.c
@@ -3055,58 +3055,67 @@ usage: (/ NUMBER &rest DIVISORS)  */)
   return arith_driver (Adiv, nargs, args, a);
 }
 
-DEFUN ("%", Frem, Srem, 2, 2, 0,
-       doc: /* Return remainder of X divided by Y.
-Both must be integers or markers.  */)
-  (register Lisp_Object x, Lisp_Object y)
-{
-  CHECK_INTEGER_COERCE_MARKER (x);
-  CHECK_INTEGER_COERCE_MARKER (y);
-
-  /* A bignum can never be 0, so don't check that case.  */
-  if (EQ (y, make_fixnum (0)))
-    xsignal0 (Qarith_error);
-
-  if (FIXNUMP (x) && FIXNUMP (y))
-    return make_fixnum (XFIXNUM (x) % XFIXNUM (y));
-  else
-    {
-      mpz_tdiv_r (mpz[0],
-                 *bignum_integer (&mpz[0], x),
-                 *bignum_integer (&mpz[1], y));
-      return make_integer_mpz ();
-    }
-}
-
-/* Return X mod Y.  Both must be integers and Y must be nonzero.  */
+/* Return NUM % DEN (or NUM mod DEN, if MODULO).  NUM and DEN must be
+   integers.  */
 static Lisp_Object
-integer_mod (Lisp_Object x, Lisp_Object y)
+integer_remainder (Lisp_Object num, Lisp_Object den, bool modulo)
 {
-  if (FIXNUMP (x) && FIXNUMP (y))
+  if (FIXNUMP (den))
     {
-      EMACS_INT i1 = XFIXNUM (x), i2 = XFIXNUM (y);
+      EMACS_INT d = XFIXNUM (den);
+      if (d == 0)
+       xsignal0 (Qarith_error);
 
-      i1 %= i2;
+      EMACS_INT r;
+      bool have_r = false;
+      if (FIXNUMP (num))
+       {
+         r = XFIXNUM (num) % d;
+         have_r = true;
+       }
+      else if (eabs (d) <= ULONG_MAX)
+       {
+         mpz_t const *n = xbignum_val (num);
+         bool neg_n = mpz_sgn (*n) < 0;
+         r = mpz_tdiv_ui (*n, eabs (d));
+         if (neg_n)
+           r = -r;
+         have_r = true;
+       }
 
-      /* If the "remainder" comes out with the wrong sign, fix it.  */
-      if (i2 < 0 ? i1 > 0 : i1 < 0)
-       i1 += i2;
+      if (have_r)
+       {
+         /* If MODULO and the remainder has the wrong sign, fix it.  */
+         if (modulo && (d < 0 ? r > 0 : r < 0))
+           r += d;
 
-      return make_fixnum (i1);
+         return make_fixnum (r);
+       }
     }
-  else
-    {
-      mpz_t const *ym = bignum_integer (&mpz[1], y);
-      bool neg_y = mpz_sgn (*ym) < 0;
-      mpz_tdiv_r (mpz[0], *bignum_integer (&mpz[0], x), *ym);
 
-      /* Fix the sign if needed.  */
-      int sgn_r = mpz_sgn (mpz[0]);
-      if (neg_y ? sgn_r > 0 : sgn_r < 0)
-       mpz_add (mpz[0], mpz[0], *ym);
+  mpz_t const *d = bignum_integer (&mpz[1], den);
+  mpz_t *r = &mpz[0];
+  mpz_tdiv_r (*r, *bignum_integer (&mpz[0], num), *d);
 
-      return make_integer_mpz ();
+  if (modulo)
+    {
+      /* If the remainder has the wrong sign, fix it.  */
+      int sgn_r = mpz_sgn (*r);
+      if (mpz_sgn (*d) < 0 ? sgn_r > 0 : sgn_r < 0)
+       mpz_add (*r, *r, *d);
     }
+
+  return make_integer_mpz ();
+}
+
+DEFUN ("%", Frem, Srem, 2, 2, 0,
+       doc: /* Return remainder of X divided by Y.
+Both must be integers or markers.  */)
+  (register Lisp_Object x, Lisp_Object y)
+{
+  CHECK_INTEGER_COERCE_MARKER (x);
+  CHECK_INTEGER_COERCE_MARKER (y);
+  return integer_remainder (x, y, false);
 }
 
 DEFUN ("mod", Fmod, Smod, 2, 2, 0,
@@ -3119,12 +3128,7 @@ Both X and Y must be numbers or markers.  */)
   CHECK_NUMBER_COERCE_MARKER (y);
   if (FLOATP (x) || FLOATP (y))
     return fmod_float (x, y);
-
-  /* A bignum can never be 0, so don't check that case.  */
-  if (EQ (y, make_fixnum (0)))
-    xsignal0 (Qarith_error);
-
-  return integer_mod (x, y);
+  return integer_remainder (x, y, true);
 }
 
 static Lisp_Object