[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Changes by Matt Joiner :


--
nosy:  -anacrolix

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Jason R. Coombs]

Jason R. Coombs added the comment:

I suspect this change is implicated in issue25447.

--
nosy: +jason.coombs
status: pending -> open

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
assignee:  -> serhiy.storchaka
status: open -> pending

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
assignee: rhettinger -> 
status: pending -> open

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Thank you Ned.

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

--
priority: release blocker -> normal
status: open -> pending

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Roundup Robot]

Roundup Robot added the comment:

New changeset 5345e5ce2eed by Serhiy Storchaka in branch '3.5':
Issue #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 #14373: Fixed segmentation fault when gc.collect() is called during
https://hg.python.org/cpython/rev/9c6d11d22801

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Ned Deily]

Ned Deily added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
priority: normal -> release blocker

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Ned Deily]

Ned Deily added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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

--
Added file: http://bugs.python.org/file39923/clru_cache_new.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Ned Deily]

Ned Deily added the comment:

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: 80 seconds

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

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

VM Regions Near 0x18:
--> 
__TEXT 0001-00011000 [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   0x00010015e5e5 
lru_cache_tp_traverse + 37
1   org.python.python   0x00010013a2d7 collect + 439
2   org.python.python   0x00010013aee5 _PyObject_GC_Alloc + 
357
3   org.python.python   0x00010013afe7 _PyObject_GC_New + 23
4   org.python.python   0x000100059bce PyDict_New + 334
5   org.python.python   0x00010015f029 lru_cache_new + 249
6   org.python.python   0x0001000795a6 type_call + 38
7   org.python.python   0x0001dc93 PyObject_Call + 99
8   org.python.python   0x0001000e9fd8 PyEval_EvalFrameEx + 
7656
9   org.python.python   0x0001000f1d00 
_PyEval_EvalCodeWithName + 2400
10  org.python.python   0x0001000f035d PyEval_EvalFrameEx + 
33133
11  org.python.python   0x0001000f1d00 
_PyEval_EvalCodeWithName + 2400
12  org.python.python   0x0001000f1e07 PyEval_EvalCodeEx + 
71
13  org.python.python   0x0001000e5ff5 
builtin___build_class__ + 485
14  org.python.python   0x000100065549 PyCFunction_Call + 
281
15  org.python.python   0x0001000f0768 PyEval_EvalFrameEx + 
34168
16  org.python.python   0x0001000f1d00 
_PyEval_EvalCodeWithName + 2400
17  org.python.python   0x0001000f1e61 PyEval_EvalCode + 81
18  org.python.python   0x0001000e5683 builtin_exec + 627
19  org.python.python   0x000100065519 PyCFunction_Call + 
233
20  org.python.python   0x0001000f0a9b PyEval_EvalFrameEx + 
34987
21  org.python.python   0x0001000f1d00 
_PyEval_EvalCodeWithName + 2400
22  org.python.python   0x0001000f035d PyEval_EvalFrameEx + 
33133
23  org.python.python   0x0001000f07fd PyEval_EvalFrameEx + 
34317
24  org.python.python   0x0001000f07fd PyEval_EvalFrameEx + 
34317
25  org.python.python   0x0001000f07fd PyEval_EvalFrameEx + 
34317
26  org.python.python   0x0001000f1d00 
_PyEval_EvalCodeWithName + 2400
27  org.python.python   0x0001000f1e07 PyEval_EvalCodeEx + 
71
28  org.python.python   0x00010004017a function_call + 186
29  org.python.python   0x0001dc93 PyObject_Call + 99
30  org.python.python   0x000100010ff6 
_PyObject_CallMethodIdObjArgs + 454
31  org.python.python   0x00010010d6d3 
PyImport_ImportModuleLevelObject + 1171
32  org.python.python   0x0001000e5e03 builtin___import__ + 
131
33  org.python.python   0x000100065549 PyCFunction_Call + 
281
34  org.python.python   0x0001dc93 PyObject_Call + 99
35  org.python.python   0x0001000e64f7 
PyEval_CallObjectWithKeywords + 87
36  org.python.python   0x0001000ea43e PyEval_EvalFrameEx + 
8782
37  org.python.python   0x0001000f1d00 
_PyEval_EvalCod

[issue14373] C implementation of functools.lru_cache

[Tim Graham]

Changes by Tim Graham :


--
nosy:  -Tim.Graham

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Stefan Behnel]

