python · brijkapadia · May 30, 2026 · May 30, 2026 · May 30, 2026 · May 31, 2026
diff --git a/Include/internal/pycore_dict.h b/Include/internal/pycore_dict.h
@@ -220,35 +220,29 @@ struct _dictkeysobject {
     /* Number of used entries in dk_entries. */
     Py_ssize_t dk_nentries;
 
-
-    /* Actual hash table of dk_size entries. It holds indices in dk_entries,
-       or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
-
-       Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
-
-       The size in bytes of an indice depends on dk_size:
-
-       - 1 byte if dk_size <= 0xff (char*)
-       - 2 bytes if dk_size <= 0xffff (int16_t*)
-       - 4 bytes if dk_size <= 0xffffffff (int32_t*)
-       - 8 bytes otherwise (int64_t*)
-
-       Dynamically sized, SIZEOF_VOID_P is minimum. */
-    char dk_indices[];  /* char is required to avoid strict aliasing. */
-
-    /* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
-       see the DK_ENTRIES() / DK_UNICODE_ENTRIES() functions below */
+     union {
+        PyDictKeyEntry entries[1];
+        PyDictUnicodeEntry unicode_entries[1];
+    } dk_entries;
 };
 
+/* For split dictionaries, the allocation layout is:
+    [_instancekeysobject    ]
+    [dk_indices[] array     ]
+    [PyDictKeysObject header]
+    [dk_entries[] array     ]
+*/
 struct _instancekeysobject {
     PyTypeObject* dsk_owning_type;
-    struct _dictkeysobject dsk_keys;
 };
 
 static inline struct _instancekeysobject *_PyDictKeys_AsSharedKeys(struct _dictkeysobject *keys)
 {
     assert(keys->dk_kind == DICT_KEYS_SPLIT);
-    return _Py_CONTAINER_OF(keys, struct _instancekeysobject, dsk_keys);
+    size_t index_bytes = (size_t)1 << keys->dk_log2_index_bytes;
+    return (struct _instancekeysobject *)((char *)keys
+                                          - index_bytes
+                                          - sizeof(struct _instancekeysobject));
 }
 
 /* This must be no more than 250, for the prefix size to fit in one byte. */
@@ -270,25 +264,32 @@ struct _dictvalues {
 };
 
 #define DK_LOG_SIZE(dk)  _Py_RVALUE((dk)->dk_log2_size)
+#define DK_LOG_INDEX_BYTES(dk) \
+    _Py_RVALUE((dk)->dk_log2_index_bytes)
 #if SIZEOF_VOID_P > 4
 #define DK_SIZE(dk)      (((int64_t)1)<<DK_LOG_SIZE(dk))
+#define DK_INDEX_BYTES(dk) \
+    (((int64_t)1)<<DK_LOG_INDEX_BYTES(dk))
 #else
 #define DK_SIZE(dk)      (1<<DK_LOG_SIZE(dk))
+#define DK_INDEX_BYTES(dk) (1<<DK_LOG_INDEX_BYTES(dk))
 #endif
+#define _DK_INDICES(dk) ((char *)(dk) - DK_INDEX_BYTES(dk))
+#define _DK_FROM_BASE(base, index_size) \
+    ((PyDictKeysObject *)((char *)(base) + ((size_t) index_size)))
 
 static inline void* _DK_ENTRIES(PyDictKeysObject *dk) {
-    int8_t *indices = (int8_t*)(dk->dk_indices);
-    size_t index = (size_t)1 << dk->dk_log2_index_bytes;
-    return (&indices[index]);
+    return (void *)(&dk->dk_entries);
 }
 
 static inline PyDictKeyEntry* DK_ENTRIES(PyDictKeysObject *dk) {
     assert(dk->dk_kind == DICT_KEYS_GENERAL);
-    return (PyDictKeyEntry*)_DK_ENTRIES(dk);
+    return dk->dk_entries.entries;
 }
+
 static inline PyDictUnicodeEntry* DK_UNICODE_ENTRIES(PyDictKeysObject *dk) {
     assert(dk->dk_kind != DICT_KEYS_GENERAL);
-    return (PyDictUnicodeEntry*)_DK_ENTRIES(dk);
+    return dk->dk_entries.unicode_entries;
 }
 
 #define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)

diff --git a/Lib/test/test_dict.py b/Lib/test/test_dict.py
@@ -1816,6 +1816,21 @@ def __hash__(self):
         self.assertEqual(dict_getitem_knownhash(d, k1, hash(k1)), 1)
         self.assertRaises(Exc, dict_getitem_knownhash, d, k2, hash(k2))
 
