gh-102471: Add PyLong import and export API #121339

vstinner · 2024-07-03T15:28:00Z

Add PyLong_Export() and PyLong_Import() functions and PyLong_LAYOUT structure.

Issue: The C-API for Python to C integer conversion is, to be frank, a mess. #102471

📚 Documentation preview 📚: https://cpython-previews--121339.org.readthedocs.build/

vstinner · 2024-07-03T15:31:47Z

cc @skirpichev @casevh

Include/cpython/longintrepr.h

vstinner · 2024-07-03T20:22:27Z

See also issue #111415

skirpichev

Just my 2c.

The gmpy2 code, used for benchmarking, can be found in my fork:
https://github.com/skirpichev/gmpy/tree/trying-py-import-export

Doc/c-api/long.rst

skirpichev · 2024-07-04T02:31:36Z

Objects/longobject.c

+PyUnstable_Long_Export(PyObject *obj, PyUnstable_LongExport *long_export)
+{
+    if (!PyLong_Check(obj)) {
+        PyErr_Format(PyExc_TypeError, "expect int, got %T", obj);
+        return -1;
+    }
+    PyLongObject *self = (PyLongObject*)obj;
+
+    long_export->obj = (PyLongObject*)Py_NewRef(obj);
+    long_export->negative = _PyLong_IsNegative(self);
+    long_export->ndigits = _PyLong_DigitCount(self);
+    if (long_export->ndigits == 0) {
+        long_export->ndigits = 1;
+    }
+    long_export->digits = self->long_value.ob_digit;
+    return 0;
+}


As this mostly give a direct access to the PyLongObject - it almost as fast as using private stuff before.

Old code:

$ python -m timeit -r20 -s 'from gmpy2 import mpz;x=10**2' 'mpz(x)' 1000000 loops, best of 20: 232 nsec per loop $ python -m timeit -r11 -s 'from gmpy2 import mpz;x=10**100' 'mpz(x)' 500000 loops, best of 11: 500 nsec per loop $ python -m timeit -r20 -s 'from gmpy2 import mpz;x=10**1000' 'mpz(x)' 100000 loops, best of 20: 2.53 usec per loop

With proposed API:

$ python -m timeit -r20 -s 'from gmpy2 import mpz;x=10**2' 'mpz(x)' 1000000 loops, best of 20: 258 nsec per loop $ python -m timeit -r20 -s 'from gmpy2 import mpz;x=10**100' 'mpz(x)' 500000 loops, best of 20: 528 nsec per loop $ python -m timeit -r20 -s 'from gmpy2 import mpz;x=10**1000' 'mpz(x)' 100000 loops, best of 20: 2.56 usec per loop

skirpichev · 2024-07-04T02:38:51Z

Objects/longobject.c

+PyObject*
+PyUnstable_Long_Import(int negative, size_t ndigits, Py_digit *digits)
+{
+    return (PyObject*)_PyLong_FromDigits(negative, ndigits, digits);
+}


But this is something I would like to avoid. This requires allocation of a temporary buffer and using memcpy. Can we offer a writable layout to use it's digits in the mpz_export directly?

Benchmarks for old code:

$ python -m timeit -r11 -s 'from gmpy2 import mpz;x=mpz(10**2)' 'int(x)' 2000000 loops, best of 11: 111 nsec per loop $ python -m timeit -r11 -s 'from gmpy2 import mpz;x=mpz(10**100)' 'int(x)' 500000 loops, best of 11: 475 nsec per loop $ python -m timeit -r11 -s 'from gmpy2 import mpz;x=mpz(10**1000)' 'int(x)' 100000 loops, best of 11: 2.39 usec per loop

With new API:

$ python -m timeit -r20 -s 'from gmpy2 import mpz;x=mpz(10**2)' 'int(x)' 2000000 loops, best of 20: 111 nsec per loop $ python -m timeit -r20 -s 'from gmpy2 import mpz;x=mpz(10**100)' 'int(x)' 500000 loops, best of 20: 578 nsec per loop $ python -m timeit -r20 -s 'from gmpy2 import mpz;x=mpz(10**1000)' 'int(x)' 100000 loops, best of 20: 2.53 usec per loop