Stefan Behnel added the comment:

test_fnmatch.py also passes, BTW.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Stefan Behnel]

Stefan Behnel added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Stefan Behnel]

Stefan Behnel added the comment:

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=0x72a80ae8, visit=0x43c528 , 
arg=0x0) at ./Modules/_functoolsmodule.c:1040
1040lru_list_elem *next = link->next;
(gdb) list
1035static int
1036lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void 
*arg)
1037{
1038lru_list_elem *link = self->root.next;
1039while (link != &self->root) {
1040lru_list_elem *next = link->next;
1041Py_VISIT(link);
1042link = next;
1043}
1044Py_VISIT(self->maxsize_O);
(gdb) print link
$1 = (lru_list_elem *) 0x0
(gdb) print self
$2 = (lru_cache_object *) 0x72a80ae8
(gdb) print self->root.next
$3 = (struct lru_list_elem *) 0x0
(gdb) print self->root
$4 = {ob_base = {_ob_next = 0x72a26458, _ob_prev = 0x90e860 , 
ob_refcnt = 1, ob_type = 0x92c500 }, 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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Roundup Robot]

Roundup Robot added the comment:

New changeset c52f381fe674 by Serhiy Storchaka in branch '3.5':
Issue #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 #14373: Other attempt to fix threaded test for lru_cache().
https://hg.python.org/cpython/rev/73acb8c187d4

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Roundup Robot]

Roundup Robot added the comment:

New changeset 19dbee688a30 by Serhiy Storchaka in branch '3.5':
Issue #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 #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 #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 #14373: C implementation of functools.lru_cache() now can be used with
https://hg.python.org/cpython/rev/f4b785d14792

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--
Added file: http://bugs.python.org/file39652/test_lru_cache_threaded.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Tim Graham]

Tim Graham added the comment:

Thanks, that does resolve the issue.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Here is a patch that adds __get__ for lru_cache object.

--
Added file: http://bugs.python.org/file39646/clru_cache_descr_get.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Tim Graham]

Tim Graham added the comment:

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

--
nosy: +Tim.Graham

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Backed out the backout in cb30db9cc029.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
dependencies: +Correct reuse argument tuple in property descriptor

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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

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

--
Added file: http://bugs.python.org/file39483/clru_cache_4.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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

--
Added file: http://bugs.python.org/file39478/clru_cache_3.patch
Added file: http://bugs.python.org/file39479/clru_cache_crasher.py

___
Python tracker 

___diff -r 2df7c958974e Lib/functools.py
--- a/Lib/functools.py  Sat May 23 18:08:55 2015 -0700
+++ b/Lib/functools.py  Sun May 24 10:11:21 2015 +0300
@@ -419,120 +419,129 @@ def lru_cache(maxsize=128, typed=False):
 if maxsize is not None and not isinstance(maxsize, int):
 raise TypeError('Expected maxsize to be an integer or None')
 
+def decorating_function(user_function):
+wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)
+return update_wrapper(wrapper, user_function)
+
+return decorating_function
+
+def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
 # Constants shared by all lru cache instances:
 sentinel = object()  # unique object used to signal cache misses
 make_key = _make_key # build a key from the function arguments
 PREV, NEXT, KEY, RESULT = 0, 1, 2, 3   # names for the link fields
 
-def decorating_function(user_function):
-cache = {}
-hits = misses = 0
-full = False
-cache_get = cache.get# bound method to lookup a key or return None
-lock = RLock()   # because linkedlist updates aren't threadsafe
-root = []# root of the circular doubly linked list
-root[:] = [root, root, None, None] # initialize by pointing to self
+cache = {}
+hits = misses = 0
+full = False
+cache_get = cache.get# bound method to lookup a key or return None
+lock = RLock()   # because linkedlist updates aren't threadsafe
+root = []# root of the circular doubly linked list
+root[:] = [root, root, None, None] # initialize by pointing to self
 
