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

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

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.

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).

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.

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.

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

• 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.

I look forward to your feedback Ezio.

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.

See also bpo-12428.

I have added a lot of comments in Rietveld. In general the patch looks good, but I have some style nitpicks and some more strong comments. Matt, please update the patch.

Tests should test both Python and C implementations.

I doubt if get rid of locking is right. Hash calculation and comparison of arguments can call Python code and this code can recursive use the wrapped function.

Some benchmarks will be interesting.

I think this acceleration must necessarily be in 3.4.

Updated patch with next points:

• fix typedefs
• python implementation works normally without C acceleration
• test cases cover both python/c implementations
• several style fixes in C module

Thanks, Alexey.

However most of my comments were not considered. I have repeated them and added some new comments.

Serhiy, thank you for review. Working further on fixes.

Fixed my previous patch according to all comments from review, except removing keyword arguments from lru_cache_new function.

Added additional Py_DECREF(s) for key and value.

LGTM. Thank you, Matt and Alexey.

Here is a simple benchmark. On my computer it shows 10-25x speedup using the C accelerator.

Antoine reminded me about a lock. In Python implementation it needed because linked list modifications are not atomic. In C implementation linked list modifications are atomic. However dict operations can call Python code and therefore they are not atomic. I don't know what bad things can happened with concurrent cache updating, however using lock will be safer and cheap enought.

Please add lock field to lru_cache_object and use it as in Python implementation. If no one can prove that a lock is not needed.

Just for the record, I've compiled Raymond's roadmap version in Cython (with only slight changes to make 'self.maxsize' a Py_ssize_t and using an external .pxd for typing) and ran Serhiy's benchmark over it (Ubuntu 12.10, 64bit). This is what I get in Py3.4:

0.022 untyped_cy(i)
0.023 untyped_cy("spam", i)
0.024 untyped_cy("spam", "spam", i)
0.106 untyped_cy(a=i)
0.133 untyped_cy(a="spam", b=i)
0.152 untyped_cy(a="spam", b="spam", c=i)
0.033 typed_cy(i)
0.038 typed_cy("spam", i)
0.039 typed_cy("spam", "spam", i)
0.129 typed_cy(a=i)
0.168 typed_cy(a="spam", b=i)
0.183 typed_cy(a="spam", b="spam", c=i)

0.143 untyped_py(i)
0.234 untyped_py("spam", i)
0.247 untyped_py("spam", "spam", i)
0.368 untyped_py(a=i)
0.406 untyped_py(a="spam", b=i)
0.425 untyped_py(a="spam", b="spam", c=i)
0.447 typed_py(i)
0.469 typed_py("spam", i)
0.480 typed_py("spam", "spam", i)
0.745 typed_py(a=i)
0.783 typed_py(a="spam", b=i)
0.819 typed_py(a="spam", b="spam", c=i)

Looking at the factors, that's about the same speedup that the dedicated hand tuned C implementation presented according to Serhiy's own runs (he reported 10-25x). Makes me wonder why we should have two entirely separate implementations for this.

Here's the lru_cache_class.pxd file I used:

"""
cimport cython

cdef make_key(tuple args, dict kwds, bint typed, tuple kwd_mark)

@cython.final
@cython.internal
cdef class c_lru_cache:
    cdef dict cache
    cdef Py_ssize_t hits
    cdef Py_ssize_t misses
    cdef Py_ssize_t maxsize
    cdef bint typed
    cdef object user_function
    cdef object cache_info_type
    cdef tuple kwd_mark
    cdef list root
"""

Hmm. Judging by the numbers for the Python version, my machine appears
to be slower than Stefan (Behnel)'s machine, and yet the C version is
much faster here than the posted Cython numbers.

If I adjust the results for the machine differences, the C version
would appear to be 2.5x faster than the Cython version.

I've managed to build the Cython version now. It's in fact between 4 and 6
times slower here than the C version.

Yep, I basically didn't do any optimisation, it's the plain Python code compiled, just with the class being converted into an extension type.

Thread-safe implementation for cache cleanup.

Unfortunately the patch caused a crash in test_ipaddress. Larry granted special exclusion for adding this feature after feature freeze if it will be fixed before beta 2.

Here are the recent version of the patch and minimal crash reproducer.

The problem is in property descriptor getter. It uses cached tuple for args and can unexpectedly modify it. Opened bpo-24276 for fixing this bug.

Another way is to remove fast path in lru_cache_make_key() and always copy args tuple.

Backed out the backout in cb30db9cc029.

This changed caused a problem in Django's test suite (bisected to 0d0989359bbb0).

File "/home/tim/code/django/django/db/models/options.py", line 709, in _populate_directed_relation_graph
all_models = self.apps.get_models(include_auto_created=True)
TypeError: get_models() missing 1 required positional argument: 'self'

