Skip to content

Commit a7252f8

Browse files
markshannonmarkshannon
authored
bpo-40116: Add insertion order bit-vector to dict values to allow dicts to share keys more freely. (GH-28520)
1 parent f6eafe1 commit a7252f8

8 files changed

Lines changed: 176 additions & 187 deletions

File tree

‎Include/cpython/dictobject.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
#endif
44

55
typedef struct _dictkeysobject PyDictKeysObject;
6+
typedef struct _dictvalues PyDictValues;
67

78
/* The ma_values pointer is NULL for a combined table
89
* or points to an array of PyObject* for a split table
@@ -24,7 +25,7 @@ typedef struct {
2425
2526
If ma_values is not NULL, the table is splitted:
2627
keys are stored in ma_keys and values are stored in ma_values */
27-
PyObject **ma_values;
28+
PyDictValues *ma_values;
2829
} PyDictObject;
2930

3031
PyAPI_FUNC(PyObject *) _PyDict_GetItem_KnownHash(PyObject *mp, PyObject *key,

‎Include/internal/pycore_dict.h‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -71,6 +71,14 @@ struct _dictkeysobject {
7171
see the DK_ENTRIES() macro */
7272
};
7373

74+
/* This must be no more than 16, for the order vector to fit in 64 bits */
75+
#define SHARED_KEYS_MAX_SIZE 16
76+
77+
struct _dictvalues {
78+
uint64_t mv_order;
79+
PyObject *values[1];
80+
};
81+
7482
#define DK_LOG_SIZE(dk) ((dk)->dk_log2_size)
7583
#if SIZEOF_VOID_P > 4
7684
#define DK_SIZE(dk) (((int64_t)1)<<DK_LOG_SIZE(dk))

‎Lib/test/test_dict.py‎

Lines changed: 1 addition & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -1020,7 +1020,6 @@ def test_splittable_del(self):
10201020
with self.assertRaises(KeyError):
10211021
del a['y']
10221022

1023-
self.assertGreater(sys.getsizeof(a), orig_size)
10241023
self.assertEqual(list(a), ['x', 'z'])
10251024
self.assertEqual(list(b), ['x', 'y', 'z'])
10261025

@@ -1031,16 +1030,12 @@ def test_splittable_del(self):
10311030

10321031
@support.cpython_only
10331032
def test_splittable_pop(self):
1034-
"""split table must be combined when d.pop(k)"""
10351033
a, b = self.make_shared_key_dict(2)
10361034

1037-
orig_size = sys.getsizeof(a)
1038-
1039-
a.pop('y') # split table is combined
1035+
a.pop('y')
10401036
with self.assertRaises(KeyError):
10411037
a.pop('y')
10421038

1043-
self.assertGreater(sys.getsizeof(a), orig_size)
10441039
self.assertEqual(list(a), ['x', 'z'])
10451040
self.assertEqual(list(b), ['x', 'y', 'z'])
10461041

@@ -1074,36 +1069,6 @@ def test_splittable_popitem(self):
10741069
self.assertEqual(list(a), ['x', 'y'])
10751070
self.assertEqual(list(b), ['x', 'y', 'z'])
10761071

1077-
@support.cpython_only
1078-
def test_splittable_setattr_after_pop(self):
1079-
"""setattr() must not convert combined table into split table."""
1080-
# Issue 28147
1081-
import _testcapi
1082-
1083-
class C:
1084-
pass
1085-
a = C()
1086-
1087-
a.a = 1
1088-
self.assertTrue(_testcapi.dict_hassplittable(a.__dict__))
1089-
1090-
# dict.pop() convert it to combined table
1091-
a.__dict__.pop('a')
1092-
self.assertFalse(_testcapi.dict_hassplittable(a.__dict__))
1093-
1094-
# But C should not convert a.__dict__ to split table again.
1095-
a.a = 1
1096-
self.assertFalse(_testcapi.dict_hassplittable(a.__dict__))
1097-
1098-
# Same for popitem()
1099-
a = C()
1100-
a.a = 2
1101-
self.assertTrue(_testcapi.dict_hassplittable(a.__dict__))
1102-
a.__dict__.popitem()
1103-
self.assertFalse(_testcapi.dict_hassplittable(a.__dict__))
1104-
a.a = 3
1105-
self.assertFalse(_testcapi.dict_hassplittable(a.__dict__))
1106-
11071072
def test_iterator_pickling(self):
11081073
for proto in range(pickle.HIGHEST_PROTOCOL + 1):
11091074
data = {1:"a", 2:"b", 3:"c"}

‎Misc/NEWS.d/next/Core and Builtins/2021-09-23-14-00-05.bpo-40116.KaoeFs.rst‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
Change to the implementation of split dictionaries. Classes where the
2+
instances differ either in the exact set of attributes, or in the order in
3+
which those attributes are set, can still share keys. This should have no
4+
observable effect on users of Python or the C-API. Patch by Mark Shannon.

‎Modules/_testcapimodule.c‎

Lines changed: 0 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -334,19 +334,6 @@ dict_getitem_knownhash(PyObject *self, PyObject *args)
334334
return result;
335335
}
336336

337-
static PyObject*
338-
dict_hassplittable(PyObject *self, PyObject *arg)
339-
{
340-
if (!PyDict_Check(arg)) {
341-
PyErr_Format(PyExc_TypeError,
342-
"dict_hassplittable() argument must be dict, not '%s'",
343-
Py_TYPE(arg)->tp_name);
344-
return NULL;
345-
}
346-
347-
return PyBool_FromLong(_PyDict_HasSplitTable((PyDictObject*)arg));
348-
}
349-
350337
/* Issue #4701: Check that PyObject_Hash implicitly calls
351338
* PyType_Ready if it hasn't already been called
352339
*/
@@ -5721,7 +5708,6 @@ static PyMethodDef TestMethods[] = {
57215708
{"test_list_api", test_list_api, METH_NOARGS},
57225709
{"test_dict_iteration", test_dict_iteration, METH_NOARGS},
57235710
{"dict_getitem_knownhash", dict_getitem_knownhash, METH_VARARGS},
5724-
{"dict_hassplittable", dict_hassplittable, METH_O},
57255711
{"test_lazy_hash_inheritance", test_lazy_hash_inheritance,METH_NOARGS},
57265712
{"test_long_api", test_long_api, METH_NOARGS},
57275713
{"test_xincref_doesnt_leak",test_xincref_doesnt_leak, METH_NOARGS},

0 commit comments

Comments
 (0)