-if maxsize == 0:
+if maxsize == 0:
 
-def wrapper(*args, **kwds):
-# No caching -- just a statistics update after a successful 
call
-nonlocal misses
-result = user_function(*args, **kwds)
-misses += 1
+def wrapper(*args, **kwds):
+# No caching -- just a statistics update after a successful call
+nonlocal misses
+result = user_function(*args, **kwds)
+misses += 1
+return result
+
+elif maxsize is None:
+
+def wrapper(*args, **kwds):
+# Simple caching without ordering or size limit
+nonlocal hits, misses
+key = make_key(args, kwds, typed)
+result = cache_get(key, sentinel)
+if result is not sentinel:
+hits += 1
 return result
+result = user_function(*args, **kwds)
+cache[key] = result
+misses += 1
+return result
 
-elif maxsize is None:
+else:
 
-def wrapper(*args, **kwds):
-# Simple caching without ordering or size limit
-nonlocal hits, misses
-key = make_key(args, kwds, typed)
-result = cache_get(key, sentinel)
-if result is not sentinel:
+def wrapper(*args, **kwds):
+# Size limited caching that tracks accesses by recency
+nonlocal root, hits, misses, full
+key = make_key(args, kwds, typed)
+with lock:
+link = cache_get(key)
+if link is not None:
+# Move the link to the front of the circular queue
+link_prev, link_next, _key, result = link
+link_prev[NEXT] = link_next
+link_next[PREV] = link_prev
+last = root[PREV]
+last[NEXT] = root[PREV] = link
+link[PREV] = last
+link[NEXT] = root
 hits += 1
 return result
-result = user_function(*args, **kwds)
-cache[key] = result
+result = user_function(*args, **kwds)
+with lock:
+if key in cache:
+# Getting here means that this same key was added to the
+# cache while the lock was released.  Since the link
+# update is already done, we need only return the
+# computed result and update the count of misses.
+pass
+elif full:
+# Use the old root to store the new key and result.
+oldroot = root
+oldroot[KEY] = key
+oldroot[RESULT] = result
+# Empty th

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger added the comment:

Thanks Serhiy.  I'll work on the next steps after the beta.

--
assignee: serhiy.storchaka -> rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Thanks Raymond.

I tried to write an implementation with locking, but it would be too 
complicated (much more complex than all proposed before patches), because 
recursive locks are needed. In any case I think that GIL is enough here. 
Locking in Python implementation is needed for atomic modifying linked list.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Roundup Robot]

Roundup Robot added the comment:

New changeset 57776eee74f2 by Serhiy Storchaka in branch 'default':
Issue #14373: Added C implementation of functools.lru_cache().  Based on
https://hg.python.org/cpython/rev/57776eee74f2

--
nosy: +python-dev

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger added the comment:

Serhiy, go ahead and apply your patch, lru_cache2.patch.  I'll fix-up the 
make_key() code after the beta1 (like the pure python version, it needs to 
guarantee that hash is called no more than once per key).

--
assignee: rhettinger -> serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Stefan Krah]

Changes by Stefan Krah :


--
nosy:  -skrah

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Antoine Pitrou]

Antoine Pitrou added the comment:

Le 06/08/2014 21:19, Raymond Hettinger a écrit :
>
> I don't think so at all. The LRU cache we have now is plenty
> efficient
for its intended use cases (caching I/O bound functions and expensive
functions). If is only unsuitable for functions that are already
blazingly fast.

This is an unrealistic simplification. Many functions can be either 
expensive or blazingly fast, depending on their input (typical examples 
are re.compile(), math.factorial()...). But the decision of applying the 
lru_cache decorator is a compile-time binary decision: it cannot encode 
the varying properties of the function depending on its inputs.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger added the comment:

> I think we should increase the priority of this issue.

I don't think so at all.  The LRU cache we have now is plenty efficient for its 
intended use cases (caching I/O bound functions and expensive functions).  If 
is only unsuitable for functions that are already blazingly fast.  

Getting the locks right and carefully looking for re-entrancy issues is 
important.  Also, keeping the memory footprint of the keys small is important 
(if people didn't care about space, they wouldn't be using an LRU at all).

