Re: Lazy mpz allocation

[Vincent Lefevre]

On 2018-04-20 18:29:55 +0200, Trevor Spiteri wrote:
> >>> Only 0 can have lazy allocation, and I think we document that it isn't
> >>> legal to put 0 on the denominator.
> >> where is this documented?
> > That was in a "I think" sentence. Now that I looked a bit more, I don't 
> > find it... Well, you can't call any mpq function that reads that mpq_t, 
> > but we don't say you can't write to that mpq_t.
> 
> The documentation states that "All rational arithmetic functions assume
> operands have a canonical form, and canonicalize their result. The
> canonical form means that the denominator and the numerator have no
> common factors, and that the denominator is positive."
> 
> I always interpreted positive there as greater than zero rather than
> non-negative, because calling mpq_canonicalize() will DIVIDE_BY_ZERO if
> the denominator is zero.

Yes, but this just means that the user must not call these
functions in such a case. But he can do some work before
calling these functions. In particular, mpq_numref and
mpq_denref should work.

-- 
Vincent Lefèvre  - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Trevor Spiteri]

>>> Only 0 can have lazy allocation, and I think we document that it isn't
>>> legal to put 0 on the denominator.
>> where is this documented?
> That was in a "I think" sentence. Now that I looked a bit more, I don't 
> find it... Well, you can't call any mpq function that reads that mpq_t, 
> but we don't say you can't write to that mpq_t.

The documentation states that "All rational arithmetic functions assume
operands have a canonical form, and canonicalize their result. The
canonical form means that the denominator and the numerator have no
common factors, and that the denominator is positive."

I always interpreted positive there as greater than zero rather than
non-negative, because calling mpq_canonicalize() will DIVIDE_BY_ZERO if
the denominator is zero.

Trevor

___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marc Glisse]

On Fri, 20 Apr 2018, paul zimmermann wrote:


Only 0 can have lazy allocation, and I think we document that it isn't
legal to put 0 on the denominator.


where is this documented?


That was in a "I think" sentence. Now that I looked a bit more, I don't 
find it... Well, you can't call any mpq function that reads that mpq_t, 
but we don't say you can't write to that mpq_t.



In mpfr_set_q we use the fact that the user can set q to 1/0
for example to represent +Inf.


I didn't remember that MPFR did that, but I did remember that some people 
did that. I'll count it as a vote for Marco's patch.


--
Marc Glisse
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[paul zimmermann]

> Only 0 can have lazy allocation, and I think we document that it isn't 
> legal to put 0 on the denominator.

where is this documented? In mpfr_set_q we use the fact that the user can set q 
to 1/0
for example to represent +Inf.

Paul
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marc Glisse]

On Fri, 20 Apr 2018, Marco Bodrato wrote:


Ciao,

Il Gio, 19 Aprile 2018 4:37 pm, Marc Glisse ha scritto:

I finally pushed it. It seemed unsafe to keep mpq unaware of lazy
allocation, in case people start swapping the numerator of a rational with
a lazy 0 integer or something like that.


If we fear swaps, then ... what about swapping the deoniminator?


Only 0 can have lazy allocation, and I think we document that it isn't 
legal to put 0 on the denominator.



Should we support a code like:

 mpz_init (saved_denominator);
 mpz_swap (saved_denominator, mpq_denref(rational));
 /* Code overwriting rational*/

?


Hmmm... I don't know. It does seem vaguely possible that someone would do:

mpz_class den;
mpq_class q = some_computation();
den = std::move(q.get_den()); // won't need this value of q anymore
q = other_computation();

(the third line does a swap)

