10000 Refactor dict lookup functions to use force inline helpers · python/cpython@32a6a41 · GitHub
[go: up one dir, main page]
Skip to content

Commit 32a6a41

Browse files
DinoVDinoV
committed
Refactor dict lookup functions to use force inline helpers
1 parent ac5e53e commit 32a6a41

File tree

1 file changed

+94
-93
lines changed

1 file changed

+94
-93
lines changed

‎Objects/dictobject.c

Lines changed: 94 additions & 93 deletions
Original file line numberDiff line numberDiff line change
@@ -875,69 +875,37 @@ lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
875875
Py_UNREACHABLE();
876876
}
877877

878-
// Search non-Unicode key from Unicode table
879-
static Py_ssize_t
880-
unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
878+
typedef void *(*generic_entries_func)(PyDictKeysObject *dk);
879+
880+
static inline Py_ALWAYS_INLINE Py_ssize_t
881+
do_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key, Py_hash_t hash,
882+
generic_entries_func entries,
883+
Py_ssize_t (*check_lookup)(PyDictObject *, PyDictKeysObject *, void *, Py_ssize_t ix, PyObject *key, Py_hash_t))
881884
{
882-
PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
885+
void *ep0 = entries(dk);
883886
size_t mask = DK_MASK(dk);
884887
size_t perturb = hash;
885888
size_t i = (size_t)hash & mask;
886889
Py_ssize_t ix;
887890
for (;;) {
888891
ix = dictkeys_get_index(dk, i);
889892
if (ix >= 0) {
890-
PyDictUnicodeEntry *ep = &ep0[ix];
891-
assert(ep->me_key != NULL);
892-
assert(PyUnicode_CheckExact(ep->me_key));
893-
if (ep->me_key == key) {
893+
ix = check_lookup(mp, dk, ep0, ix, key, hash);
894+
if (ix != DKIX_DUMMY) {
894895
return ix;
895896
}
896-
if (unicode_get_hash(ep->me_key) == hash) {
897-
PyObject *startkey = ep->me_key;
898-
Py_INCREF(startkey);
899-
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
900-
Py_DECREF(startkey);
901-
if (cmp < 0) {
902-
return DKIX_ERROR;
903-
}
904-
if (dk == mp->ma_keys && ep->me_key == startkey) {
905-
if (cmp > 0) {
906-
return ix;
907-
}
908-
}
909-
else {
910-
/* The dict was mutated, restart */
911-
return DKIX_KEY_CHANGED;
912-
}
913-
}
914897
}
915898
else if (ix == DKIX_EMPTY) {
916899
return DKIX_EMPTY;
917900
}
918901
perturb >>= PERTURB_SHIFT;
919902
i = mask & (i*5 + perturb + 1);
920-
}
921-
Py_UNREACHABLE();
922-
}
923903

924-
// Search Unicode key from Unicode table.
925-
static Py_ssize_t _Py_HOT_FUNCTION
926-
unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
927-
{
928-
PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
929-
size_t mask = DK_MASK(dk);
930-
size_t perturb = hash;
931-
size_t i = (size_t)hash & mask;
932-
Py_ssize_t ix;
933-
for (;;) {
904+
// Manual loop unrolling
934905
ix = dictkeys_get_index(dk, i);
935906
if (ix >= 0) {
936-
PyDictUnicodeEntry *ep = &ep0[ix];
937-
assert(ep->me_key != NULL);
938-
assert(PyUnicode_CheckExact(ep->me_key));
939-
if (ep->me_key == key ||
940-
(unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) {
907+
ix = check_lookup(mp, dk, ep0, ix, key, hash);
908+
if (ix != DKIX_DUMMY) {
941909
return ix;
942910
}
943911
}
@@ -946,69 +914,102 @@ unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
946914
}
947915
perturb >>= PERTURB_SHIFT;
948916
i = mask & (i*5 + perturb + 1);
949-
// Manual loop unrolling
950-
ix = dictkeys_get_index(dk, i);
951-
if (ix >= 0) {
952-
PyDictUnicodeEntry *ep = &ep0[ix];
953-
assert(ep->me_key != NULL);
954-
assert(PyUnicode_CheckExact(ep->me_key));
955-
if (ep->me_key == key ||
956-
(unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) {
917+
}
918+
Py_UNREACHABLE();
919+
}
920+
921+
static inline Py_ALWAYS_INLINE
922+
Py_ssize_t compare_unicode_generic(PyDictObject *mp, PyDictKeysObject *dk,
923+
void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash)
924+
{
925+
PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
926+
assert(ep->me_key != NULL);
927+
assert(PyUnicode_CheckExact(ep->me_key));
928+
assert(!PyUnicode_CheckExact(key));
929+
// TODO: Thread safety
930+
931+
if (unicode_get_hash(ep->me_key) == hash) {
932+
PyObject *startkey = ep->me_key;
933+
Py_INCREF(startkey);
934+
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
935+
Py_DECREF(startkey);
936+
if (cmp < 0) {
937+
return DKIX_ERROR;
938+
}
939+
if (dk == mp->ma_keys && ep->me_key == startkey) {
940+
if (cmp > 0) {
957941
return ix;
958942
}
959943
}
960-
else if (ix == DKIX_EMPTY) {
961-
F438 return DKIX_EMPTY;
944+
else {
945+
/* The dict was mutated, restart */
946+
return DKIX_KEY_CHANGED;
962947
}
963-
perturb >>= PERTURB_SHIFT;
964-
i = mask & (i*5 + perturb + 1);
965948
}
966-
Py_UNREACHABLE();
949+
return DKIX_DUMMY;
967950
}
968951

969-
// Search key from Generic table.
952+
// Search non-Unicode key from Unicode table
970953
static Py_ssize_t
971-
dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
954+
unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
972955
{
973-
PyDictKeyEntry *ep0 = DK_ENTRIES(dk);
974-
size_t mask = DK_MASK(dk);
975-
size_t perturb = hash;
976-
size_t i = (size_t)hash & mask;
977-
Py_ssize_t ix;
978-
for (;;) {
979-
ix = dictkeys_get_index(dk, i);
980-
if (ix >= 0) {
981-
PyDictKeyEntry *ep = &ep0[ix];
982-
assert(ep->me_key != NULL);
983-
if (ep->me_key == key) {
956+
return do_lookup(mp, dk, key, hash, (generic_entries_func)DK_UNICODE_ENTRIES, compare_unicode_generic);
957+
}
958+
959+
static inline Py_ALWAYS_INLINE
960+
Py_ssize_t compare_unicode_unicode(PyDictObject *mp, PyDictKeysObject *dk,
961+
void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash)
962+
{
963+
PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
964+
assert(ep->me_key != NULL);
965+
assert(PyUnicode_CheckExact(ep->me_key));
966+
if (ep->me_key == key ||
967+
(unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) {
968+
return ix;
969+
}
970+
return DKIX_DUMMY;
971+
}
972+
973+
static Py_ssize_t _Py_HOT_FUNCTION
974+
unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
975+
{
976+
return do_lookup(NULL, dk, key, hash, (generic_entries_func)DK_UNICODE_ENTRIES, compare_unicode_unicode);
977+
}
978+
979+
static inline Py_ALWAYS_INLINE
980+
Py_ssize_t compare_generic(PyDictObject *mp, PyDictKeysObject *dk,
981+
void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash)
982+
{
983+
PyDictKeyEntry *ep = &((PyDictKeyEntry *)ep0)[ix];
984+
assert(ep->me_key != NULL);
985+
if (ep->me_key == key) {
986+
return ix;
987+
}
988+
if (ep->me_hash == hash) {
989+
PyObject *startkey = ep->me_key;
990+
Py_INCREF(startkey);
991+
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
992+
Py_DECREF(startkey);
993+
if (cmp < 0) {
994+
return DKIX_ERROR;
995+
}
996+
if (dk == mp->ma_keys && ep->me_key == startkey) {
997+
if (cmp > 0) {
984998
return ix;
985999
}
986-
if (ep->me_hash == hash) {
987-
PyObject *startkey = ep->me_key;
988-
Py_INCREF(startkey);
989-
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
990-
Py_DECREF(startkey);
991-
if (cmp < 0) {
992-
return DKIX_ERROR;
993-
}
994-
if (dk == mp->ma_keys && ep->me_key == startkey) {
995-
if (cmp > 0) {
996-
return ix;
997-
}
998-
}
999-
else {
1000-
/* The dict was mutated, restart */
1001-
return DKIX_KEY_CHANGED;
1002-
}
1003-
}
10041000
}
1005-
else if (ix == DKIX_EMPTY) {
1006-
return DKIX_EMPTY;
1001+
else {
1002+
/* The dict was mutated, restart */
1003+
return DKIX_KEY_CHANGED;
10071004
}
1008-
perturb >>= PERTURB_SHIFT;
1009-
i = mask & (i*5 + perturb + 1);
10101005
}
1011-
Py_UNREACHABLE();
1006+
return DKIX_DUMMY;
1007+
}
1008+
1009+
static Py_ssize_t
1010+
dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
1011+
{
1012+
return do_lookup(mp, dk, key, hash, (generic_entries_func)DK_ENTRIES, compare_generic);
10121013
}
10131014

10141015
/* Lookup a string in a (all unicode) dict keys.

0 commit comments

Comments
 (0)
0