This requires allocation of a temporary buffer and using memcpy.

Right, PyLongObject has to manage its own memory.

Can we offer a writable layout to use it's digits in the mpz_export directly?

That sounds strange from the Python point of view and make the internals "less opaque". I would prefer to leak less implementation details.

Right, PyLongObject has to manage its own memory.

I'm not trying to change that. More complete proposal: vstinner#4

gmpy2 patch: https://github.com/skirpichev/gmpy/tree/trying-py-import-export-v2

New benchmarks:

$ python -m timeit -r20 -s 'from gmpy2 import mpz;x=mpz(10**2)' 'int(x)' 2000000 loops, best of 20: 111 nsec per loop $ python -m timeit -r20 -s 'from gmpy2 import mpz;x=mpz(10**100)' 'int(x)' 500000 loops, best of 20: 509 nsec per loop $ python -m timeit -r20 -s 'from gmpy2 import mpz;x=mpz(10**1000)' 'int(x)' 100000 loops, best of 20: 2.44 usec per loop

I would prefer to leak less implementation details.

I don't think this leak anything. It doesn't leak memory management details. PyLong_Import will just do allocation memory. Writting digits will be job for mpz_export, as before.

Without this, it seems - there are noticeable performance regression for integers of intermediate range. Something up to 20% vs 7% on my branch.

Edit: currently, proposed PyUnstable_Long_ReleaseImport() match PyUnstable_Long_ReleaseExport(). Perhaps, it could be one function (say, PyUnstable_Long_ReleaseDigitArray()), but I unsure - maybe it puts some constraints on internals of the PyLongObject.

Objects/longobject.c

Doc/c-api/long.rst

skirpichev · 2024-07-04T03:27:09Z

CC @tornaria, as Sage people might be interested in this feature.

skirpichev · 2024-07-04T05:06:03Z

CC @oscarbenjamin, you may want this for python-flint

vstinner · 2024-07-04T07:08:41Z

I updated my PR:

Use -1 for little endian and +1 for big endian.
Rename PyUnstable_LongExport to PyUnstable_Long_DigitArray.
Add "always succeed" mention in the doc.

Lib/test/test_capi/test_long.py

Misc/NEWS.d/next/C API/2024-07-03-17-26-53.gh-issue-102471.XpmKYk.rst

Doc/whatsnew/3.14.rst

oscarbenjamin · 2024-07-04T11:23:49Z

CC @oscarbenjamin, you may want this for python-flint

Absolutely. Currently python-flint uses a hex-string as an intermediate format when converting between large int and fmpz so anything more direct is an improvement. I expect that python-flint would use mpz_import/mpz_export just like gmpy2.

Objects/longobject.c

vstinner · 2024-07-04T12:56:16Z

@skirpichev: I added a PyLongWriter API similar to what @encukou proposed.

Example:

PyLongObject *
_PyLong_FromDigits(int negative, Py_ssize_t digit_count, digit *digits)
{
    PyLongWriter *writer = PyLongWriter_Create();
    if (writer == NULL) {
        return NULL;
    }

    if (negative) {
        PyLongWriter_SetSign(writer, -1);
    }

    Py_digit *writer_digits = PyLongWriter_AllocDigits(writer, digit_count);
    if (writer_digits == NULL) {
        goto error;
    }
    memcpy(writer_digits, digits, digit_count * sizeof(digit));

    return (PyLongObject*)PyLongWriter_Finish(writer);

error:
    PyLongWriter_Discard(writer);
    return NULL;
}

The PyLongWriter_Finish() function normalizes the number and gets a small number if needed. Example:

>>> import _testcapi; _testcapi.pylong_import(0, [100, 0, 0]) is 100
True

vstinner · 2024-07-04T13:00:48Z

I mark the PR as a draft until we agree on the API.

skirpichev · 2024-07-04T13:20:48Z

I added a PyLongWriter API similar to what @encukou proposed.

Yes, that looks better and should fix speed regression. I'll try to benchmark that, perhaps tomorrow.