But that seems unlikely and contrived. If testing for this case is costly 
(it is likely cheap enough that I shouldn't worry), I'd be sad to pay for 
it :-( I'd be less negative if we were reaping some benefit from those new 
tests, for instance allowing a lazy denominator of 1.


But safety is a strong argument indeed.


If yes, a larger patch is needed, I attach a proposal.


If yes, then something like that looks right, thanks.

--
Marc Glisse
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marco Bodrato]

Ciao,

Il Gio, 19 Aprile 2018 4:37 pm, Marc Glisse ha scritto:
> I finally pushed it. It seemed unsafe to keep mpq unaware of lazy
> allocation, in case people start swapping the numerator of a rational with
> a lazy 0 integer or something like that.

If we fear swaps, then ... what about swapping the deoniminator?

Should we support a code like:

  mpz_init (saved_denominator);
  mpz_swap (saved_denominator, mpq_denref(rational));
  /* Code overwriting rational*/

?

If yes, a larger patch is needed, I attach a proposal.

Ĝis,
m

-- 
http://bodrato.it/diff -r 6e5b01dd940f mpq/clear.c
--- a/mpq/clear.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/clear.c	Fri Apr 20 07:59:01 2018 +0200
@@ -35,5 +35,6 @@
 {
   if (ALLOC (NUM(x)))
 __GMP_FREE_FUNC_LIMBS (PTR(NUM(x)), ALLOC(NUM(x)));
-  __GMP_FREE_FUNC_LIMBS (PTR(DEN(x)), ALLOC(DEN(x)));
+  if (ALLOC (DEN(x)))
+__GMP_FREE_FUNC_LIMBS (PTR(DEN(x)), ALLOC(DEN(x)));
 }
diff -r 6e5b01dd940f mpq/clears.c
--- a/mpq/clears.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/clears.c	Fri Apr 20 07:59:01 2018 +0200
@@ -42,7 +42,8 @@
 {
   if (ALLOC (NUM(x)))
 	__GMP_FREE_FUNC_LIMBS (PTR(NUM(x)), ALLOC(NUM(x)));
-  __GMP_FREE_FUNC_LIMBS (PTR(DEN(x)), ALLOC(DEN(x)));
+  if (ALLOC (DEN(x)))
+	__GMP_FREE_FUNC_LIMBS (PTR(DEN(x)), ALLOC(DEN(x)));
   x = va_arg (ap, mpq_ptr);
 }
   while (x != NULL);
diff -r 6e5b01dd940f mpq/div.c
--- a/mpq/div.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/div.c	Fri Apr 20 07:59:01 2018 +0200
@@ -48,12 +48,9 @@
 
   if (UNLIKELY (quot == op2))
 {
-  if (op1 == op2)
+  if (UNLIKELY (op1 == op2))
 	{
-	  PTR(NUM(quot))[0] = 1;
-	  SIZ(NUM(quot)) = 1;
-	  PTR(DEN(quot))[0] = 1;
-	  SIZ(DEN(quot)) = 1;
+	  mpq_set_ui (quot, 1, 1);
 	  return;
 	}
 
@@ -82,7 +79,7 @@
   /* We special case this to simplify allocation logic; gcd(0,x) = x
 	 is a singular case for the allocations.  */
   SIZ(NUM(quot)) = 0;
-  PTR(DEN(quot))[0] = 1;
+  MPZ_NEWALLOC (DEN(quot), 1)[0] = 1;
   SIZ(DEN(quot)) = 1;
   return;
 }
diff -r 6e5b01dd940f mpq/inp_str.c
--- a/mpq/inp_str.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/inp_str.c	Fri Apr 20 07:59:01 2018 +0200
@@ -43,7 +43,7 @@
 fp = stdin;
 
   SIZ(DEN(q)) = 1;
-  PTR(DEN(q))[0] = 1;
+  MPZ_NEWALLOC (DEN(q), 1)[0] = 1;
 
   nread = mpz_inp_str (mpq_numref(q), fp, base);
   if (nread == 0)
diff -r 6e5b01dd940f mpq/md_2exp.c
--- a/mpq/md_2exp.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/md_2exp.c	Fri Apr 20 07:59:01 2018 +0200
@@ -102,7 +102,7 @@
 {
   SIZ(NUM(dst)) = 0;
   SIZ(DEN(dst)) = 1;
-  PTR(DEN(dst))[0] = 1;
+  MPZ_NEWALLOC (DEN(dst), 1)[0] = 1;
   return;
 }
 
diff -r 6e5b01dd940f mpq/mul.c
--- a/mpq/mul.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/mul.c	Fri Apr 20 07:59:01 2018 +0200
@@ -61,7 +61,7 @@
   /* We special case this to simplify allocation logic; gcd(0,x) = x
 	 is a singular case for the allocations.  */
   SIZ(NUM(prod)) = 0;
-  PTR(DEN(prod))[0] = 1;
+  MPZ_NEWALLOC (DEN(prod), 1)[0] = 1;
   SIZ(DEN(prod)) = 1;
   return;
 }
