Avoid repeated hash calculation in C implementation of functools.lru_cache()

[serhiy-storchaka]

BPO	24483
Nosy	@rhettinger, @ncoghlan, @vstinner, @taleinat, @larryhastings, @meadori, @serhiy-storchaka, @1st1
Files	clru_cache_known_hash.patch clru_cache_known_hash_2.patch clru_cache_known_hash_3.patch clru_cache_known_hash_4.patch clru_cache_known_hash_5.larry.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2015-10-02.10:16:19.873>
created_at = <Date 2015-06-21.12:34:02.134>
labels = ['library', 'performance']
title = 'Avoid repeated hash calculation in C implementation of functools.lru_cache()'
updated_at = <Date 2015-10-02.10:27:08.921>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2015-10-02.10:27:08.921>
actor = 'vstinner'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2015-10-02.10:16:19.873>
closer = 'serhiy.storchaka'
components = ['Library (Lib)']
creation = <Date 2015-06-21.12:34:02.134>
creator = 'serhiy.storchaka'
dependencies = []
files = ['39758', '39761', '39766', '39773', '39785']
hgrepos = []
issue_num = 24483
keywords = ['patch']
message_count = 24.0
messages = ['245593', '245601', '245604', '245619', '245623', '245627', '245645', '245646', '245672', '245720', '245733', '245754', '245755', '245775', '245799', '245813', '245933', '246111', '246715', '246974', '251777', '251832', '252100', '252105']
nosy_count = 9.0
nosy_names = ['rhettinger', 'ncoghlan', 'vstinner', 'taleinat', 'larry', 'meador.inge', 'python-dev', 'serhiy.storchaka', 'yselivanov']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue24483'
versions = ['Python 3.5', 'Python 3.6']

[serhiy-storchaka]

There is a difference between Python and C implementations of functools.lru_cache(). Python implementation caches the hash of the key, C implementation doesn't. May be this is not too important (at least I have no an example that shows the benefit of caching the hash), but there is a place for possible optimization. Proposed patch uses private functions _PyDict_GetItem_KnownHash() and _PyDict_SetItem_KnownHash() to avoid the second calculating of the hash for new keys.

The hash is still calculated second time when the key is deleted from full cache. To avoid this _PyDict_DelItem_KnownHash() is needed.

[rhettinger]

I would like the full functionality of the Python version to be implemented. Guaranteeing that the hash is only calculated once prevents a reentrancy hole and provides a speed benefit as well. Please implement exactly what the pure python version does (no more than one call to hash ever).

[serhiy-storchaka]

New patch adds _PyDict_DelItem_KnownHash() and uses it to guarantee that the hash is only calculated once.

[serhiy-storchaka]

New patch touches also unbounded cache version.

Larry, do you allow to commit such patch in 3.5?

[larryhastings]

I can accept this change, but I don't like that code. Is it really considered acceptable to have that much copy-and-paste code in the dict implementation for KnownHash calls?

Could the common code be split off into a Py_LOCAL_INLINE function?

[rhettinger]

Serhiy's code looks like the cleanest way to do it.

[larryhastings]

Patch doesn't build for me against current trunk:

gcc -pthread -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes    -Werror=declaration-after-statement   -I. -IInclude -I./Include    -DPy_BUILD_CORE  -c ./Modules/_functoolsmodule.c -o Modules/_functoolsmodule.o
./Modules/_functoolsmodule.c: In function ‘infinite_lru_cache_wrapper’:
./Modules/_functoolsmodule.c:769:14: error: too few arguments to function ‘_PyDict_GetItem_KnownHash’
     result = _PyDict_GetItem_KnownHash(self->cache, key);
              ^
In file included from Include/Python.h:87:0,
                 from ./Modules/_functoolsmodule.c:2:
Include/dictobject.h:59:24: note: declared here
 PyAPI_FUNC(PyObject *) _PyDict_GetItem_KnownHash(PyObject *mp, PyObject *key,
                        ^
./Modules/_functoolsmodule.c:785:9: error: too few arguments to function ‘_PyDict_SetItem_KnownHash’
     if (_PyDict_SetItem_KnownHash(self->cache, key, result) < 0) {
         ^
In file included from Include/Python.h:87:0,
                 from ./Modules/_functoolsmodule.c:2:
Include/dictobject.h:71:17: note: declared here
 PyAPI_FUNC(int) _PyDict_SetItem_KnownHash(PyObject *mp, PyObject *key,
                 ^
Makefile:1695: recipe for target 'Modules/_functoolsmodule.o' failed
make: *** [Modules/_functoolsmodule.o] Error 1

[serhiy-storchaka]

My bad. I submitted the last patch without checking (rebuilding Python takes too much time on my slow netbook). Here is fixed and tested patch.

[larryhastings]

I suggest that 20 lines of identical code copy-and-pasted between two functions is not the cleanest way to do it. Find attached my version of the patch, which splits this common code out into a static function.

[rhettinger]

Sorry Larry, but I prefer Serhiy's version. The known_hash variants need to have their own function intact version and gum up the rest of the code. See the current known_hash function for comparison (Serhiy modeled on what we had already decided to do much earlier on a separate issue).

[serhiy-storchaka]

I would prefer do not repeat the code, but I afraid this can affect the performance, and the performance of PyDict_GetItem is critical for Python.

[1st1]

I would prefer do not repeat the code, but I afraid this can affect the performance, and the performance of PyDict_GetItem is critical for Python.

Static function calls like that one will most likely be inlined by the compiler... But if you don't want to rely on that, maybe we can use a macro to avoid code duplication?