Ticket #572 (closed enhancement: worksforme)

Opened 4 years ago

Last modified 3 years ago

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) (diff)

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

Changed 4 years ago by scoder

  • owner changed from scoder to somebody

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.

Changed 4 years ago by scoder

  • cc scoder, mhansen added

Changed 4 years ago by scoder

  • keywords needinfo added

Changed 3 years ago by scoder

  • status changed from new to closed
  • resolution set to worksforme

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

Changed 3 years ago by robertwb

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