[RFC][PATCH] mini-gmp: move memory allocation out of loops

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> Il Mar, 6 Febbraio 2018 7:21 pm, Ilya Yanok ha scritto:
>> I did a small patch for mini-gmp, that removes memory allocations in loop,
>> when mpz_get_str gets called. This might be undesired behaviour in the

In general, we should not try too hard to optimize in mini-gmp. Guidance
is roughly: optimize when there's a large performance gain for smallish
input sizes, and moderate extra complexity, or when the code stays as
clean after optimization.

> Modify mpn_div_qr_1_preinv to work in-place, whenever the funcion is
> called to overwrite its input anyway.

Good idea! There's one internal call with qp == np, mpn_get_str_other,
which will also benefit. And maybe some application calls via the public
division functions too.

Note we also allow qp == NULL, with the interesting corner case that qp
== tp because both are NULL. In that case, your patch avoids calling
gmp_free(NULL), which is nice.

Hmm, but except if qp == NULL, can't we *always* reuse the qp area for the
shifted input? Something like (untested):

diff -r 0e10f8f34eb4 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c	Wed Dec 27 17:12:48 2017 +0100
+++ b/mini-gmp/mini-gmp.c	Sat Feb 10 10:37:31 2018 +0100
@@ -930,9 +930,10 @@ mpn_div_qr_1_preinv (mp_ptr qp, mp_srcpt
 
   if (inv->shift > 0)
     {
-      tp = gmp_xalloc_limbs (nn);
+      /* Shift, reusing qp area if possible. In-place shift if qp == np. */
+      tp = qp ? qp : gmp_xalloc_limbs (nn);
       r = mpn_lshift (tp, np, nn, inv->shift);
-      np = tp;
+      np = tp ;
     }
   else
     r = 0;
@@ -947,7 +948,7 @@ mpn_div_qr_1_preinv (mp_ptr qp, mp_srcpt
       if (qp)
 	qp[nn] = q;
     }
-  if (inv->shift > 0)
+  if (inv->shift > 0 && (tp != qp))
     gmp_free (tp);
 
   return r >> inv->shift;

It would be even nicer if the dealloc check could be just

  if (tp)
    gmp_free (tp);

but I don't see any nice and concise way to set that up in the earlier
"if (inv->shift > 0){...}" block, without extra variables or duplicate
calls to mpn_lshift.

I also note that we have a very similar allocation in
mpn_div_qr_2_preinv.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.