diff -r 6e5b01dd940f mpq/set_d.c
--- a/mpq/set_d.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/set_d.c	Fri Apr 20 07:59:01 2018 +0200
@@ -76,7 +76,7 @@
 	{
 	  SIZ(NUM(dest)) = 0;
 	  SIZ(DEN(dest)) = 1;
-	  PTR(DEN(dest))[0] = 1;
+	  MPZ_NEWALLOC (DEN(dest), 1)[0] = 1;
 	  return;
 	}
 
@@ -157,7 +157,7 @@
 	  break;
 #endif
 	}
-  *PTR(DEN(dest)) = 1;
+  MPZ_NEWALLOC (DEN(dest), 1)[0] = 1;
   SIZ(DEN(dest)) = 1;
 }
   SIZ(NUM(dest)) = negative ? -nn : nn;
diff -r 6e5b01dd940f mpq/set_f.c
--- a/mpq/set_f.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/set_f.c	Fri Apr 20 07:59:01 2018 +0200
@@ -46,7 +46,7 @@
   /* set q=0 */
   SIZ(NUM(q)) = 0;
   SIZ(DEN(q)) = 1;
-  PTR(DEN(q))[0] = 1;
+  MPZ_NEWALLOC (DEN(q), 1)[0] = 1;
   return;
 }
 
@@ -65,7 +65,7 @@
 
   SIZ(NUM(q)) = fsize >= 0 ? fexp : -fexp;
   SIZ(DEN(q)) = 1;
-  PTR(DEN(q))[0] = 1;
+  MPZ_NEWALLOC (DEN(q), 1)[0] = 1;
 }
   else
 {
diff -r 6e5b01dd940f mpq/set_si.c
--- a/mpq/set_si.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/set_si.c	Fri Apr 20 07:59:01 2018 +0200
@@ -59,6 +59,6 @@
   SIZ(NUM(dest)) = num > 0 ? 1 : -1;
 }
 
-  PTR(DEN(dest))[0] = den;
+  MPZ_NEWALLOC (DEN(dest), 1)[0] = den;
   SIZ(DEN(dest)) = (den != 0);
 }
diff -r 6e5b01dd940f mpq/set_str.c
--- a/mpq/set_str.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/set_str.c	Fri Apr 20 07:59:01 2018 +0200
@@ -49,7 +49,7 @@
   if (slash == NULL)
 {
   SIZ(DEN(q)) = 1;
-  PTR(DEN(q))[0] = 1;
+  MPZ_NEWALLOC (DEN(q), 1)[0] = 1;
 
   return mpz_set_str (mpq_numref(q), str, base);
 }
diff -r 6e5b01dd940f mpq/set_ui.c
--- a/mpq/set_ui.c	Wed Apr 18 23:28:26 2018 +0200
+++ b/mpq/set_ui.c	Fri Apr 20 07:59:01 2018 +0200
@@ -55,6 +55,6 @@
   SIZ(NUM(dest)) = 1;
 }
 
-  PTR(DEN(dest))[0] = den;
+  MPZ_NEWALLOC (DEN(dest), 1)[0] = den;
   SIZ(DEN(dest)) = (den != 

Re: Lazy mpz allocation

[Marc Glisse]

On Mon, 11 Apr 2016, Marc Glisse wrote:


On Mon, 9 Nov 2015, Marco Bodrato wrote:


Moreover, the mpq layer and mini-gmp need to migrate to lazy allocation
too...


For mpq, the attached seems sufficient to pass make check.


I finally pushed it. It seemed unsafe to keep mpq unaware of lazy 
allocation, in case people start swapping the numerator of a rational with 
a lazy 0 integer or something like that.


--
Marc Glisse
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marc Glisse]

