Add portable way to extract all digits of a `PyLongObject` from C?

Python mandates integers need to be “big ints”, i.e., integers can be of arbitrary length. CPython currently implements this with the following type:

typedef struct {
    /* ... */
    ssize_t ob_size;
    uint32_t ob_digit[1];  /* variable-length array */
} PyLongObject;

and provides the following method in its stable C API/ABI for converting this to a C number:

long PyLong_AsLongAndOverflow(PyObject *obj, int *overflow);

which returns the Python integer if it fits inside a C long, and sets overflow to a non-zero value otherwise. However, suppose I want to extract all digits of the python in order to, e.g., feed it to a BigInt library. How do I do that in a portable and stable way?

I could of course parse the object above, but as far as I understand the docs correctly, for ABI stability sake the Python devs consider PyLongObject * an opaque pointer, its structure an implementation detail, and subject to change. Alternatively, but this is painfully slow, I could round-trip through the python divide and modulo functions.

So how about adding a pair of new methods:

size_t PyLong_AsChunks(PyObject *obj, uint32_t *chunks, size_t chunk_size);
int PyLong_FromChunks(PyObject *obj, const uint32_t *chunks, size_t chunk_size);

which convert from and to a set of chunks, which then can be assembled and fed into an external bigint library?

You may have overlooked int.to_bytes and int.bit_length.

But that incurs a roundtrip through Python, right? The question is how to do that from the C API.

Related ideas discussion:
https://www.mail-archive.com/python-ideas@python.org/msg28177.html

1 Like

@mwallerb is your intent for the to-bytes function to return the internal structure (a list of 4 * ceil(log(n, 2**30)) bytes to represent the base-2**30 ‘digits’ of int n; see Internal structure, likely also needs the header)?
That differs from the less implementation-specific ‘logical’ representation (a list of ceil(log(n, 256)) bytes to represent the base-256 ‘digits’ of int n)

The former would expose internal detail and not be obviously useful for consumers because of the 30 mantissa bits per uint_32.
The latter would still require processing (bit-shifting to repackage) to construct, though less than a roundtrip via decimal (which apparently is quadratical, see recent restriction for security). But that basically is the existing to-bytes function, I guess.

1 Like

PyObject_CallMethod is part of the C API, anything wrong with that? It may be slightly slower than a dedicated C API function, but not painfully so.

3 Likes

I concur with @Dutcho that the internal structure is probably not terribly useful, and to_bytes is better.

@AndersMunch I am not sure about the overhead, I suspect it is not huge. But just from a conceptual perspective I find it strange that the C API for an arbitrary-length integer does not contain a method for
converting it to anything but longs and long longs.

Especially since there’s already a _PyLong_FromByteArray function in CPython that has a somewhat nicer interface than packing and unpacking tuples:

PyObject *_PyLong_FromByteArray(const unsigned char *bytes, size_t n,
                                int little_endian, int is_signed);

but alas, it is not public. Is there any harm in exposing this to the user?

Or, at the very least, if the to_bytes method is the “blessed” way of getting the full integer, shouldn’t we add something to this effect to the PyLong docs?

By the time someone wants this feature is there really significant benefit to maintaining direct C API functions to do the same?

They’re already making a call saying they expect to handle arbitrary length bigints more than long long (64-128) bits. At which point added overhead from CallMethod may be dwarfed when faced with actually high bit count numbers. One fewer memory copy out of the PyBytes object and excess Mallorca/free. Do you have a practical application where that is a measurable performance bottleneck?

1 Like

It’s not so much the performance overhead. It’s the conceptual overhead (but I think that is small).

On a separate note, the author of _PyLong_FromByteArray (Tim Peters) commented on the python mailing list (_PyLong_FromByteArray) that he’d made it an _Py function because he didn’t want the overhead of having to document it and maintain it. There was no architectural objection to it being part of the API.

Actually, I’ve just noticed _PyLong_FromByteArray is “memory->PyLong”, where the original discussion was about “PyLong->memory” (but I think the internal functions were written at the same time and the same logic applies)

Our objection to adding such a C API is that it’d expose an internal implementation detail if the desire is to do this “for performance”. The only way it’d perform well is if we never fundamentally change our internals.

What size digits are and that we use as a number base is something we shouldn’t guarantee to users. If we exposed our internal digits via a C API, we’d have limited ability to change those in the future. We’ve changed our internal number base once in the past.

We do not store the internal representation in memory in the same manner that I expect most other bignum libraries do. So you really are best off just calling the Python to_bytes() and from_bytes() methods. Can you demonstrate a practical performance problem in an application with that approach?

1 Like

@gpshead

Can you demonstrate a practical performance problem in an application with that approach?