I will look at this but currently have much higher priorities elsewhere in 
Python (adding C accelerators for tricky code is less important for the time 
being -- we have a long time until 3.5).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Antoine Pitrou]

Antoine Pitrou added the comment:

I think a lock is still needed for cache misses. The dict operations (set and 
del) can release the GIL (as well as course as the PyObject_Call()), therefore 
you might end up with duplicate list links for a given key.

(and given cache misses are supposed to be much more expensive anyway, I don't 
think acquiring a lock there is detrimental)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Antoine Pitrou]

Changes by Antoine Pitrou :


--
priority: low -> normal

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Raymond, do you have time for the review? It will be easier to support both 
implementation at the same time, than change only Python implementation and 
asynchronously update the patch with the risk to lost changes in C 
implementation.

I think we should increase the priority of this issue. Efficient lru_cache will 
affect other parts of the stdlib. In particular the use of lru_cache was 
withdrawed in the re module due to large overhead of Python implementation. The 
ipaddress module now uses own specialized implementation of the caching instead 
of general lru_cache for the same reason. Issue13299 proposition will be more 
acceptable with faster lru_cache.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Mark Lawrence]

Mark Lawrence added the comment:

https://pypi.python.org/pypi/fastcache/0.4.0 also seems relevant.

--
nosy: +BreamoreBoy

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Aaron Meurer]

Changes by Aaron Meurer :


--
nosy: +Aaron.Meurer

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Patrick Westerhoff]

Changes by Patrick Westerhoff :


--
nosy: +poke

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger added the comment:

> Could you please make a review Raymond?

Yes, I will take a look.   I looking a making other changes to the lru_cache 
and don't want the C implementation to go it first.  There are still some open 
questions about re-entrancy that still need to be addressed before a C 
implementation gets added to the mix.

--
priority: high -> low

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Could you please make a review Raymond?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Josh Rosenberg]

Changes by Josh Rosenberg :


--
nosy: +ShadowRanger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Updated patch fixes bugs found by Antoine. Thank you Antoine.

--
Added file: http://bugs.python.org/file32784/clru_cache2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Antoine Pitrou]

Antoine Pitrou added the comment:

> Got rid of the lock, the new code must be thread-safe with GIL only.

I'm not convinced by this (see the review I posted).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Here is a revised patch. It is synchronized with tip. Got rid of capsules (sped 
up about 10%). lru_list_elem is now true Python object. Got rid of the lock, 
the new code must be thread-safe with GIL only.

I very much hope that this code will be included in 3.4. We can fix bugs later 
if there are any. I am also planning to optimize the make_key() functions.

--
priority: low -> high
Added file: http://bugs.python.org/file32779/clru_cache.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger added the comment:

After Serhiy looks at this, I need to review it for reentrancy thread-safety 
and reentrancy issues.

--
priority: normal -> low
versions: +Python 3.5 -Python 3.4

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

I'm working on this.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Brecht Machiels]

Brecht Machiels added the comment:

What's the status of this patch? What still needs to be done for it to be 
accepted?

--
nosy: +brechtm

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Jesús Cea Avión]

Changes by Jesús Cea Avión :


--
nosy: +jcea

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Alexey Kachayev]

Alexey Kachayev added the comment:

Updated diff with:
 * fix object leaks
 * tp_clear
 * additional test for maxsize < 0

I also reimplemented multithreading test (fixed error and added skip rule). But 
actually, I'm not sure that it's enough for ensuring thread-safety of clear 
operation. I'm working on other variant now. I will be appreciated for any 
advice about where to find example of the same (or close enough) test cases 
from other modules.

Regarding to previous comments from review. 

1. "guard against negative numbers"

I added special test case for negative maxsize in order to show, that now C 
version works the same as Python one. So, should we change both implementation? 
What behavior is most logical here? Reimplementation will change public API, so 
it's not only about acceleration.

2. Use regular PyObject instead of lru_list_elem.

What the problems are with current implementation?

--
Added file: http://bugs.python.org/file28498/14373.v9.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Alexey, as I see, you have missed some Antoine's comments (and my comments 
about whitespaces). Please, be more careful.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Alexey Kachayev]

