Issue python#24483: C implementation of functools.lru_cache() now calculates key's

serhiy-storchaka · serhiy-storchaka · commit b9d98d532cb9 · 2015-10-02T12:47:11.000+03:00
hash only once.
diff --git a/Include/dictobject.h b/Include/dictobject.h
@@ -72,6 +72,10 @@ PyAPI_FUNC(int) _PyDict_SetItem_KnownHash(PyObject *mp, PyObject *key,
                                           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
@@ -32,6 +32,9 @@ Core and Builtins
 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
@@ -601,6 +601,7 @@ struct lru_cache_object;
 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 @@ static PyObject *
 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 @@ infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd
         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 @@ bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds
 {
     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 @@ bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds
         /* 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 @@ bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds
         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 @@ bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds
             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
@@ -1242,6 +1242,7 @@ _PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value,
     }
     assert(key);
     assert(value);
+    assert(hash != -1);
     mp = (PyDictObject *)op;
 
     /* insertdict() handles any resizing that might be necessary */
@@ -1290,6 +1291,42 @@ PyDict_DelItem(PyObject *op, PyObject *key)
     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)
 {
