Re: Reduced number of allocated limbs after calling mpz_remove

2024-05-20 Thread Niels Möller
Torbjörn Granlund  writes:

> It is possible that the docs need clarification.

I think so, we should not write "never" if that's not what we mean.

My understanding is that allocation grows as needed, and is not returned
to the the system until mpz_clear. Except that allocation can shrink
only as the effect of mpz_realloc2 (never called internally) or mpz_swap
(called internally in few places).

But we also shouldn't over-allocate things. It could perhaps be
described like this: Each mpz output for a gmp function has an "expected
size" depending on the sizes of the inputs. E.g., excpected size of the
mpz_add output is the size of the largest input + 1, while actual size
may be as small as zero, due to cancellation.

On return, the allocation size of of an mpz_t output parameter should
either be unchanged (available storage could be reused, without any
reallocation, pointer would typically be unchanged too in this case), or
at most a limb or two larger than the expected output size for the
operation. E.g., mpz_powm internally needs storage for squares (twice
the expected output size), but it shouldn't inflate the allocation of
the output parameter to that size.

To the GMP application, the allocation size of an mpz_t is then bounded
by the largest "expected size" for any operation ever using that mpz_t
as output (+ effects of any mpz_swap or mpz_realloc2 in the
*application* code), which should be sufficient to get predictable
memory usage.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs


Re: Reduced number of allocated limbs after calling mpz_remove

2024-05-20 Thread Torbjörn Granlund
Niels Möller  writes:

  I don't have a strong opinion on how to fix this discrepancy between
  docs and implementation. But I feel rather strongly that mini-gmp
  shpuldn't make this promise, so code that rely on it will not work with
  mini-gmp.

It is, in my opinion, not a bug in the code, nor is is a bug in the
documentation.

What we indended to say in the docs is that a variable which once
contained something large then will occupy lots of RAM even if is later
is used for only small things.  (This in turn was an optimisation as
trimming the allocation after each operaton would slow down GMP very,
very much.)

That's the only thing we should promise, as it has obvious exceptions.

It is possible that the docs need clarification.  Perhaps a "in most
cases" can be inserted somewhere?

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


Re: Reduced number of allocated limbs after calling mpz_remove

2024-05-20 Thread Albin Ahlbäck
On 5/20/24 4:40 PM, Niels Möller wrote:> Could you use mpz_limbs_write 
(x, 2) for the functions that want a

result area of at least two limbs? Added in gmp-6-0.0. There's also the
mpz_realloc2 function, which does something related, but which may also
shrink the allocation.


We do utilize the internal function mpz_realloc for almost everything as 
we mostly work with limbs instead of bits.


Just to note, we have "patched" every call to mpz_remove so that the 
returning mpz does not have less limbs than we require.


Best,
Albin

P.S. Looks like my previous email didn't make it to the list.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs


Re: Reduced number of allocated limbs after calling mpz_remove

2024-05-20 Thread Albin Ahlbäck

Hejsan Niels,


So not sure if code or docs should be adjusted ("usually not" rather
than "never"). Do you think the "never reduce their allocated space"
property is important for your usecase, or for other GMP applications
general? If the strong statement is kept, this should perhaps be mention
as another execption in mini-gmp/README.


In the project I help maintaining, we have started to rely on that mpz 
never reduce the number of limbs. This is to keep a minimum number of 
limbs allocated to 2, so that if one where to do a multiplication of two 
limbs, the result is guaranteed to fit inside the mpz without having to 
do a reallocation. Of course, the memory manager could check that 
recycled mpzs do have at least 2 limbs allocated, but that seems 
unnecessary since `mpz_remove` seems to be the exception.


Since this indeed seems to be the exception, I am fine with either 
documenting that this indeed is the exception (perhaps it should then be 
stated under the section "Memory management" as well as the docstring 
for `mpz_remove`), or fixing this in `mpz_remove`.


Best,
Albin
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs


Re: Reduced number of allocated limbs after calling mpz_remove

2024-05-20 Thread Niels Möller
marco.bodr...@tutanota.com writes:

>> I don't have a strong opinion on how to fix this discrepancy between
>> docs and implementation.
>
> I'll correct the _remove function, it's quite easy to do :-)

Nice! To avoid regressions, it would be good to have tests for this.
Could possibly go in tests/mpz/reuse.c, but looks like a fair amount of
work to do properly.

>> But I feel rather strongly that mini-gmp shouldn't make this promise,
>> so code that rely on it will not work with mini-gmp.
>
> I agree for the mini-gmp side.

Then it should be documented as an exception in mini-gmp/README.
Suggested update below.

Regards,
/Niels

--- a/mini-gmp/README   Wed May 15 20:51:11 2024 +0200
+++ b/mini-gmp/README   Mon May 20 20:53:53 2024 +0200
@@ -39,21 +39,24 @@ mini-gmp as a fallback when for some rea
 not desired as a dependency.
 
 The supported GMP subset of the mpn and mpz interfaces is declared in
