Tagged pointers, again. This time with deferred reference counting.

[markshannon]

Tagged pointers are standard optimization for dynamic languages.
In fact, of the major implementations of dynamic languages, CPython* is the only implementation that doesn't use them.
All the major JS engines uses tagged pointers, as does MRI for Ruby.

The reason we haven't implemented them so far is that implementing tagged pointers is fiddly and most likely not that much more efficient due to the conversions from tagged to non-tagged pointers across C API calls.

However, the acceptance of PEP 703 means we will need deferred reference counting. Deferred reference counting has a few parts, but the one of interest here is the need to tag pointers to show that they contain a (deferred) reference to the object pointed to.

In Sam Gross's NoGIL (for 3.9) repo, references are marked as deferred by setting the low bit.
Given that we then need to change every PyObject * in the frame stack to some sort of PyRef, we might as well tag some other values as well.

Tagging scheme

Given we already have GIL/NoGIL builds, and are likely to have JIT/NoJIT builds as well, lets not add another build option, so we want
to use the same tagging scheme on both 32 and 64 machines. Thus we must limit ourselves to two tag bits.

Tag	Meaning	Encoding
00	Normal reference	(uintptr)ptr
01	Deferred reference	((uintptr)ptr) + 1
10	Reserved/unused
11	Tagged integer	(val << 2) -1

We encode NULL as a deferred reference, so it is encoded as 1.
The tagged int 0 is encoded as -1.

The above tagging scheme is not necessarily the best. We can find out the best scheme empirically.

Operations

We will need the equivalent of Py_INCREF and Py_DECREF which would gain an extra branch, except for the rule that immortal objects always use deferred references, so we can eliminate the check.

Py_INCREF and Py_DECREF

Goes from

if ((obj->ob_refcnt & IMMORTAL_BIT) == 0) {
    obj->ob_refcnt++;    
}

to

#define DEFERRED_BIT 1
if ((obj.bits & DEFERRED_BIT) == 0) {
    ((PyObject *)obj.bits)->ob_refcnt++;
}

which should be faster.

Py_DECREF is similar

Py_XINCREF and Py_XDECREF are the same as Py_INCREF and Py_DECREF and NULL is encoded as a deferred reference.

Py_TYPE

Py_TYPE is more complex than before, however.

#define IS_INT_BIT 2
PyTypeObject *Py_TYPE(PyRef ref) {
    if (ref.bits & IS_INT_BIT) {
        return &PyLong_Type;
    }
    return ((PyObject *)(ref.bits & ~DEFERRED_BIT))->ob_type;
}

Storing tagged pointers in the heap.

We cannot store deferred references in the heap, as the cycle collector might not see them.
We can, however store tagged ints. The benefits and costs of doing this are unclear as yet.

---

Prior discussion of a different tagging scheme which included some tagged floats, but no deferred references and differed between 32 bit and 64 bit machines.

* PyPy and the various Tuffle based implementations do not used tagged pointers, but those aren't really major implementations.

[corona10]

cc @colesbury

Maybe related to this PR: python/cpython#110764

[markshannon]

See #678 for an improved version.