8000 Lock less and deal with atomic updates to shared size · python/cpython@fe12c49 · GitHub
[go: up one dir, main page]
Skip to content

Commit fe12c49

Browse files
DinoVDinoV
committed
Lock less and deal with atomic updates to shared size
1 parent 4da5161 commit fe12c49

File tree

5 files changed

+65
-19
lines changed

5 files changed

+65
-19
lines changed

‎Include/cpython/pyatomic.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -469,6 +469,9 @@ _Py_atomic_store_int_release(int *obj, int value);
469469
static inline int
470470
_Py_atomic_load_int_acquire(const int *obj);
471471

472+
static inline Py_ssize_t
473+
_Py_atomic_load_ssize_acquire(const Py_ssize_t *obj);
474+
472475

473476
// --- _Py_atomic_fence ------------------------------------------------------
474477

‎Include/cpython/pyatomic_gcc.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -495,6 +495,9 @@ static inline int
495495
_Py_atomic_load_int_acquire(const int *obj)
496496
{ return __atomic_load_n(obj, __ATOMIC_ACQUIRE); }
497497

498+
static inline Py_ssize_t
499+
_Py_atomic_load_ssize_acquire(const Py_ssize_t *obj)
500+
{ return __atomic_load_n(obj, __ATOMIC_ACQUIRE); }
498501

499502
// --- _Py_atomic_fence ------------------------------------------------------
500503

‎Include/cpython/pyatomic_msc.h

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -938,6 +938,17 @@ _Py_atomic_load_int_acquire(const int *obj)
938938
#endif
939939
}
940940

941+
static inline Py_ssize_t
942+
_Py_atomic_load_ssize_acquire(const Py_ssize_t *obj)
943+
{
944+
#if defined(_M_X64) || defined(_M_IX86)
945+
return *(Py_ssize_t volatile *)obj;
946+
#elif defined(_M_ARM64)
947+
return (Py_ssize_t)__ldar64((unsigned __int64 volatile *)obj);
948+
#else
949+
# error "no implementation of _Py_atomic_load_ssize_acquire"
950+
#endif
951+
}
941952

942953
// --- _Py_atomic_fence ------------------------------------------------------
943954

‎Include/cpython/pyatomic_std.h

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -870,6 +870,13 @@ _Py_atomic_load_int_acquire(const int *obj)
870870
memory_order_acquire);
871871
}
872872

873+
static inline Py_ssize_t
874+
_Py_atomic_load_ssize_acquire(const Py_ssize_t *obj)
875+
{
876+
_Py_USING_STD;
877+
return atomic_load_explicit((const _Atomic(Py_ssize_t)*)obj,
878+
memory_order_acquire);
879+
}
873880

874881

875882
// --- _Py_atomic_fence ------------------------------------------------------

‎Objects/dictobject.c

Lines changed: 41 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -143,7 +143,7 @@ it's USABLE_FRACTION (currently two-thirds) full.
143143

144144
#ifdef Py_GIL_DISABLED
145145

146-
#define LOCK_KEYS(keys) PyMutex_Lock(&keys->dk_mutex)
146+
#define LOCK_KEYS(keys) PyMutex_LockFlags(&keys->dk_mutex, _Py_LOCK_DONT_DETACH)
147147
#define UNLOCK_KEYS(keys) PyMutex_Unlock(&keys->dk_mutex)
148148

149149
#define ASSERT_KEYS_LOCKED(keys) assert(PyMutex_IsLocked(&keys->dk_mutex))
@@ -153,6 +153,15 @@ it's USABLE_FRACTION (currently two-thirds) full.
153153
#define INCREF_KEYS(dk) _Py_atomic_add_ssize(&dk->dk_refcnt, 1)
154154
// Dec refs the keys object, giving the previous value
155155
#define DECREF_KEYS(dk) _Py_atomic_add_ssize(&dk->dk_refcnt, -1)
156+
static inline void split_keys_entry_added(PyDictKeysObject *keys)
157+
{
158+
ASSERT_KEYS_LOCKED(keys);
159+
160+
// We increase before we decrease so we never get too small of a value
161+
// when we're racing with reads
162+
_Py_atomic_store_ssize(&keys->dk_nentries, keys->dk_nentries + 1);
163+
_Py_atomic_store_ssize(&keys->dk_usable, keys->dk_usable - 1);
164+
}
156165

