Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#572 closed enhancement (worksforme)

study alternatives to PyType_IsSubtype

Reported by: mhansen Owned by: somebody
Priority: minor Milestone: Dupe/Invalid
Component: Optimization Keywords: needinfo
Cc: scoder, mhansen

Description (last modified by scoder)

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;
        }
}

Change History (6)

comment:1 Changed 4 years ago by scoder

  • Owner changed from scoder to somebody

comment:2 Changed 4 years ago by scoder

  • Description modified (diff)

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.

comment:3 Changed 4 years ago by scoder

  • Cc scoder mhansen added

comment:4 Changed 4 years ago by scoder

  • Keywords needinfo added

comment:5 Changed 4 years ago by scoder

  • Resolution set to worksforme
  • Status changed from new to closed

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

comment:6 Changed 4 years ago by robertwb

  • Milestone changed from wishlist to Dupe/Invalid
Note: See TracTickets for help on using tickets.