But cost is 5 (!) public functions and one new struct, additionally to PyUnstable_Long_Import(), which will be a more slow API. Correct? C.f. just one function in above proposal.

vstinner · 2024-07-04T13:31:12Z

I updated the PR to remove the PyUnstable_ prefix, replace it with the PyLong prefix.

vstinner · 2024-07-04T13:38:57Z

But cost is 5 (!) public functions and one new struct, additionally to PyUnstable_Long_Import(), which will be a more slow API. Correct? C.f. just one function in #121339 (comment) proposal.

My concern is to avoid the problem capi-workgroup/api-evolution#36 : avoid exposing _PyLong_New() object until it's fully initialized. The "writer" API hides the implementation details but also makes sure that the object is not "leaked" to Python before it's fully initialized and valid. By the way, the implementation uses functions which are only safe if the object cannot be seen in Python: if Py_REFCNT(obj) is 1.

vstinner · 2024-07-04T13:43:25Z

@skirpichev: Would it be useful to add a PyLongWriter_SetValue(PyLongWriter *writer, long value) function? It would be similar to PyLong_FromLong(long value) (but may be less efficient), so I'm not sure if it's relevant.

vstinner · 2024-09-05T12:37:48Z

Update:

Remove layout parameter of PyLongWriter_Create().
Remove layout member of PyLong_DigitArray structure.
Use an unsigned type (size_t) for ndigits.

This reverts commit b70a6dd.

Doc/c-api/long.rst

vstinner · 2024-09-06T12:09:47Z

Use an unsigned type (size_t) for ndigits.

Change reverted: capi-workgroup/decisions#35 (comment)

skirpichev · 2024-09-15T07:23:57Z

Doc/c-api/long.rst

+   This function always succeeds if *obj* is a Python :class:`int` object or a
+   subclass.


@vstinner, after some thinking I believe we should drop this contract, if we take into account future changes in internals of CPython's integers. If single layout view will be invalid - this function, probably, will allocate temporary buffers. That might fail.

Can we offer a different contract instead, something like this: "This function always succeeds if obj is a Python int object or a subclass and it's value can't be converted to C long."? In this case users have a clear hint: "try something like PyLong_AsLongAndOverflow and if it fails - fallback to this function". If not, I think this is a severe issue with that part of API.

vstinner · 2024-09-15T12:46:24Z

Can we offer a different contract instead, something like this: "This function always succeeds if obj is a Python int object or a subclass and it's value can't be converted to C long."? In this case users have a clear hint: "try something like PyLong_AsLongAndOverflow and if it fails - fallback to this function". If not, I think this is a severe issue with that part of API.

If tomorrow, Python internals change and exporting a small integer requires a copy, I would prefer to copy by default. Maybe we can add a "NO_COPY" flag to the function: it would fail if a copy is needed.

skirpichev · 2024-09-15T13:32:11Z

If tomorrow, Python internals change and exporting a small integer requires a copy, I would prefer to copy by default.

That's fine. My point is: this might fail.

Maybe we can add a "NO_COPY" flag to the function: it would fail if a copy is needed.

Then what user should do in this case? Catch exception and try some PyLong_As*() function?

"This function always succeeds if obj is a Python int object or a subclass and it's value can't be converted to C long."

Well, if we can't do this, maybe we could say that this function might raise only MemoryError's?

oscarbenjamin · 2024-09-15T15:50:36Z

If tomorrow, Python internals change and exporting a small integer requires a copy, I would prefer to copy by default.

That seems reasonable.

Maybe we can add a "NO_COPY" flag to the function: it would fail if a copy is needed.

I don't see how that would be useful.

If this fails because there is not enough memory when allocating a PyLong for a small integer then it is probably reasonable that there is a MemoryError and that the call should fail. The calling code should likely give up whatever it is trying to do as well.

It already says "On error, set an exception and return -1" which implies that the caller should check the return value.

skirpichev · 2024-09-15T16:07:58Z

If this fails because there is not enough memory when allocating a PyLong for a small integer then it is probably reasonable that there is a MemoryError and that the call should fail. The calling code should likely give up whatever it is trying to do as well.

Exactly.