157166
#else
158167

@@ -163,6 +172,11 @@ it's USABLE_FRACTION (currently two-thirds) full.
163172
#define STORE_SHARED_KEY(key, value) key = value
164173
#define INCREF_KEYS(dk) dk->dk_refcnt++
165174
#define DECREF_KEYS(dk) dk->dk_refcnt--
175+
static inline void split_keys_entry_added(PyDictKeysObject *keys)
176+
{
177+
keys->dk_usable--;
178+
keys->dk_nentries++;
179+
}
166180

167181
#endif
168182

@@ -790,15 +804,25 @@ new_dict(PyInterpreterState *interp,
790804
static inline size_t
791805
shared_keys_usable_size(PyDictKeysObject *keys)
792806
{
793-
ASSERT_KEYS_LOCKED(keys);
807+
#ifdef Py_GIL_DISABLED
808+
// dk_usable will decrease for each instance that is created and each
809+
// value that is added. dk_entries will increase for each value that
810+
// is added. We want to always return the right value or larger.
811+
// We therefore increase dk_entries first and we decrease dk_usable
812+
// second, and conversely here we read dk_usable first and dk_entries
813+
// second (to avoid the case where we read entries before the increment
814+
// and read usable after the decrement)
815+
return (size_t)(_Py_atomic_load_ssize_acquire(&keys->dk_usable) +
816+
_Py_atomic_load_ssize_acquire(&keys->dk_nentries));
817+
#else
794818
return (size_t)keys->dk_nentries + (size_t)keys->dk_usable;
819+
#endif
795820
}
796821

797822
/* Consumes a reference to the keys object */
798823
static PyObject *
799824
new_dict_with_shared_keys(PyInterpreterState *interp, PyDictKeysObject *keys)
800825
{
801-
LOCK_KEYS(keys);
802826
size_t size = shared_keys_usable_size(keys);
803827
PyDictValues *values = new_values(size);
804828
if (values == NULL) {
@@ -811,7 +835,6 @@ new_dict_with_shared_keys(PyInterpreterState *interp, PyDictKeysObject *keys)
811835
values->values[i] = NULL;
812836
}
813837
PyObject *res = new_dict(interp, keys, values, 0, 1);
814-
UNLOCK_KEYS(keys);
815838
return res;
816839
}
817840

@@ -1248,8 +1271,7 @@ insert_into_dictkeys(PyDictKeysObject *keys, PyObject *name)
12481271
dictkeys_set_index(keys, hashpos, ix);
12491272
assert(ep->me_key == NULL);
12501273
ep->me_key = Py_NewRef(name);
1251-
keys->dk_usable--;
1252-
keys->dk_nentries++;
1274+
split_keys_entry_added(keys);
12531275
}
12541276
assert (ix < SHARED_KEYS_MAX_SIZE);
12551277
return ix;
@@ -1258,7 +1280,7 @@ insert_into_dictkeys(PyDictKeysObject *keys, PyObject *name)
12581280

