[issue14373] C implementation of functools.lru_cache

Changes by Serhiy Storchaka : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___

[issue14373] C implementation of functools.lru_cache

Changes by Matt Joiner : -- nosy: -anacrolix ___ Python tracker ___ ___

[issue14373] C implementation of functools.lru_cache

Jason R. Coombs added the comment: I suspect this change is implicated in issue25447. -- nosy: +jason.coombs status: pending -> open ___ Python tracker

[issue14373] C implementation of functools.lru_cache

Changes by Raymond Hettinger : -- assignee: -> serhiy.storchaka status: open -> pending ___ Python tracker ___

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

Changes by Serhiy Storchaka storch...@gmail.com: -- priority: normal - release blocker ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

Changes by Tim Graham timogra...@gmail.com: -- nosy: -Tim.Graham ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

Stefan Behnel added the comment: test_fnmatch.py also passes, BTW. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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:

[issue14373] C implementation of functools.lru_cache

Tim Graham added the comment: Thanks, that does resolve the issue. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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:

[issue14373] C implementation of functools.lru_cache

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:

[issue14373] C implementation of functools.lru_cache

Changes by Serhiy Storchaka storch...@gmail.com: -- dependencies: +Correct reuse argument tuple in property descriptor ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

Serhiy Storchaka added the comment: Backed out the backout in cb30db9cc029. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

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 ___

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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 ___

[issue14373] C implementation of functools.lru_cache

Raymond Hettinger added the comment: Thanks Serhiy. I'll work on the next steps after the beta. -- assignee: serhiy.storchaka - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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 -

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

Changes by Stefan Krah stefan-use...@bytereef.org: -- nosy: -skrah ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

Changes by Antoine Pitrou pit...@free.fr: -- priority: low - normal ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

Mark Lawrence added the comment: https://pypi.python.org/pypi/fastcache/0.4.0 also seems relevant. -- nosy: +BreamoreBoy ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

Changes by Aaron Meurer asmeu...@gmail.com: -- nosy: +Aaron.Meurer ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

Changes by Patrick Westerhoff patrickwesterh...@gmail.com: -- nosy: +poke ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

Serhiy Storchaka added the comment: Could you please make a review Raymond? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

Changes by Josh Rosenberg shadowran...@gmail.com: -- nosy: +ShadowRanger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

Serhiy Storchaka added the comment: I'm working on this. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list mailing

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org

[issue14373] C implementation of functools.lru_cache

Changes by Jesús Cea Avión j...@jcea.es: -- nosy: +jcea ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list mailing list

[issue14373] C implementation of functools.lru_cache

Alexey Kachayev added the comment: Thread-safe implementation for cache cleanup. -- Added file: http://bugs.python.org/file28490/14373.v7.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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:

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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.

[issue14373] C implementation of functools.lru_cache

Alexey Kachayev added the comment: Serhiy, thank you for review. Working further on fixes. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org http://bugs.python.org/issue14373

[issue14373] C implementation of functools.lru_cache

Changes by Serhiy Storchaka storch...@gmail.com: -- stage: needs patch - patch review ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

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 rep...@bugs.python.org

[issue14373] C implementation of functools.lru_cache

Changes by Ned Batchelder n...@nedbatchelder.com: -- nosy: -nedbat ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

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:

[issue14373] C implementation of functools.lru_cache

Changes by Andrew Svetlov andrew.svet...@gmail.com: -- nosy: +amaury.forgeotdarc, pitrou ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

Changes by Serhiy Storchaka storch...@gmail.com: -- nosy: +serhiy.storchaka ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

Changes by Andrew Svetlov andrew.svet...@gmail.com: -- nosy: +asvetlov ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

Matt Joiner added the comment: I look forward to your feedback Ezio. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

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

[issue14373] C implementation of functools.lru_cache

Ezio Melotti added the comment: See also #12428. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list mailing list

[issue14373] C implementation of functools.lru_cache

Changes by Eric Snow ericsnowcurren...@gmail.com: -- nosy: +eric.snow ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

Changes by Ezio Melotti ezio.melo...@gmail.com: -- nosy: +ezio.melotti stage: - patch review versions: +Python 3.4 -Python 3.3 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

Matt Joiner anacro...@gmail.com 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

[issue14373] C implementation of functools.lru_cache

Changes by Matt Joiner anacro...@gmail.com: Removed file: http://bugs.python.org/file25026/functools.lru_cache-in-c.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

Changes by Matt Joiner anacro...@gmail.com: Removed file: http://bugs.python.org/file24984/functools.lru_cache-in-c.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

Raymond Hettinger raymond.hettin...@gmail.com 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

[issue14373] C implementation of functools.lru_cache

Raymond Hettinger raymond.hettin...@gmail.com 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 rep...@bugs.python.org

[issue14373] C implementation of functools.lru_cache

Changes by Raymond Hettinger raymond.hettin...@gmail.com: Removed file: http://bugs.python.org/file25084/lru_cache_class.py ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

Raymond Hettinger raymond.hettin...@gmail.com 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

[issue14373] C implementation of functools.lru_cache

Matt Joiner anacro...@gmail.com 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

[issue14373] C implementation of functools.lru_cache

Changes by Matt Joiner anacro...@gmail.com: Removed file: http://bugs.python.org/file24958/functools.lru_cache-in-c ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

Changes by Matt Joiner anacro...@gmail.com: -- nosy: +nedbat ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list mailing

[issue14373] C implementation of functools.lru_cache

Matt Joiner anacro...@gmail.com 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

[issue14373] C implementation of functools.lru_cache

Changes by Meador Inge mead...@gmail.com: -- nosy: +meador.inge ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___ Python-bugs-list

[issue14373] C implementation of functools.lru_cache

New submission from Matt Joiner anacro...@gmail.com: 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

[issue14373] C implementation of functools.lru_cache

Changes by Matt Joiner anacro...@gmail.com: Added file: http://bugs.python.org/file24958/functools.lru_cache-in-c ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___

[issue14373] C implementation of functools.lru_cache

Changes by Giampaolo Rodola' g.rod...@gmail.com: -- nosy: +giampaolo.rodola ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373 ___ ___

[issue14373] C implementation of functools.lru_cache

Raymond Hettinger raymond.hettin...@gmail.com added the comment: Thank you for working on this. I look forward to reviewing it. -- assignee: - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue14373