aleaxit / gmpy

General Multi-Precision arithmetic for Python 2.6+/3+ (GMP, MPIR, MPFR, MPC)
https://gmpy2.readthedocs.io/en/latest/
GNU Lesser General Public License v3.0
516 stars 87 forks source link

Update int <-> mpz conversion #484

Closed skirpichev closed 4 months ago

skirpichev commented 4 months ago

@casevh, that solves issue, mentioned in #483. But this code should be benchmarked.

casevh commented 4 months ago

It is a definite performance improvement for the conversion of small mpz->int.

There is a slight performance decrease for the conversion of int->mpz. I used the the PyLong_AsLongAndOverflow() to avoid creation of a temporary mpz variable. It wasn't used to for a faster conversion to mpz. I would revert the changes for int->mpz.

I need to think more about the Windows platform. The new compact integer object in 3.13 is a restricted range ssize_t value. In WIndows, ssize_t is equivalent to long long so we can't use mpz_fits_si. There is PyLong_FromSsize_t. What is the best way to extract a ssize_t from an mpz type? I want to allow Python 3.13+ to construct compact values whenever possible. Using PyLong_From[Long|Ssize_t] should be a stable way to do it.

skirpichev commented 4 months ago

I would revert the changes for int->mpz.

Done. I'll not try other variants here to not block release.

we can't use mpz_fits_si

I doubt there are other options. This will solve mentioned issue with small integers (previously, new objects were created).

casevh commented 4 months ago

Can you double-check my logic to check if an mpz object can be converted to a 64-bit ssize_t assuming a 64-bit unsigned limb?

if mpz_size(object) > 1 then return false if mpz_size(object) == 0 then return true (and the actual value is 0) if mpz_sign > 0 and object[0] <= 263 - 1 then return true (and the actual value is object[0]) if mpz_sign < 0 and object[0] <= 263 then return true (and the actual value is -1 * object[0])

An implementation of GMPy_mpz_AsSssize_tAndOverflow() using the above logic followed by PyLong_FromSsize_t() should allow Windows to create compact integers for all the same values as Linux/MacOS.

I don't care if B1 is released without this but I would like to add this for an RC1 release.

skirpichev commented 4 months ago

Looks fine, assuming given fixed sizes.

But I'm not sure I realize what you are trying to solve. Current PR do mpz->int conversion in a portable way for small mpz's (mpz_fits_slong_p(), mpz_get_si() and PyLong_FromLong()) and ensure that int's value is taken from the cache (i.e. by get_small_int()). That solves int(mpz(x)) is int(mpz(x)) identity problem for all small x.

For the rest - we fallback to old code. I think if we want to streamline conversion for bigger values - this will require a better API both from the CPython and GMP.

casevh commented 4 months ago

But I'm not sure I realize what you are trying to solve.

The current patch solves two issues: (1) small ints were not used and (2) on platforms where sizeof(long) == sizeof(ssize_t) a compact value would be returned for all possible valid compact results (since they all fit in a long). But on Windows, sizeof(long) != sizeof(ssize_t) so values outside the range of a long but inside the range of a compact are converted to PyLong instead. For example, int(mpz(2**33)) will be a compact type on Linux but a PyLong type on Windows. I'm concerned that the different types will trigger a slower code path on Windows.

I'll commit your PR as-is. I've already started on a version of GMPy_MPZ_AsSsize_tAndOverflow and I'll commit that when it is tested.

skirpichev commented 4 months ago

For example, int(mpz(2**33)) will be a compact type on Linux but a PyLong type on Windows.

Hmm, are you sure (you can test by PyUnstable_Long_CompactValue())? sys.int_info shows on x64 windows just same as on my linux box:

$ python -c 'import sys;print(sys.int_info)'
sys.int_info(bits_per_digit=30, sizeof_digit=4, default_max_str_digits=4300, str_digits_check_threshold=640)
skirpichev commented 4 months ago

BTW, int(mpz(2**33)) is not a compact value on my box:)

>>> example.is_compact(2**33)
False
>>> example.is_compact(2**29)  # 30 bits per digit
True
>>> example.is_compact(int(gmpy2.mpz(2**30)))
False
>>> example.is_compact(int(gmpy2.mpz(2**29)))
True
static PyObject *
is_compact(PyObject *self, PyObject *op)
{   
    return PyBool_FromLong(PyUnstable_Long_IsCompact((PyLongObject *) op));
}
casevh commented 4 months ago

Sigh. I think I remember reading early proposals where compact values had a range of 60 bits. And the documentation states that compact values will not require more that 63 bits on systems with a 64-bit ssize_t. And that tagged pointers would be used. So either I'm not interpreting the code correctly or my memory is faulty. Or both. ;)

If I publish 2.2.0b1 with binary wheels and just a source release of 2.1.6, will "pip install gmpy2" attempt a source installation of 2.1.6 over a 2.2.0.b1 binary wheel? If so, does bumping to 2.2.0rc1 allow "pip install gmpy2" to choose the 2.2.0 binary wheels?

skirpichev commented 4 months ago

If I publish 2.2.0b1 with binary wheels and just a source release of 2.1.6, will "pip install gmpy2" attempt a source installation of 2.1.6 over a 2.2.0.b1 binary wheel?

Sure. pip will prefer stable release, unless you use --pre option.

If so, does bumping to 2.2.0rc1 allow "pip install gmpy2" to choose the 2.2.0 binary wheels?

No. rc1 is still pre-release version.