It already says "On error, set an exception and return -1" which implies that the caller should check the return value.

No, currently is says "This function always succeeds if obj is a Python :class:int object or a subclass." And this is a documentation bug, as I think.

But we can't just drop this sentence. Should caller expect here other exceptions? What to do for them?

vstinner · 2024-09-15T17:56:44Z

@skirpichev:

@vstinner, after some thinking I believe we should drop this contract, if we take into account future changes in internals of CPython's integers. If single layout view will be invalid - this function, probably, will allocate temporary buffers. That might fail.

I created python/peps#3965 to remove the sentence.

Doc/c-api/long.rst

Rename reserved member to _reserved.

vstinner · 2024-09-16T12:25:55Z

On PyPy, a copy is always needed, so the function can fail (with MemoryError) even for small integers: https://discuss.python.org/t/pep-757-c-api-to-import-export-python-integers/63895/12

skirpichev · 2024-09-16T14:54:55Z

FYI, in aleaxit/gmpy#517 I did int<->mpz conversion PyLong_AsNativeBytes/FromNativeBytes. Maybe it worth to include this in PEP's benchmarks?

ericsnowcurrently · 2024-09-16T16:43:19Z

Objects/longobject.c

+const PyLongLayout PyLong_LAYOUT = {
+    .bits_per_digit = PyLong_SHIFT,
+    .digits_order = -1,  // least significant first
+    .endian = PY_LITTLE_ENDIAN ? -1 : 1,
+    .digit_size = sizeof(digit),
+};


I'm pretty sure that if you make this static const ... then you shouldn't need to add this to ignored.tsv.

It fails with:

Objects/longobject.c - PyLong_LAYOUT not supported (typespec (unknown)) static const PyLongLayout

vstinner · 2024-09-16T17:02:46Z

FYI, in aleaxit/gmpy#517 I did int<->mpz conversion PyLong_AsNativeBytes/FromNativeBytes. Maybe it worth to include this in PEP's benchmarks?

I would prefer to only have a single flavor of the code in the PEP benchmarks. Moreover, the API is still being discussed: https://discuss.python.org/t/pep-757-c-api-to-import-export-python-integers/63895/18 Let's wait and update benchmarks later.

skirpichev · 2024-09-16T17:27:43Z

On Mon, Sep 16, 2024 at 10:03:11AM -0700, Victor Stinner wrote: FYI, in [1]aleaxit/gmpy#517 I did int<->mpz conversion PyLong_AsNativeBytes/FromNativeBytes. Maybe it worth to include this in PEP's benchmarks? I would prefer to only have a single flavor of the code in the PEP benchmarks. Moreover, the API is still being discussed: [2]https://discuss.python.org/t/pep-757-c-api-to-import-export-python-integers/63895/18 Let's wait and update benchmarks later.

The rationale is to show, that using existing API costs performance regression wrt current master (using private API). We will keep just code snippets with new API, as examples of it's usage. (E.g. we don't show now code in the gmpy2 master.) Just add a link to this pr. But I agree, lets wait. Edit: reading (int->mpz): | Benchmark | master | bytes | new-api | |----------------|:-------:|:---------------------:|:---------------------:| | 1<<7 | 262 ns | 274 ns: 1.05x slower | 267 ns: 1.02x slower | | 1<<38 | 319 ns | 283 ns: 1.12x faster | 275 ns: 1.16x faster | | 1<<300 | 514 ns | 913 ns: 1.77x slower | 586 ns: 1.14x slower | | 1<<3000 | 2.35 us | 4.49 us: 1.91x slower | 2.42 us: 1.03x slower | | Geometric mean | (ref) | 1.33x slower | 1.01x slower | writing (mpz->int): | Benchmark | master | bytes | new-api | |----------------|:-------:|:---------------------:|:---------------------:| | 1<<38 | 210 ns | 215 ns: 1.02x slower | not significant | | 1<<300 | 519 ns | 795 ns: 1.53x slower | 567 ns: 1.09x slower | | 1<<3000 | 2.26 us | 4.52 us: 2.00x slower | 2.31 us: 1.02x slower | | Geometric mean | (ref) | 1.33x slower | 1.02x slower | Benchmark hidden because not significant (1): 1<<7 I think, that my patch with *Bytes API can be optimized to avoid memory allocation, but hardly this will critically mitigate speed difference. And this will not work with ``--enable-nails`` GMP builds.

