Skip to content

Consider restoring _PyLong_New() function as public #111415

Closed as not planned
Closed as not planned
Consider restoring _PyLong_New() function as public#111415
Labels
topic-C-APItype-featureA feature request or enhancement

Description

@skirpichev
skirpichev
opened on Oct 28, 2023

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.

Activity

  1. skirpichev
    added
    type-featureA feature request or enhancement
    on Oct 28, 2023
  2. skirpichev
    added a commit that references this issue on Oct 28, 2023

    pythongh-111415: restoring _PyLong_New() as public

    cc5240c

  3. skirpichev commented on Oct 28, 2023

    @skirpichev
    skirpichev
    on Oct 28, 2023
    MemberAuthor

    CC @vstinner

  4. Eclips4
    added
    topic-C-API
    on Oct 28, 2023

  5. vstinner commented on Oct 28, 2023

    @vstinner
    vstinner
    on Oct 28, 2023
    Member

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

  6. vstinner commented on Oct 28, 2023

    @vstinner
    vstinner
    on Oct 28, 2023
    Member

    cc @serhiy-storchaka

  7. vstinner commented on Oct 30, 2023

    @vstinner
    vstinner
    on Oct 30, 2023
    Member

    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.

  8. skirpichev commented on Oct 30, 2023

    @skirpichev
    skirpichev
    on Oct 30, 2023
    MemberAuthor

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

  9. vstinner commented on Nov 15, 2023

    @vstinner
    vstinner
    on Nov 15, 2023
    Member

    The _PyLong_New() function was restored by #112115

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

  10. skirpichev commented on Nov 16, 2023

    @skirpichev
    skirpichev
    on Nov 16, 2023
    MemberAuthor

    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

  11. skirpichev commented on Mar 10, 2024

    @skirpichev
    skirpichev
    on Mar 10, 2024
    MemberAuthor

    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.

  12. vstinner commented on Mar 10, 2024

    @vstinner
    vstinner
    on Mar 10, 2024
    Member

    @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

  13. skirpichev commented on Mar 10, 2024

    @skirpichev
    skirpichev
    on Mar 10, 2024
    MemberAuthor

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

  14. vstinner commented on Mar 10, 2024

    @vstinner
    vstinner
    on Mar 10, 2024
    Member

    It will be a performance regression.

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

  15. skirpichev commented on Mar 11, 2024

    @skirpichev
    skirpichev
    on Mar 11, 2024
    MemberAuthor

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

  16. casevh commented on Mar 11, 2024

    @casevh
    casevh
    on Mar 11, 2024

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

  17. skirpichev commented on Mar 11, 2024

    @skirpichev
    skirpichev
    on Mar 11, 2024
    MemberAuthor

    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.

  18. casevh commented on Mar 11, 2024

    @casevh
    casevh
    on Mar 11, 2024

    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.

  19. skirpichev commented on Mar 12, 2024

    @skirpichev
    skirpichev
    on Mar 12, 2024
    MemberAuthor

    Is the memory consumed by an extra digit an issue?

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

  20. casevh commented on Mar 12, 2024

    @casevh
    casevh
    on Mar 12, 2024

    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.

  21. skirpichev commented on Mar 12, 2024

    @skirpichev
    skirpichev
    on Mar 12, 2024
    MemberAuthor

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

  22. vstinner commented on Jul 3, 2024

    @vstinner
    vstinner
    on Jul 3, 2024
    Member

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

  23. skirpichev commented on Jul 4, 2024

    @skirpichev
    skirpichev
    on Jul 4, 2024
    MemberAuthor

    I'm closing this as a duplicate of #102471

  24. skirpichev
    closed this as not plannedon Jul 4, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    topic-C-APItype-featureA feature request or enhancement

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions