study alternatives to PyType_IsSubtype

[robertwb]

This is an old ticket from the Sage Trac which more appropriately belongs here:

Lots of our Pyrex code is going to be using PyObject_TypeCheck as a replacement for isinstance. This is a C macro (defined in python's object.h file), HOWEVER if the types don't match exactly it has to call the API PyType?_IsSubType. The code for that function is shown below. Probably we can write something somewhat faster that covers many of the situations we need, because we don't need to worry about the MRO (method resolution order) stuff.

/* type test with subclassing support */

int
PyType_IsSubtype(PyTypeObject *a, PyTypeObject *b)
{
        PyObject *mro;

        if (!(a->tp_flags & Py_TPFLAGS_HAVE_CLASS))
                return b == a || b == &PyBaseObject_Type;

        mro = a->tp_mro;
        if (mro != NULL) {
                /* Deal with multiple inheritance without recursion
                   by walking the MRO tuple */
                Py_ssize_t i, n;
                assert(PyTuple_Check(mro));
                n = PyTuple_GET_SIZE(mro);
                for (i = 0; i < n; i++) {
                        if (PyTuple_GET_ITEM(mro, i) == (PyObject *)b)
                                return 1;
                }
                return 0;
        }
        else {
                /* a is not completely initilized yet; follow tp_base */
                do {
                        if (a == b)
                                return 1;
                        a = a->tp_base;
                } while (a != NULL);
                return b == &PyBaseObject_Type;
        }
}

Migrated from http://trac.cython.org/ticket/572

[robertwb]

scoder changed owner from scoder to somebody
commented

[robertwb]

scoder changed description from

This is an old ticket from the Sage Trac which more appropriately belongs here:

Lots of our Pyrex code is going to be using PyObject_TypeCheck as a replacement for isinstance. This is a C macro (defined in python's object.h file), HOWEVER if the types don't match exactly it has to call the API PyType?_IsSubType. The code for that function is shown below. Probably we can write something somewhat faster that covers many of the situations we need, because we don't need to worry about the MRO (method resolution order) stuff.

/* type test with subclassing support */

int
PyType_IsSubtype(PyTypeObject *a, PyTypeObject *b)
{
        PyObject *mro;

        if (!(a->tp_flags & Py_TPFLAGS_HAVE_CLASS))
                return b == a || b == &PyBaseObject_Type;

        mro = a->tp_mro;
        if (mro != NULL) {
                /* Deal with multiple inheritance without recursion
                   by walking the MRO tuple */
                Py_ssize_t i, n;
                assert(PyTuple_Check(mro));
                n = PyTuple_GET_SIZE(mro);
                for (i = 0; i < n; i++) {
                        if (PyTuple_GET_ITEM(mro, i) == (PyObject *)b)
                                return 1;
                }
                return 0;
        }
        else {
                /* a is not completely initilized yet; follow tp_base */
                do {
                        if (a == b)
                                return 1;
                        a = a->tp_base;
                } while (a != NULL);
                return b == &PyBaseObject_Type;
        }
}

to

This is an old ticket from the Sage Trac which more appropriately belongs here:

Lots of our Pyrex code is going to be using PyObject_TypeCheck as a replacement for isinstance. This is a C macro (defined in python's object.h file), HOWEVER if the types don't match exactly it has to call the API PyType?_IsSubType. The code for that function is shown below. Probably we can write something somewhat faster that covers many of the situations we need, because we don't need to worry about the MRO (method resolution order) stuff.

/* type test with subclassing support */

int
PyType_IsSubtype(PyTypeObject *a, PyTypeObject *b)
{
        PyObject *mro;

        if (!(a->tp_flags & Py_TPFLAGS_HAVE_CLASS))
                return b == a || b == &PyBaseObject_Type;

        mro = a->tp_mro;
        if (mro != NULL) {
                /* Deal with multiple inheritance without recursion
                   by walking the MRO tuple */
                Py_ssize_t i, n;
                assert(PyTuple_Check(mro));
                n = PyTuple_GET_SIZE(mro);
                for (i = 0; i < n; i++) {
                        if (PyTuple_GET_ITEM(mro, i) == (PyObject *)b)
                                return 1;
                }
                return 0;
        }
        else {
                /* a is not completely initilized yet; follow tp_base */
                do {
                        if (a == b)
                                return 1;
                        a = a->tp_base;
                } while (a != NULL);
                return b == &PyBaseObject_Type;
        }
}

commented

This code looks very fast and cache efficient. It basically runs through the array of pointers that underlies the MRO tuple and compares the pointers with the type pointer in question. The MRO tuple should usually fit into a single cache line, so the whole algorithm should finish within a few CPU cycles for reasonably sized inheritance hierarchies.

Is there any special case that you want to see optimised? Otherwise, I don't think there's much you could do better.

[robertwb]

scoder changed cc to scoder, mhansen
commented

[robertwb]

scoder changed keywords to needinfo
commented

[robertwb]

scoder changed resolution to worksforme
status from new to closed
commented

Closing this since there hasn't been any further interest and it's not clear why this is supposed to be a problem.

[robertwb]

@robertwb changed milestone from wishlist to Dupe/Invalid
commented