[Gmp-commit] /var/hg/gmp: mpn/generic/remove.c: Delay (possibly smaller) allo...

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/463d91873945
changeset: 15460:463d91873945
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Feb 18 22:41:17 2013 +0100
description:
mpn/generic/remove.c: Delay (possibly smaller) allocation.

diffstat:

 ChangeLog            |   1 +
 mpn/generic/remove.c |  22 ++++++++++++----------
 2 files changed, 13 insertions(+), 10 deletions(-)

diffs (79 lines):

diff -r 596470e0bc62 -r 463d91873945 ChangeLog
--- a/ChangeLog	Mon Feb 18 10:57:37 2013 +0100
+++ b/ChangeLog	Mon Feb 18 22:41:17 2013 +0100
@@ -18,6 +18,7 @@
 
 	* mpz/remove.c: Delay allocation in the generic case; use swap
 	instead of set.
+	* mpn/generic/remove.c: Delay (possibly smaller) allocation.
 
 2013-02-17  Marc Glisse  <marc.glisse at inria.fr>
 
diff -r 596470e0bc62 -r 463d91873945 mpn/generic/remove.c
--- a/mpn/generic/remove.c	Mon Feb 18 10:57:37 2013 +0100
+++ b/mpn/generic/remove.c	Mon Feb 18 22:41:17 2013 +0100
@@ -7,7 +7,7 @@
    SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
    GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
 
-Copyright 2009, 2012 Free Software Foundation, Inc.
+Copyright 2009, 2012, 2013 Free Software Foundation, Inc.
 
 This file is part of the GNU MP Library.
 
@@ -42,9 +42,10 @@
 
    FIXME: We currently allow any operand overlap.  This is quite non mpn-ish
    and might be changed, since it cost significant temporary space.
-   * If we require W to have space for un limbs, we could save qp or qp2 (but
-     we will still need to copy things into wp 50% of the time).
-   * If we allow ourselves to clobber U, we could save the other of qp and qp2.
+   * If we require W to have space for un + 1 limbs, we could save qp or qp2
+     (but we will still need to copy things into wp 50% of the time).
+   * If we allow ourselves to clobber U, we could save the other of qp and qp2,
+     and the initial COPY (but also here we would need un + 1 limbs).
 */
 
 /* FIXME: We need to wrap mpn_bdiv_qr due to the itch interface.  This need
@@ -89,7 +90,6 @@
   tp = TMP_ALLOC_LIMBS ((un + 1 + vn) / 2); /* remainder */
   qp = TMP_ALLOC_LIMBS (un + 1);	/* quotient, alternating */
   qp2 = TMP_ALLOC_LIMBS (un + 1);	/* quotient, alternating */
-  np = TMP_ALLOC_LIMBS (un + LOG);	/* powers of V */
   pp = vp;
   pn = vn;
 
@@ -119,18 +119,20 @@
       if (nn > qn)
 	break;			/* next power would be overlarge */
 
+      if (npowers == 1)		/* Alloc once, but only if it's needed */
+	np = TMP_ALLOC_LIMBS (qn + LOG);	/* powers of V */
+      else
+	np += pn;
+
       mpn_sqr (np, pp, pn);
-      nn += np[nn] != 0;
+      pn = nn + (np[nn] != 0);
       pp = np;
-      pn = nn;
-      np += nn;
     }
 
   pwr = ((mp_bitcnt_t) 1 << npowers) - 1;
 
   for (i = npowers - 1; i >= 0; i--)
     {
-      pp = pwpsp[i];
       pn = pwpsn[i];
       if (qn < pn)
 	continue;
@@ -139,7 +141,7 @@
 	continue;		/* V^i would bring us past cap */
 
       qp[qn] = 0;
-      mpn_bdiv_qr_wrap (qp2, tp, qp, qn + 1, pp, pn);
+      mpn_bdiv_qr_wrap (qp2, tp, qp, qn + 1, pwpsp[i], pn);
       if (!mpn_zero_p (tp, pn))
 	continue;		/* could not divide by V^i */