Description

Fidget-Spinner

opened on Mar 21, 2024

Issue body actions

Feature or enhancement

Proposal:

This issue mostly mirrors Mark's original one at faster-cpython/ideas#632.

As part of PEP 703, tagged pointers will help achieve deferred reference counting.

Tagged pointers will also help the default GIL builds in 3.14 and future with unboxed ints.

Here's the initial design (open for comments):

We change the evaluation stack from PyObject * to PyTaggedObject. PyTaggedObject looks like this.

typedef union PyTaggedObject {
    PyObject *obj;
    uintptr_t bits;
} PyTaggedObject;

Note: I am limiting the tagged pointers to just the evaluation stack (this is up for debate as well). The main reason is to keep the change as minimally invasive as possible for 3.13 and not leak out any implementation details for now. For example, I don't want to support tagged pointers in C API functions. This may/will change in 3.14.

Thanks to the cases generator, we can then autogenerate all the proper accessors to said object. For example, a stack effect of PyObject * will generate the code effect.obj, while a stack effect of PyTaggedObject (the new default) will generate the code (PyObject *)(effect.bits & ~TAGS) or something similar.

Unboxed ints will also help both free-threaded and non-free-threaded builds by reducing refcounting even more for simple arithmetic operations (and making integer operations native). However, I am aiming for deferred tags in 3.13, and anything else is a plus.

Further note: due to wanting to respect immediate finalizers, we are not deferring that many objects. So this may not be a win on default builds. On free-threaded builds, I see a slight (10%) speedup on fibonacci microbenchmarks. Will benchmark on the default bulid as well and see the results.

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

Linked PRs

• gh-117139: Set up the tagged evaluation stack #117186
• gh-117139: Add header for tagged pointers #118330
• gh-117139: Convert the evaluation stack to stack refs #118450
• gh-117139: Fix missing semicolon #118573
• gh-117139: Fix a few wrong steals in bytecodes.c #121127
• gh-117139: A StackRef Debugging Mode #121134
• gh-117139: Add _PyTuple_FromStackRefSteal and use it #121244
• gh-117139: Fix an incorrect borrow in bytecodes.c #122318
• gh-117139: Replace _PyList_FromArraySteal with stack ref variant #122830
• gh-117139: Fix a few _PyStackRef related bugs #122831
• gh-117139: Garbage collector support for deferred refcounting #122956

### Tasks
- [ ] https://github.com/python/cpython/issues/118926
- [ ] https://github.com/python/cpython/issues/118930

Activity

1. Fidget-Spinner

   added

   type-featureA feature request or enhancementA feature request or enhancement

   on Mar 21, 2024
2. Fidget-Spinner

   self-assigned this

   on Mar 21, 2024
3. gvanrossum commented on Mar 21, 2024

   

   gvanrossum

   on Mar 21, 2024

   Member

   More actions

   So the mentions of unboxed ints are speculative and not part of the initial implementation, right?

   And the tagged pointers just have their tag bit(s) removed when used in the "blob of C code" that's the instruction definition's body. For example,

           inst(STORE_FAST, (value --)) {
               SETLOCAL(oparg, value);
           }
   

   would expand its body to

               SETLOCAL(oparg, (PyObject *)(value.bits & ~TAGS));

   How do pointers receive their tag bit? Does every stack push just "or in" the tag bit(s)?

   I recall trying to do this manually (before we had the generator) and it was a lot of work -- the code generator should make this much simpler. It also was quite a bit slower -- have you thought about this?

   My biggest question is what does the tag bit mean? Is there a specific section of PEP 703 I should read to learn more about this?
