PyLongObject: just use GMP?

Core Development
29

I’ll leave the math and optimization to you mathematicians, but I do have some engineering input.

Integers fall (very roughly) into 2 categories, numbers which are used by everywhere to count things and bigints which have niche, but very important, uses as number theory integers to build useful things like crypto libraries.

So while we want big ints to have nice asymptotic behavior, we want numbers (ints that fit into a single machine word) to be generally fast*.

In practical terms that means we want numbers to look like this:

struct _py_compact_int {
    PyObject header;
    intptr_t tagged_value;
} PyCompactIntObject;

which means we want general purpose ints to look like this:

struct _pylong {
    PyObject header;
    union {
        intptr_t tagged_value;
        BigIng_t bigint_value;
    };
} PyLongObject;

with the important property that the first word of BigInt_thas low bit zero when cast to intptr_t; all aligned pointers have this property.

With this struct in place, it should be possible to swap 3rd party implementation of BigInt_t in and out relatively easily, for experimentation and development.

Some prior discussion: More efficient implementation of integers · Issue #548 · faster-cpython/ideas · GitHub

* Currently we special case “compact” ints, i.e. ints in range(-(2**32), 2**32+1), to avoid branching and to use fewer machine level operations, but tagged ints would be faster; almost as fast as C. It is all the memory management that is slow. A fixed size int will help us reduce the memory management overhead as well.

8 Likes