On Wed, 4 May 2016, Niels Möller wrote:


Marc Glisse  writes:


The fact that an mpq is made of 2 mpz that can be accessed directly is
part of the interface. I think following your suggestion would mean
changing that.


I guess you're right, it would break mpq_denref. Which I guess is also
expected to work on a const mpq_t, so it's not an easy solution to
redefine it to do lazy assignment.

And it's used in quite a lot of places, debian codesearch lists the
following packages:

 python-gmpy, llvm-toolchain-3.8, mpfr4, lcalc, yap, flint-arb, mlgmp,
 ats-lang-anairiats, givaro, parrot, llvm-toolchain-snapshot, librep,
 linbox, python-gmpy2, swi-prolog, libgmpada, isl, polymake, kcalc,
 pynac, flint, pike7.8, apron, cloog, llvm-toolchain-3.7, pike8.0,
 ocamlcreal, qsopt-ex, gambas3, cgal, surf-alggeo, singular, cvc3, gmp,
 regina-normal, gcl, ppl, libaqbanking, gmp-ecm, zimpl, ats2-lang,
 ledger, libalkimia, gfan, guile-1.8, genius, postgresql-pgmp

But I'm not giving up just yet. Would it be possible to initialize the
denominator as

 static const mp_limb_t the_one = 1;

 q->_mp_den._mp_alloc = 0;
 q->_mp_den._mp_size = 1;
 q->_mp_den._mp_d = (mp_limb_t*) _one;

(This kind-of requires that _mp_alloc == 0, _mp_size != 0 is supported
in general for mpz_t, meaning any modification requires new storage, and
that the storage pointed to by _mp_d should not be deallocated by gmp).


That looks pretty much like the copy-on-write thing you and Marco were 
discussing last year


https://gmplib.org/list-archives/gmp-devel/2015-September/004169.html

It should be possible, but it may require changing quite a number of 
places in the code.


--
Marc Glisse
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marc Glisse]

On Wed, 4 May 2016, Niels Möller wrote:


t...@gmplib.org (Torbjörn Granlund) writes:


I forgot about that we need to have an explicit denominator.
We could surely point that to some static read-only data, but that would
of course incur a cost when "re-allocating".


I'm not familiar with mpq internals, but I guess it might be possible to
get away with leaving the denominator as zero on initialization.

Then one would need to follow the convention that if numerator is zero,
then the denominator is ignored. Or (but I guess that's more cumbersome)
adapt the convention that zero denominator means "this is an integer",
and treated as one.


The fact that an mpq is made of 2 mpz that can be accessed directly is 
part of the interface. I think following your suggestion would mean 
changing that.


--
Marc Glisse
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Niels Möller]

t...@gmplib.org (Torbjörn Granlund) writes:

> I forgot about that we need to have an explicit denominator.
> We could surely point that to some static read-only data, but that would
> of course incur a cost when "re-allocating".

I'm not familiar with mpq internals, but I guess it might be possible to
get away with leaving the denominator as zero on initialization.

Then one would need to follow the convention that if numerator is zero,
then the denominator is ignored. Or (but I guess that's more cumbersome)
adapt the convention that zero denominator means "this is an integer",
and treated as one.

/nisse

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marc Glisse]

On Mon, 9 Nov 2015, Marco Bodrato wrote:


Moreover, the mpq layer and mini-gmp need to migrate to lazy allocation
too...


For mpq, the attached seems sufficient to pass make check. Of course, 
without a copy-on-write mechanism for the 1 in the denominator, the gains 
are not comparable to the mpz case, it is more for consistency.


--
Marc Glissediff -r 835f8974ff6e mpq/clear.c
--- a/mpq/clear.c   Thu Apr 07 22:50:07 2016 +0200
+++ b/mpq/clear.c   Mon Apr 11 11:42:59 2016 +0200
@@ -34,6 +34,7 @@
 void
 mpq_clear (mpq_t x)
 {
-  __GMP_FREE_FUNC_LIMBS (PTR(NUM(x)), ALLOC(NUM(x)));
+  if (ALLOC (NUM(x)))
+__GMP_FREE_FUNC_LIMBS (PTR(NUM(x)), ALLOC(NUM(x)));
   __GMP_FREE_FUNC_LIMBS (PTR(DEN(x)), ALLOC(DEN(x)));
 }