Alexey Kachayev added the comment:

Thread-safe implementation for cache cleanup.

--
Added file: http://bugs.python.org/file28490/14373.v7.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Stefan Behnel]

Stefan Behnel added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Stefan Krah]

Stefan Krah added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Stefan Krah]

Stefan Krah added the comment:

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.

--
nosy: +skrah

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Stefan Behnel]

Stefan Behnel added the comment:

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
"""

--
nosy: +scoder

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--
stage: commit review -> patch review

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

LGTM. Thank you, Matt and Alexey.

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

--
stage: needs patch -> commit review
Added file: http://bugs.python.org/file28400/lru_cache_bench.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Alexey Kachayev]

Alexey Kachayev added the comment:

Added additional Py_DECREF(s) for key and value.

--
Added file: http://bugs.python.org/file28390/14373.v4.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Alexey Kachayev]

Alexey Kachayev added the comment:

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

--
Added file: http://bugs.python.org/file28386/14373.v3.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Alexey Kachayev]

Alexey Kachayev added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Ned Batchelder]

Changes by Ned Batchelder :


--
nosy:  -nedbat

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Thanks, Alexey.

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

--
stage: patch review -> needs patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
stage: needs patch -> patch review

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Andrew Svetlov]

Changes by Andrew Svetlov :


--
nosy: +amaury.forgeotdarc, pitrou

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Alexey Kachayev]

Alexey Kachayev added the comment:

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

--
nosy: +kachayev
Added file: http://bugs.python.org/file28369/14373.fixed.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--
components: +Extension Modules -Interpreter Core
stage: patch review -> needs patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Andrew Svetlov]

Changes by Andrew Svetlov :


--
nosy: +asvetlov

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Ezio Melotti]

Ezio Melotti added the comment:

See also #12428.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Ezio Melotti]

Ezio Melotti added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Matt Joiner added the comment:

I look forward to your feedback Ezio.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Ezio Melotti]

Changes by Ezio Melotti :


--
nosy: +ezio.melotti
stage:  -> patch review
versions: +Python 3.4 -Python 3.3

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Eric Snow]

Changes by Eric Snow :


--
nosy: +eric.snow

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Changes by Matt Joiner :


Removed file: http://bugs.python.org/file24984/functools.lru_cache-in-c.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Changes by Matt Joiner :


Removed file: http://bugs.python.org/file25026/functools.lru_cache-in-c.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Matt Joiner  added the comment:

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

--
Added file: http://bugs.python.org/file25094/functools.lru_cache-in-c.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Changes by Raymond Hettinger :


Removed file: http://bugs.python.org/file25084/lru_cache_class.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger  added the comment:

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

--
Added file: http://bugs.python.org/file25085/lru_cache_class.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger  added the comment:

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.

--
Added file: http://bugs.python.org/file25084/lru_cache_class.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Changes by Matt Joiner :


Removed file: http://bugs.python.org/file24958/functools.lru_cache-in-c

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Matt Joiner  added the comment:

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.

--
Added file: http://bugs.python.org/file25026/functools.lru_cache-in-c.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger  added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Changes by Matt Joiner :


--
nosy: +nedbat

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Meador Inge]

Changes by Meador Inge :


--
nosy: +meador.inge

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Matt Joiner  added the comment:

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.

--
keywords: +patch
Added file: http://bugs.python.org/file24984/functools.lru_cache-in-c.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Raymond Hettinger]

Raymond Hettinger  added the comment:

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

--
assignee:  -> rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Giampaolo Rodola']

Changes by Giampaolo Rodola' :


--
nosy: +giampaolo.rodola

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

Changes by Matt Joiner :


Added file: http://bugs.python.org/file24958/functools.lru_cache-in-c

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue14373] C implementation of functools.lru_cache

[Matt Joiner]

New submission from Matt Joiner :

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

--
components: Interpreter Core, Library (Lib)
messages: 156405
nosy: anacrolix, rhettinger
priority: normal
severity: normal
status: open
title: C implementation of functools.lru_cache
type: performance
versions: Python 3.3

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com