Re: Reduced number of allocated limbs after calling mpz_remove
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
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
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
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
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
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
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
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
Reduced number of allocated limbs after calling mpz_remove
Hello, Standing at the following commit: changeset: 18465:7ecb3b2beea1 tag: tip user:Niels Möller date:Sun Feb 18 20:20:57 2024 +0100 summary: mini-gmp: Fix bug in gcdext canonicalization, and strengthen related tests. I have noticed that `mpz_remove` may reduce the number of allocated limbs after a call. I haven't looked into this too much, but I suppose it is due to the variable `x` being initialized in the routine, whose limbs I believe are allocated in `mpz_tdiv_q`, is then being swapped with `dest`. 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. Is this the expected behavior? Have I overlooked something perhaps? Please let me know if you need more information. Best, Albin ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