The get_models() method is decorated with @lru_cache.lru_cache(maxsize=None)

https://github.com/django/django/blob/c2b4967e76fd671e6199e4dd54d2a2c1f096b8eb/django/apps/registry.py#L157-L179

Here is a patch that adds __get__ for lru_cache object.

Thanks, that does resolve the issue.

test_lru_cache_threaded is randomly failed on PPC64 PowerLinux buildbot: http://buildbot.python.org/all/builders/PPC64%20PowerLinux%203.x/builds/3573/steps/test/logs/stdio

======================================================================
FAIL: test_lru_cache_threaded (test.test_functools.TestLRUPy)
----------------------------------------------------------------------

Traceback (most recent call last):
  File "/home/shager/cpython-buildarea/3.x.edelsohn-powerlinux-ppc64/build/Lib/test/test_functools.py", line 1129, in test_lru_cache_threaded
    self.assertEqual(hits, 45)
AssertionError: 43 != 45

The tests looks incorrect, it should fail when cached function is called simultaneously from different threads. Unfortunately it is hard reproduce the failure on other platform.

Proposed patch fixes the test and adds other threaded test, specially for simultaneous call.

New changeset 19dbee688a30 by Serhiy Storchaka in branch '3.5':
Issue bpo-14373: Fixed threaded test for lru_cache(). Added new threaded test.
https://hg.python.org/cpython/rev/19dbee688a30

New changeset da331f50aad4 by Serhiy Storchaka in branch 'default':
Issue bpo-14373: Fixed threaded test for lru_cache(). Added new threaded test.
https://hg.python.org/cpython/rev/da331f50aad4

New changeset eff50d543c79 by Serhiy Storchaka in branch '3.5':
Issue bpo-14373: C implementation of functools.lru_cache() now can be used with
https://hg.python.org/cpython/rev/eff50d543c79

New changeset f4b785d14792 by Serhiy Storchaka in branch 'default':
Issue bpo-14373: C implementation of functools.lru_cache() now can be used with
https://hg.python.org/cpython/rev/f4b785d14792

New changeset c52f381fe674 by Serhiy Storchaka in branch '3.5':
Issue bpo-14373: Other attempt to fix threaded test for lru_cache().
https://hg.python.org/cpython/rev/c52f381fe674

New changeset 73acb8c187d4 by Serhiy Storchaka in branch 'default':
Issue bpo-14373: Other attempt to fix threaded test for lru_cache().
https://hg.python.org/cpython/rev/73acb8c187d4

If the C version is to remain in Python3.5, please make sure it provides all of the carefully designed features of the pure python version:

• The hash function is called no more than once per element
• The key is constructed to be flat as possible
• Thread-safe where needed:
  • make_key called outside locks
  • within a reentrant lock (either a real lock or the GIL),
    check to see if the key is in the cache and if so,
    update the stats and return the value
    + outside of locks, call the user function
    (allowing for recursive functions)
    + within a reentrant lock (either a real lock or the GIL)
    handle cache misses by 1) verifying there was not an
    intervening cache update by the user function, 2)
    updating links, 3) updating stats. During the updates,
    make only one potentially reentrant cache[key]
    assignment after all invariants have been restored.
    Save all decrefs until all other state updates
    have been completed.

A number of features of the lru_cache were designed for space savings over speed (lru is all about eviction to make space for a new entry), for thread safety and to not fall apart during reentrancy. It also provides a guarantee that the hash function is not called more than once per element and is called *before* any of the lru structure updates or lookups (this makes reasoning about correctness *much* easier).

In these capabilities can't be reliably reproduced for 3.5, I think the whole thing should be reverted and deferred to 3.6.

If the C version is to remain in Python3.5, please make sure it provides all
of the carefully designed features of the pure python version:

• The hash function is called no more than once per element

Will be satisfied by bpo-24483.

I think all other capabilities are satisfied. The GIL is used to satisfy
thread-safe.

I'm witnessing a crash in the C implementation during garbage collection. Interestingly, it only shows in the Py3.6 branch, not in Py3.5 (both latest). Here's the gdb session:

