[Python-checkins] cpython (merge 3.5 -> default): Issue #24483: C implementation of functools.lru_cache() now calculates key's

Fri Oct 2 05:51:08 EDT 2015

https://hg.python.org/cpython/rev/5758b85627c9
changeset: 98476:5758b85627c9
parent: 98474:c98cc9f7e2c5
parent: 98475:3f4c319a822f
user: Serhiy Storchaka <storchaka at gmail.com>
date: Fri Oct 02 12:47:59 2015 +0300
summary:
 Issue #24483: C implementation of functools.lru_cache() now calculates key's
hash only once.
files:
 Include/dictobject.h | 4 ++
 Misc/NEWS | 3 ++
 Modules/_functoolsmodule.c | 26 ++++++++++++++----
 Objects/dictobject.c | 37 ++++++++++++++++++++++++++
 4 files changed, 64 insertions(+), 6 deletions(-)

diff --git a/Include/dictobject.h b/Include/dictobject.h
--- a/Include/dictobject.h
+++ b/Include/dictobject.h
@@ -72,6 +72,10 @@
 PyObject *item, Py_hash_t hash);
 #endif
 PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key);
+#ifndef Py_LIMITED_API
+PyAPI_FUNC(int) _PyDict_DelItem_KnownHash(PyObject *mp, PyObject *key,
+ Py_hash_t hash);
+#endif
 PyAPI_FUNC(void) PyDict_Clear(PyObject *mp);
 PyAPI_FUNC(int) PyDict_Next(
 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value);
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -203,6 +203,9 @@
 Library
 -------
 
+- Issue #24483: C implementation of functools.lru_cache() now calculates key's
+ hash only once.
+
 - Issue #22958: Constructor and update method of weakref.WeakValueDictionary
 now accept the self and the dict keyword arguments.
 
diff --git a/Modules/_functoolsmodule.c b/Modules/_functoolsmodule.c
--- a/Modules/_functoolsmodule.c
+++ b/Modules/_functoolsmodule.c
@@ -601,6 +601,7 @@
 typedef struct lru_list_elem {
 PyObject_HEAD
 struct lru_list_elem *prev, *next; /* borrowed links */
+ Py_hash_t hash;
 PyObject *key, *result;
 } lru_list_elem;
 
@@ -762,10 +763,14 @@
 infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
 {
 PyObject *result;
+ Py_hash_t hash;
 PyObject *key = lru_cache_make_key(args, kwds, self->typed);
 if (!key)
 return NULL;
- result = PyDict_GetItemWithError(self->cache, key);
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return NULL;
+ result = _PyDict_GetItem_KnownHash(self->cache, key, hash);
 if (result) {
 Py_INCREF(result);
 self->hits++;
@@ -781,7 +786,7 @@
 Py_DECREF(key);
 return NULL;
 }
- if (PyDict_SetItem(self->cache, key, result) < 0) {
+ if (_PyDict_SetItem_KnownHash(self->cache, key, result, hash) < 0) {
 Py_DECREF(result);
 Py_DECREF(key);
 return NULL;
@@ -813,11 +818,15 @@
 {
 lru_list_elem *link;
 PyObject *key, *result;
+ Py_hash_t hash;
 
 key = lru_cache_make_key(args, kwds, self->typed);
 if (!key)
 return NULL;
- link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return NULL;
+ link = (lru_list_elem *)_PyDict_GetItem_KnownHash(self->cache, key, hash);
 if (link) {
 lru_cache_extricate_link(link);
 lru_cache_append_link(self, link);
@@ -845,7 +854,8 @@
 /* Remove it from the cache.
 The cache dict holds one reference to the link,
 and the linked list holds yet one reference to it. */
- if (PyDict_DelItem(self->cache, link->key) < 0) {
+ if (_PyDict_DelItem_KnownHash(self->cache, link->key,
+ link->hash) < 0) {
 lru_cache_append_link(self, link);
 Py_DECREF(key);
 Py_DECREF(result);
@@ -859,9 +869,11 @@
 oldkey = link->key;
 oldresult = link->result;
 
+ link->hash = hash;
 link->key = key;
 link->result = result;
- if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
+ if (_PyDict_SetItem_KnownHash(self->cache, key, (PyObject *)link,
+ hash) < 0) {
 Py_DECREF(link);
 Py_DECREF(oldkey);
 Py_DECREF(oldresult);
@@ -881,10 +893,12 @@
 return NULL;
 }
 
+ link->hash = hash;
 link->key = key;
 link->result = result;
 _PyObject_GC_TRACK(link);
- if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
+ if (_PyDict_SetItem_KnownHash(self->cache, key, (PyObject *)link,
+ hash) < 0) {
 Py_DECREF(link);
 return NULL;
 }
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -1242,6 +1242,7 @@
 }
 assert(key);
 assert(value);
+ assert(hash != -1);
 mp = (PyDictObject *)op;
 
 /* insertdict() handles any resizing that might be necessary */
@@ -1290,6 +1291,42 @@
 return 0;
 }
 
+int
+_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
+{
+ PyDictObject *mp;
+ PyDictKeyEntry *ep;
+ PyObject *old_key, *old_value;
+ PyObject **value_addr;
+
+ if (!PyDict_Check(op)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ assert(key);
+ assert(hash != -1);
+ mp = (PyDictObject *)op;
+ ep = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr);
+ if (ep == NULL)
+ return -1;
+ if (*value_addr == NULL) {
+ _PyErr_SetKeyError(key);
+ return -1;
+ }
+ old_value = *value_addr;
+ *value_addr = NULL;
+ mp->ma_used--;
+ if (!_PyDict_HasSplitTable(mp)) {
+ ENSURE_ALLOWS_DELETIONS(mp);
+ old_key = ep->me_key;
+ Py_INCREF(dummy);
+ ep->me_key = dummy;
+ Py_DECREF(old_key);
+ }
+ Py_DECREF(old_value);
+ return 0;
+}
+
 void
 PyDict_Clear(PyObject *op)
 {
-- 
Repository URL: https://hg.python.org/cpython
