From 42bae3a3d9d79f28e6b3b619bd27296d125c4c2c Mon Sep 17 00:00:00 2001 From: Victor Stinner Date: Wed, 13 May 2020 05:36:23 +0200 Subject: bpo-40602: Optimize _Py_hashtable_get_ptr() (GH-20066) _Py_hashtable_get_entry_ptr() avoids comparing the entry hash: compare directly keys. Move _Py_hashtable_get_entry_ptr() just after _Py_hashtable_get_entry_generic(). --- Python/hashtable.c | 47 +++++++++++++++++++++++------------------------ 1 file changed, 23 insertions(+), 24 deletions(-) diff --git a/Python/hashtable.c b/Python/hashtable.c index dc4af33..d1467ad 100644 --- a/Python/hashtable.c +++ b/Python/hashtable.c @@ -193,6 +193,29 @@ _Py_hashtable_get_entry_generic(_Py_hashtable_t *ht, const void *key) } +// Specialized for: +// hash_func == _Py_hashtable_hash_ptr +// compare_func == _Py_hashtable_compare_direct +static _Py_hashtable_entry_t * +_Py_hashtable_get_entry_ptr(_Py_hashtable_t *ht, const void *key) +{ + Py_uhash_t key_hash = _Py_hashtable_hash_ptr(key); + size_t index = key_hash & (ht->num_buckets - 1); + _Py_hashtable_entry_t *entry = entry = TABLE_HEAD(ht, index); + while (1) { + if (entry == NULL) { + return NULL; + } + // Compare directly keys (ignore entry->key_hash) + if (entry->key == key) { + break; + } + entry = ENTRY_NEXT(entry); + } + return entry; +} + + void* _Py_hashtable_steal(_Py_hashtable_t *ht, const void *key) { @@ -275,30 +298,6 @@ _Py_hashtable_get(_Py_hashtable_t *ht, const void *key) } -// Specialized for: -// hash_func == _Py_hashtable_hash_ptr -// compare_func == _Py_hashtable_compare_direct -_Py_hashtable_entry_t * -_Py_hashtable_get_entry_ptr(_Py_hashtable_t *ht, const void *key) -{ - Py_uhash_t key_hash = _Py_hashtable_hash_ptr(key); - size_t index = key_hash & (ht->num_buckets - 1); - _Py_hashtable_entry_t *entry = entry = TABLE_HEAD(ht, index); - while (1) { - if (entry == NULL) { - return NULL; - } - if (entry->key_hash == key_hash) { - if (entry->key == key) { - break; - } - } - entry = ENTRY_NEXT(entry); - } - return entry; -} - - int _Py_hashtable_foreach(_Py_hashtable_t *ht, _Py_hashtable_foreach_func func, -- cgit v0.12