gh-145685: per-type method cache implementation (#150160)
kumaraditya303 <[email protected]>
| Newsgroups | gmane.comp.python.cvs |
|---|---|
| Message-ID | <[email protected]> |
https://github.com/python/cpython/commit/daf09e17bf99c544e8ab7a72b11f10f2e382a381 commit: daf09e17bf99c544e8ab7a72b11f10f2e382a381 branch: main author: Kumar Aditya <[email protected]> committer: kumaraditya303 <[email protected]> date: 2026-07-21T14:11:22+05:30 summary: gh-145685: per-type method cache implementation (#150160) files: A Include/internal/pycore_typecache.h A Misc/NEWS.d/next/Core_and_Builtins/2026-06-05-09-25-08.gh-issue-145685.afO33b.rst A Modules/_testinternalcapi/typecache.c A Python/typecache.c M Doc/c-api/type.rst M Doc/whatsnew/3.16.rst M Include/cpython/object.h M Include/cpython/pystats.h M Include/internal/pycore_interp_structs.h M Include/internal/pycore_object.h M Include/internal/pycore_typeobject.h M Lib/test/test_free_threading/test_type.py M Lib/test/test_sys.py M Lib/test/test_type_cache.py M Makefile.pre.in M Modules/Setup.stdlib.in M Modules/_testinternalcapi.c M Modules/_testinternalcapi/parts.h M Objects/typeobject.c M PCbuild/_freeze_module.vcxproj M PCbuild/_freeze_module.vcxproj.filters M PCbuild/_testinternalcapi.vcxproj M PCbuild/_testinternalcapi.vcxproj.filters M PCbuild/pythoncore.vcxproj M PCbuild/pythoncore.vcxproj.filters M Python/pystate.c M Python/pystats.c M Tools/c-analyzer/cpython/ignored.tsv M Tools/ftscalingbench/ftscalingbench.py diff --git a/Doc/c-api/type.rst b/Doc/c-api/type.rst index 99a7ed8b1cb7b8e..2e48c56bd2c5a5b 100644 --- a/Doc/c-api/type.rst +++ b/Doc/c-api/type.rst @@ -37,6 +37,10 @@ Type Objects Clear the internal lookup cache. Return the current version tag. + .. versionchanged:: 3.16 + This function is now a no-op as the type cache is now implemented + per-type. It still returns the current version tag. + .. c:function:: unsigned long PyType_GetFlags(PyTypeObject* type) Return the :c:member:`~PyTypeObject.tp_flags` member of *type*. This function is primarily diff --git a/Doc/whatsnew/3.16.rst b/Doc/whatsnew/3.16.rst index 7aac17fc1c7b433..662defa709a246c 100644 --- a/Doc/whatsnew/3.16.rst +++ b/Doc/whatsnew/3.16.rst @@ -815,7 +815,8 @@ New features Porting to Python 3.16 ---------------------- -* TODO +* :c:func:`PyType_ClearCache` is now a no-op as the type cache is now + implemented per-type. It still returns the current version tag. Deprecated C APIs ----------------- diff --git a/Include/cpython/object.h b/Include/cpython/object.h index 326254c335b4895..4c5a677e5543ece 100644 --- a/Include/cpython/object.h +++ b/Include/cpython/object.h @@ -246,6 +246,8 @@ struct _typeobject { * This function must escape to any code that can result in * the GC being run, such as Py_DECREF. */ _Py_iteritemfunc _tp_iteritem; + + void *_tp_cache; }; #define _Py_ATTR_CACHE_UNUSED (30000) // (see tp_versions_used) diff --git a/Include/cpython/pystats.h b/Include/cpython/pystats.h index 69659c48a3bf882..738e342d1407686 100644 --- a/Include/cpython/pystats.h +++ b/Include/cpython/pystats.h @@ -96,7 +96,9 @@ typedef struct _object_stats { uint64_t type_cache_misses; uint64_t type_cache_dunder_hits; uint64_t type_cache_dunder_misses; - uint64_t type_cache_collisions; + uint64_t type_cache_too_big; + uint64_t type_cache_invalidations; + uint64_t type_cache_resizes; /* Temporary value used during GC */ uint64_t object_visits; } ObjectStats; diff --git a/Include/internal/pycore_interp_structs.h b/Include/internal/pycore_interp_structs.h index d3efac906aeb933..0623adce693d465 100644 --- a/Include/internal/pycore_interp_structs.h +++ b/Include/internal/pycore_interp_structs.h @@ -560,23 +560,6 @@ struct _types_runtime_state { }; -// Type attribute lookup cache: speed up attribute and method lookups, -// see _PyType_Lookup(). -struct type_cache_entry { - unsigned int version; // initialized from type->tp_version_tag -#ifdef Py_GIL_DISABLED - _PySeqLock sequence; -#endif - PyObject *name; // reference to exactly a str or None - PyObject *value; // borrowed reference or NULL -}; - -#define MCACHE_SIZE_EXP 12 - -struct type_cache { - struct type_cache_entry hashtable[1 << MCACHE_SIZE_EXP]; -}; - typedef struct { PyTypeObject *type; int isbuiltin; @@ -591,6 +574,10 @@ typedef struct { are also some diagnostic uses for the list of weakrefs, so we still keep it. */ PyObject *tp_weaklist; + /* Per-interpreter attribute lookup cache (struct type_cache *). + For static builtin types the cache must be per-interpreter + because tp_dict and the values it stores are per-interpreter. */ + void *_tp_cache; } managed_static_type_state; #define TYPE_VERSION_CACHE_SIZE (1<<12) /* Must be a power of 2 */ @@ -601,8 +588,6 @@ struct types_state { where all those lower numbers are used for core static types. */ unsigned int next_version_tag; - struct type_cache type_cache; - /* Every static builtin type is initialized for each interpreter during its own initialization, including for the main interpreter during global runtime initialization. This is done by calling diff --git a/Include/internal/pycore_object.h b/Include/internal/pycore_object.h index 307ecdbaaefcea2..41786cb267c2e96 100644 --- a/Include/internal/pycore_object.h +++ b/Include/internal/pycore_object.h @@ -285,8 +285,6 @@ _PyType_HasFeature(PyTypeObject *type, unsigned long feature) { return ((type->tp_flags) & feature) != 0; } -extern void _PyType_InitCache(PyInterpreterState *interp); - extern PyStatus _PyObject_InitState(PyInterpreterState *interp); extern void _PyObject_FiniState(PyInterpreterState *interp); extern bool _PyRefchain_IsTraced(PyInterpreterState *interp, PyObject *obj); diff --git a/Include/internal/pycore_typecache.h b/Include/internal/pycore_typecache.h new file mode 100644 index 000000000000000..76f87e8548d9c90 --- /dev/null +++ b/Include/internal/pycore_typecache.h @@ -0,0 +1,47 @@ +#ifndef PY_INTERNAL_TYPECACHE_H +#define PY_INTERNAL_TYPECACHE_H +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef Py_BUILD_CORE +# error "this header requires Py_BUILD_CORE define" +#endif + +#include "pycore_stackref.h" + + +#define _Py_TYPECACHE_MINSIZE (1 << 3) +#define _Py_TYPECACHE_MAXSIZE (1 << 16) + +struct type_cache_entry { + PyObject *name; // name of the attribute or method, interned string, NULL if the entry is empty + PyObject *value; // borrowed reference or NULL +}; + +// Per-type attribute lookup cache: speed up attribute and method lookups, +// see _PyTypeCache_Lookup(). +struct type_cache { + uint32_t mask; // mask for indexing into hashtable, i.e. size of hashtable is mask + 1 + uint32_t available; // number of available entries in hashtable + uint32_t used; // number of used entries in hashtable + unsigned int version_tag; // initialized from type->tp_version_tag + struct type_cache_entry hashtable[_Py_TYPECACHE_MINSIZE]; // hashtable entries +}; + +struct _PyTypeCacheLookupResult { + _PyStackRef value; // value is a stack reference to the cached attribute or method, or NULL if not found + int cache_hit; // 1 if the cache entry is valid and matches the type's version tag, 0 otherwise + unsigned int version_tag; // version tag of the type when the value was cached +}; + + +extern void _PyTypeCache_InitType(PyTypeObject *type); +extern void _PyTypeCache_Insert(PyTypeObject *type, PyObject *name, PyObject *value); +PyAPI_FUNC(struct _PyTypeCacheLookupResult) _PyTypeCache_Lookup(PyTypeObject *type, PyObject *name); +PyAPI_FUNC(void) _PyTypeCache_Invalidate(PyTypeObject *type); + +#ifdef __cplusplus +} +#endif +#endif /* PY_INTERNAL_TYPECACHE_H */ diff --git a/Include/internal/pycore_typeobject.h b/Include/internal/pycore_typeobject.h index c8b888f1c395483..ecb3c78a35b9165 100644 --- a/Include/internal/pycore_typeobject.h +++ b/Include/internal/pycore_typeobject.h @@ -41,7 +41,6 @@ extern PyStatus _PyTypes_InitTypes(PyInterpreterState *); extern void _PyTypes_FiniTypes(PyInterpreterState *); extern void _PyTypes_FiniExtTypes(PyInterpreterState *interp); extern void _PyTypes_Fini(PyInterpreterState *); -extern void _PyTypes_AfterFork(void); extern void _PyTypes_FiniCachedDescriptors(PyInterpreterState *); static inline PyObject ** diff --git a/Lib/test/test_free_threading/test_type.py b/Lib/test/test_free_threading/test_type.py index 0c99bbc759e672a..f17d12532c63ced 100644 --- a/Lib/test/test_free_threading/test_type.py +++ b/Lib/test/test_free_threading/test_type.py @@ -4,8 +4,10 @@ from concurrent.futures import ThreadPoolExecutor from threading import Barrier, Thread from unittest import TestCase +import sys +from test.support import import_helper, threading_helper -from test.support import threading_helper +_testinternalcapi = import_helper.import_module("_testinternalcapi") @@ -84,6 +86,24 @@ def reader_func(): self.run_one(writer_func, reader_func) + def test_attr_cache_mortal(self): + class C: + x = object() + + class D(C): + pass + + def writer_func(): + for _ in range(3000): + C.x = object() + + def reader_func(): + for _ in range(3000): + C.x + D.x + + self.run_one(writer_func, reader_func) + def test___class___modification(self): loops = 200 @@ -160,6 +180,51 @@ def reader(): self.run_one(writer, reader) + def test_per_type_cache_concurrent_reads(self): + class C: + pass + + names = [sys.intern(f"attr_{i}") for i in range( + _testinternalcapi._Py_TYPECACHE_MINSIZE * 4)] + for name in names: + setattr(C, name, name) + # Prime the cache. + for name in names: + getattr(C, name) + + lookup = _testinternalcapi.type_cache_lookup + + def reader(): + for _ in range(500): + for name in names: + hit, value, _ = lookup(C, name) + self.assertEqual(hit, 1, name) + self.assertEqual(value, name) + + threading_helper.run_concurrently(reader, nthreads=NTHREADS) + + def test_per_type_cache_concurrent_invalidate(self): + class C: + x = "value" + + # Prime the cache. + C.x + hit, value, version = _testinternalcapi.type_cache_lookup(C, "x") + self.assertEqual(hit, 1) + self.assertIs(value, "value") + self.assertGreater(version, 0) + + def reader(): + for _ in range(10_000): + self.assertIs(C.x, "value") + + def invalidator(): + for _ in range(10_000): + _testinternalcapi.type_cache_invalidate(C) + + workers = [invalidator] + [reader] * (NTHREADS - 1) + threading_helper.run_concurrently(workers) + def test_race_type_attr_added(self): NROUNDS = 50 NSTOPPERS = 4 diff --git a/Lib/test/test_sys.py b/Lib/test/test_sys.py index 56c5c2aa2025b9a..dab03ef06a8b8e5 100644 --- a/Lib/test/test_sys.py +++ b/Lib/test/test_sys.py @@ -1809,7 +1809,7 @@ def delx(self): del self.__x check((1,2,3), vsize('') + self.P + 3*self.P) # type # static type: PyTypeObject - fmt = 'P2nPI13Pl4Pn9Pn12PI2Pc' + fmt = 'P2nPI13Pl4Pn9Pn12PI2PcP' s = vsize(fmt) check(int, s) typeid = 'n' if support.Py_GIL_DISABLED else '' diff --git a/Lib/test/test_type_cache.py b/Lib/test/test_type_cache.py index 849a2afd8ed7986..9827f2498554a5b 100644 --- a/Lib/test/test_type_cache.py +++ b/Lib/test/test_type_cache.py @@ -1,6 +1,7 @@ """ Tests for the internal type cache in CPython. """ import collections.abc import dis +import sys import unittest import warnings from test import support @@ -281,5 +282,163 @@ def to_bool_2(instance): self._check_specialization(to_bool_2, H(), "TO_BOOL", should_specialize=False) [email protected]_only +class PerTypeLookupCacheTests(unittest.TestCase): + """Tests for the per-type lookup cache.""" + + type_cache_lookup = staticmethod(_testinternalcapi.type_cache_lookup) + type_cache_invalidate = staticmethod(_testinternalcapi.type_cache_invalidate) + + def _make_type(self): + class C: + x = "x-value" + return C + + def test_lookup_miss_on_empty_cache(self): + # A freshly-created type has not cached any names yet; the cache + # should report a miss for an arbitrary name. + C = self._make_type() + hit, value, version = self.type_cache_lookup(C, "x") + self.assertEqual(hit, 0) + self.assertIsNone(value) + self.assertEqual(version, 0) + + def test_lookup_hit_after_access(self): + # Reading an attribute goes through _PyType_Lookup which + # caches the result. Subsequent lookups for the same name + # should hit the cache. + C = self._make_type() + hit, value, version = self.type_cache_lookup(C, "x") + self.assertEqual(hit, 0) + attr = C.x + hit, value, version = self.type_cache_lookup(C, "x") + self.assertEqual(hit, 1) + self.assertIs(value, attr) + self.assertNotEqual(version, 0) + self.assertEqual(version, type_get_version(C)) + + def test_lookup_caches_missing_name(self): + # _PyType_Lookup caches negative results too: a name that is not in + # the MRO should still produce a cache hit with a None value. + C = self._make_type() + with self.assertRaises(AttributeError): + C.does_not_exist + hit, value, _ = self.type_cache_lookup(C, "does_not_exist") + self.assertEqual(hit, 1) + self.assertIsNone(value) + + def test_lookup_on_static_type(self): + # The cache for static types is stored on interpreter for isolation + # between subinterpreters, test that cache works for them as well. + self.type_cache_invalidate(int) + name = sys.intern("bit_length") + self.assertEqual(self.type_cache_lookup(int, name)[0], 0) + attr = getattr(int, name) + hit, value, _ = self.type_cache_lookup(int, name) + self.assertEqual(hit, 1) + self.assertIs(value, attr) + + def test_invalidate_clears_cache(self): + C = self._make_type() + C.x # populate cache + self.assertEqual(self.type_cache_lookup(C, "x")[0], 1) + + self.type_cache_invalidate(C) + hit, value, _ = self.type_cache_lookup(C, "x") + self.assertEqual(hit, 0) + self.assertIsNone(value) + + def test_setattr_invalidates_cache(self): + # Mutating a type's attributes must invalidate any cached entries + # for that type. + C = self._make_type() + C.x + self.assertEqual(self.type_cache_lookup(C, "x")[0], 1) + + C.x = "new-value" + hit, _, _ = self.type_cache_lookup(C, "x") + self.assertEqual(hit, 0) + + # The next access should re-populate the cache with the new value. + self.assertEqual(C.x, "new-value") + hit, value, _ = self.type_cache_lookup(C, "x") + self.assertEqual(hit, 1) + self.assertEqual(value, "new-value") + + def test_setattr_on_subclass_preserves_base(self): + # Adding an attribute to a subclass changes the lookup result for + # the subclass, so its cache must be invalidated, but the base's + # cache for the same name stays valid. + class Base: + x = "base" + class Sub(Base): + pass + + self.assertEqual(Sub.x, "base") + self.assertEqual(Base.x, "base") + self.assertEqual(self.type_cache_lookup(Sub, "x")[0], 1) + self.assertEqual(self.type_cache_lookup(Base, "x")[0], 1) + + Sub.x = "sub" + # Sub's cache should be invalidated. + self.assertEqual(self.type_cache_lookup(Sub, "x")[0], 0) + # Base is untouched. + hit, value, _ = self.type_cache_lookup(Base, "x") + self.assertEqual(hit, 1) + self.assertEqual(value, "base") + + def test_setattr_on_base_invalidates_subclass(self): + class Base: + x = "base" + class Sub(Base): + pass + + Sub.x + self.assertEqual(self.type_cache_lookup(Sub, "x")[0], 1) + + Base.x = "new-base" + # Modifying the base must invalidate the subclass cache too. + self.assertEqual(self.type_cache_lookup(Sub, "x")[0], 0) + + def test_lookup_detects_stale_cache_version(self): + # The cache stores the type's tp_version_tag alongside its entries + # and re-checks it after locating a hit. If the type version moves + # forward without the cache being invalidated (the race window in + # lock-free invalidation), the consistency check must downgrade + # the hit to a miss. + C = self._make_type() + C.x # populate cache + orig_version = type_get_version(C) + self.assertNotEqual(orig_version, 0) + self.assertEqual(self.type_cache_lookup(C, "x")[0], 1) + + # Bump the type version directly without touching the cache slot + # (PyType_Modified would also invalidate, defeating the test). + type_assign_specific_version_unsafe(C, orig_version + 1) + self.assertEqual(type_get_version(C), orig_version + 1) + + hit, value, _ = self.type_cache_lookup(C, "x") + self.assertEqual(hit, 0) + self.assertIsNone(value) + + def test_setattr_on_unrelated_type_preserves_cache(self): + # Modifying one type must not invalidate a sibling's cache. + class A: + x = "a" + class B: + x = "b" + + A.x + B.x + self.assertEqual(self.type_cache_lookup(A, "x")[0], 1) + self.assertEqual(self.type_cache_lookup(B, "x")[0], 1) + + B.x = "b2" + # A's cache is unaffected. + hit, value, _ = self.type_cache_lookup(A, "x") + self.assertEqual(hit, 1) + self.assertEqual(value, "a") + + if __name__ == "__main__": unittest.main() diff --git a/Makefile.pre.in b/Makefile.pre.in index b42a8491733c636..465981f8fd4deda 100644 --- a/Makefile.pre.in +++ b/Makefile.pre.in @@ -511,6 +511,7 @@ PYTHON_OBJS= \ Python/thread.o \ Python/traceback.o \ Python/tracemalloc.o \ + Python/typecache.o \ Python/uniqueid.o \ Python/getopt.o \ Python/pystrcmp.o \ @@ -1419,6 +1420,7 @@ PYTHON_HEADERS= \ $(srcdir)/Include/internal/pycore_tracemalloc.h \ $(srcdir)/Include/internal/pycore_tstate.h \ $(srcdir)/Include/internal/pycore_tuple.h \ + $(srcdir)/Include/internal/pycore_typecache.h \ $(srcdir)/Include/internal/pycore_typedefs.h \ $(srcdir)/Include/internal/pycore_typeobject.h \ $(srcdir)/Include/internal/pycore_typevarobject.h \ diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2026-06-05-09-25-08.gh-issue-145685.afO33b.rst b/Misc/NEWS.d/next/Core_and_Builtins/2026-06-05-09-25-08.gh-issue-145685.afO33b.rst new file mode 100644 index 000000000000000..c95fc34b546aabb --- /dev/null +++ b/Misc/NEWS.d/next/Core_and_Builtins/2026-06-05-09-25-08.gh-issue-145685.afO33b.rst @@ -0,0 +1 @@ +The internal method cache used for types is now a per-type cache instead of a global per-interpreter one, improving performance and reducing cache misses. Patch by Kumar Aditya. diff --git a/Modules/Setup.stdlib.in b/Modules/Setup.stdlib.in index 524f1466b191f64..0f88dddf03b9f68 100644 --- a/Modules/Setup.stdlib.in +++ b/Modules/Setup.stdlib.in @@ -172,7 +172,7 @@ @MODULE_XXSUBTYPE_TRUE@xxsubtype xxsubtype.c @MODULE__XXTESTFUZZ_TRUE@_xxtestfuzz _xxtestfuzz/_xxtestfuzz.c _xxtestfuzz/fuzzer.c @MODULE__TESTBUFFER_TRUE@_testbuffer _testbuffer.c -@MODULE__TESTINTERNALCAPI_TRUE@_testinternalcapi _testinternalcapi.c _testinternalcapi/test_lock.c _testinternalcapi/pytime.c _testinternalcapi/set.c _testinternalcapi/test_critical_sections.c _testinternalcapi/complex.c _testinternalcapi/interpreter.c _testinternalcapi/tuple.c +@MODULE__TESTINTERNALCAPI_TRUE@_testinternalcapi _testinternalcapi.c _testinternalcapi/test_lock.c _testinternalcapi/pytime.c _testinternalcapi/set.c _testinternalcapi/test_critical_sections.c _testinternalcapi/complex.c _testinternalcapi/interpreter.c _testinternalcapi/tuple.c _testinternalcapi/typecache.c @MODULE__TESTCAPI_TRUE@_testcapi _testcapimodule.c _testcapi/vectorcall.c _testcapi/heaptype.c _testcapi/abstract.c _testcapi/unicode.c _testcapi/dict.c _testcapi/set.c _testcapi/list.c _testcapi/tuple.c _testcapi/getargs.c _testcapi/datetime.c _testcapi/docstring.c _testcapi/mem.c _testcapi/watchers.c _testcapi/long.c _testcapi/float.c _testcapi/complex.c _testcapi/numbers.c _testcapi/structmember.c _testcapi/exceptions.c _testcapi/code.c _testcapi/buffer.c _testcapi/pyatomic.c _testcapi/run.c _testcapi/file.c _testcapi/codec.c _testcapi/immortal.c _testcapi/gc.c _testcapi/hash.c _testcapi/time.c _testcapi/bytes.c _testcapi/object.c _testcapi/modsupport.c _testcapi/monitoring.c _testcapi/config.c _testcapi/import.c _testcapi/frame.c _testcapi/type.c _testcapi/function.c _testcapi/module. c _testcapi/weakref.c @MODULE__TESTLIMITEDCAPI_TRUE@_testlimitedcapi _testlimitedcapi.c _testlimitedcapi/abstract.c _testlimitedcapi/bytearray.c _testlimitedcapi/bytes.c _testlimitedcapi/codec.c _testlimitedcapi/complex.c _testlimitedcapi/dict.c _testlimitedcapi/eval.c _testlimitedcapi/float.c _testlimitedcapi/heaptype_relative.c _testlimitedcapi/import.c _testlimitedcapi/list.c _testlimitedcapi/long.c _testlimitedcapi/object.c _testlimitedcapi/pyos.c _testlimitedcapi/set.c _testlimitedcapi/slots.c _testlimitedcapi/sys.c _testlimitedcapi/threadstate.c _testlimitedcapi/tuple.c _testlimitedcapi/unicode.c _testlimitedcapi/vectorcall_limited.c _testlimitedcapi/version.c _testlimitedcapi/file.c _testlimitedcapi/weakref.c _testlimitedcapi/run.c @MODULE__TESTCLINIC_TRUE@_testclinic _testclinic.c diff --git a/Modules/_testinternalcapi.c b/Modules/_testinternalcapi.c index ea3ad2b81c28668..166397a72da3aa7 100644 --- a/Modules/_testinternalcapi.c +++ b/Modules/_testinternalcapi.c @@ -3423,6 +3423,9 @@ module_exec(PyObject *module) if (_PyTestInternalCapi_Init_Tuple(module) < 0) { return 1; } + if (_PyTestInternalCapi_Init_TypeCache(module) < 0) { + return 1; + } Py_ssize_t sizeof_gc_head = 0; #ifndef Py_GIL_DISABLED diff --git a/Modules/_testinternalcapi/parts.h b/Modules/_testinternalcapi/parts.h index 81f536c3babb18c..3775792b8b87156 100644 --- a/Modules/_testinternalcapi/parts.h +++ b/Modules/_testinternalcapi/parts.h @@ -16,5 +16,6 @@ int _PyTestInternalCapi_Init_Set(PyObject *module); int _PyTestInternalCapi_Init_Complex(PyObject *module); int _PyTestInternalCapi_Init_CriticalSection(PyObject *module); int _PyTestInternalCapi_Init_Tuple(PyObject *module); +int _PyTestInternalCapi_Init_TypeCache(PyObject *module); #endif // Py_TESTINTERNALCAPI_PARTS_H diff --git a/Modules/_testinternalcapi/typecache.c b/Modules/_testinternalcapi/typecache.c new file mode 100644 index 000000000000000..b5fe0cae353801b --- /dev/null +++ b/Modules/_testinternalcapi/typecache.c @@ -0,0 +1,95 @@ +// Test wrappers for the per-type lookup cache (pycore_typecache.h). +// +// Insertion is exercised indirectly through normal attribute access (which +// calls _PyType_Lookup); only Lookup and Invalidate need direct wrappers. + +#include "parts.h" + +#include "pycore_critical_section.h" +#include "pycore_pystate.h" // _PyInterpreterState_GET() +#include "pycore_stackref.h" // PyStackRef_AsPyObjectSteal() +#include "pycore_typecache.h" // _PyTypeCache_Lookup() + + +static int +require_type(PyObject *obj) +{ + if (!PyType_Check(obj)) { + PyErr_SetString(PyExc_TypeError, "expected a type"); + return -1; + } + return 0; +} + +static PyObject * +intern_name(PyObject *name) +{ + if (!PyUnicode_CheckExact(name)) { + PyErr_SetString(PyExc_TypeError, "name must be a str"); + return NULL; + } + Py_INCREF(name); + PyUnicode_InternInPlace(&name); + return name; +} + +// type_cache_lookup(type, name) -> (cache_hit, value_or_None, version_tag) +static PyObject * +type_cache_lookup(PyObject *Py_UNUSED(self), PyObject *args) +{ + PyObject *type_obj, *name; + if (!PyArg_ParseTuple(args, "OU", &type_obj, &name)) { + return NULL; + } + if (require_type(type_obj) < 0) { + return NULL; + } + name = intern_name(name); + if (name == NULL) { + return NULL; + } + struct _PyTypeCacheLookupResult r = + _PyTypeCache_Lookup((PyTypeObject *)type_obj, name); + Py_DECREF(name); + PyObject *value; + if (PyStackRef_IsNull(r.value)) { + value = Py_NewRef(Py_None); + } + else { + value = PyStackRef_AsPyObjectSteal(r.value); + } + return Py_BuildValue("(iNk)", + r.cache_hit, value, + (unsigned long)r.version_tag); +} + +static PyObject * +type_cache_invalidate(PyObject *Py_UNUSED(self), PyObject *type_obj) +{ + if (require_type(type_obj) < 0) { + return NULL; + } + Py_BEGIN_CRITICAL_SECTION_MUTEX(&_PyInterpreterState_GET()->types.mutex); + _PyTypeCache_Invalidate((PyTypeObject *)type_obj); + Py_END_CRITICAL_SECTION(); + Py_RETURN_NONE; +} + + +static PyMethodDef test_methods[] = { + {"type_cache_lookup", type_cache_lookup, METH_VARARGS}, + {"type_cache_invalidate", type_cache_invalidate, METH_O}, + {NULL}, +}; + +int +_PyTestInternalCapi_Init_TypeCache(PyObject *m) +{ + if (PyModule_AddFunctions(m, test_methods) < 0) { + return -1; + } + if (PyModule_AddIntMacro(m, _Py_TYPECACHE_MINSIZE) < 0) { + return -1; + } + return 0; +} diff --git a/Objects/typeobject.c b/Objects/typeobject.c index ffa20ccaf3dfb87..60e26eab069b094 100644 --- a/Objects/typeobject.c +++ b/Objects/typeobject.c @@ -21,7 +21,8 @@ #include "pycore_slots.h" // _PySlotIterator_Init #include "pycore_symtable.h" // _Py_Mangle() #include "pycore_tuple.h" // _PyTuple_FromPair -#include "pycore_typeobject.h" // struct type_cache +#include "pycore_typecache.h" // _PyTypeCache_Lookup() +#include "pycore_typeobject.h" // _PyTypes_InitTypes() #include "pycore_unicodeobject.h" // _PyUnicode_Copy #include "pycore_unionobject.h" // _Py_union_type_or #include "pycore_weakref.h" // _PyWeakref_GET_REF() @@ -41,21 +42,7 @@ class object "PyObject *" "&PyBaseObject_Type" /* Support type attribute lookup cache */ -/* The cache can keep references to the names alive for longer than - they normally would. This is why the maximum size is limited to - MCACHE_MAX_ATTR_SIZE, since it might be a problem if very large - strings are used as attribute names. */ -#define MCACHE_MAX_ATTR_SIZE 100 -#define MCACHE_HASH(version, name_hash) \ - (((unsigned int)(version) ^ (unsigned int)(name_hash)) \ - & ((1 << MCACHE_SIZE_EXP) - 1)) - -#define MCACHE_HASH_METHOD(type, name) \ - MCACHE_HASH(FT_ATOMIC_LOAD_UINT_RELAXED((type)->tp_version_tag), \ - ((Py_ssize_t)(name)) >> 3) -#define MCACHE_CACHEABLE_NAME(name) \ - (PyUnicode_CheckExact(name) && \ - (PyUnicode_GET_LENGTH(name) <= MCACHE_MAX_ATTR_SIZE)) +#define MCACHE_CACHEABLE_NAME(name) (PyUnicode_CheckExact(name) && PyUnicode_CHECK_INTERNED(name)) #define NEXT_VERSION_TAG(interp) \ (interp)->types.next_version_tag @@ -969,75 +956,17 @@ _PyType_GetTextSignatureFromInternalDoc(const char *name, const char *internal_d } -static struct type_cache* -get_type_cache(void) -{ - PyInterpreterState *interp = _PyInterpreterState_GET(); - return &interp->types.type_cache; -} - - -static void -type_cache_clear(struct type_cache *cache, PyObject *value) -{ - for (Py_ssize_t i = 0; i < (1 << MCACHE_SIZE_EXP); i++) { - struct type_cache_entry *entry = &cache->hashtable[i]; -#ifdef Py_GIL_DISABLED - _PySeqLock_LockWrite(&entry->sequence); -#endif - entry->version = 0; - Py_XSETREF(entry->name, _Py_XNewRef(value)); - entry->value = NULL; -#ifdef Py_GIL_DISABLED - _PySeqLock_UnlockWrite(&entry->sequence); -#endif - } -} - - -void -_PyType_InitCache(PyInterpreterState *interp) -{ - struct type_cache *cache = &interp->types.type_cache; - for (Py_ssize_t i = 0; i < (1 << MCACHE_SIZE_EXP); i++) { - struct type_cache_entry *entry = &cache->hashtable[i]; - assert(entry->name == NULL); - - entry->version = 0; - // Set to None so _PyType_LookupRef() can use Py_SETREF(), - // rather than using slower Py_XSETREF(). - entry->name = Py_None; - entry->value = NULL; - } -} - - -static unsigned int -_PyType_ClearCache(PyInterpreterState *interp) -{ - struct type_cache *cache = &interp->types.type_cache; - // Set to None, rather than NULL, so _PyType_LookupRef() can - // use Py_SETREF() rather than using slower Py_XSETREF(). - type_cache_clear(cache, Py_None); - - return NEXT_VERSION_TAG(interp) - 1; -} - - unsigned int PyType_ClearCache(void) { PyInterpreterState *interp = _PyInterpreterState_GET(); - return _PyType_ClearCache(interp); + return NEXT_VERSION_TAG(interp) - 1; } void _PyTypes_Fini(PyInterpreterState *interp) { - struct type_cache *cache = &interp->types.type_cache; - type_cache_clear(cache, NULL); - // All the managed static types should have been finalized already. assert(interp->types.for_extensions.num_initialized == 0); for (size_t i = 0; i < _Py_MAX_MANAGED_STATIC_EXT_TYPES; i++) { @@ -1231,6 +1160,7 @@ _PyType_Modified_Unlocked(PyTypeObject *type) } set_version_unlocked(type, 0); /* 0 is not a valid version tag */ + _PyTypeCache_Invalidate(type); if (PyType_HasFeature(type, Py_TPFLAGS_HEAPTYPE)) { // This field *must* be invalidated if the type is modified (see the // comment on struct _specialization_cache): @@ -1314,6 +1244,7 @@ type_mro_modified(PyTypeObject *type, PyObject *bases) clear: assert(!(type->tp_flags & _Py_TPFLAGS_STATIC_BUILTIN)); set_version_unlocked(type, 0); /* 0 is not a valid version tag */ + _PyTypeCache_Invalidate(type); type->tp_versions_used = _Py_ATTR_CACHE_UNUSED; if (PyType_HasFeature(type, Py_TPFLAGS_HEAPTYPE)) { // This field *must* be invalidated if the type is modified (see the @@ -6212,69 +6143,6 @@ is_dunder_name(PyObject *name) return 0; } -static PyObject * -update_cache(struct type_cache_entry *entry, PyObject *name, unsigned int version_tag, PyObject *value) -{ - _Py_atomic_store_ptr_relaxed(&entry->value, value); /* borrowed */ - assert(PyUnstable_Unicode_GET_CACHED_HASH(name) != -1); - OBJECT_STAT_INC_COND(type_cache_collisions, entry->name != Py_None && entry->name != name); - // We're releasing this under the lock for simplicity sake because it's always a - // exact unicode object or Py_None so it's safe to do so. - PyObject *old_name = entry->name; - _Py_atomic_store_ptr_relaxed(&entry->name, Py_NewRef(name)); - // We must write the version last to avoid _Py_TryXGetStackRef() - // operating on an invalid (already deallocated) value inside - // _PyType_LookupRefAndVersion(). If we write the version first then a - // reader could pass the "entry_version == type_version" check but could - // be using the old entry value. - _Py_atomic_store_uint32_release(&entry->version, version_tag); - return old_name; -} - -#if Py_GIL_DISABLED - -static void -update_cache_gil_disabled(struct type_cache_entry *entry, PyObject *name, - unsigned int version_tag, PyObject *value) -{ - _PySeqLock_LockWrite(&entry->sequence); - - // update the entry - if (entry->name == name && - entry->value == value && - entry->version == version_tag) { - // We raced with another update, bail and restore previous sequence. - _PySeqLock_AbandonWrite(&entry->sequence); - return; - } - - PyObject *old_value = update_cache(entry, name, version_tag, value); - - // Then update sequence to the next valid value - _PySeqLock_UnlockWrite(&entry->sequence); - - Py_DECREF(old_value); -} - -#endif - -void -_PyTypes_AfterFork(void) -{ -#ifdef Py_GIL_DISABLED - struct type_cache *cache = get_type_cache(); - for (Py_ssize_t i = 0; i < (1 << MCACHE_SIZE_EXP); i++) { - struct type_cache_entry *entry = &cache->hashtable[i]; - if (_PySeqLock_AfterFork(&entry->sequence)) { - // Entry was in the process of updating while forking, clear it... - entry->value = NULL; - Py_SETREF(entry->name, Py_None); - entry->version = 0; - } - } -#endif -} - /* Internal API to look for a name through the MRO. This returns a strong reference, and doesn't set an exception! If nonzero, version is set to the value of type->tp_version at the time of @@ -6305,45 +6173,16 @@ should_assign_version_tag(PyTypeObject *type, PyObject *name, unsigned int versi unsigned int _PyType_LookupStackRefAndVersion(PyTypeObject *type, PyObject *name, _PyStackRef *out) { - unsigned int h = MCACHE_HASH_METHOD(type, name); - struct type_cache *cache = get_type_cache(); - struct type_cache_entry *entry = &cache->hashtable[h]; -#ifdef Py_GIL_DISABLED - // synchronize-with other writing threads by doing an acquire load on the sequence - while (1) { - uint32_t sequence = _PySeqLock_BeginRead(&entry->sequence); - uint32_t entry_version = _Py_atomic_load_uint32_acquire(&entry->version); - uint32_t type_version = _Py_atomic_load_uint32_acquire(&type->tp_version_tag); - if (entry_version == type_version && - _Py_atomic_load_ptr_relaxed(&entry->name) == name) { + int cacheable = MCACHE_CACHEABLE_NAME(name); + if (cacheable) { + struct _PyTypeCacheLookupResult r = _PyTypeCache_Lookup(type, name); + if (r.cache_hit) { OBJECT_STAT_INC_COND(type_cache_hits, !is_dunder_name(name)); OBJECT_STAT_INC_COND(type_cache_dunder_hits, is_dunder_name(name)); - if (_Py_TryXGetStackRef(&entry->value, out)) { - // If the sequence is still valid then we're done - if (_PySeqLock_EndRead(&entry->sequence, sequence)) { - return entry_version; - } - PyStackRef_XCLOSE(*out); - } - else { - // If we can't incref the object we need to fallback to locking - break; - } - } - else { - // cache miss - break; + *out = r.value; + return r.version_tag; } } -#else - if (entry->version == type->tp_version_tag && entry->name == name) { - assert(type->tp_version_tag); - OBJECT_STAT_INC_COND(type_cache_hits, !is_dunder_name(name)); - OBJECT_STAT_INC_COND(type_cache_dunder_hits, is_dunder_name(name)); - *out = entry->value ? PyStackRef_FromPyObjectNew(entry->value) : PyStackRef_NULL; - return entry->version; - } -#endif OBJECT_STAT_INC_COND(type_cache_misses, !is_dunder_name(name)); OBJECT_STAT_INC_COND(type_cache_dunder_misses, is_dunder_name(name)); @@ -6354,14 +6193,25 @@ _PyType_LookupStackRefAndVersion(PyTypeObject *type, PyObject *name, _PyStackRef PyInterpreterState *interp = _PyInterpreterState_GET(); unsigned int version_tag = FT_ATOMIC_LOAD_UINT(type->tp_version_tag); - if (should_assign_version_tag(type, name, version_tag)) { + if (cacheable && + (version_tag != 0 || should_assign_version_tag(type, name, version_tag))) + { BEGIN_TYPE_LOCK(); - assign_version_tag(interp, type); version_tag = type->tp_version_tag; + if (version_tag == 0) { + assign_version_tag(interp, type); + version_tag = type->tp_version_tag; + } res = find_name_in_mro(type, name, out); + // find_name_in_mro can release the type lock and another thread can + // modify the type, so we need to check version tag again before caching the result. + if (res >= 0 && version_tag != 0 && version_tag == type->tp_version_tag) { + _PyTypeCache_Insert(type, name, PyStackRef_AsPyObjectBorrow(*out)); + } END_TYPE_LOCK(); } else { + version_tag = 0; res = find_name_in_mro(type, name, out); } @@ -6371,17 +6221,6 @@ _PyType_LookupStackRefAndVersion(PyTypeObject *type, PyObject *name, _PyStackRef return 0; } - if (version_tag == 0 || !MCACHE_CACHEABLE_NAME(name)) { - return 0; - } - - PyObject *res_obj = PyStackRef_AsPyObjectBorrow(*out); -#if Py_GIL_DISABLED - update_cache_gil_disabled(entry, name, version_tag, res_obj); -#else - PyObject *old_value = update_cache(entry, name, version_tag, res_obj); - Py_DECREF(old_value); -#endif return version_tag; } @@ -6840,7 +6679,10 @@ type_setattro(PyObject *self, PyObject *name, PyObject *value) done: Py_DECREF(name); Py_XDECREF(descr); - Py_XDECREF(old_value); + // delay decref of the old value as lock-free type cache readers may access it + if (old_value != NULL && !_Py_IsImmortal(old_value)) { + _PyObject_XDecRefDelayed(old_value); + } return res; } @@ -6912,6 +6754,7 @@ clear_static_type_objects(PyInterpreterState *interp, PyTypeObject *type, if (final) { Py_CLEAR(type->tp_cache); } + _PyTypeCache_Invalidate(type); clear_tp_dict(type); clear_tp_bases(type, final); clear_tp_mro(type, final); @@ -7022,6 +6865,7 @@ type_dealloc(PyObject *self) Py_XDECREF(type->tp_mro); Py_XDECREF(type->tp_cache); clear_tp_subclasses(type); + _PyTypeCache_Invalidate(type); /* A type's tp_doc is heap allocated, unlike the tp_doc slots * of most other objects. It's okay to cast it to char *. @@ -9536,6 +9380,8 @@ type_ready(PyTypeObject *type, int initial) goto error; } + _PyTypeCache_InitType(type); + #ifdef Py_TRACE_REFS /* PyType_Ready is the closest thing we have to a choke point * for type objects, so is the best place I can think of to try diff --git a/PCbuild/_freeze_module.vcxproj b/PCbuild/_freeze_module.vcxproj index 04bd36404366a57..246a07785168161 100644 --- a/PCbuild/_freeze_module.vcxproj +++ b/PCbuild/_freeze_module.vcxproj @@ -284,6 +284,7 @@ <ClCompile Include="..\Python\thread.c" /> <ClCompile Include="..\Python\traceback.c" /> <ClCompile Include="..\Python\tracemalloc.c" /> + <ClCompile Include="..\Python\typecache.c" /> <ClCompile Include="..\Python\uniqueid.c" /> </ItemGroup> <ItemGroup> diff --git a/PCbuild/_freeze_module.vcxproj.filters b/PCbuild/_freeze_module.vcxproj.filters index 7710acf43b5137c..35082f57f54e9d8 100644 --- a/PCbuild/_freeze_module.vcxproj.filters +++ b/PCbuild/_freeze_module.vcxproj.filters @@ -496,6 +496,9 @@ <ClCompile Include="..\Python\tracemalloc.c"> <Filter>Source Files</Filter> </ClCompile> + <ClCompile Include="..\Python\typecache.c"> + <Filter>Source Files</Filter> + </ClCompile> <ClCompile Include="..\Python\uniqueid.c"> <Filter>Source Files</Filter> </ClCompile> diff --git a/PCbuild/_testinternalcapi.vcxproj b/PCbuild/_testinternalcapi.vcxproj index f3e423fa04668ec..cd58c3523e8c160 100644 --- a/PCbuild/_testinternalcapi.vcxproj +++ b/PCbuild/_testinternalcapi.vcxproj @@ -101,6 +101,7 @@ <ClCompile Include="..\Modules\_testinternalcapi\complex.c" /> <ClCompile Include="..\Modules\_testinternalcapi\interpreter.c" /> <ClCompile Include="..\Modules\_testinternalcapi\tuple.c" /> + <ClCompile Include="..\Modules\_testinternalcapi\typecache.c" /> </ItemGroup> <ItemGroup> <ResourceCompile Include="..\PC\python_nt.rc" /> diff --git a/PCbuild/_testinternalcapi.vcxproj.filters b/PCbuild/_testinternalcapi.vcxproj.filters index 7ab242c2c230b67..4082c36234bdf0f 100644 --- a/PCbuild/_testinternalcapi.vcxproj.filters +++ b/PCbuild/_testinternalcapi.vcxproj.filters @@ -30,6 +30,9 @@ <ClCompile Include="..\Modules\_testinternalcapi\tuple.c"> <Filter>Source Files</Filter> </ClCompile> + <ClCompile Include="..\Modules\_testinternalcapi\typecache.c"> + <Filter>Source Files</Filter> + </ClCompile> </ItemGroup> <ItemGroup> <ResourceCompile Include="..\PC\python_nt.rc"> diff --git a/PCbuild/pythoncore.vcxproj b/PCbuild/pythoncore.vcxproj index 47296a93424a8f6..7fec674c550e027 100644 --- a/PCbuild/pythoncore.vcxproj +++ b/PCbuild/pythoncore.vcxproj @@ -332,6 +332,7 @@ <ClInclude Include="..\Include\internal\pycore_tracemalloc.h" /> <ClInclude Include="..\Include\internal\pycore_tstate.h" /> <ClInclude Include="..\Include\internal\pycore_tuple.h" /> + <ClInclude Include="..\Include\internal\pycore_typecache.h" /> <ClInclude Include="..\Include\internal\pycore_typedefs.h" /> <ClInclude Include="..\Include\internal\pycore_typeobject.h" /> <ClInclude Include="..\Include\internal\pycore_typevarobject.h" /> @@ -703,6 +704,7 @@ <ClCompile Include="..\Python\thread.c" /> <ClCompile Include="..\Python\traceback.c" /> <ClCompile Include="..\Python\tracemalloc.c" /> + <ClCompile Include="..\Python\typecache.c" /> <ClCompile Include="..\Python\uniqueid.c" /> </ItemGroup> <ItemGroup Condition="$(IncludeExternals)"> diff --git a/PCbuild/pythoncore.vcxproj.filters b/PCbuild/pythoncore.vcxproj.filters index 124f6c7bb90de6c..cb0f6fce86df51a 100644 --- a/PCbuild/pythoncore.vcxproj.filters +++ b/PCbuild/pythoncore.vcxproj.filters @@ -897,6 +897,9 @@ <ClInclude Include="..\Include\internal\pycore_tuple.h"> <Filter>Include\internal</Filter> </ClInclude> + <ClInclude Include="..\Include\internal\pycore_typecache.h"> + <Filter>Include\internal</Filter> + </ClInclude> <ClInclude Include="..\Include\internal\pycore_typedefs.h"> <Filter>Include\internal</Filter> </ClInclude> @@ -1622,6 +1625,9 @@ <ClCompile Include="..\Python\tracemalloc.c"> <Filter>Python</Filter> </ClCompile> + <ClCompile Include="..\Python\typecache.c"> + <Filter>Python</Filter> + </ClCompile> <ClCompile Include="..\Python\uniqueid.c"> <Filter>Python</Filter> </ClCompile> diff --git a/Python/pystate.c b/Python/pystate.c index e90642fa882db72..d10b38def32911d 100644 --- a/Python/pystate.c +++ b/Python/pystate.c @@ -12,7 +12,7 @@ #include "pycore_freelist.h" // _PyObject_ClearFreeLists() #include "pycore_initconfig.h" // _PyStatus_OK() #include "pycore_interpframe.h" // _PyThreadState_HasStackSpace() -#include "pycore_object.h" // _PyType_InitCache(), _Py_ClearImmortal() +#include "pycore_object.h" // _Py_ClearImmortal() #include "pycore_obmalloc.h" // _PyMem_obmalloc_state_on_heap() #include "pycore_opcode_utils.h" // NUM_COMMON_CONSTANTS #include "pycore_optimizer.h" // JIT_CLEANUP_THRESHOLD @@ -420,8 +420,6 @@ _PyRuntimeState_ReInitThreads(_PyRuntimeState *runtime) } #endif - _PyTypes_AfterFork(); - _PyThread_AfterFork(&runtime->threads); return _PyStatus_OK(); @@ -573,7 +571,6 @@ init_interpreter(PyInterpreterState *interp, _PyEval_InitState(interp); _PyGC_InitState(&interp->gc); PyConfig_InitPythonConfig(&interp->config); - _PyType_InitCache(interp); #ifdef Py_GIL_DISABLED _Py_brc_init_state(interp); #endif diff --git a/Python/pystats.c b/Python/pystats.c index 2fac2db1b738c7e..6862521f659f202 100644 --- a/Python/pystats.c +++ b/Python/pystats.c @@ -230,9 +230,11 @@ print_object_stats(FILE *out, ObjectStats *stats) fprintf(out, "Object materialize dict (str subclass): %" PRIu64 "\n", stats->dict_materialized_str_subclass); fprintf(out, "Object method cache hits: %" PRIu64 "\n", stats->type_cache_hits); fprintf(out, "Object method cache misses: %" PRIu64 "\n", stats->type_cache_misses); - fprintf(out, "Object method cache collisions: %" PRIu64 "\n", stats->type_cache_collisions); + fprintf(out, "Object method cache too big: %" PRIu64 "\n", stats->type_cache_too_big); fprintf(out, "Object method cache dunder hits: %" PRIu64 "\n", stats->type_cache_dunder_hits); fprintf(out, "Object method cache dunder misses: %" PRIu64 "\n", stats->type_cache_dunder_misses); + fprintf(out, "Object method cache invalidations: %" PRIu64 "\n", stats->type_cache_invalidations); + fprintf(out, "Object method cache resizes: %" PRIu64 "\n", stats->type_cache_resizes); } static void @@ -439,7 +441,9 @@ merge_object_stats(ObjectStats *dest, const ObjectStats *src) dest->type_cache_misses += src->type_cache_misses; dest->type_cache_dunder_hits += src->type_cache_dunder_hits; dest->type_cache_dunder_misses += src->type_cache_dunder_misses; - dest->type_cache_collisions += src->type_cache_collisions; + dest->type_cache_too_big += src->type_cache_too_big; + dest->type_cache_invalidations += src->type_cache_invalidations; + dest->type_cache_resizes += src->type_cache_resizes; dest->object_visits += src->object_visits; } diff --git a/Python/typecache.c b/Python/typecache.c new file mode 100644 index 000000000000000..26079de5ce341f7 --- /dev/null +++ b/Python/typecache.c @@ -0,0 +1,246 @@ +// Per-type method cache implementation + +// The cache is used for method and attribute lookups on type objects. +// The stored names are always interned strings, and the +// stored values are borrowed references to the corresponding method or attribute object. +// For static types, the cache is stored on the per-interpreter managed_static_type_state, +// and for heap types the cache is stored in the `PyTypeObject._tp_cache` field. + +#include "Python.h" +#include "pycore_typecache.h" +#include "pycore_interp.h" // PyInterpreterState +#include "pycore_pymem.h" +#include "pycore_pystate.h" // _PyInterpreterState_GET() +#include "pycore_pyatomic_ft_wrappers.h" +#include "pycore_typeobject.h" // _PyStaticType_GetState() +#include "pycore_stats.h" // OBJECT_STAT_INC + + +// The empty cache is statically allocated and shared across all the types, +// when a type is modified, the cache of type is set to the empty cache +// and when a cache entry is inserted to the empty cache, a new cache is +// allocated for the type and the entry is inserted to the new cache. +static struct type_cache empty_cache = { + .mask = _Py_TYPECACHE_MINSIZE - 1, + .version_tag = 0, + .available = 0, + .used = 0, +}; + +static inline uint32_t +cache_size(struct type_cache *cache) +{ + return cache->mask + 1; +} + +static inline size_t +cache_nbytes(struct type_cache *cache) +{ + return offsetof(struct type_cache, hashtable) + + (size_t)cache_size(cache) * sizeof(struct type_cache_entry); +} + +static struct type_cache * +cache_allocate(uint32_t size) +{ + // size must be a power of two + assert((size & (size - 1)) == 0); + size_t nbytes = offsetof(struct type_cache, hashtable) + + (size_t)size * sizeof(struct type_cache_entry); + struct type_cache *cache = PyMem_Calloc(1, nbytes); + if (cache == NULL) { + return NULL; + } + cache->mask = size - 1; + // load factor of 0.75 + cache->available = size - (size >> 2); + cache->used = 0; + return cache; +} + +static void +cache_free_delayed(struct type_cache *cache) +{ + if (cache == NULL || cache == &empty_cache) { + return; + } +#ifndef Py_GIL_DISABLED + // On gil-enabled builds, the cache owns strong references to the interned strings, + // so we need to decref them before freeing the cache memory. + for (uint32_t i = 0; i < cache_size(cache); i++) { + if (cache->hashtable[i].name != NULL) { + Py_DECREF(cache->hashtable[i].name); + } + } +#endif + // Delay the freeing of old cache for concurrent lock-free readers + _PyMem_FreeDelayed(cache, cache_nbytes(cache)); +} + + +static inline void ** +cache_slot(PyTypeObject *type) +{ + if (type->tp_flags & _Py_TPFLAGS_STATIC_BUILTIN) { + PyInterpreterState *interp = _PyInterpreterState_GET(); + managed_static_type_state *state = _PyStaticType_GetState(interp, type); + assert(state != NULL); + return &state->_tp_cache; + } + return &type->_tp_cache; +} + +static inline struct type_cache * +cache_get(PyTypeObject *type) +{ + return (struct type_cache *)FT_ATOMIC_LOAD_PTR_ACQUIRE(*cache_slot(type)); +} + +static inline void +cache_set(PyTypeObject *type, struct type_cache *cache) +{ + FT_ATOMIC_STORE_PTR_RELEASE(*cache_slot(type), cache); +} + +void +_PyTypeCache_InitType(PyTypeObject *type) +{ + *cache_slot(type) = &empty_cache; +} + +static inline void +cache_insert(struct type_cache *cache, PyObject *name, + PyObject *value) +{ + Py_hash_t hash = PyUnstable_Unicode_GET_CACHED_HASH(name); + assert(hash != -1); + uint32_t index = hash & cache->mask; + for (;;) { + if (cache->hashtable[index].name == NULL) { +#ifndef Py_GIL_DISABLED + // On free-threading, all interned strings are immortal. + Py_INCREF(name); +#endif + cache->hashtable[index].value = value; + FT_ATOMIC_STORE_PTR_RELEASE(cache->hashtable[index].name, name); + cache->used++; + cache->available--; + return; + } + else if (cache->hashtable[index].name == name) { + /* someone else added the entry before us. */ + return; + } + index = (index + 1) & cache->mask; + } +} + +static inline int +cache_resize(PyTypeObject *type, struct type_cache *cache) +{ + uint32_t old_size = cache_size(cache); + uint32_t new_size; + if (cache->used == 0) { + // the cache is the empty cache, we need to allocate a new cache with the minimum size + new_size = _Py_TYPECACHE_MINSIZE; + } + else { + // double the cache size when resizing + new_size = old_size * 2; + } + if (new_size > _Py_TYPECACHE_MAXSIZE) { + // The new size is too big, don't resize and just return. + OBJECT_STAT_INC(type_cache_too_big); + return -1; + } + struct type_cache *new_cache = cache_allocate(new_size); + if (new_cache == NULL) { + return -1; + } + OBJECT_STAT_INC(type_cache_resizes); + for (uint32_t i = 0; i < old_size; i++) { + if (cache->hashtable[i].name != NULL) { + cache_insert(new_cache, cache->hashtable[i].name, cache->hashtable[i].value); + } + } + new_cache->version_tag = type->tp_version_tag; + cache_set(type, new_cache); + cache_free_delayed(cache); + return 0; +} + +// Insert a new entry to the type cache. +// The TYPE_LOCK should be held while calling this function. +void +_PyTypeCache_Insert(PyTypeObject *type, PyObject *name, PyObject *value) +{ + struct type_cache *cache = cache_get(type); + // If the cache is full, resize it before inserting the new entry. + // this also handles the case of empty cache where available is 0 but there are no entries. + if (cache->available == 0) { + if (cache_resize(type, cache) == -1) { + // out of memory, don't cache the value + return; + } + cache = cache_get(type); + assert(cache->available > 0); + } + assert(cache->version_tag == type->tp_version_tag); + cache_insert(cache, name, value); +} + + +// Lookup the given name in the type cache. +// The cache is lock-free so it is possible that cache becomes stale during the lookup, +// to prevent returning stale cache entry, the cache version is compared with the type version tag. +struct _PyTypeCacheLookupResult +_PyTypeCache_Lookup(PyTypeObject *type, PyObject *name) +{ + assert(PyUnicode_CheckExact(name) && PyUnicode_CHECK_INTERNED(name)); + struct _PyTypeCacheLookupResult miss = {PyStackRef_NULL, 0, 0}; + struct type_cache *cache = cache_get(type); + if (cache == NULL) { + return miss; + } + Py_hash_t hash = PyUnstable_Unicode_GET_CACHED_HASH(name); + assert(hash != -1); + uint32_t index = hash & cache->mask; + _PyStackRef out_ref; + for (;;) { + PyObject *entry_name = FT_ATOMIC_LOAD_PTR_ACQUIRE(cache->hashtable[index].name); + if (entry_name == name) { +#ifdef Py_GIL_DISABLED + if (!_Py_TryXGetStackRef(&cache->hashtable[index].value, &out_ref)) { + return miss; + } +#else + PyObject *v = cache->hashtable[index].value; + out_ref = v ? PyStackRef_FromPyObjectNew(v) : PyStackRef_NULL; +#endif + break; + } + else if (entry_name == NULL) { + return miss; + } + index = (index + 1) & cache->mask; + } + // Check the cache version against the type version tag to maintain + // consistency with find_name_in_mro and prevent stale cache reads + if (cache->version_tag != FT_ATOMIC_LOAD_UINT_RELAXED(type->tp_version_tag)) { + PyStackRef_XCLOSE(out_ref); + return miss; + } + return (struct _PyTypeCacheLookupResult){out_ref, 1, cache->version_tag}; +} + +// Invalidate the type cache of the type. +// The cache is set to the empty cache and the old cache is freed with QSBR. +// The TYPE_LOCK should be held while calling this function. +void +_PyTypeCache_Invalidate(PyTypeObject *type) +{ + OBJECT_STAT_INC(type_cache_invalidations); + struct type_cache *cache = cache_get(type); + cache_set(type, &empty_cache); + cache_free_delayed(cache); +} diff --git a/Tools/c-analyzer/cpython/ignored.tsv b/Tools/c-analyzer/cpython/ignored.tsv index 6e18593ad698570..ef314625d507d61 100644 --- a/Tools/c-analyzer/cpython/ignored.tsv +++ b/Tools/c-analyzer/cpython/ignored.tsv @@ -57,6 +57,9 @@ Python/pyhash.c - _Py_HashSecret - ## thread-safe hashtable (internal locks) Python/parking_lot.c - buckets - +## shared empty sentinel for the per-type method cache +Python/typecache.c - empty_cache - + ## data needed for introspecting asyncio state from debuggers and profilers Modules/_asynciomodule.c - _Py_AsyncioDebug - diff --git a/Tools/ftscalingbench/ftscalingbench.py b/Tools/ftscalingbench/ftscalingbench.py index c8a914c22a9e137..a79242e740371ba 100644 --- a/Tools/ftscalingbench/ftscalingbench.py +++ b/Tools/ftscalingbench/ftscalingbench.py @@ -325,6 +325,19 @@ def enum_attr(): MyEnum.Y MyEnum.Z +_MCACHE_NUM_TYPES = 1 << 14 +_MCACHE_PAIRS = [ + (type(f"C{i}", (), {f"m{i}": i % 256})(), sys.intern(f"m{i}")) + for i in range(_MCACHE_NUM_TYPES) +] + +@register_benchmark +def type_lookup(): + pairs = _MCACHE_PAIRS + for _ in range(WORK_SCALE // 10): + for inst, name in pairs: + getattr(inst, name) + def bench_one_thread(func): t0 = time.perf_counter_ns() _______________________________________________ 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]