+    @support.cpython_only
+    def test_dict_keys_layout(self):
+        _testinternalcapi = import_helper.import_module('_testinternalcapi')
+        check_layout = _testinternalcapi.dict_keys_layout
+
+        for i in range(4):
+            self.assertTrue(check_layout({j: j for j in range(10**i)}))
+
+    @support.cpython_only
+    def test_dict_keys_to_base(self):
+        _testinternalcapi = import_helper.import_module('_testinternalcapi')
+        check_base = _testinternalcapi.dict_keys_to_base
+
+        for i in range(4):
+            self.assertTrue(check_base({j: j for j in range(10**i)}))
 
 from test import mapping_tests
 

diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2026-05-30-21-37-54.gh-issue-142889.LvkzYw.rst b/Misc/NEWS.d/next/Core_and_Builtins/2026-05-30-21-37-54.gh-issue-142889.LvkzYw.rst
@@ -0,0 +1 @@
+Update the memory layout of how :class:`dict` handles the memory of the keys to improve performance.
@@ -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/tokenizer.c _testinternalcapi/tuple.c _testinternalcapi/typecache.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/tokenizer.c _testinternalcapi/tuple.c _testinternalcapi/typecache.c _testinternalcapi/dict.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/capsule.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 _testlimitedcapi/type.c
 @MODULE__TESTCLINIC_TRUE@_testclinic _testclinic.c

diff --git a/Modules/_testinternalcapi.c b/Modules/_testinternalcapi.c
@@ -3428,6 +3428,9 @@ module_exec(PyObject *module)
     if (_PyTestInternalCapi_Init_TypeCache(module) < 0) {
         return 1;
     }
+    if (_PyTestInternalCapi_Init_Dict(module) < 0) {
+        return 1;
+    }
 
     Py_ssize_t sizeof_gc_head = 0;
 #ifndef Py_GIL_DISABLED

diff --git a/Modules/_testinternalcapi/dict.c b/Modules/_testinternalcapi/dict.c
@@ -0,0 +1,50 @@
+#include "parts.h"
+
+#include "pycore_dict.h"
+
+static PyObject*
+dict_keys_layout(PyObject *self, PyObject *arg)
+{
+    PyDictObject *mp = (PyDictObject *)arg;
+    PyDictKeysObject *keys = mp->ma_keys;
+
+    size_t indices_size = DK_INDEX_BYTES(keys);
+
+    char *base = _DK_INDICES(keys);
+    char *header = (char *)keys;
+    char *entries = (char *)_DK_ENTRIES(keys);
+
+    bool ok = true;
+    ok &= (header == base + indices_size);
+    ok &= (entries == header + offsetof(PyDictKeysObject, dk_entries));
+
+    return PyBool_FromLong(ok);
+}
+
+static PyObject*
+dict_keys_to_base(PyObject *self, PyObject *arg)
+{
+    PyDictObject *mp = (PyDictObject *)arg;
+    PyDictKeysObject *keys = mp->ma_keys;
+
+    void *base = _DK_INDICES(keys);
+    size_t indices_size = DK_INDEX_BYTES(keys);
+    bool ok = _DK_FROM_BASE(base, indices_size) == keys;
+
+    return PyBool_FromLong(ok);
+}
+
+static PyMethodDef test_methods[] = {
+    {"dict_keys_layout", dict_keys_layout, METH_O},
+    {"dict_keys_to_base", dict_keys_to_base, METH_O},
+    {NULL},
+};
+
+int
+_PyTestInternalCapi_Init_Dict(PyObject *m)
+{
+    if (PyModule_AddFunctions(m, test_methods) < 0) {
+        return -1;
+    }
+    return 0;
+}
diff --git a/Modules/_testinternalcapi/parts.h b/Modules/_testinternalcapi/parts.h
@@ -18,5 +18,6 @@ int _PyTestInternalCapi_Init_CriticalSection(PyObject *module);
 int _PyTestInternalCapi_Init_Tokenizer(PyObject *module);
 int _PyTestInternalCapi_Init_Tuple(PyObject *module);
 int _PyTestInternalCapi_Init_TypeCache(PyObject *module);
+int _PyTestInternalCapi_Init_Dict(PyObject *module);
 
 #endif // Py_TESTINTERNALCAPI_PARTS_H
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		Update the memory layout of how :class:`dict` handles the memory of the keys to improve performance.