# Fast Subtype Checking for Single Inheritance

**URL:** <https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630>\
**Category:** Ideas\
**Created:** [May 11, 2025, 10:50pm UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630 "2025-05-11T22:50:52Z")\
**Posts on this page:** 9\
**Page:** 2

<div class="post-metadata">

**Author:** ![Thrameos](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/thrameos/32/22312_2.png) [@Thrameos](https://discuss.python.org/u/Thrameos)\
**Post date:** [May 19, 2025, 1:03pm UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/21 "2025-05-19T13:03:04Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Thrameos](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/thrameos/32/22312_2.png) [@Thrameos](https://discuss.python.org/u/Thrameos)\
**Post date:** [May 19, 2025, 1:20pm UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/22 "2025-05-19T13:20:00Z")

</div>

Let me rephrase. If we are using a slot based implementation, we would have 4 implementations to choose from.

1. strict single inherited
2. ordered
3. hash (random, long, and arbitrary)
4. linear (random, short, and arbitrary)

Ordered and strictly ordered are strictly less tests than linear. (Speed depends on implementation)

---

<div class="post-metadata">

**Author:** ![Thrameos](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/thrameos/32/22312_2.png) [@Thrameos](https://discuss.python.org/u/Thrameos)\
**Post date:** [May 20, 2025, 5:49am UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/23 "2025-05-20T05:49:15Z")

</div>

@blhsing

To make it more clear I have made some (hopefully correct) implementations for you to look over.

```c
/** 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.

---

<div class="post-metadata">

**Author:** ![blhsing](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/blhsing/32/25812_2.png) [@blhsing](https://discuss.python.org/u/blhsing)\
**Post date:** [May 20, 2025, 8:51am UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/24 "2025-05-20T08:51:28Z")

</div>

> [@Thrameos](#):
>
> 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.

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.

> [@Thrameos](#):
>
> ```python
> 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);
> 
> ```

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:

```python
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.

---

<div class="post-metadata">

**Author:** ![Thrameos](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/thrameos/32/22312_2.png) [@Thrameos](https://discuss.python.org/u/Thrameos)\
**Post date:** [May 20, 2025, 10:30am UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/25 "2025-05-20T10:30:12Z")

</div>

> [@blhsing](#):
>
> 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

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.

---

<div class="post-metadata">

**Author:** ![blhsing](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/blhsing/32/25812_2.png) [@blhsing](https://discuss.python.org/u/blhsing)\
**Post date:** [May 21, 2025, 9:22am UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/26 "2025-05-21T09:22:18Z")

</div>

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.

> [@Thrameos](#):
>
> The slot approach will give the best possible results. We can try the dict option without a slot by placing the look up table in the types dict.

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`](https://github.com/python/cpython/blob/c740fe3bd092911d9e474bcc0eed2a009482be9f/Python/hashtable.c#L323) instead of creating a dict/set object for a hash table with minimal overhead.

---

<div class="post-metadata">

**Author:** ![Thrameos](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/thrameos/32/22312_2.png) [@Thrameos](https://discuss.python.org/u/Thrameos)\
**Post date:** [May 21, 2025, 12:10pm UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/27 "2025-05-21T12:10:02Z")

</div>

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.

Thanks for being a great sounding board.

---

<div class="post-metadata">

**Author:** ![Thrameos](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/thrameos/32/22312_2.png) [@Thrameos](https://discuss.python.org/u/Thrameos)\
**Post date:** [May 21, 2025, 11:14pm UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/28 "2025-05-21T23:14:28Z")

</div>

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**

---

<div class="post-metadata">

**Author:** ![Thrameos](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/thrameos/32/22312_2.png) [@Thrameos](https://discuss.python.org/u/Thrameos)\
**Post date:** [May 22, 2025, 2:30am UTC](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630/29 "2025-05-22T02:30:49Z")

</div>

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.

[Previous page](https://discuss.python.org/t/fast-subtype-checking-for-single-inheritance/91630.md?page=1)