* Rename functions and structure: * PyLong_AsDigitArray() => PyLong_Export() * PyLong_FreeDigitArray() => PyLong_FreeExport() * PyLong_DigitArray => PyLongExport * 'array' => 'export_long'

vstinner · 2024-09-17T08:52:37Z

Since PEP 757 is actively being discussed, I mark this PR as a draft again.

@skirpichev @pitrou: I updated my PR to implement @pitrou's idea: add int64_t value to the structure. It's also based on python/peps#3970.

vstinner requested review from erlend-aasland and corona10 as code owners July 3, 2024 15:28

bedevere-app bot mentioned this pull request Jul 3, 2024

The C-API for Python to C integer conversion is, to be frank, a mess. #102471

Open

bedevere-app bot added the awaiting core review label Jul 3, 2024

vstinner force-pushed the long_export branch from 21dd5b9 to a087b0a Compare July 3, 2024 15:30

vstinner mentioned this pull request Jul 3, 2024

Add public function PyLong_GetDigits() capi-workgroup/decisions#31

Open

zooba reviewed Jul 3, 2024

View reviewed changes

Include/cpython/longintrepr.h Outdated Show resolved Hide resolved

vstinner requested a review from ericsnowcurrently as a code owner July 3, 2024 20:13

vstinner mentioned this pull request Jul 3, 2024

Consider restoring _PyLong_New() function as public #111415

Closed

skirpichev reviewed Jul 4, 2024

View reviewed changes

skirpichev mentioned this pull request Jul 4, 2024

Consider adding public PyLong_FlipSign() function #120446

Open

skirpichev reviewed Jul 4, 2024

View reviewed changes

oscarbenjamin mentioned this pull request Jul 4, 2024

More efficient conversion from Python int to fmpz flintlib/python-flint#159

Open

skirpichev reviewed Jul 4, 2024

View reviewed changes

Objects/longobject.c Outdated Show resolved Hide resolved

vstinner marked this pull request as draft July 4, 2024 13:00

bedevere-app bot removed the awaiting core review label Jul 4, 2024

vstinner force-pushed the long_export branch from a191357 to 294f53a Compare July 4, 2024 13:26

vstinner mentioned this pull request Jul 4, 2024

Avoid creating incomplete/invalid objects capi-workgroup/api-evolution#36

Open

Revert "Use unsigned type for ndigits"

0d0f942

This reverts commit b70a6dd.

picnixz reviewed Sep 6, 2024

View reviewed changes

Doc/c-api/long.rst Outdated Show resolved Hide resolved

doc: adjust ndigits documentation

762c33a

Update doc

20be7a3

skirpichev reviewed Sep 15, 2024

View reviewed changes

steve-s reviewed Sep 16, 2024

View reviewed changes

Doc/c-api/long.rst Outdated Show resolved Hide resolved

Make PyLong_DigitArray.obj private

d92bf1e

skirpichev reviewed Sep 16, 2024

View reviewed changes

Doc/c-api/long.rst Outdated Show resolved Hide resolved

Remove reserved documentation

b3b02a2

Rename reserved member to _reserved.

PyLong_FreeDigitArray() only clears _reserved

caca2d7

ericsnowcurrently reviewed Sep 16, 2024

View reviewed changes

Make PyLong_LAYOUT static

4221a49

Add PyLong_AsDigitArray.value

37b1d49

* Rename functions and structure: * PyLong_AsDigitArray() => PyLong_Export() * PyLong_FreeDigitArray() => PyLong_FreeExport() * PyLong_DigitArray => PyLongExport * 'array' => 'export_long'

vstinner marked this pull request as draft September 17, 2024 08:51

bedevere-app bot removed the awaiting core review label Sep 17, 2024

vstinner added 3 commits September 17, 2024 10:55

Inline PyLong_AsInt64() to avoid the exception

