Bias refcounts by -1 and eliminate the last dependent write

[sweeneyde]

In this interesting 2014 C++ talk by Andrei Alexandrescu (slides), the speaker mentions that ref-counting performance of a shared pointer can improve by biasing all refcounts by -1. That way, we could change:

static inline void _Py_DECREF(PyObject *op)
{
    if (--op->ob_refcnt == 0) {
        Py_TYPE(op)->tp_dealloc(op);
    }
}

to

static inline void _Py_DECREF(PyObject *op)
{
    if (op->ob_refcnt) {
        op->ob_refcnt--;
    }
    else {
        // No decrement needed.
        // Try not to write to the soon-to-be-freed memory.
        Py_TYPE(op)->tp_dealloc(op);
    }
}

Since reference counts are typically small, the percentage of memory writes saved could be significant.

For compatibility, we could even define

static inline Py_ssize_t _Py_REFCNT(const PyObject *ob) {
    return ob->ob_refcnt + 1;
}

static inline void _Py_SET_REFCNT(PyObject *ob, Py_ssize_t refcnt) {
    ob->ob_refcnt = refcnt - 1;
}

[oraluben]

static inline void _Py_DECREF(PyObject *op)
{
    if (op->ob_refcnt) {
        op->ob_refcnt--;
    }
    else {
        // No decrement needed.
        // Try not to write to the soon-to-be-freed memory.
        Py_TYPE(op)->tp_dealloc(op);
    }
}

do you mean this? otherwise _Py_DECREF(op) on whose rc is 1 won't deallocate it.

static inline void _Py_DECREF(PyObject *op)
{
    if (op->ob_refcnt > 1) {
        op->ob_refcnt--;
    }
    else {
        // No decrement needed.
        // Try not to write to the soon-to-be-freed memory.
        Py_TYPE(op)->tp_dealloc(op);
    }
}

[sweeneyde]

That would be one approach, but it's not what Andrei Alexandrescu proposes.

I mean to suggest representing the concept of "this object has one reference" using the data ob_refcnt = 0. Generally, if an object has n references to it, the proposal is to represent that as ob_refcnt = n-1. The only effective difference between what you suggest and what I suggest would be comparing to 0 rather than comparing to 1 in Py_DECREF. The supposed advantage of comparing to 0 is that the size of the code generated by Py_DECREF might be a few bytes smaller.

[oraluben]

I see, thanks for the clarification!

[gvanrossum]

This is worth an experiment to see if it makes a difference, but I worry that it will break the stable ABI, and also that there are many additional APIs around refcounting that will have to be adjusted before it passes all the tests.

[markshannon]

I would recommend changing the name of ob_refcnt to ob_refcnt_less_one to make it clear to anyone accessing the field directly what is going on. Any code that uses the macros would be fine.
I think, in theory, this doesn't break the ABI as that requires the use of functions to modify the refcount.

[markshannon]

There are two parts to this change:

1. Not modifying the refcount if an object is about to be deallocated.
2. Biasing the refcount, so that the test is against 0, rather than 1.

Change 1 is less likely to break anything.
It might be worth assessing the impact of the two changes independently.

[sweeneyde]

I don't think I have the bandwidth for this at the moment, so if anyone wants to try this out, feel free.

[brandtbucher]

There are two parts to this change:

1. Not modifying the refcount if an object is about to be deallocated.
2. Biasing the refcount, so that the test is against 0, rather than 1.

Change 1 is less likely to break anything. It might be worth assessing the impact of the two changes independently.

Change 1 by itself sounds like a nightmare for finalizers, weakrefs, GC, etc. There would now be two very different meanings of Py_REFCNT(o) == 1:

• o is currently being deallocated
• o is alive and well

I don't see much value in testing change 2 without change 1, and I don't really see how we can test only change 1 without giving ourselves lots of headaches and extra work.

I think the easiest path forward would be to try both, since that shouldn't require much more than mechanically changing a bunch of places where we check for certain refcount values. At least that would give us an idea of how beneficial this could be (while ignoring compatibility for the time being).

Edit:

Ah, I think I misunderstood the original proposal. Biasing doesn't change the fact that we can't tell living and dying objects apart.

[brandtbucher]

PyObject_HEAD_INIT sets it to 1 without naming it explicitly. Trying to think of other places that might happen...

[sweeneyde]

I also think some of the GC-nightmareishness you mention still applies if both changes are implemented, it's just that Py_REFCNT(o) == 0 can take on those two meanings. Maybe there's some way to distinguish complicated tp_dealloc slots with side effects from simple ones that just call free()? Then set ob_refcnt_minus_one to -1 but only for the side-effect-y ones?

[brandtbucher]

We might prototype it with an opt-in flag in tp_flags (Py_TPFLAGS_NO_FUNNY_BUSINESS?), and apply it to as many builtins as we can...

[brandtbucher]

Or, easier: just check that Py_TYPE(op)->tp_dealloc == PyBaseObject_Type.tp_dealloc && Py_TYPE(op)->tp_free == PyBaseObject_Type.tp_free.

[oraluben]

Change 1 by itself sounds like a nightmare for finalizers, weakrefs, GC, etc. There would now be two very different meanings of Py_REFCNT(o) == 1:

• o is currently being deallocated
• o is alive and well

That's true, GC (e.g. PyObject_CallFinalizerFromDealloc) and finalizer of specific types (e.g. _PyIOBase_finalize) both determine if the object is alive based on Py_REFCNT(o).
I have some early-stage changes at https://github.com/oraluben/cpython/tree/test-rc, and on the passed pyperformance tests (some failed because of incomplete implementation) I don't see significant improvement in time or binary size.