diff -r 835f8974ff6e mpq/clears.c
--- a/mpq/clears.c  Thu Apr 07 22:50:07 2016 +0200
+++ b/mpq/clears.c  Mon Apr 11 11:42:59 2016 +0200
@@ -41,7 +41,8 @@
 
   do
 {
-  __GMP_FREE_FUNC_LIMBS (PTR(NUM(x)), ALLOC(NUM(x)));
+  if (ALLOC (NUM(x)))
+   __GMP_FREE_FUNC_LIMBS (PTR(NUM(x)), ALLOC(NUM(x)));
   __GMP_FREE_FUNC_LIMBS (PTR(DEN(x)), ALLOC(DEN(x)));
   x = va_arg (ap, mpq_ptr);
 }
diff -r 835f8974ff6e mpq/init.c
--- a/mpq/init.cThu Apr 07 22:50:07 2016 +0200
+++ b/mpq/init.cMon Apr 11 11:42:59 2016 +0200
@@ -34,8 +34,9 @@
 void
 mpq_init (mpq_t x)
 {
-  ALLOC(NUM(x)) = 1;
-  PTR(NUM(x)) = __GMP_ALLOCATE_FUNC_LIMBS (1);
+  static const mp_limb_t dummy_limb=0xc1a0;
+  ALLOC(NUM(x)) = 0;
+  PTR(NUM(x)) = (mp_ptr) _limb;
   SIZ(NUM(x)) = 0;
   ALLOC(DEN(x)) = 1;
   PTR(DEN(x)) = __GMP_ALLOCATE_FUNC_LIMBS (1);
diff -r 835f8974ff6e mpq/set_si.c
--- a/mpq/set_si.c  Thu Apr 07 22:50:07 2016 +0200
+++ b/mpq/set_si.c  Mon Apr 11 11:42:59 2016 +0200
@@ -56,7 +56,7 @@
 }
   else
 {
-  PTR(NUM(dest))[0] = abs_num;
+  MPZ_NEWALLOC (NUM(dest), 1)[0] = abs_num;
   SIZ(NUM(dest)) = num > 0 ? 1 : -1;
 }
 
diff -r 835f8974ff6e mpq/set_ui.c
--- a/mpq/set_ui.c  Thu Apr 07 22:50:07 2016 +0200
+++ b/mpq/set_ui.c  Mon Apr 11 11:42:59 2016 +0200
@@ -52,7 +52,7 @@
 }
   else
 {
-  PTR(NUM(dest))[0] = num;
+  MPZ_NEWALLOC (NUM(dest), 1)[0] = num;
   SIZ(NUM(dest)) = 1;
 }
 
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Torbjörn Granlund]

Marc Glisse  writes:

  the function mpz_init could now be marked __GMP_NOTHROW. Do we want to
  do it? I could then propagate the change to the C++ wrapper, which
  would have a significant impact on the performance of
  std::vector for instance. On the other hand, this is a
  promise in the interface, going back to a throwing mpz_init would be
  an ABI break.

I'd say that we should go ahead and declare it __GMP_NOTHROW.

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marc Glisse]

Hello,

the function mpz_init could now be marked __GMP_NOTHROW. Do we want to do 
it? I could then propagate the change to the C++ wrapper, which would have 
a significant impact on the performance of std::vector for 
instance. On the other hand, this is a promise in the interface, going 
back to a throwing mpz_init would be an ABI break.


--
Marc Glisse
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marco Bodrato]

Ciao,

Il Lun, 9 Novembre 2015 8:36 pm, Niels Möller ha scritto:
> I agree on the direction. Please do it!

Done: https://gmplib.org/repo/gmp/rev/299ec6187305

Of course you may have better suggestions for mpz/init*.c (currently there
are different dummy_limbs, all defined inside their own init function...),
and we have to check that all functions was actually adapted correctly...

Moreover, the mpq layer and mini-gmp need to migrate to lazy allocation
too...