4. colesbury commented on Mar 22, 2024

   

   colesbury

   on Mar 22, 2024

   Contributor

   More actions

   My biggest question is what does the tag bit mean?

   PEP 703 doesn't go into detail about the tag bits. I'd expect it to match the description in Mark's issue, except with unboxed ints not part of the initial implementation:

   Tag	Meaning	Encoding
   00	Normal reference	(uintptr)ptr
   01	Deferred reference	((uintptr)ptr) + 1

   01 includes both immortal objects and those whose reference count has been deferred (but are not immortal).

   I recall trying to do this manually... It also was quite a bit slower

   We should only enable this in the free-threaded build to start. We do not want to introduce any performance regressions in the default build. If it turns out to be a net win for the default build, then we can consider enabling it there. Otherwise, we can revisit that in 3.14, if we pursue tagged integers.

   How do pointers receive their tag bit? Does every stack push just "or in" the tag bit(s)?

   Yeah, most pushes just "or in" the tag bit, which is an immortal check. So for, example GET_ITER currently has:

   cpython/Python/generated_cases.c.h

   Line 2922 in 40d75c2

   stack_pointer[-1] = iter;

   That might be generated instead as:

   #define PACK(obj) ((PyTaggedObject){.bits = (uintptr_t)obj | _Py_IsImmortal(obj)})
   
   stack_pointer[-1] = PACK(iter);

   For example, ... [STORE_FAST]

   I think we want to use tagged pointers in the locals as well as the evaluation stack, but it may be easier to start with just using tagged pointers the evaluation stack. In that case STORE_FAST will need extra refcounting to convert a tagged pointer into a regular object reference. For example,

   PyObject *obj = (PyObject *)(value.bits & ~TAGS);
   if ((value.bits & IS_DEFERRED) {
     Py_INCREF(obj);
   }
   SETLOCAL(oparg, obj);
   

   If we use tagged pointers for the locals as well, then we could skip the extra work in STORE_FAST.

   Motivation

   The primary motivation is to avoid reference count contention in multithreaded programs on things like functions/methods (in the free-threaded build). In particular, the benefit (from avoid reference counting contention) is going to be in LOAD_ATTR, LOAD_GLOBAL, and their variants.

   For example, currently LOAD_ATTR_SLOT has code that looks like:

   PyObject *attr = ...;
   Py_INCREF(attr);
   stack_pointer[-1] = attr;

   We want the generated code to instead look something like the following, but probably refactored with helper macros/functions:

   PyObject *attr = ...;
   PyTaggedObject attr_tag;
   if (_Py_IsImmortalOrDeferred(attr)) {
       attr_tag.bits = (uintptr_t)attr | IS_DEFERRED;
   }
   else {
       attr_tag.obj = attr;
   }
   stack_pointer[-1] = attr_tag;
5. colesbury

   added

   topic-free-threading

   on Mar 22, 2024
6. gvanrossum commented on Mar 23, 2024

   

   gvanrossum

   on Mar 23, 2024

   Member

   More actions

   Okay...

   So from this definition

   #define PACK(obj) ((PyTaggedObject){.bits = (uintptr_t)obj | _Py_IsImmortal(obj)})

   I gather that the tag bit is (by default) only set if the object is immortal. From your Motivation here (and also from the section on deferred refcounting in PEP 703) I take it that the tag bit would also be set for selected objects like functions and methods.

   Mark's original issue describes variants of INCREF/DECREF to check for the tag bit; presumably these variants should only be used in the interpreter.

   @Fidget-Spinner Good luck!
7. Fidget-Spinner

   added 2 commits that reference this issue on Apr 30, 2024

   gh-117139: Add header for tagged pointers (GH-118330)

   dc6b12d

   gh-117139: Fix missing semicolon (GH-118573)

   978fba5
8. SonicField

   added 2 commits that reference this issue on May 8, 2024

   pythongh-117139: Add header for tagged pointers (pythonGH-118330)

   6585a6f

   pythongh-117139: Fix missing semicolon (pythonGH-118573)

   2670633
9. markshannon commented on Jun 12, 2024

   

   markshannon

   on Jun 12, 2024

   Member

   More actions

   One thing to note:

   If we are going to use tagged ints, all plain "borrow" transformations will need to be removed, as it is impossible to borrow a PyObject * from a tagged int or vice-versa.
   Ultimately, we will want to extend the API that takes stack references to avoid having the double conversion ref -> PyObject * -> ref when calling common API functions that take PyObject *.

   In cases where it is known that the stack ref is not an int we could add StackRefNotInt_ToObjectBorrow and the reverse, so avoid the cost of two conversions.
10. Fidget-Spinner

    added 2 commits that reference this issue on Jun 26, 2024

    gh-117139: Convert the evaluation stack to stack refs (#118450)

    22b0de2

    gh-117139: Fix a few wrong steals in bytecodes.c (GH-121127)

    e6543da
11. mrahtz

    added 2 commits that reference this issue on Jun 30, 2024

    pythongh-117139: Convert the evaluation stack to stack refs (python#1…

    a8eaa06

    pythongh-117139: Fix a few wrong steals in bytecodes.c (pythonGH-121127)

    d2dc86f
12. 7 remaining items
13. colesbury

    added a commit that references this issue on Aug 6, 2024

    Merge branch 'main' into pythongh-117139-fix-steal

    b75aa5b
14. kumaraditya303

    added a commit that references this issue on Aug 7, 2024

    gh-117139: Fix an incorrect borrow in bytecodes.c (#122318)

    674a50e
15. colesbury

    added 7 commits that reference this issue on Aug 8, 2024

    pythongh-117139: Replace _PyList_FromArraySteal with stack ref variant

    6f00706

    pythongh-117139: Replace _PyList_FromArraySteal with stack ref variant

    47d3235

    pythongh-117139: Fix a few `_PyStackRef` related bugs

    e613606

    gh-117139: Fix a few `_PyStackRef` related bugs (#122831)

    736fe4d

    gh-117139: Replace _PyList_FromArraySteal with stack ref variant (#12…

    ab094d1

    pythongh-117139: Garbage collector support for deferred refcounting

    44d7dff

    gh-117139: Garbage collector support for deferred refcounting (#122956)

    e001027
16. blhsing

    added 4 commits that reference this issue on Aug 22, 2024

    pythongh-117139: Fix an incorrect borrow in bytecodes.c (python#122318)

    8ff32a1

    pythongh-117139: Fix a few `_PyStackRef` related bugs (python#122831)

    db3a8a5

    pythongh-117139: Replace _PyList_FromArraySteal with stack ref variant (

    d678b1c

    pythongh-117139: Garbage collector support for deferred refcounting (p…

    dd045df
17. Fidget-Spinner

    closed this as completedon Sep 18, 2024
18. navytux

    added a commit that references this issue on Mar 3, 2026

    golang: Fix XPyFrame_WhiteoutFastLocal for py3.14

    e9ce7b0

Issue actions