C implementation of functools.lru_cache

[anacrolix]

BPO	14373
Nosy	@rhettinger, @jcea, @amauryfa, @jaraco, @pitrou, @scoder, @giampaolo, @ned-deily, @ezio-melotti, @asvetlov, @meadori, @asmeurer, @ericsnowcurrently, @serhiy-storchaka, @MojoVampire
Dependencies	bpo-24276: Correct reuse argument tuple in property descriptor
Files	lru_cache_class.py: Updated pure python roadmap for the C implementation. Adds handling for kwd_mark and try/except functools.lru_cache-in-c.patch 14373.fixed.diff: Python version works without C acceleration, test cases for both implementations 14373.v3.diff 14373.v4.diff lru_cache_bench.py: Benchmark script 14373.v7.diff 14373.v9.diff clru_cache.patch clru_cache2.patch clru_cache_3.patch clru_cache_crasher.py clru_cache_4.patch: Removed fast path in make_key clru_cache_descr_get.patch test_lru_cache_threaded.patch clru_cache_new.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/serhiy-storchaka'
closed_at = <Date 2015-11-01.08:32:11.814>
created_at = <Date 2012-03-20.13:40:44.952>
labels = ['extension-modules', 'library', 'performance']
title = 'C implementation of functools.lru_cache'
updated_at = <Date 2015-11-01.08:32:11.813>
user = 'https://github.com/anacrolix'

bugs.python.org fields:

activity = <Date 2015-11-01.08:32:11.813>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2015-11-01.08:32:11.814>
closer = 'serhiy.storchaka'
components = ['Extension Modules', 'Library (Lib)']
creation = <Date 2012-03-20.13:40:44.952>
creator = 'anacrolix'
dependencies = ['24276']
files = ['25085', '25094', '28369', '28386', '28390', '28400', '28490', '28498', '32779', '32784', '39478', '39479', '39483', '39646', '39652', '39923']
hgrepos = []
issue_num = 14373
keywords = ['patch']
message_count = 66.0
messages = ['156405', '156449', '156492', '156803', '156808', '157224', '157226', '157343', '175533', '175540', '175545', '176287', '177784', '177808', '177867', '177889', '177903', '177953', '177955', '177967', '177976', '177980', '177993', '178573', '178589', '178611', '203597', '203599', '203654', '203821', '203846', '203894', '214208', '214209', '223439', '224938', '224941', '224980', '224981', '243932', '243939', '243940', '243962', '243967', '243970', '243982', '244002', '244928', '244944', '244950', '244966', '244992', '244994', '245606', '245618', '246573', '246576', '246580', '246582', '246592', '246718', '246720', '247309', '247320', '247321', '253235']
nosy_count = 21.0
nosy_names = ['rhettinger', 'jcea', 'amaury.forgeotdarc', 'jaraco', 'pitrou', 'scoder', 'giampaolo.rodola', 'ned.deily', 'ezio.melotti', 'asvetlov', 'poke', 'meador.inge', 'Aaron.Meurer', 'BreamoreBoy', 'python-dev', 'eric.snow', 'serhiy.storchaka', 'brechtm', 'kmike', 'kachayev', 'josh.r']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue14373'
versions = ['Python 3.5']

[anacrolix]

functools.lru_cache is optimized to the point that it may benefit from a C implementation.

[rhettinger]

Thank you for working on this. I look forward to reviewing it.

[anacrolix]

Updated patch to fix a crash if maxsize isn't given, and add a unit test for that.

Possible issues:

• I've tried to emulate object() by calling PyBaseObject_Type. Not sure if there's a more lightweight object for this that just provides the needed __hash__ and __eq__ attributes.
• Not sure if kwd_mark is deallocated correctly.
• Can't quite work out the best way to wrap the C cache_info() method to output the _CacheInfo named tuple. The current mechanism might not be wrapping the attributes correctly.

[rhettinger]

I've just started looking at this. Nice job and good attention to detail on the error checking. Expect to have a few high-level suggestions and a ton of minor edits.

Here are a couple of quick thoughts:

• The comment style needs to switch to the /* style */
• Use the pure python _cache_info by looking it up on the module object.
• I had expected PyList objects rather than links between C structs (following the pure python lru_cache as closely as possible).

[anacrolix]

I've fixed the commenting, and cache_info use.

I've left the element management in pure C as it reduces memory use (56 bytes for 4 element list, vs. 16 for lru_cache_elem), and avoids ref counting overhead (3 refs per link, plus GC). The difference might become quite marked for very large caches. There's also a nice invariant that links the key to the cache dict, and the result object to the lru_cache_elem. I'm happy to change this if it doesn't matter.

My only concern now is the wrapping of the lru cache object. In the Python version, @wraps allows the lru_cache to masquerade as the wrapped function wrt str/repr. The C version is wrapped, but str/repr remain unchanged. Not sure if this is a problem.

[rhettinger]

Matt, I'm attaching a pure python version to serve as a better map for how to implement this in C.

• it incorporate the recent lru_cache algorithmic updates (moving the root around the circular queue to re-use old links).

• it shows which parts should be implemented in C using a regular type and shows how to call it from pure python.

• it gives hints on use of #defines and PyDict_GetItem

• the critical sections are marked so you can use the GIL rather than using locks.

• there are hints for what datatypes to use (only the hits and misses need the ability to grow beyond sys.maxsize).

• it shows how to access the named tuple from within the C code (using a straight PyObject_Call).

• this code passes the test suite and should be directly translatable (and very fast).

• please follow the model and use PyList objects instead of C structure for links

• let me know if there are any questions.

[rhettinger]

Updated to show how to handle the kwd_mark and the try/except.

[anacrolix]

• it incorporate the recent lru_cache algorithmic updates (moving the root around the circular queue to re-use old links).

The existing C patch already does this.

• it shows which parts should be implemented in C using a regular type and shows how to call it from pure python.

The existing patch already did this.

• it gives hints on use of #defines and PyDict_GetItem

I'm familiar with C. I've retained PyDict_GetItemWithError so as not to suppress typing errors from keys constructed from bad arguments from the user.

• the critical sections are marked so you can use the GIL rather than using locks.

The existing patch is already using the GIL, it didn't have any locks.

• there are hints for what datatypes to use (only the hits and misses need the ability to grow beyond sys.maxsize).

The existing patch already had this.

• it shows how to access the named tuple from within the C code (using a straight PyObject_Call).

I incorporated this.

• this code passes the test suite and should be directly translatable (and very fast).

So did the old code.

• please follow the model and use PyList objects instead of C structure for links

I've left this as is, the linked list in C is idiomatic, avoids a lot of branching and reference counting and is also more readable than the equivalent C/Python.

[anacrolix]

I look forward to your feedback Ezio.

[ezio-melotti]

I wonder if we should keep the original Python implementation alongside the new C version. If we do, it would be nice to see a 100% coverage of the Python version and have the tests check both the implementations.

[ezio-melotti]

See also bpo-12428.