PyType_IsSubtype is doing excessive work in the common case

[itamaro]

BPO	45697
Nosy	@serhiy-storchaka, @sweeneyde, @Fidget-Spinner, @itamaro, @arhadthedev
PRs	bpo-45697: PyType_IsSubtype: Return early for identical type objects #29380 bpo-45697: Use PyObject_TypeCheck in type_call and binary_op1 #29392

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2021-11-04.10:41:48.112>
created_at = <Date 2021-11-03.01:12:41.206>
labels = ['interpreter-core', '3.11', 'performance']
title = 'PyType_IsSubtype is doing excessive work in the common case'
updated_at = <Date 2021-11-04.10:41:48.111>
user = '/~https://github.com/itamaro'

bugs.python.org fields:

activity = <Date 2021-11-04.10:41:48.111>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2021-11-04.10:41:48.112>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2021-11-03.01:12:41.206>
creator = 'itamaro'
dependencies = []
files = []
hgrepos = []
issue_num = 45697
keywords = ['patch']
message_count = 11.0
messages = ['405575', '405577', '405581', '405586', '405589', '405596', '405633', '405642', '405654', '405674', '405675']
nosy_count = 5.0
nosy_names = ['serhiy.storchaka', 'Dennis Sweeney', 'kj', 'itamaro', 'arhadthedev']
pr_nums = ['29380', '29392']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue45697'
versions = ['Python 3.11']

[itamaro]

Based on real world profiling data we collected, a vast amount of PyType_IsSubtype calls are coming from type_call, when it decides whether __init__ should run or not.

In the common case, the arguments to this call are identical, but the implementation still walks the MRO.

By returning early for identical types, the common case can be optimized with a non-trivial performance gain.

[sweeneyde]

Interesting. It seems like several call sites already check the equality case:

---- setobject.h: ----

#define PyFrozenSet_Check(ob) \
    (Py_IS_TYPE(ob, &PyFrozenSet_Type) || \
      PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type))

---- object.h: ----

static inline int _PyObject_TypeCheck(PyObject *ob, PyTypeObject *type) {
    return Py_IS_TYPE(ob, type) || PyType_IsSubtype(Py_TYPE(ob), type);
}
#define PyObject_TypeCheck(ob, type) _PyObject_TypeCheck(_PyObject_CAST(ob), type)

Perhaps it would be better to use PyObject_TypeCheck where applicable (such as in the type_call function you mention, and in abstract.c's binary_op1()).

[itamaro]

Dennis, you mean something like this? itamaro@92d46b2

sure, that would preempt the PyType_IsSubtype calls coming from these specific callsites, but the early return in PyType_IsSubtype would cover those as well as any other path, wouldn't it?

[arhadthedev]

Dennis, can PyFrozenSet_Check and _PyObject_TypeCheck get rid of Py_IS_TYPE invocation then, so PyType_IsSubtype becomes the only source of truth here?

[serhiy-storchaka]

The PyObject_TypeCheck() macro is used in performance critical cases. If it is not the case the PyType_IsSubtype() function can be used. Adding yet check in PyType_IsSubtype() will slow down more performance sensitive cases in which PyObject_TypeCheck() is used and speed up less performance sensitive cases. So there is no reason to add it.

[Fidget-Spinner]

Dennis, you mean something like this? itamaro@92d46b2

Not Dennis, but these changes looks good. As Serhiy mentioned, we can replace the hot callsites with PyObject_TypeCheck without slowing down PyType_IsSubtype.

[itamaro]

thanks for the feedback & discussion, I submitted a new PR

[serhiy-storchaka]

Creating a new type takes microseconds, and using PyObject_TypeCheck() instead of PyType_IsSubtype() can save nanoseconds. So, while this replacement looks harmless, its effect can hardly be measured even in microbenchmarks.

[itamaro]

thanks for the feedback Serhiy!

repeating my response from the PR here as well (not sure what's the proper etiquette.. :-) )

note that this code path is not for creating new types (which is slow as you say), but for creating new instances (which is quite fast).

I ran some synthetic benchmarks with this change and without it (on an opt build with PGO and LTO), and the gain is measurable:

build from main (commit acc89db which is the base commit for this PR):

>for _ in {1..10}; do ./main-opt/python -m timeit -n 10000 -s 'class Spam: pass' -- 'ten_k_spams = [Spam() for _ in range(10000)]'; done
10000 loops, best of 5: 896 usec per loop
10000 loops, best of 5: 887 usec per loop
10000 loops, best of 5: 857 usec per loop
10000 loops, best of 5: 838 usec per loop
10000 loops, best of 5: 847 usec per loop
10000 loops, best of 5: 863 usec per loop
10000 loops, best of 5: 845 usec per loop
10000 loops, best of 5: 902 usec per loop
10000 loops, best of 5: 890 usec per loop
10000 loops, best of 5: 875 usec per loop

build with this change applied (commit 2362bf6):

>for _ in {1..10}; do ./test-opt/python -m timeit -n 10000 -s 'class Spam: pass' -- 'ten_k_spams = [Spam() for _ in range(10000)]'; done
10000 loops, best of 5: 833 usec per loop
10000 loops, best of 5: 885 usec per loop
10000 loops, best of 5: 845 usec per loop
10000 loops, best of 5: 838 usec per loop
10000 loops, best of 5: 833 usec per loop
10000 loops, best of 5: 827 usec per loop
10000 loops, best of 5: 858 usec per loop
10000 loops, best of 5: 811 usec per loop
10000 loops, best of 5: 843 usec per loop
10000 loops, best of 5: 845 usec per loop

also worth noting that the previous approach (GH-29380) was implemented on the Instagram Server production workload in Meta/Facebook/Instagram (choose your favorite) and resulted measurable perf gain of around 0.2%

[serhiy-storchaka]

New changeset 2c045bd by Itamar Ostricher in branch 'main':
bpo-45697: Use PyObject_TypeCheck in type_call (GH-29392)
2c045bd

[serhiy-storchaka]

Thank you for your contribution Itamar.