Program received signal SIGSEGV, Segmentation fault.
lru_cache_tp_traverse (self=0x7ffff2a80ae8, visit=0x43c528 <visit_decref>, arg=0x0) at ./Modules/_functoolsmodule.c:1040
1040 lru_list_elem *next = link->next;
(gdb) list
1035 static int
1036 lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg)
1037 {
1038 lru_list_elem *link = self->root.next;
1039 while (link != &self->root) {
1040 lru_list_elem *next = link->next;
1041 Py_VISIT(link);
1042 link = next;
1043 }
1044 Py_VISIT(self->maxsize_O);
(gdb) print link
$1 = (lru_list_elem *) 0x0
(gdb) print self
$2 = (lru_cache_object *) 0x7ffff2a80ae8
(gdb) print self->root.next
$3 = (struct lru_list_elem *) 0x0
(gdb) print self->root
$4 = {ob_base = {_ob_next = 0x7ffff2a26458, _ob_prev = 0x90e860 <refchain>, ob_refcnt = 1, ob_type = 0x92c500 <lru_cache_type>}, prev = 0x0, next = 0x0, key = 0x0, result = 0x0}

IIUC correctly, there is only one entry and the code doesn't expect that. An additional "is empty?" NULL check may or may not be the right fix. It might also be the linking itself that's incorrect here. The code seems to expect a cyclic data structure which is apparently not maintained that way.

self->root.next and self->root.prev should never be NULL. Could you please provide minimal example of code that produces a crash?

It's not actually my own code using the lru_cache here. From a quick grep
over the code tree, the only potentially related usage I found was in
Python's fnmatch module, on the "_compile_pattern()" function. Commenting
that out then made the crash go away, so this was the culprit.

However, I ran test_functools.py of the same installation and it passes, so
not every usage is broken here. Simple manual testing didn't reveal
anything either so far.

test_fnmatch.py also passes, BTW.

I've also seen a crash in lru_cache_tp_traverse but with the 3.5.0b3 release build for the OS X 64-bit/32-bit installer. I just stumbled across the segfault by bringing up the interactive interpreter and typing "import ssl". After a lot of playing around, I reduced the failing case to: 1. have an "import pprint" in a startup file referred to by PYTHONSTARTUP *and* 2. "import ssl" must be the very first command entered in the interactive interpreter. Odd! Unfortunately, the release build is a non-debug build and, so far, I have not been able to reproduce the segfault with any other build, debug or non-debug. So, whatever the problem is, it's very build dependent. Here is the OS X system traceback from the segfault:

Path: /Library/Frameworks/Python.framework/Versions/3.5.0b3_10_6/Resources/Python.app/Contents/MacOS/Python
Identifier: Python
Version: ???
Code Type: X86-64 (Native)
Parent Process: bash [51285]
Responsible: iTerm [754]
User ID: 503

Date/Time: 2015-07-10 19:57:16.086 -0700
OS Version: Mac OS X 10.10.4 (14E46)
Report Version: 11
Anonymous UUID: CFED52E3-698C-835B-D61C-F4B1F18D2CB6

Time Awake Since Boot: 800000 seconds

Crashed Thread: 0 Dispatch queue: com.apple.main-thread

Exception Type: EXC_BAD_ACCESS (SIGSEGV)
Exception Codes: KERN_INVALID_ADDRESS at 0x0000000000000018

VM Regions Near 0x18:
-->
__TEXT 0000000100000000-0000000100001000 [ 4K] r-x/rwx SM=COW /Library/Frameworks/Python.framework/Versions/3.5.0b3_10_6/Resources/Python.app/Contents/MacOS/Python

Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0 org.python.python 0x000000010015e5e5 lru_cache_tp_traverse + 37
1 org.python.python 0x000000010013a2d7 collect + 439
2 org.python.python 0x000000010013aee5 _PyObject_GC_Alloc + 357
3 org.python.python 0x000000010013afe7 _PyObject_GC_New + 23
4 org.python.python 0x0000000100059bce PyDict_New + 334
5 org.python.python 0x000000010015f029 lru_cache_new + 249
6 org.python.python 0x00000001000795a6 type_call + 38
7 org.python.python 0x000000010000dc93 PyObject_Call + 99
8 org.python.python 0x00000001000e9fd8 PyEval_EvalFrameEx + 7656
9 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
10 org.python.python 0x00000001000f035d PyEval_EvalFrameEx + 33133
11 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
12 org.python.python 0x00000001000f1e07 PyEval_EvalCodeEx + 71
13 org.python.python 0x00000001000e5ff5 builtin___build_class__ + 485
14 org.python.python 0x0000000100065549 PyCFunction_Call + 281
15 org.python.python 0x00000001000f0768 PyEval_EvalFrameEx + 34168
16 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
17 org.python.python 0x00000001000f1e61 PyEval_EvalCode + 81
18 org.python.python 0x00000001000e5683 builtin_exec + 627
19 org.python.python 0x0000000100065519 PyCFunction_Call + 233
20 org.python.python 0x00000001000f0a9b PyEval_EvalFrameEx + 34987
21 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
22 org.python.python 0x00000001000f035d PyEval_EvalFrameEx + 33133
23 org.python.python 0x00000001000f07fd PyEval_EvalFrameEx + 34317
24 org.python.python 0x00000001000f07fd PyEval_EvalFrameEx + 34317
25 org.python.python 0x00000001000f07fd PyEval_EvalFrameEx + 34317
26 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
27 org.python.python 0x00000001000f1e07 PyEval_EvalCodeEx + 71
28 org.python.python 0x000000010004017a function_call + 186
29 org.python.python 0x000000010000dc93 PyObject_Call + 99
30 org.python.python 0x0000000100010ff6 _PyObject_CallMethodIdObjArgs + 454
31 org.python.python 0x000000010010d6d3 PyImport_ImportModuleLevelObject + 1171
32 org.python.python 0x00000001000e5e03 builtin___import__ + 131
33 org.python.python 0x0000000100065549 PyCFunction_Call + 281
34 org.python.python 0x000000010000dc93 PyObject_Call + 99
35 org.python.python 0x00000001000e64f7 PyEval_CallObjectWithKeywords + 87
36 org.python.python 0x00000001000ea43e PyEval_EvalFrameEx + 8782
37 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
38 org.python.python 0x00000001000f1e61 PyEval_EvalCode + 81
39 org.python.python 0x00000001000e5683 builtin_exec + 627
40 org.python.python 0x0000000100065519 PyCFunction_Call + 233
41 org.python.python 0x00000001000f0a9b PyEval_EvalFrameEx + 34987
42 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
43 org.python.python 0x00000001000f035d PyEval_EvalFrameEx + 33133
44 org.python.python 0x00000001000f07fd PyEval_EvalFrameEx + 34317
45 org.python.python 0x00000001000f07fd PyEval_EvalFrameEx + 34317
46 org.python.python 0x00000001000f07fd PyEval_EvalFrameEx + 34317
47 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
48 org.python.python 0x00000001000f1e07 PyEval_EvalCodeEx + 71
49 org.python.python 0x000000010004017a function_call + 186
50 org.python.python 0x000000010000dc93 PyObject_Call + 99
51 org.python.python 0x0000000100010ff6 _PyObject_CallMethodIdObjArgs + 454
52 org.python.python 0x000000010010d6d3 PyImport_ImportModuleLevelObject + 1171
53 org.python.python 0x00000001000e5e03 builtin___import__ + 131
54 org.python.python 0x0000000100065549 PyCFunction_Call + 281
55 org.python.python 0x000000010000dc93 PyObject_Call + 99
56 org.python.python 0x00000001000e64f7 PyEval_CallObjectWithKeywords + 87
57 org.python.python 0x00000001000ea43e PyEval_EvalFrameEx + 8782
58 org.python.python 0x00000001000f1d00 _PyEval_EvalCodeWithName + 2400
59 org.python.python 0x00000001000f1e61 PyEval_EvalCode + 81
60 org.python.python 0x000000010011fa7a PyRun_InteractiveOneObject + 474
61 org.python.python 0x000000010011fdfe PyRun_InteractiveLoopFlags + 110
62 org.python.python 0x000000010012076c PyRun_AnyFileExFlags + 76
63 org.python.python 0x00000001001390a9 Py_Main + 3785
64 org.python.python 0x0000000100000e32 0x100000000 + 3634
65 org.python.python 0x0000000100000c84 0x100000000 + 3204

Thread 0 crashed with X86 Thread State (64-bit):
rax: 0x000000010023d6c0 rbx: 0x00000001006fdb70 rcx: 0x0000000100382048 rdx: 0x0000000000000000
rdi: 0x0000000000000000 rsi: 0x00000001001392e0 rbp: 0x00007fff5bffb530 rsp: 0x00007fff5bffb510
r8: 0x0000000000000000 r9: 0x0000000000000001 r10: 0x0000000000000016 r11: 0x00000001001392e0
r12: 0x00000001006fdb88 r13: 0x0000000000000000 r14: 0x00000001001392e0 r15: 0x000000010102fdb8
rip: 0x000000010015e5e5 rfl: 0x0000000000010206 cr2: 0x0000000000000018

Stefan, Ned, can you reproduce the same crash with following patch?

Serhiy, I'll try making a 3.5.0b3+patch installer build in the same manner as the 3.5.0b3 installer build. But I may not get to it for several days.

Sorry about the delay in testing the patch. I just confirmed (1) that I am still able to produce a segfault on OS X as described above under the specific conditions with a 10.6-like installer built with the current 3.5 tip and (2) that, with clru_cache_new.patch applied to the same current 3.5 tip, I no longer see the segfault. So it looks like a fix.

New changeset 5345e5ce2eed by Serhiy Storchaka in branch '3.5':
Issue bpo-14373: Fixed segmentation fault when gc.collect() is called during
https://hg.python.org/cpython/rev/5345e5ce2eed

New changeset 9c6d11d22801 by Serhiy Storchaka in branch 'default':
Issue bpo-14373: Fixed segmentation fault when gc.collect() is called during
https://hg.python.org/cpython/rev/9c6d11d22801

Thank you Ned.

Is anything left to do with this issue or it can be closed?

I suspect this change is implicated in bpo-25447.