12591281
static inline int
12601282
insert_combined_dict(PyInterpreterState *interp, PyDictObject *mp,
1261-
Py_hash_t hash, PyObject *key, PyObject *value, int unicode)
1283+
Py_hash_t hash, PyObject *key, PyObject *value, int unicode)
12621284
{
12631285
if (mp->ma_keys->dk_usable <= 0) {
12641286
/* Need to resize. */
@@ -1319,8 +1341,7 @@ insert_split_dict(PyInterpreterState *interp, PyDictObject *mp,
13191341
assert (mp->ma_values->values[index] == NULL);
13201342
mp->ma_values->values[index] = value;
13211343

1322-
keys->dk_usable--;
1323-
keys->dk_nentries++;
1344+
split_keys_entry_added(keys);
13241345
assert(keys->dk_usable >= 0);
13251346
UNLOCK_KEYS(keys);
13261347
return 0;
@@ -3234,9 +3255,7 @@ PyDict_Copy(PyObject *o)
32343255

32353256
if (_PyDict_HasSplitTable(mp)) {
32363257
PyDictObject *split_copy;
3237-
LOCK_KEYS(mp->ma_keys);
32383258
size_t size = shared_keys_usable_size(mp->ma_keys);
3239-
UNLOCK_KEYS(mp->ma_keys);
32403259
PyDictValues *newvalues = new_values(size);
32413260
if (newvalues == NULL)
32423261
return PyErr_NoMemory();
@@ -3351,7 +3370,7 @@ dict_equal(PyDictObject *a, PyDictObject *b)
33513370
Py_hash_t hash;
33523371
if (DK_IS_UNICODE(a->ma_keys)) {
33533372
PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(a->ma_keys)[i];
3354-
key = LOAD_SHARED_KEY(ep->me_key);
3373+
key = ep->me_key;
33553374
if (key == NULL) {
33563375
continue;
33573376
}
@@ -3661,8 +3680,8 @@ dict_popitem_impl(PyDictObject *self)
36613680
LOCK_KEYS(keys);
36623681

36633682
int status = dictresize(interp, self, DK_LOG_SIZE(self->ma_keys), 1);
3664-
dictkeys_decref(interp, keys);
36653683
UNLOCK_KEYS(keys);
3684+
dictkeys_decref(interp, keys);
36663685

36673686
if (status < 0) {
36683687
Py_DECREF(res);
@@ -3769,9 +3788,7 @@ _PyDict_SizeOf(PyDictObject *mp)
37693788
{
37703789
size_t res = _PyObject_SIZE(Py_TYPE(mp));
37713790
if (_PyDict_HasSplitTable(mp)) {
3772-
LOCK_KEYS(mp->ma_keys);
37733791
res += shared_keys_usable_size(mp->ma_keys) * sizeof(PyObject*);
3774-
UNLOCK_KEYS(mp->ma_keys);
37753792
}
37763793
/* If the dictionary is split, the keys portion is accounted-for
37773794
in the type object. */
@@ -5589,12 +5606,19 @@ _PyObject_InitInlineValues(PyObject *obj, PyTypeObject *tp)
55895606
assert(tp->tp_flags & Py_TPFLAGS_MANAGED_DICT);
55905607
PyDictKeysObject *keys = CACHED_KEYS(tp);
55915608
assert(keys != NULL);
5609+
#ifdef Py_GIL_DISABLED
5610+
Py_ssize_t usable = keys->dk_usable;
5611+
while (usable > 1) {
5612+
if (_Py_atomic_compare_exchange_ssize(&keys->dk_usable, &usable, usable - 1)) {
5613+
break;
5614+
}
5615+
}
5616+
#else
55925617
if (keys->dk_usable > 1) {
55935618
keys->dk_usable--;
55945619
}
5595-
LOCK_KEYS(keys);
5620+
#endif
55965621
size_t size = shared_keys_usable_size(keys);
5597-
UNLOCK_KEYS(keys);
55985622
PyDictValues *values = new_values(size);
55995623
if (values == NULL) {
56005624
PyErr_NoMemory();
@@ -5644,9 +5668,7 @@ make_dict_from_instance_attributes(PyInterpreterState *interp,
56445668
dictkeys_incref(keys);
56455669
Py_ssize_t used = 0;
56465670
Py_ssize_t track = 0;
5647-
LOCK_KEYS(keys);
56485671
size_t size = shared_keys_usable_size(keys);
5649-
UNLOCK_KEYS(keys);
56505672
for (size_t i = 0; i < size; i++) {
56515673
PyObject *val = values->values[i];
56525674
if (val != NULL) {

0 commit comments

Comments
 (0)
0