https://github.com/python/cpython/commit/efeeb6cc1ba61c9cccbf39c0690b98b4135d201b commit: efeeb6cc1ba61c9cccbf39c0690b98b4135d201b branch: main author: Pieter Eendebak <[email protected]> committer: eendebakpt <[email protected]> date: 2026-11-01T20:35:16+01:00 summary:
gh-132042: Speed up slot lookup during class creation (#159479) * gh-132042: Speed up slot lookup during class creation Resolve the special method slots of a new class with one pass over each class dict along the MRO instead of one lookup per slot name and per class. A small static table maps slot names to slotdef indices; it also replaces the temporary dict in _PyType_InitSlotDefs() and the linear scan in has_slotdef(). Co-Authored-By: Claude Fable 5.1 <[email protected]> * Replace dead defensive checks in collect_slot_descrs() with asserts * Use the slot name table in update_slot() * Share the slot name table probe loop * review comments * gh-132042: Allow dict subclasses as tp_dict in the slot scan An extension may initialize tp_dict with a dict subclass before calling PyType_Ready(), so assert PyDict_Check() like find_name_in_mro() does. Co-Authored-By: Claude Fable 5.1 <[email protected]> * gh-132042: Test subclassing a type whose tp_dict is a dict subclass Add _testcapi.MyListDictSubclass, a static type like MyList whose tp_dict is initialized with a dict subclass before PyType_Ready(), as extensions may do, and check that subclasses created from Python still inherit its special methods. Co-Authored-By: Claude Fable 5.1 <[email protected]> * gh-132042: Ignore the MyListDictSubclass_Type static type in check-c-globals Co-Authored-By: Claude Fable 5.1 <[email protected]> --------- Co-authored-by: Claude Fable 5.1 <[email protected]> files: A Misc/NEWS.d/next/Core_and_Builtins/2026-10-14-23-05-00.gh-issue-132042.k7Qs2w.rst M Lib/test/test_capi/test_type.py M Lib/test/test_free_threading/test_type.py M Modules/_testcapimodule.c M Objects/typeobject.c M Tools/c-analyzer/cpython/ignored.tsv diff --git a/Lib/test/test_capi/test_type.py b/Lib/test/test_capi/test_type.py index 90b1f57d1c3c9d3..9aca0d4741dd60d 100644 --- a/Lib/test/test_capi/test_type.py +++ b/Lib/test/test_capi/test_type.py @@ -485,6 +485,19 @@ class MyList(list): self.assertFalse(type_issubtype(frozendict, dict)) self.assertFalse(type_issubtype(MyList, tuple)) + def test_subclass_type_with_dict_subclass_tp_dict(self): + # gh-132042: MyListDictSubclass initializes tp_dict with a dict + # subclass before PyType_Ready(), as extensions may do. Creating a + # subclass must still find the special methods in that dict. + class Sub(_testcapi.MyListDictSubclass): + pass + self.assertEqual(len(Sub([1, 2, 3])), 3) + + class Sub2(_testcapi.MyListDictSubclass): + def __len__(self): + return 5 + self.assertEqual(len(Sub2([1, 2, 3])), 5) + def test_type_modified(self): # Test PyType_Modified() type_modified = _testlimitedcapi.type_modified diff --git a/Lib/test/test_free_threading/test_type.py b/Lib/test/test_free_threading/test_type.py index a55c4815a038376..77af1c1e9d387f7 100644 --- a/Lib/test/test_free_threading/test_type.py +++ b/Lib/test/test_free_threading/test_type.py @@ -401,6 +401,74 @@ class B(A): with threading_helper.start_threads(threads): pass + def test_class_creation_with_concurrent_setattr(self): + # Creating a class resolves its slots from the dicts along the MRO + # while holding the type lock, before the class is reachable from + # its bases. If that resolution blocked on a base's dict mutex, the + # type lock would be released while blocked, and another thread + # could then assign a special method on a base that was already + # resolved. The new class would end up with a slot that does not + # match its MRO. + N = 300 + + class B2: + pass + + class B1(B2): + pass + + lock = threading.Lock() + mismatches = [] + done = False + + def custom_repr(self): + return "custom repr" + + def setter(): + # Toggle B1.__repr__, so a stale resolution of B1 gives the new + # class object.__repr__ while B1.__repr__ is custom_repr. + barrier.wait() + while not done: + with lock: + B1.__repr__ = custom_repr + with lock: + del B1.__repr__ + + def churner(): + # type.__setattr__ takes B2's dict mutex before the type lock + # and holds it while waiting for the type lock, so B2's dict + # mutex is contended whenever creator holds the type lock. + barrier.wait() + n = 0 + while not done: + n += 1 + B2.attr = n + + def creator(): + nonlocal done + # Mark the base dicts as shared, so lookups from this thread + # never need to take their mutexes. + getattr(B1, "nope", None) + barrier.wait() + try: + for _ in range(N): + C = type("C", (B1,), {}) + c = C() + with lock: + slot_result = repr(c) + mro_result = C.__repr__(c) + if slot_result != mro_result: + mismatches.append((slot_result, mro_result)) + finally: + done = True + + targets = (setter, churner, churner, creator) + barrier = threading.Barrier(len(targets)) + threads = [Thread(target=target) for target in targets] + with threading_helper.start_threads(threads): + pass + self.assertEqual(mismatches, []) + if __name__ == "__main__": unittest.main() diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2026-10-14-23-05-00.gh-issue-132042.k7Qs2w.rst b/Misc/NEWS.d/next/Core_and_Builtins/2026-10-14-23-05-00.gh-issue-132042.k7Qs2w.rst new file mode 100644 index 000000000000000..887df4fca00a789 --- /dev/null +++ b/Misc/NEWS.d/next/Core_and_Builtins/2026-10-14-23-05-00.gh-issue-132042.k7Qs2w.rst @@ -0,0 +1,3 @@ +Speed up class creation by resolving the special method slots of a new class +with one pass over each class dict along the MRO instead of one lookup per +slot name and per class. diff --git a/Modules/_testcapimodule.c b/Modules/_testcapimodule.c index 00ba09b6e2fe248..08dbfabde547478 100644 --- a/Modules/_testcapimodule.c +++ b/Modules/_testcapimodule.c @@ -3307,6 +3307,17 @@ static PyTypeObject MyList_Type = { MyList_new, /* tp_new */ }; +/* Like MyList, but tp_dict is initialized with a dict subclass before + PyType_Ready(), as extension modules may do (e.g. ctypes before 3.13). */ +static PyTypeObject MyListDictSubclass_Type = { + PyVarObject_HEAD_INIT(NULL, 0) + "MyListDictSubclass", + sizeof(MyListObject), + .tp_dealloc = MyList_dealloc, + .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, + .tp_new = MyList_new, +}; + /* Test PEP 560 */ typedef struct { @@ -3623,6 +3634,28 @@ _testcapi_exec(PyObject *m) Py_INCREF(&MyList_Type); PyModule_AddObject(m, "MyList", (PyObject *)&MyList_Type); + MyListDictSubclass_Type.tp_base = &PyList_Type; + if (MyListDictSubclass_Type.tp_dict == NULL) { + PyObject *cls = PyObject_CallFunction((PyObject *)&PyType_Type, + "s(O){}", "DictSubclass", + &PyDict_Type); + if (cls == NULL) { + return -1; + } + MyListDictSubclass_Type.tp_dict = PyObject_CallNoArgs(cls); + Py_DECREF(cls); + if (MyListDictSubclass_Type.tp_dict == NULL) { + return -1; + } + } + /* PyModule_AddType() would skip PyType_Ready() as tp_dict is set. */ + if (PyType_Ready(&MyListDictSubclass_Type) < 0) { + return -1; + } + if (PyModule_AddType(m, &MyListDictSubclass_Type) < 0) { + return -1; + } + if (PyType_Ready(&GenericAlias_Type) < 0) return -1; Py_INCREF(&GenericAlias_Type); diff --git a/Objects/typeobject.c b/Objects/typeobject.c index 87da481f0a5f60c..22be94bacbc0a36 100644 --- a/Objects/typeobject.c +++ b/Objects/typeobject.c @@ -11736,6 +11736,62 @@ static pytype_slotdef slotdefs[] = { interpreter starts. */ static uint8_t slotdefs_dups[Py_ARRAY_LENGTH(slotdefs)][1 + MAX_EQUIV]; +/* Open-addressing hash table: slot name -> index of the first slotdef with + that name (slotdefs_dups[] lists the others). Entry 0 means "empty". + Built by _PyType_InitSlotDefs(). */ +#define SLOTNAME_TABLE_SIZE 512 +static uint16_t slotname_table[SLOTNAME_TABLE_SIZE]; +#ifndef NDEBUG +static bool slotname_table_initialized = false; +#endif + +static size_t +slotname_probe(PyObject *key, Py_hash_t hash) +{ + size_t i = (size_t)hash & (SLOTNAME_TABLE_SIZE - 1); + while (slotname_table[i] != 0) { + PyObject *name = slotdefs[slotname_table[i] - 1].name_strobj; + if (name == key + || (PyUnstable_Unicode_GET_CACHED_HASH(name) == hash + && _PyUnicode_Equal(name, key))) { + break; + } + i = (i + 1) & (SLOTNAME_TABLE_SIZE - 1); + } + return i; +} + +static void +init_slotname_table(void) +{ +#ifndef NDEBUG + slotname_table_initialized = true; +#endif + memset(slotname_table, 0, sizeof(slotname_table)); + for (size_t idx = 0; slotdefs[idx].name != NULL; idx++) { + PyObject *name = slotdefs[idx].name_strobj; + /* Computes and caches the hash of name_strobj if not done yet. */ + Py_hash_t hash = _PyObject_HashDictKey(name); + size_t i = slotname_probe(name, hash); + if (slotname_table[i] == 0) { + slotname_table[i] = (uint16_t)(idx + 1); + } + } + /* Keep the load factor low so probe sequences stay short. */ + Py_BUILD_ASSERT(4 * Py_ARRAY_LENGTH(slotdefs) <= SLOTNAME_TABLE_SIZE); +} + +/* Return the index of the first slotdef named 'key' (a str with hash + 'hash'), or -1 if 'key' is not a slot name. */ +static Py_ssize_t +slotname_lookup(PyObject *key, Py_hash_t hash) +{ + assert(slotname_table_initialized); + assert(hash != -1); + size_t i = slotname_probe(key, hash); + return slotname_table[i] ? slotname_table[i] - 1 : -1; +} + /* Given a type pointer and an offset gotten from a slotdef entry, return a pointer to the actual slot. This is not quite the same as simply adding the offset to the type pointer, since it takes care to indirect through the @@ -11783,12 +11839,82 @@ slotptr(PyTypeObject *type, int ioffset) static bool has_slotdef(PyObject *name) { - for (pytype_slotdef *p = slotdefs; p->name_strobj; p++) { - if (p->name_strobj == name) { - return true; + return slotname_lookup(name, _PyObject_HashDictKey(name)) >= 0; +} + +#define SLOT_SCAN_MAX_DICT_SIZE 1000 + +static void +clear_slot_descrs(PyObject **descrs) +{ + for (size_t i = 0; i < Py_ARRAY_LENGTH(slotdefs) - 1; i++) { + Py_CLEAR(descrs[i]); + } +} + +/* Scan the dicts along the MRO once and set descrs[i] to a strong reference + to what find_name_in_mro() would return for slotdefs[i].name, or NULL. + Return -1 (descrs[] all NULL) if some dict cannot be scanned. */ +static int +collect_slot_descrs(PyTypeObject *type, PyObject **descrs) +{ + ASSERT_NEW_TYPE_OR_LOCKED(type); + PyObject *mro = lookup_tp_mro(type); + assert(mro != NULL && PyTuple_CheckExact(mro)); + memset(descrs, 0, sizeof(PyObject *) * (Py_ARRAY_LENGTH(slotdefs) - 1)); + Py_ssize_t mro_size = PyTuple_GET_SIZE(mro); + for (Py_ssize_t m = 0; m < mro_size; m++) { + PyObject *base = PyTuple_GET_ITEM(mro, m); + assert(PyType_Check(base)); + PyObject *dict = lookup_tp_dict(_PyType_CAST(base)); + assert(dict != NULL && PyDict_Check(dict)); +#ifdef Py_GIL_DISABLED + /* _PyDict_Next() needs the dict mutex, but we must not block for it: + blocking detaches the thread, which releases TYPE_LOCK and lets + another thread change a dict scanned earlier. Fall back instead. */ + PyMutex *mutex = &dict->ob_mutex; + if (!PyMutex_LockFast(mutex)) { + goto fail; + } +#endif + int ok = 1; + if (!DK_IS_UNICODE(((PyDictObject *)dict)->ma_keys) + || PyDict_GET_SIZE(dict) > SLOT_SCAN_MAX_DICT_SIZE) { + ok = 0; + } + else { + Py_ssize_t pos = 0; + PyObject *key, *value; + Py_hash_t hash; + while (_PyDict_Next(dict, &pos, &key, &value, &hash)) { + if (!is_dunder_name(key)) { + continue; + } + Py_ssize_t idx = slotname_lookup(key, hash); + if (idx < 0) { + continue; + } + /* First class in the MRO wins. */ + const uint8_t *dups = slotdefs_dups[idx]; + for (uint8_t k = 1; k <= dups[0]; k++) { + if (descrs[dups[k]] == NULL) { + descrs[dups[k]] = Py_NewRef(value); + } + } + } + } +#ifdef Py_GIL_DISABLED + PyMutex_Unlock(mutex); +#endif + if (!ok) { + goto fail; } } - return false; + return 0; + +fail: + clear_slot_descrs(descrs); + return -1; } /* Common code for update_slots_callback() and fixup_slot_dispatchers(). @@ -11855,7 +11981,7 @@ has_slotdef(PyObject *name) * occur internally are ignored, such as when looking up descriptors. */ static int update_one_slot(PyTypeObject *type, pytype_slotdef *p, pytype_slotdef **next_p, - slot_update_t *queued_updates) + slot_update_t *queued_updates, PyObject **descrs) { ASSERT_NEW_TYPE_OR_LOCKED(type); @@ -11887,9 +12013,18 @@ update_one_slot(PyTypeObject *type, pytype_slotdef *p, pytype_slotdef **next_p, /* We may end up clearing live exceptions below, so make sure it's ours. */ assert(!PyErr_Occurred()); do { - /* Use faster uncached lookup as we won't get any cache hits during type setup. */ _PyStackRef descr_ref; - int res = find_name_in_mro(type, p->name_strobj, &descr_ref); + int res; + if (descrs != NULL) { + /* Precomputed by collect_slot_descrs(), which owns the refs. */ + PyObject *found = descrs[p - slotdefs]; + res = (found != NULL); + descr_ref = res ? PyStackRef_FromPyObjectBorrow(found) : PyStackRef_NULL; + } + else { + /* Use faster uncached lookup as we won't get any cache hits during type setup. */ + res = find_name_in_mro(type, p->name_strobj, &descr_ref); + } if (res <= 0) { if (ptr == (void**)&type->tp_iternext) { specific = (void *)_PyObject_NextNotImplemented; @@ -12027,7 +12162,8 @@ update_slots_callback(PyTypeObject *type, void *data) update_callback_data_t *update_data = (update_callback_data_t *)data; pytype_slotdef **pp = update_data->defs; for (; *pp; pp++) { - if (update_one_slot(type, *pp, NULL, update_data->queued_updates) < 0) { + if (update_one_slot(type, *pp, NULL, update_data->queued_updates, + NULL) < 0) { return -1; } } @@ -12047,26 +12183,21 @@ update_slot(PyTypeObject *type, PyObject *name, slot_update_t *queued_updates) assert(PyUnicode_CheckExact(name)); assert(PyUnicode_CHECK_INTERNED(name)); - pp = ptrs; - for (p = slotdefs; p->name; p++) { - assert(PyUnicode_CheckExact(p->name_strobj)); - assert(PyUnicode_CHECK_INTERNED(p->name_strobj)); - assert(PyUnicode_CheckExact(name)); - /* bpo-40521: Using interned strings. */ - if (p->name_strobj == name) { - *pp++ = p; - } + Py_ssize_t idx = slotname_lookup(name, _PyObject_HashDictKey(name)); + if (idx < 0) { + return 0; /* Not an attribute that affects any slots */ } - *pp = NULL; - for (pp = ptrs; *pp; pp++) { - p = *pp; + /* All slotdefs with this name, in slotdefs order. */ + const uint8_t *dups = slotdefs_dups[idx]; + pp = ptrs; + for (uint8_t k = 1; k <= dups[0]; k++) { + p = &slotdefs[dups[k]]; offset = p->offset; while (p > slotdefs && (p-1)->offset == offset) --p; - *pp = p; + *pp++ = p; } - if (ptrs[0] == NULL) - return 0; /* Not an attribute that affects any slots */ + *pp = NULL; update_callback_data_t callback_data; callback_data.defs = ptrs; @@ -12085,12 +12216,20 @@ fixup_slot_dispatchers(PyTypeObject *type) ASSERT_TYPE_LOCK_HELD(); ASSERT_WORLD_STOPPED_OR_NEW_TYPE(type); assert(!PyErr_Occurred()); + PyObject *descrs_buf[Py_ARRAY_LENGTH(slotdefs) - 1]; + PyObject **descrs = descrs_buf; + if (collect_slot_descrs(type, descrs_buf) < 0) { + descrs = NULL; + } for (pytype_slotdef *p = slotdefs; p->name; ) { - int rv = update_one_slot(type, p, &p, NULL); + int rv = update_one_slot(type, p, &p, NULL, descrs); // always returns 0 if queued_updates == NULL assert (rv == 0); (void)rv; } + if (descrs != NULL) { + clear_slot_descrs(descrs); + } } #ifdef Py_GIL_DISABLED @@ -12143,68 +12282,30 @@ _PyType_InitSlotDefs(PyInterpreterState *interp) if (!_Py_IsMainInterpreter(interp)) { return 0; } - PyObject *bytearray = NULL; - PyObject *cache = PyDict_New(); - if (!cache) { - return -1; - } + init_slotname_table(); - pytype_slotdef *p; - Py_ssize_t idx = 0; - for (p = slotdefs; p->name_strobj; p++, idx++) { + /* Group the slotdefs by name: slotdefs_dups[i] lists the indices of + all slotdefs with the same name as slotdefs[i], in slotdefs order. */ + memset(slotdefs_dups, 0, sizeof(slotdefs_dups)); + for (Py_ssize_t idx = 0; slotdefs[idx].name_strobj != NULL; idx++) { assert(idx < 255); - - if (PyDict_GetItemRef(cache, p->name_strobj, &bytearray) < 0) { - goto error; - } - - if (!bytearray) { - Py_ssize_t size = sizeof(uint8_t) * (1 + MAX_EQUIV); - bytearray = PyByteArray_FromStringAndSize(NULL, size); - if (!bytearray) { - goto error; - } - - uint8_t *data = (uint8_t *)PyByteArray_AS_STRING(bytearray); - data[0] = 0; - - if (PyDict_SetItem(cache, p->name_strobj, bytearray) < 0) { - goto error; - } - } - - assert(PyByteArray_CheckExact(bytearray)); - uint8_t *data = (uint8_t *)PyByteArray_AS_STRING(bytearray); - + PyObject *name = slotdefs[idx].name_strobj; + Py_ssize_t first = slotname_lookup(name, _PyObject_HashDictKey(name)); + assert(first >= 0 && first <= idx); + uint8_t *data = slotdefs_dups[first]; data[0] += 1; assert(data[0] < MAX_EQUIV); - data[data[0]] = (uint8_t)idx; - - Py_CLEAR(bytearray); } - - memset(slotdefs_dups, -1, sizeof(slotdefs_dups)); - - Py_ssize_t pos = 0; - PyObject *key = NULL; - PyObject *value = NULL; - while (PyDict_Next(cache, &pos, &key, &value)) { - uint8_t *data = (uint8_t *)PyByteArray_AS_STRING(value); - uint8_t n = data[0]; - for (uint8_t i = 0; i < n; i++) { - uint8_t idx = data[i + 1]; - memcpy(&slotdefs_dups[idx], data, sizeof(uint8_t) * (n + 1)); + for (Py_ssize_t idx = 0; slotdefs[idx].name_strobj != NULL; idx++) { + PyObject *name = slotdefs[idx].name_strobj; + Py_ssize_t first = slotname_lookup(name, _PyObject_HashDictKey(name)); + if (first != idx) { + memcpy(slotdefs_dups[idx], slotdefs_dups[first], + sizeof(slotdefs_dups[idx])); } } - - Py_DECREF(cache); return 0; - -error: - Py_XDECREF(bytearray); - Py_DECREF(cache); - return -1; } diff --git a/Tools/c-analyzer/cpython/ignored.tsv b/Tools/c-analyzer/cpython/ignored.tsv index 62f454b63559d05..a51ac686268f411 100644 --- a/Tools/c-analyzer/cpython/ignored.tsv +++ b/Tools/c-analyzer/cpython/ignored.tsv @@ -525,6 +525,7 @@ Modules/_testcapimodule.c - MethodDescriptor2_Type - Modules/_testcapimodule.c - MethodDescriptorBase_Type - Modules/_testcapimodule.c - MethodDescriptorDerived_Type - Modules/_testcapimodule.c - MethodDescriptorNopGet_Type - +Modules/_testcapimodule.c - MyListDictSubclass_Type - Modules/_testcapimodule.c - MyList_Type - Modules/_testcapimodule.c - PyRecursingInfinitelyError_Type - Modules/_testcapimodule.c - TestError - _______________________________________________ Python-checkins mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3//lists/python-checkins.python.org Member address: [email protected]
