Using tagged pointers to support efficient integer operations

Core Development
1

Integers are ubiquitous, both in Python code and the virtual machine.
However our representation of integers is somewhat clunky and inefficient.

There is an old technique for handling ints efficiently in dynamic language VMs, called tagged pointers.
A normal object pointer always has its low bits set to zero, as objects are 8 or 16 byte aligned in memory.
We can use those low bits as “tags” to denote the meaning of the high bits.
Historically, the low bit has been set to zero to indicate that the high bits are a pointer, and to 1 to indicate that the high bits are an integer.

We already use another tagging scheme within the interpreter and in the frame stack, the tag indicating whether the reference is borrowed.

This techniques is used in many older VMs and runtimes, including many lisps and Smalltalk.
It is also used in newer VMs, including Ruby.
It is not used in high-performance javascript VMs, because all numbers in JS are floats, so a different scheme is used called “Nan boxing”

Why do this?

Speed.

Python is notoriously slow at integer handling. While tagged integers are not as fast as C integers, they are at least an order of magnitude faster than the boxed integers that Python currently uses. The tags will add some small cost to non-integer operations, but very little as most operations already know whether they are operating on an int or another type.

How would we implement this?

Fortunately, there is no need to implement this all at once, everywhere.
We would add it to the interpreter first, using tagged ints to support faster iteration and arithmetic.
Then we would add it to a few core objects that make heavy use of ints, such as range and enumerate.
Thereafter, we would broaden the use of tagged pointers, adding support for them to builtin collections like list, tuple and dict.
Finally, we would add them to the C API so that third-party code can avoid the overhead of tagged pointer ↔ PyObject * conversions.

Tagging schemes

The exact tagging scheme we use is likely to change and be a result of experimentation and experience, but here is a possible scheme

20 Likes
2

Which CPython release do you think would contain this implementation?

3

No particular version, as we would implement this incrementally.
Some very narrow use of tagged ints might happen in 3.14.

4

Should this be a PEP?

5

If this is our first exposure of tagged pointers to CPython C API users in the form of an opaque PyObject* that code may otherwise attempt to dereference… we should move with care here. If these aren’t intended to “escape” internal-only uses then I do not think it matters as much.

Past relevant discussions:

We already use another tagging scheme within the interpreter and in the frame stack, the tag indicating whether the reference is borrowed.

for those not deep in the context of code daily, got links to where in the code we do this today?

6

If these aren’t intended to “escape” internal-only uses then I do not think it matters as much.

The current implementation explicitly takes care to not “escape” to external C API. It is explicitly limited to the evaluation stack, the fields of the internal frame struct, and cell objects. We convert back to PyObject * when it escapes.

for those not deep in the context of code daily, got links to where in the code we do this today?

See cpython/Include/internal/pycore_stackref.h at main · python/cpython · GitHub

Especially the parts that use Py_TAG_DEFERRED. The evaluation stack (localsplus and a few other fields) was changed to use _PyStackRef in gh-117139: Convert the evaluation stack to stack refs by Fidget-Spinner · Pull Request #118450 · python/cpython · GitHub .

Should this be a PEP?

I think implementing it within CPython doesn’t need a PEP. But once it exposes itself to third party libraries in the C API, it needs a PEP.

3 Likes
7

The initial use of tagged pointers is going to be very limited in scope, probably only on the evaluation stack. That clearly won’t need a PEP.

Then we’ll broaden the use to all of the frame stack, which is a larger change.
I think it is good to keep people informed, but I don’t think that needs a PEP as there will be no language change and no API change.

However, when we do expose these in the C API, that would need at least one PEP.
But, but that point, I expect we will already want to be proposing PEP(s) for a new C API anyway.
That API would use opaque references, like HPy. We would probably implement those references using tagged pointers, but that would be an implementation detail.

What part(s) do you think would need a PEP?

1 Like
8

A PyObject * is a pointer. Making it a tagged pointer would be lying to both the C compiler and to API consumers. We won’t do that.

Using an opaque one word struct or union is the most likely approach, especially as we already do that for the _PyStackRef tagged pointer in the interpreter.

Using struct or unions gives quite good type safety, especially compared to using pointers, which is a real help when converting code from using PyObject * to using tagged pointers.

3 Likes