-mini-gmp.h, and implemented in mini-gmp.c. The implemented
-functions are fully compatible with the corresponding GMP functions,
-as specified in the GMP manual, with a few exceptions:
+mini-gmp.h, and implemented in mini-gmp.c. The supported GMP subset of
+the mpq layer is declared in mini-mpq.h, and implemented in
+mini-mpq.c. The implemented functions are fully compatible with the
+corresponding GMP functions, as specified in the GMP manual, with a
+few exceptions:
 
   mpz_export and mpz_import support only NAILS = 0.
 
+  mini-gmp's handling of destinations operands does not satisfy the
+  documented property that 'mpz_t' and 'mpq_t' variables never reduce
+  their allocated space.
+
 The performance target for mini-gmp is to be at most 10 times slower
 than the real GMP library, for numbers of size up to a few hundred
 bits. No asymptotically fast algorithms are included in mini-gmp, so
 it will be many orders of magnitude slower than GMP for very large
 numbers.
 
-The supported GMP subset of the mpq layer is declared in mini-mpq.h,
-and implemented in mini-mpq.c.
-
 You should never "install" mini-gmp. Applications can either just
 #include mini-gmp.c (but then, beware that it defines several macros
 and functions outside of the advertised interface), and if needed


-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs


Re: Reduced number of allocated limbs after calling mpz_remove

2024-05-20 Thread marco . bodrato
Ciao,

20 mag 2024, 16:40 da ni...@lysator.liu.se:

> Albin Ahlbäck  writes:
>
>> In the project I help maintaining, we have started to rely on that mpz
>> never reduce the number of limbs. This is to keep a minimum number of
>> limbs allocated to 2
>>

With lazy allocation, we moved toward the opposite direction, but having at 
least two limbs when at least one is allocated anyway might be a good idea.


> Could you use mpz_limbs_write (x, 2) for the functions that want a
> result area of at least two limbs?
>

They can, but surely they want an already allocated couple of limbs for speed 
reasons, calling _limbs_write every now and then might not be in the spirit of 
the optimization.


>> Since this indeed seems to be the exception, I am fine with either
>> documenting that this indeed is the exception (perhaps it should then
>> be stated under the section "Memory management" as well as the
>> docstring for `mpz_remove`), or fixing this in `mpz_remove`.
>>

Actually the manual (https://gmplib.org/manual/Memory-Management ) reads:
"mpz_t and mpq_t variables never reduce their allocated space."

The mis-behaviour of mpz_remove is my fault. When I experimented with that 
function I tested both the "never reduce" and the "may reduce" version, but 
when I did commit I forgot to push the correct one.

https://gmplib.org/repo/gmp/rev/596470e0bc62

As you can see, the correct code is already there, but #if-ed out because 
WANT_ORIGINAL_DEST is not defined.

> I don't have a strong opinion on how to fix this discrepancy between
> docs and implementation.
>

I'll correct the _remove function, it's quite easy to do :-)


> But I feel rather strongly that mini-gmp
> shouldn't make this promise, so code that rely on it will not work with
> mini-gmp.
>

I agree for the mini-gmp side.

Ĝis,
mb

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


Re: Reduced number of allocated limbs after calling mpz_remove

2024-05-20 Thread Niels Möller
Albin Ahlbäck  writes:

> In the project I help maintaining, we have started to rely on that mpz
> never reduce the number of limbs. This is to keep a minimum number of
> limbs allocated to 2, so that if one where to do a multiplication of
> two limbs, the result is guaranteed to fit inside the mpz without
> having to do a reallocation.

Thanks for explaining. To me, it seems a bit brittle to rely in this.

Could you use mpz_limbs_write (x, 2) for the functions that want a
result area of at least two limbs? Added in gmp-6-0.0. There's also the
mpz_realloc2 function, which does something related, but which may also
shrink the allocation.

> Since this indeed seems to be the exception, I am fine with either
> documenting that this indeed is the exception (perhaps it should then
> be stated under the section "Memory management" as well as the
> docstring for `mpz_remove`), or fixing this in `mpz_remove`.

I don't have a strong opinion on how to fix this discrepancy between
docs and implementation. But I feel rather strongly that mini-gmp
shpuldn't make this promise, so code that rely on it will not work with
mini-gmp.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs


Re: Reduced number of allocated limbs after calling mpz_remove

2024-05-20 Thread Niels Möller
Albin Ahlbäck  writes:

> It is stated in the documentation that "mpz_t and mpq_t variables
> never reduce their allocated space.", which is sort of true given that
> `x` and `dest` are only being swapped, but that requires the user to
> know what the internals are doing.

Whenever an mpz function is called with destination operant equal to one
of the inputs, and the lower-level functions don't support in-place
operation, mpz functions would need to either

1. allocate new storage for the result (violating the above property),
or

2. allocate a copy of the inputs.

It looks like mpz_remove does option (1), while, e.g., mpz_tdiv_qr
follows option (2). I would prefer to give the implementation a bit more
freedom. And mini-gmp follows (1) rather aggressively, even when there
is no argument overlap.

So not sure if code or docs should be adjusted ("usually not" rather
than "never"). Do you think the "never reduce their allocated space"
property is important for your usecase, or for other GMP applications
general? If the strong statement is kept, this should perhaps be mention
as another execption in mini-gmp/README.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs