Consider restoring _PyLong_New() function as public

[skirpichev]

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.

[skirpichev]

CC @vstinner

[vstinner]

GMP import and export functions: https://gmplib.org/manual/Integer-Import-and-Export

[vstinner]

cc @serhiy-storchaka

[vstinner]

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.

https://github.com/aleaxit/gmpy/blob/e0944795008e6929c3d6cdfabb8344ce8a9e99d6/src/gmpy2_convert_gmp.c#L148-L181

This function calls also _PyLong_SetSignAndDigitCount(), not only _PyLong_New().

https://github.com/sagemath/sage/blob/2f1a76dc24af6c8ca9a804b10913c33a936b4fb8/src/sage/libs/gmp/pylong.pyx#L57-L69

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.

[skirpichev]

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() and GMPy_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 without PyInt_Import/Export() functions...

[vstinner]

The _PyLong_New() function was restored by #112115

Should others functions such as _PyLong_SetSignAndDigitCount(), _PyLong_IsNegative() and _PyLong_DigitCount() be restored as well?

[skirpichev]

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

[skirpichev]

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]

@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

[skirpichev]

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 loop

With 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 loop

diff 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;
 }
 

[vstinner]

It will be a performance regression.

Oh, that's bad. Thank you very much for testing! Which API do you need?

[skirpichev]

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;
    }
}

[casevh]

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 digit is the same size (or smaller) than a long. This may not be true in the future if the bits per digit changes to 45 or 60 or something else. I would use PyLong_AsLongAndOverflow and check overflow to check if it is too large. This mostly a Windows issue. Note: checking overflow is significantly faster than raising an exception. The ...AndOverflow functions are used extensively in gmpy2.

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 if size was 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_FromSignSizeArray work? Array is an array of digits created by PyMem_Malloc(size * sizeof(digit)). Array would be filled by mpz_export. Then PyLong_FromSignSizeArray(mpz_sgn(obj->z) < 0, count, Array)would create the actualPyLong`.

[skirpichev]

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 the PyLong_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) with obj==NULL allocates new integer objects with size digits and returns it, while for existing obj - it just change the space, allocated for the absolute value of to size digits.

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.

[casevh]

I was thinking about using PyLong_AsLongAndOverflow(), but I'm not sure if this will be more efficient: I assume the PyLong_AsLong() doesn't raise an exception here.

If the number of bits per digit is greater than 32, then digit will be a long long. So any number between 33 and 64 bits will still have len equal to 1 but it won't fit into a long on Windows. Compact integer values are defined as Py_ssize_t so they also exceed the size of long on 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 digit an issue? gmpy2 has ensured that size was valid but has never reallocated the memory.

[skirpichev]

Is the memory consumed by an extra digit an issue?

Maybe not. But CPython at least run long_normalize() in such cases.

[casevh]

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.

[skirpichev]

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).

[vstinner]

I wrote a PR adding an import-export API for Python int objects: #121339

[skirpichev]

I'm closing this as a duplicate of #102471