But we can say we started :-)

Regards,
m

-- 
http://bodrato.it/

___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Niels Möller]

"Marco Bodrato"  writes:

> Moreover, the mpq layer and mini-gmp need to migrate to lazy allocation
> too...

As for mini-gmp, there's no user visible interface change yet, right?
So not urgent, even if for consistency it would make sense to to it in
the same way there.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marco Bodrato]

Ciao,

Il Lun, 28 Settembre 2015 10:26 am, Torbjörn Granlund ha scritto:
> Some weeks ago, I made a naive testsuite-driven attempt at implementing
> lazy allocation.  I had 55 FAILures and 114 PASSes after having fixed
> these files:
>
> M mpz/clear.c
> M mpz/clears.c
> M mpz/init.c
> M mpz/mul.c
> M mpz/realloc.c
> M mpz/realloc2.c
> M mpz/set_si.c
> M mpz/set_ui.c
> M tests/mpz/t-limbs.c
>
> Curiously, there are some tests/mpn failures too.

Some tests in mpn use mpz to obtain uniformly distributed random numbers...

I did read all mpz files implementing function with an mpz_ptr argument,
and I changed all the following files: mpz/2fac_ui.c, mpz/aors_ui.h,
mpz/bin_ui.c, mpz/bin_uiui.c, mpz/cdiv_qr_ui.c, mpz/cdiv_r_ui.c,
mpz/cfdiv_q_2exp.c, mpz/clear.c, mpz/clears.c, mpz/com.c, mpz/fac_ui.c,
mpz/fdiv_qr_ui.c, mpz/fdiv_r_ui.c, mpz/fib2_ui.c, mpz/fib_ui.c, mpz/gcd.c,
mpz/gcd_ui.c, mpz/gcdext.c, mpz/init.c, mpz/inits.c, mpz/iset_d.c,
mpz/lucnum2_ui.c, mpz/lucnum_ui.c, mpz/mfac_uiui.c, mpz/mul.c,
mpz/n_pow_ui.c, mpz/oddfac_1.c, mpz/powm.c, mpz/powm_sec.c, mpz/powm_ui.c,
mpz/primorial_ui.c, mpz/realloc.c, mpz/realloc2.c, mpz/set_si.c,
mpz/set_ui.c, mpz/tdiv_qr_ui.c, mpz/tdiv_r_ui.c, mpz/ui_sub.c,
rand/randlc2x.c .

Most of the times the change was simply:

-  PTR (x)[0] = y;
+  MPZ_NEWALLOC (x, 1)[0] = y;

The test-suite passes... But I did not look into mpq yet.

If we agree with moving towards lazy allocation, I'll commit the changes.
So that we start testing early!

Regards,
m

-- 
http://bodrato.it/papers/

___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Niels Möller]

"Marco Bodrato"  writes:

> If we agree with moving towards lazy allocation, I'll commit the changes.
> So that we start testing early!

I agree on the direction. Please do it!

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Torbjörn Granlund]

"Marco Bodrato"  writes:

  I looked into the code and realised that my proposal requires an
  MPZ_REALLOC or if(ALLOC(x)==0) branch in ANY place where we write into an
  mpz_t. E.g. mpz_combit starts with:
  
if (limb_index + 1 < SIZ(x)) {
  PTR(x)[limb_index] ^= bit;
  return;
}
  
  If we allow the ALLOC(x)==0 && SIZ(x) != 0 case, we need to insert a check
  also in the simpler cases...
  
I assume this argues against being lazy with SIZE(x), not against being
lazy with allocation?

Some weeks ago, I made a naive testsuite-driven attempt at implementing
lazy allocation.  I had 55 FAILures and 114 PASSes after having fixed
these files:

M mpz/clear.c
M mpz/clears.c
M mpz/init.c
M mpz/mul.c
M mpz/realloc.c
M mpz/realloc2.c
M mpz/set_si.c
M mpz/set_ui.c
M tests/mpz/t-limbs.c

Curiously, there are some tests/mpn failures too.

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Niels Möller]

"Marco Bodrato"  writes:

