Repository navigation
Consider restoring _PyLong_New() function as public #111415
Description
Activity
- added a commit that references this issue
on Oct 28, 2023 CC @vstinner
GMP import and export functions: https://gmplib.org/manual/Integer-Import-and-Export
I don't think that accessing directly PyLongObject members and having a public "PyLong_New" API to create an uninitialized integer is a good pattern: see capi-workgroup/problems#56
I would prefer to have a generic API to create a Python int object from any format, with a convenient, but generic enough, "import" API.
This function calls also
_PyLong_SetSignAndDigitCount(), not only_PyLong_New().This function calls also
Py_SET_SIZE(L, -pylong_size)to sets the integer sign (make it negative).The problem is to have a generic but efficient API. A generic API would be to:
- (1) Convert a GMP integer into an "array of digits" allocated on the stack or on the heap (depending on the size)
- (2) Create a Python integer from this array
- (3) Delete the temporary array
The problem is to avoid (1) and (3) steps.
I don't think that accessing directly PyLongObject members and having a public "PyLong_New" API to create an uninitialized integer is a good pattern
No, that's not what was proposed. Sure, I would prefer a better alternative: mpz_export/import-like pair + functions to get/set the sign of int and to get the length of an "array of digits". Something like #102471. (see also @casevh comment)
The point is: we shouldn't hide
_PyLong_New()without introducing an alternative in 3.13.This function calls also _PyLong_SetSignAndDigitCount(), not only _PyLong_New().
Yes.
GMPy_MPZ_From_PyLong()andGMPy_PyLong_From_MPZ()are typical consumers of this "_API".PS: In principle, I think some parts like
_PyLong_IsNegative()and_PyLong_DigitCount()could be exposed as public (or as an unstable API at least) right now, but this doesn't make too much sense withoutPyInt_Import/Export()functions...They are copied in the gmpy2, yes. (See https://github.com/aleaxit/gmpy/blob/1edb0369690cce69ec5d90964eaead31a57e7a9b/src/gmpy2_convert.h#L135-L155) And to sage: sagemath/sage@dc71bd0
I don't think that accessing directly PyLongObject members and having a public "PyLong_New" API to create an uninitialized integer is a good pattern: see capi-workgroup/problems#56
@vstinner, do you think that mpz_limbs_read/write-like API to access unsigned value of "big enough" PyLongObject as an array of "digits" is an example of this bad pattern or it does make sense and could be discussed somewhere?
With this kind of API (probably much less complex than PyInt_Import/Export) on the CPython side - Sage/gmpy2/python-flint/etc could do fast conversion to/from PyLong's using mpz_import/export functions.
@vstinner, do you think that mpz_limbs_read/write-like API to access unsigned value of "big enough" PyLongObject as an array of "digits" is an example of this bad pattern or it does make sense and could be discussed somewhere?
Does the new PyLong_FromNativeBytes() API fit your needs? https://docs.python.org/dev/c-api/long.html#c.PyLong_FromNativeBytes
Does the new PyLong_FromNativeBytes() API fit your needs?
It will be a performance regression. In the gmpy2 master:
$ python -m timeit -r11 -unsec -s 'from gmpy2 import mpz;a=10**100' 'mpz(a)' 500000 loops, best of 11: 491 nsec per loop $ python -m timeit -r11 -unsec -s 'from gmpy2 import mpz;a=10**1000' 'mpz(a)' 100000 loops, best of 11: 2.53e+03 nsec per loopWith PyLong_FromNativeBytes:
$ python -m timeit -r11 -unsec -s 'from gmpy2 import mpz;a=10**100' 'mpz(a)' 500000 loops, best of 11: 851 nsec per loop $ python -m timeit -r11 -unsec -s 'from gmpy2 import mpz;a=10**1000' 'mpz(a)' 50000 loops, best of 11: 4.8e+03 nsec per loopdiff wrt gmpy2 master
@@ -42,9 +42,6 @@ static MPZ_Object * GMPy_MPZ_From_PyLong(PyObject *obj, CTXT_Object *context) { MPZ_Object *result; - int negative; - Py_ssize_t len; - PyLongObject *templong = (PyLongObject*)obj; if(!(result = GMPy_MPZ_New(context))) { /* LCOV_EXCL_START */ @@ -52,25 +49,12 @@ GMPy_MPZ_From_PyLong(PyObject *obj, CTXT_Object *context) /* LCOV_EXCL_STOP */ } - len = _PyLong_DigitCount(templong); - negative = _PyLong_IsNegative(templong); - - switch (len) { - case 1: - mpz_set_si(result->z, (sdigit)GET_OB_DIGIT(templong)[0]); - break; - case 0: - mpz_set_si(result->z, 0); - break; - default: - mpz_import(result->z, len, -1, sizeof(GET_OB_DIGIT(templong)[0]), 0, - sizeof(GET_OB_DIGIT(templong)[0])*8 - PyLong_SHIFT, - GET_OB_DIGIT(templong)); - } - - if (negative) { - mpz_neg(result->z, result->z); - } + char *bytes = NULL; + Py_ssize_t expected = PyLong_AsNativeBytes(obj, bytes, 0, 1); + bytes = malloc(expected); + PyLong_AsNativeBytes(obj, bytes, expected, 1); + mpz_import(result->z, expected, -1, sizeof(char), 0, 0, bytes); + free(bytes); return result; }
It will be a performance regression.
Oh, that's bad. Thank you very much for testing! Which API do you need?
I think that mpz_limbs_read/write-like API could look like this.
Reading (see current code):
int PyLong_Sign(PyObject *obj); // mpz_sgn() Py_ssize_t PyLong_DigitCount(PyObject *obj); // mpz_size() digit * PyLong_AsDigits(PyObject *obj); // mpz_limbs_read() // digit * PyLong_AsDigits(PyObject *obj, Py_ssize_t *size) ? static MPZ_Object * GMPy_MPZ_From_PyLong(PyObject *obj, CTXT_Object *context) { MPZ_Object *result; if(!(result = GMPy_MPZ_New(context))) { return NULL; } Py_ssize_t len = PyLong_DigitCount(obj); if (len <= 1) { mpz_set_si(result->z, PyLong_AsLong(obj)); } else { mpz_import(result->z, len, -1, sizeof(digit), 0, sizeof(digit)*8 - PyLong_SHIFT, PyLong_AsDigits(obj)); if (PyLong_Sign(obj) < 0) { mpz_neg(result->z, result->z); } } return result; }
Writing (see current code):
PyObject * PyLong_ReallocDigits(PyObject *obj, Py_ssize_t size); static PyObject * GMPy_PyLong_From_MPZ(MPZ_Object *obj, CTXT_Object *context) { if (mpz_fits_slong_p(obj->z)) { return PyLong_FromLong(mpz_get_si(obj->z)); } else { PyObject *result = NULL; size_t size = (mpz_sizeinbase(obj->z, 2) + PyLong_SHIFT - 1) / PyLong_SHIFT; result = PyLong_ReallocDigits(result, size); if (!result) { return NULL; } size_t count; mpz_export(PyLong_AsDigits(result), &count, -1, sizeof(digit), 0, sizeof(digit)*8 - PyLong_SHIFT, obj->z); result = PyLong_ReallocDigits(result, count); if (mpz_sgn(obj->z) < 0) { result = PyNumber_Negative(result); } return result; } }
I think that mpz_limbs_read/write-like API could look like this.
I was working on a response but I'll comment on @skirpichev proposal instead.
Reading (see current code):
int PyLong_Sign(PyObject *obj); // mpz_sgn() Py_ssize_t PyLong_DigitCount(PyObject *obj); // mpz_size() const digit * PyLong_AsDigits(PyObject *obj); // mpz_limbs_read() // const digit * PyLong_AsDigits(PyObject *obj, Py_ssize_t *size) ? static MPZ_Object * GMPy_MPZ_From_PyLong(PyObject *obj, CTXT_Object *context) { MPZ_Object *result; if(!(result = GMPy_MPZ_New(context))) { return NULL; } Py_ssize_t len = PyLong_DigitCount(obj); if (len <= 1) { mpz_set_si(result->z, PyLong_AsLong(obj)); } else { mpz_import(result->z, len, -1, sizeof(digit), 0, sizeof(digit)*8 - PyLong_SHIFT, PyLong_AsDigits(obj)); if (PyLong_Sign(obj) < 0) { mpz_neg(result->z, result->z); } } return result; }
There is a minor issue that also impacts the current code so it doesn't impact the proposed design.
The current and example code both assume that
digitis the same size (or smaller) than along. This may not be true in the future if the bits per digit changes to 45 or 60 or something else. I would usePyLong_AsLongAndOverflowand checkoverflowto check if it is too large. This mostly a Windows issue. Note: checkingoverflowis significantly faster than raising an exception. The...AndOverflowfunctions are used extensively ingmpy2.Writting (see current code):
// mpz_realloc2() & mpz_limbs_write() digit * PyLong_ReallocDigits(PyObject *obj, Py_ssize_t size); static PyObject * GMPy_PyLong_From_MPZ(MPZ_Object *obj, CTXT_Object *context) { if (mpz_fits_slong_p(obj->z)) { return PyLong_FromLong(mpz_get_si(obj->z)); } else { PyObject *result = NULL; size_t size = (mpz_sizeinbase(obj->z, 2) + PyLong_SHIFT - 1) / PyLong_SHIFT; digit *digits = PyLong_ReallocDigits(result, size); if (!digits) { return NULL; } size_t count; mpz_export(digits, &count, -1, sizeof(digit), 0, sizeof(digit)*8 - PyLong_SHIFT, obj->z); PyLong_ReallocDigits(result, count); if (mpz_sgn(obj->z) < 0) { result = PyNumber_Negative(result); } return result; } }
Is there a precise definition of the behavior of
PyLong_ReallocDigits? Does is always return a new object? If so, there would be a new object created ifsizewas too large and another new object if the number is negative. I'm concerned about but I can't think of a viable solution that only uses public interfaces.Would something like
PyLong_FromSignSizeArraywork?Arrayis an array of digits created byPyMem_Malloc(size * sizeof(digit)).Arraywould be filled bympz_export. ThenPyLong_FromSignSizeArray(mpz_sgn(obj->z) < 0, count, Array)would create the actualPyLong`.checking overflow is significantly faster than raising an exception.
I was thinking about using
PyLong_AsLongAndOverflow(), but I'm not sure if this will be more efficient: I assume thePyLong_AsLong()doesn't raise an exception here.Is there a precise definition of the behavior of PyLong_ReallocDigits?
Thanks for asking, that question actually changed design:) (Above post was updated.)
PyLong_ReallocDigits(obj, size)withobj==NULLallocates new integer objects withsizedigits and returns it, while for existingobj- it just change the space, allocated for the absolute value of tosizedigits.Would something like PyLong_FromSignSizeArray work?
Hmm, maybe it's even better. IIUIC, this solution will also avoid creation of a temporary array.
But in above code we could overestimate
size.Then PyLong_FromSignSizeArray(mpz_sgn(obj->z) < 0, count, Array)would create the actualPyLong`.
We also might want to call
PyMem_Realloc()on the Array before.I was thinking about using
PyLong_AsLongAndOverflow(), but I'm not sure if this will be more efficient: I assume thePyLong_AsLong()doesn't raise an exception here.If the number of bits per digit is greater than 32, then
digitwill be along long. So any number between 33 and 64 bits will still havelenequal to 1 but it won't fit into alongon Windows. Compact integer values are defined asPy_ssize_tso they also exceed the size oflongon Windows. We still need to address this for gmpy2.Would something like PyLong_FromSignSizeArray work?
Hmm, maybe it's even better. IIUIC, this solution will also avoid creation of a temporary array.
But in above code we could overestimate
size.Then PyLong_FromSignSizeArray(mpz_sgn(obj->z) < 0, count, Array)would create the actualPyLong`.
We also might want to call
PyMem_Realloc()on the Array before.Is the memory consumed by an extra
digitan issue? gmpy2 has ensured thatsizewas valid but has never reallocated the memory.Is the memory consumed by an extra digit an issue?
Maybe not. But CPython at least run long_normalize() in such cases.
Is the memory consumed by an extra digit an issue?
Maybe not. But CPython at least run long_normalize() in such cases.
We would always run the equivalent of long_normalize() before returning the array of digits.
We would always run the equivalent of long_normalize() before returning the array of digits.
This sounds like an implementation detail. But hardly this will be changed.
PS: Actually, we already have (public in fact!) function
_PyLong_FromDigits(). @casevh, I think it works exactly as in your proposal (for writing). Edit: no (it uses memcpy).I'm closing this as a duplicate of #102471
This was used to streamline conversion between ints and gmp-based integers. E.g. in the gmpy2: https://github.com/aleaxit/gmpy/blob/e0944795008e6929c3d6cdfabb8344ce8a9e99d6/src/gmpy2_convert_gmp.c#L148-L181 or in the Sage: https://github.com/sagemath/sage/blob/2f1a76dc24af6c8ca9a804b10913c33a936b4fb8/src/sage/libs/gmp/pylong.pyx#L57-L69
Clearly, we want a better C-API e.g. for import/export ints, like mpz_import/export (probably, #102471 is the right metaissue here), but I don't see good reasons to hide this function now, without any alternatives.
See #106320 and #108604.