I cannot, but that is not my point. Open the C API documentation for PyLong and you will not find any method for extracting all the digits for a bigint, not binary digits, not base-256 (bytes), not base-2^32 (internal representation). This is I think fundamentally weird for a type that represents arbitrary-size integers. This confused me.

So my point is I suggest one of two things be added:

  • a dedicated function PyLong_ToBytes or similar (which may very well be just a simple wrapper around PyObject_CallMethod(...) of to_bytes)
  • a note in the C API documentation pointing to the Python to_bytes functions, perhaps even a code example.

Again, I do not care which basis the chunks are in, it does not have to match the internal representation. I am afraid don’t know how to make this any clearer.

1 Like

That makes sense. Feel free to open a feature/docs request in the CPython issue tracker to expose .to_bytes and .from_bytes equivalents as C APIs or if not at least document with examples how to call those in the C API docs near our other PyLong_ APIs.

2 Likes

Our objection to adding such a C API is that it’d expose an internal implementation detail if the desire is to do this “for performance”. The only way it’d perform well is if we never fundamentally change our internals.

Now that PEP 689 got accepted, we have a way to handle this: PEP 689 – Unstable C API tier | peps.python.org

The portable way is int.to_bytes, but for extensions that want peak performance with a specific CPython version, we could expose a PyUnstable_LongToBase30Digits function.
But yes, we should only do that if it’s needed. Greg’s question stands:

Can you demonstrate a practical performance problem in an application with that approach?

2 Likes

@encukou

Can you demonstrate a practical performance problem in an application with that approach?

As I mentioned several times now, I cannot: my point is conceptual, not performance-centric. I do not think that the performance will be significantly worse with a round-trip through int.to_bytes. Put differently: to_bytes is a perfectly fine paradigm for getting the digits of a big int.

To quote myself:

Open the C API documentation for PyLong and you will not find any method for extracting all the digits for a bigint, not binary digits, not base-256 (bytes), not base-2^32 (internal representation). This is I think fundamentally weird for a type that represents arbitrary-size integers.

Since you are asking for real-world impact: this confused me, and as I could not figure out how to get all the digits of a long. Now I understand that I have to do this using PyMethod_Call, but that’s (at least to me) not at all obvious from the docs. So I suggest, again to quote:

  • a dedicated function PyLong_ToBytes or similar (which may very well be just a simple wrapper around PyObject_CallMethod(...) of to_bytes)
  • a note in the C API documentation pointing to the Python to_bytes functions, perhaps even a code example.

IMO, a docs example should be sufficient in this case.

1 Like

I must admit I am puzzled by the desire to replicate the python language in C. Any C-API is a burden for other non-C python implementations (PyPy, GraalPython) or python accelerators and transpilers (cython, pyston, numba, and more).

This also came up in the “Adding a C API for coroutines/awaitables” thread. What is so attractive about C that makes it more desirable than writing code in python?

4 Likes

Well, the situation is a bit different here though, isn’t it?

Suppose you want to connect Python to an external bigint or even extended precision library, which will in all likelihood not be written in Python but in C, C++, Rust, what have you. Then I do think the functionality of “get the actual number out of a number box” is fairly core to what you are trying to achieve with a number type.

Along the same lines, you could argue to deprecate and scrap PyLong_FromLong, PyLong_ToLong, etc. methods, since they duplicate functionality available already with to_bytes and from_bytes. [Edited to add:] So there is a tradeoff to be had between providing useful core functionality accessible from C and not duplicating anything that can reasonably simply and quickly be done with those building blocks.

4 Likes

A difference is that one connects Python to C’s native numeric types, which, given that this is the C-API, is a pretty fundamental operation – albeit a lossy one.
To connect to a some external bigint library, you’ll need to write extra glue code. You have the portable but perhaps slow way (to_bytes), and if there’s a need, we could expose a bit of the internals to give you a faster way with higher maintenance costs.

Another difference is that the policy for adding new API is much different now than it was when PyLong_FromLong was added. Python is more mature and conservative, and bar is higher now.
And it’s also much higher for deprecating and scrapping stuff than for adding new stuff.

Anyway, I seem to have buried Greg’s suggestion in discussion that’s might not be relevant. This is the best next step:

FWIW I’m documenting the existing solution in [docs] Mention how to get/set a bigint PyLong via the C API by gpshead · Pull Request #101270 · python/cpython · GitHub.

2 Likes

I’m in favour of adding a C API. If we say “call int.to_bytes using PyObject_CallMethod()”, then C developers will decide that is too slow and access the internal data structure, whether we like it or not.

longint_repr.h is #included in Python.h so the internals are fully visible. I don’t know why, but they are.

The decimal module in the standard library is an example. With an API to create a long from digits, it wouldn’t need to.

We are moving to 30 bit digits internally, although 15 bits are still supported, so an API that copied to and from a 30 bit digit array would make sense.

4 Likes