Yes 1 and 2 are the original. I am trying to clearly state each of the rules.
3 is that for many class inheritances you cant be earlier than the lenth of your bases.
object->A->B
object->C
When we inherit from B,C we may get something like object->A->B->C–>D not B->A-> object ->C->D.
That means to test of B we need to test 3 and 4 and for C 2,3,4. There would be no reason to test 1,2,3,4,5. Especially since D only needs to test 5. The other question of order as currently tests are 5,4,3,2,1. Thus there is strictly single inherited and a second proper ordered type to consider.
To make it more clear I have made some (hopefully correct) implementations for you to look over.
/** For types with short or random ordering do a linear search*/
int subtype_slot_linear(PyTypeObject *a, PyTypeObject* b)
{
Py_ssize_t i, n;
PyObject *a_mro = a->tp_mro;
n = PyTuple_GET_SIZE(a_mro);
for (i = 0; i < n; i++) {
if (PyTuple_GET_ITEM(a_mro, i) == (PyObject *)b) {
return 1;
}
}
return 0;
}
/** For types that are strictly single inherited they must have a match by position.*/
int subtype_slot_single(PyTypeObject *a, PyTypeObject* b)
{
Py_ssize_t an, bn;
PyObject *a_mro = a->tp_mro;
PyObject *b_mro = b->tp_mro;
an = PyTuple_GET_SIZE(a_mro);
bn = PyTuple_GET_SIZE(b_mro);
if (an<bn)
return 0;
return PyTuple_GET_ITEM(a_mro, an-bn) == (PyObject* b);
}
/** For a properly inherited object with multiple inheritance were every parent sequence appears in the correct order (a child never proceeds its parent in an mro) */
int subtype_slot_ordered(PyTypeObject *a, PyTypeObject* b)
{
Py_ssize_t i, an, bn;
PyObject *a_mro = a->tp_mro;
PyObject *b_mro = b->tp_mro;
an = PyTuple_GET_SIZE(a_mro);
bn = PyTuple_GET_SIZE(b_mro);
/*
* Consider optimum type checks for a diamond inheritance pattern.
* Orders for object->A->B with object->C to get D (shown in MRO order):
*
* Examples of MRO orders:
* - D <- C <- B <- A <- object
* - D <- B <- C <- A <- object
* - D <- B <- A <- C <- object
*
* Key assumptions about "ordered" inheritance:
* - A class `X` is considered "ordered" relative to another class `Y` if `X` appears
* before `Y` in the MRO subset being searched.
* - Patterns like `B <- D <- ? <- ? <- ?` are not "ordered" because `D` appears
* before `B`, violating the assumption.
*
* Search logic for subsets of the MRO:
* - For `A`: Search slots 3, 2, 1 (skip slot 0, which represents the class itself).
* - For `B`: Search slots 2, 1.
* - For `C`: Search slots 3, 2, 1.
* - For `D`: Search slot 0 only (as it represents the class itself).
* - For `E`: Shortcut the search (no relevant entries in the MRO subset).
*
* This logic ensures that subsets of the MRO are searched efficiently while respecting
* the ordered assumption. The indexing of the MRO follows Python's tuple representation,
* where slot 0 represents the class itself, and subsequent slots represent parent classes.
*/
/*
* This loop uses a `do-while` construct instead of the more common `while` loop.
* The rationale for this choice is based on reducing unnecessary instructions:
*
* 1. A `while` loop requires an initial condition check before entering the loop.
* This adds an extra branch instruction, even though the loop is guaranteed
* to execute at least once when `bn < an`.
*
* 2. A `do-while` loop eliminates this initial check, reducing the instruction
* count for the first iteration. This makes the loop more efficient on most
* instruction sets.
*
* 3. The logic of this function ensures that the loop will only execute when
* `bn < an`, so the `do-while` construct is safe and avoids unnecessary
* execution of the loop body.
*
* Note: While `do-while` loops are less common and may seem unusual, this choice
* is deliberate to optimize performance in tight loops where instruction count
* matters. On some advanced CPUs with predication or branch prediction, the
* difference may be negligible, but this approach remains a safe and efficient
* default for most architectures.
*/
if (bn<an) {
i = an-bn;
do {
if (PyTuple_GET_ITEM(a_mro, i) == (PyObject *)b) {
return 1;
}
i--;
} while (i>0);
else
return (PyTuple_GET_ITEM(a_mro, 0) == (PyObject *)b);
return 0;
}
I hope it helps answer your questions. And thanks so much for the feedback.
It took me a while to understand what you’re trying to say because you’re somehow listing the inheritance in the opposite order of Python’s convention while using a base-1 index.
Anyway, I don’t think it’s a valid optimization because we can’t actually know if C comes before B in D’s inheritance chain when we test if B is a superclass of D, so assuming that you can simply test 3 and 4 for B will fail to find B when it’s at 2, when B comes before C in D’s inheritance chain.
The else clause isn’t needed if you change bn<an to bn<=an. If fact, the if statement isn’t really needed if you change the do-while loop to a while loop or a for loop:
for (i = an - bn; i >= 0; i--) {
if (PyTuple_GET_ITEM(a_mro, i) == (PyObject *)b) {
return 1;
}
}
But again I don’t think this is a valid optimization for the reason above unless I misunderstood something.
I tried to explain it in my words but I fear that my language difficulties may be interfering. So (I) fed my reply through an AI to help turn my meandering style into something more concise. I then worked with it to make sure that it was properly framed in mro tuple style and checking it for accuracy. The AI provided additional insights, which I reviewed and included where appropriate. I hope that using that tool will aid with making my explanation more clear. Your feed back on this topic is valuable. We can discuss the for loop version that you proposed after we resolve if this is a valid optimization as it would be moot otherwise. And with the assistance of the AI… (drum roll)
Explanation Using Python MRO Tuple Order
The optimization relies on the assumption that the MRO (Method Resolution Order)
for the type being checked (D) has been validated to follow Python’s rules for
inheritance ordering. This ensures every child precedes its parent in the MRO.
MRO Constraints
When D is created, its MRO is determined based on Python’s inheritance rules.
For example, if D inherits from B and C, the MRO might look like:
(D, C, B, A, object)
This ordering ensures:
D appears first (index 0).
Parents (C, B, etc.) follow in order of precedence.
The base class object appears last.
Abstract Representation of B’s MRO
Since B has an MRO length of 3 (len(mro_b) == 3), its MRO can be abstractly
represented as: (B, ?, object)
Here:
B is the class itself.
? represents the parent class of B.
object is the root base class.
Optimization Logic (Using Python Tuple Order)
Given B’s MRO length of 3, it can only occupy certain positions in D’s MRO.
Specifically, B must appear in positions 1 or 2 (using Python tuple order).
Any other position (e.g., 0, 3, or 4) would violate MRO constraints:
B cannot appear before D (index 0).
B cannot appear after its own parent classes (A, object).
Instance Check Validation
When D is created, Python validates that its parents (A, B, C) follow
proper ordering rules. This allows us to optimize instance checks by limiting
searches to positions 1 and 2 in D’s MRO.
Example
If D has an MRO of: (D, C, B, A, object)
And B has an abstract MRO of: (B, ?, object)
B can only appear in positions 1 or 2 of D’s MRO. Testing positions
outside this range is unnecessary and violates MRO constraints.
Addressing Concerns About MRO Validity
(AI) Python’s MRO is determined using the C3 linearization algorithm, which ensures
that every child precedes its parent and that parents are ordered consistently
across the inheritance chain. This means that B cannot appear in unexpected
positions (e.g., after C if B precedes C in the inheritance hierarchy).
Therefore, the optimization is valid as long as the MRO remains unchanged.
Rare Modifications to MRO
(AI) While Python discourages dynamic modifications to class inheritance, it is
technically possible to alter a class’s parent classes at runtime (e.g., by
modifying the __bases__ attribute). Such changes would invalidate the MRO
assumptions and could cause the optimization to fail. However, these cases
are rare and typically avoided in well-designed systems.
Summary
This optimization is valid because the MRO ordering is validated during type
creation and remains consistent during runtime. Rare modifications to parent
classes after creation could invalidate this assumption, but such changes are
discouraged in Python.
Ahh I was confused by your reversed index in your original post, where your 1,2,3,4,5 really meant 4,3,2,1,0 in Python’s indexing rules.
The “ordered” optimization makes total sense now. And I now see you have the if statement to skip testing D if bn<an, and you have the do-while loop because i>0 is always true in the first iteration. These are micro-optimizations but every little bit counts.
Yeah but then it’ll cost a name-based key lookup. So yeah definitely try the slot approach first for the hash table optimization to get a sense of how much performance improvement you can get for a large multiple inheritance chain.
Note that for an internal API you can use _Py_hashtable_new_full instead of creating a dict/set object for a hash table with minimal overhead.
So that means a prefabed key looking up _check equivalent hashcode in the types dict and the one frozen hashset to return. Don’t suppose i could convert a type hash code directly into key and then just use presence in the original type hash dict? That would be a bit too abusive even for me.
Alright I think I have the major pieces for the experiment. I just need to analyze to determibe all entry points and their requirements so I can insert the slot.
I may try something tricky on the random order types by computing a function of the type hash id and then use the actual mro as the table. But construction of ordered set from high entropy words may not be a viable option due to the expense. If it is viable then all i would need is the blend code and the give up length (bit field as part of blend word) which tells you the maximum tests before giving up. The burden for this is low to test, but has a high setup cost.
Edit Strike that. Perfect hash code algorithm is too short of range to be meaningful
Is it worth considering the position tracking cache approach? Each time a class is used in an mro, it sets a bit in the cache indicating how close it is to the end. When we are testing we take the cache and pull off the lowest bits up to a nibble which computes the number of zeros leading to the first one. This allows us to skip through the mro tree testing only positions that are valid for the class.
For many types this will allow testing in just a few operations and is efficient at avoiding long chain misses. It would be strictly better than linear search though the change of search order may change effectiveness.