d70a121

Remove Py_digit type; update the doc

4aa25f6

Merge branch 'main' into long_export

90973d4

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

gh-102471: Add PyLong import and export API #121339

gh-102471: Add PyLong import and export API #121339

vstinner commented Jul 3, 2024 •

edited by github-actions bot

Loading

vstinner commented Jul 3, 2024 •

edited

Loading

vstinner commented Jul 3, 2024

skirpichev left a comment

skirpichev Jul 4, 2024

skirpichev Jul 4, 2024

vstinner Jul 4, 2024

skirpichev Jul 4, 2024 •

edited

Loading

skirpichev commented Jul 4, 2024

skirpichev commented Jul 4, 2024

vstinner commented Jul 4, 2024

oscarbenjamin commented Jul 4, 2024

vstinner commented Jul 4, 2024

vstinner commented Jul 4, 2024

skirpichev commented Jul 4, 2024

vstinner commented Jul 4, 2024

vstinner commented Jul 4, 2024

vstinner commented Jul 4, 2024

vstinner commented Sep 5, 2024

vstinner commented Sep 6, 2024

skirpichev Sep 15, 2024

vstinner commented Sep 15, 2024

skirpichev commented Sep 15, 2024 •

edited

Loading

oscarbenjamin commented Sep 15, 2024

skirpichev commented Sep 15, 2024

vstinner commented Sep 15, 2024

vstinner commented Sep 16, 2024

skirpichev commented Sep 16, 2024

ericsnowcurrently Sep 16, 2024

vstinner Sep 16, 2024

vstinner commented Sep 16, 2024 •

edited

Loading

skirpichev commented Sep 16, 2024 via email •

edited

Loading

vstinner commented Sep 17, 2024

		This function always succeeds if obj is a Python :class:`int` object or a
		subclass.

gh-102471: Add PyLong import and export API #121339

Are you sure you want to change the base?

gh-102471: Add PyLong import and export API #121339

Conversation

vstinner commented Jul 3, 2024 • edited by github-actions bot Loading

vstinner commented Jul 3, 2024 • edited Loading

vstinner commented Jul 3, 2024

skirpichev left a comment

Choose a reason for hiding this comment

skirpichev Jul 4, 2024

Choose a reason for hiding this comment

skirpichev Jul 4, 2024

Choose a reason for hiding this comment

vstinner Jul 4, 2024

Choose a reason for hiding this comment

skirpichev Jul 4, 2024 • edited Loading

Choose a reason for hiding this comment

skirpichev commented Jul 4, 2024

skirpichev commented Jul 4, 2024

vstinner commented Jul 4, 2024

oscarbenjamin commented Jul 4, 2024

vstinner commented Jul 4, 2024

vstinner commented Jul 4, 2024

skirpichev commented Jul 4, 2024

vstinner commented Jul 4, 2024

vstinner commented Jul 4, 2024

vstinner commented Jul 4, 2024

vstinner commented Sep 5, 2024

vstinner commented Sep 6, 2024

skirpichev Sep 15, 2024

Choose a reason for hiding this comment

vstinner commented Sep 15, 2024

skirpichev commented Sep 15, 2024 • edited Loading

oscarbenjamin commented Sep 15, 2024

skirpichev commented Sep 15, 2024

vstinner commented Sep 15, 2024

vstinner commented Sep 16, 2024

skirpichev commented Sep 16, 2024

ericsnowcurrently Sep 16, 2024

Choose a reason for hiding this comment

vstinner Sep 16, 2024

Choose a reason for hiding this comment

vstinner commented Sep 16, 2024 • edited Loading

skirpichev commented Sep 16, 2024 via email • edited Loading

vstinner commented Sep 17, 2024

vstinner commented Jul 3, 2024 •

edited by github-actions bot

Loading

vstinner commented Jul 3, 2024 •

edited

Loading

skirpichev Jul 4, 2024 •

edited

Loading

skirpichev commented Sep 15, 2024 •

edited

Loading

vstinner commented Sep 16, 2024 •

edited

Loading

skirpichev commented Sep 16, 2024 via email •

edited

Loading