>> I'd like a sort of "copy-on-write" interface, that allocates the needed
>
> I looked into the code and realised that my proposal requires an
> MPZ_REALLOC or if(ALLOC(x)==0) branch in ANY place where we write into an
> mpz_t. E.g. mpz_combit starts with:
>
>   if (limb_index + 1 < SIZ(x)) {
> PTR(x)[limb_index] ^= bit;
> return;
>   }

Good point. I'd say we postpone the "copy-on-write" thing for now. And
only support the following cases:

1. alloc > 0: Normal case, |size| <= alloc, reallocated as needed.

2. alloc == 0, size == 0: Initial lazy state, produced by mpz_init.
   Allocated on first write.

3. alloc == 0, size != 0: Allowed for input (read-only) mpz:s. Produced
   by mpz_roinit. Any attempt at writing the variable is invalid, and
   should call abort in all cases where checking for this case is cheap
   enough.

One corner case is what should be produced by mpz_roinit with a zero
input. After normalization we get size == 0. The intended meaning is
that of case (3), but if it is misused as an output variable, it will be
treated as case (2), and the allocated storage will leak. But I think it
is acceptable to have some random bad things happen on misuse.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marco Bodrato]

Ciao,

Il Mar, 1 Settembre 2015 6:46 am, Marco Bodrato ha scritto:
> I think that the condition to distinguish mpzs that where not allocated
> yet should be ALLOC(x)==0. As a consequence, MPZ_ROINIT_N can be the
> interface for initialising you ask for.
> I'd like a sort of "copy-on-write" interface, that allocates the needed

I looked into the code and realised that my proposal requires an
MPZ_REALLOC or if(ALLOC(x)==0) branch in ANY place where we write into an
mpz_t. E.g. mpz_combit starts with:

  if (limb_index + 1 < SIZ(x)) {
PTR(x)[limb_index] ^= bit;
return;
  }

If we allow the ALLOC(x)==0 && SIZ(x) != 0 case, we need to insert a check
also in the simpler cases...

Regards,
m

-- 
http://bodrato.it/papers/

___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Shared lib symbol hiding (Was: Re: Lazy mpz allocation)

[Torbjörn Granlund]

"Marco Bodrato"  writes:

  You pushed a patch to check if both 'attribute ((visibility ("hidden")))'
  and '__attribute__ ((alias...' are available.
  Maybe in some cases (e.g. the constant limb we are speaking about in this
  thread) we only want to hide, without the need of an alias?
  
We could separate them.  We need to worry about ELF, Mach-o and the
Windows format(s).  Does any of these support just hiding but not
aliasing?  I don't know.

I intend to soon make some hiding experiements over our great test
environment.  If it doesn't break things, I have a much larger change
which extensively does hiding + aliasing.  The resulting .so file
becomes much smaller, and GMP's performance should benefit too.

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Marco Bodrato]

Ciao,

Il Lun, 31 Agosto 2015 6:27 pm, Torbjörn Granlund ha scritto:
> (We should use 'attribute ((visibility ("hidden")))' for the the constant
> zero limbs at any rate.  I'll commit a basic patch for that soonish.)

You pushed a patch to check if both 'attribute ((visibility ("hidden")))'
and '__attribute__ ((alias...' are available.
Maybe in some cases (e.g. the constant limb we are speaking about in this
thread) we only want to hide, without the need of an alias?

Regards,
m

-- 
http://bodrato.it/papers/

___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Shared lib symbol hiding (Was: Re: Lazy mpz allocation)

[Marco Bodrato]

Ciao,

Il Lun, 7 Settembre 2015 5:34 pm, Torbjörn Granlund ha scritto:
> "Marco Bodrato"  writes:
>   Maybe in some cases (e.g. the constant limb we are speaking about in
>   this thread) we only want to hide, without the need of an alias?
>
> We could separate them.  We need to worry about ELF, Mach-o and the
> Windows format(s).  Does any of these support just hiding but not
> aliasing?  I don't know.

The same for me, I don't know. Moreover I don't know anything about
possible other (future?) formats... That's why I'd leave the checking task
to the configure step.

> I intend to soon make some hiding experiments over our great test
> environment.  If it doesn't break things, I have a much larger change
> which extensively does hiding + aliasing.  The resulting .so file
> becomes much smaller, and GMP's performance should benefit too.

Great!

Regards,
m
-- 
http://bodrato.it/

___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Torbjörn Granlund]

ni...@lysator.liu.se (Niels Möller) writes:

  Sure, but we could do
  
static const mp_limb_t dummy_limb = 0xc0dedead;
  
void mpz_init (mpz_t x)
{
  x->_mp_size = x->_mp_alloc = 0;
  x->_mp_d = _limb;
}
  
  It still represents the number zero, it's just that _mp_d[0] points to a
  dummy limb which happens to be far from zero.
  
Sorry, I misunderstood your proposal.

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Niels Möller]

t...@gmplib.org (Torbjörn Granlund) writes:

> "Marco Bodrato"  writes:
>
>   If we change (I'd agree) mpz_init into
>   
>   void
>   mpz_init (mpz_ptr x)
>   {
> ALLOC (x) = 0; /* ZERO, any MPZ_REALLOC will allocate */
> PTR (x) = & static_const_limb_shared_by_all_instances;
> SIZ (x) = 0;
>   }
>   
> I suppose we should do this!

Me too! Actually, mpz_init could then be

  static const mp_limb_t dummy_limb = 0;
  #define INITIAL_MPZ {0, 0, _limb};
  static const mpz_t initial_mpz = INITIAL_MPZ;  

  void
  mpz_init (mpz_ptr x)
  {
 *x = initial_mpz; /* Inline or memcpy, depending on compiler */
  }

and later on we can consider some public interface for initializing an
mpz without any library call. 

A use case I had a couple of years ago is initialization of a struct
containing a couple of mpz_t values together with other stuff, and with
the above change one could initialize a complete such a struct using a
single memcpy.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Niels Möller]

t...@gmplib.org (Torbjörn Granlund) writes:

> (We should use 'attribute ((visibility ("hidden")))' for the the
> constant zero limbs at any rate.  I'll commit a basic patch for that
> soonish.)

Maybe it should have a more interesting value than zero, to help catch
bugs if it is used when it shouldn't. And when running valgrind, it
could be explicitly marked as readable but undefined, to generate
valgrind warnings if any branch or memory access depends on the value.

It's tempting to try to rely on it being zero, like eliminating the
_mp_size != 0 test in mpz_odd_p, but that's broken unless all code that
may assign zero to _mp_size makes sure that _mp_size == 0 implies
_mp_d[0] == 0, which I doubt is a good idea.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Torbjörn Granlund]

ni...@lysator.liu.se (Niels Möller) writes:

  t...@gmplib.org (Torbjörn Granlund) writes:
  
  > (We should use 'attribute ((visibility ("hidden")))' for the the
  > constant zero limbs at any rate.  I'll commit a basic patch for that
  > soonish.)
  
  Maybe it should have a more interesting value than zero, to help catch
  bugs if it is used when it shouldn't. And when running valgrind, it
  could be explicitly marked as readable but undefined, to generate
  valgrind warnings if any branch or memory access depends on the value.
  
Unfortunately, the manual sayd "Initialize x, and set its value to 0."
about mpz_init.

  It's tempting to try to rely on it being zero, like eliminating the
  _mp_size != 0 test in mpz_odd_p, but that's broken unless all code that
  may assign zero to _mp_size makes sure that _mp_size == 0 implies
  _mp_d[0] == 0, which I doubt is a good idea.
  
I don't think we do that, nor should we.

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Lazy mpz allocation

[Niels Möller]

t...@gmplib.org (Torbjörn Granlund) writes:

> Unfortunately, the manual sayd "Initialize x, and set its value to 0."
> about mpz_init.

Sure, but we could do

  static const mp_limb_t dummy_limb = 0xc0dedead;

  void mpz_init (mpz_t x)
  {
x->_mp_size = x->_mp_alloc = 0;
x->_mp_d = _limb;
  }

It still represents the number zero, it's just that _mp_d[0] points to a
dummy limb which happens to be far from zero.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel