functools.lru_cache manual cache modification
Hi, I've written a tail call optimization lib for python3. <https://titania.fs.uni-saarland.de/projects/libtco> It works fine. I use a custom return, which throws the next function arguments as an exception and a decorator, which handles the exception. One strength of the functools.lru_cache lies in caching results of calls initiated by the function itself (i.e. recursive call results). However because of the exception, the intermediate results from the tail recursion don't end up in the cache, if my tail call optimization is used together with lru_cache. So I would like to be able to manually add argument-result pairs in the cache. A manual lookup is not needed for my purpose, but I propose that there should be methods to 1. add argument-result pairs to the cache 2. lookup if there is a result for given arguments 3. lookup the result for given arguments if it exists (exception thrown otherwise) 4. invalidate specific cache entries (at the moment you can only invalidate the cache as a whole through func.cache_clear()) What do you think? Best Regards, Constantin
On 01Dec2014 17:34, Constantin Berhard <constantin@exxxtremesys.lu> wrote:
I'm kind of +1 on this, but I'd be for a different exposure. Let lru_cache expose a mapping of the cache. Once you have that mapping, expecially if it is just a dict, everything else comes for free. In fact, I'd advocate moving the LRU cache supporting object off into collections and building functools.lru_cache on top of that. Use case: I had to write my own LRU cache bcause I wasn't just wrapping a function. Having that available as a standalone object from collections which looked like a lossy mapping (i.e. things vanish from the mapping when the cache overflows) would be immensely useful. Cheers, Cameron Simpson <cs@zip.com.au> The first ninety percent of the task takes ninety percent of the time, and the last ten percent takes the other ninety percent.
On 2 December 2014 at 08:41, Cameron Simpson <cs@zip.com.au> wrote:
As far as I'm aware, this is actually a deliberate design decision. There are so many degrees of freedom in designing a cache API that without constrainting the usage model it's really quite difficult to come up with a flexible abstraction that's easier to use than just building your own custom caching class. And once you expose the underlying mapping in functools.lru_cache itself, it hugely constraints the internal implementation of that cache (since you just made a whole lot of things that are currently implementation details part of the public API). So collections.OrderedDict provides the raw building block needed to implement an LRU cache, while functools.lru_cache applies that building block to a particular use case. It's OK if folks with needs that don't quite fit the standard idiom write their own custom class to handle it - that makes it possible to keep the standard tools simple to handle the standard cases, while folks with different needs can just write something specifically tailored to their situation, rather than trying to learn and configure a more generic API. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 02.12.2014 13:57, Nick Coghlan wrote:
collections.LruCache class, which is the data structure currently used in functools.lru_cache.
Then @functools.lru_cache would become @functools.cache(collections.LruCache(maxsize=128)) Where LruCache would be quite trivially based on collections.OrderedDict
This can then be done more explicitly by exposing the underlying cache as decorated_function.cache or something like that. there are function calls that the cache decorator can't get directly notified of. Best Regards, Constantin [1] my tail call optimization lib: <https://titania.fs.uni-saarland.de/projects/libtco>
On Tue, Dec 2, 2014 at 1:20 PM, Antoine Pitrou <solipsis@pitrou.net> wrote:
collections.OrderedDict uses its own slow linked list. I suppose lru_cache is micro-optimized; also, it's thread-safe.
One of the propositions is to expose these implementations in a way that: 1. The implementation used for functools.lru_cache can be chosen/switched. 2. The current implementation in lru_cache can be used for other purposes. Grako parsers, for example don't use lru_cache in memoization because they need finer control about what gets cached. -- Juancarlo *Añez*
Yes, that is exactly correct. For example, there is a proposed C implementation that has different internal details that it surely won't want to or be able to expose.
Right. The OrderedDict makes it really easy to roll your own variants. And that is what the LRU cache used originally. Later, it evolved to use its own linked list so that it could have only one internal dictionary instead of the two used by the OrderedDict. This cut the space overhead almost in half and sped-up cache lookups considerably. Having its own structure also lets the LRU cache neatly deal with multi-threading and re-entrancy so that it does fail in odd ways when used in complex environments.
I concur. Raymond
On Dec 3, 2014, at 9:11, Raymond Hettinger <raymond.hettinger@gmail.com> wrote:
Maybe just providing the original version as a recipe in functools, as an "equivalent to..." block to show people how to roll their own, would solve the problem well enough for this thread? (Especially if 3.5 or 3.6 is going to get a C implementation of OrderedDict, which would presumably help the single-threaded speed problem, if not the space and coarse locking problems, for people who wanted to build something between the odict and the cache?) the 3.2 version is under 100 lines, so it doesn't seem too horrible to copy into the docs.
On 03.12.2014 22:22, Andrew Barnert wrote:
I need this to make my decorator compatible with lru_cache. <https://titania.fs.uni-saarland.de/projects/libtco> It's only 27 lines of code, you may read it if you want to understand my problem. (additionally 62 lines of example code) The problem is that the exception carrying the arguments->return_data information is thrown past the lru_cache decorator because it can't catch it. Best Regards, Constantin
On 03.12.2014 23:33, Ethan Furman wrote:
I don't need or want an lru_cache. I want people, who want to use my library, to be able to use the standard functools together with my lib. So I want to become compatible with lru_cache. Of course, I could provide a special version of an lru cache, which is tuned to work well with my library, but I regard that solution as unelegant. Constantin
On 4 December 2014 at 08:41, Constantin Berhard <constantin@exxxtremesys.lu> wrote:
There are *a lot* of memoisation decorators out there - functools.lru_cache is only one of them. It's highly unlikely *any* of them are going to trigger if the call throws an exception. However, it looks as if your library will add the appropriate cache entry on the next pass through the iterative loop, so it isn't clear what additional values you would like to cache. As Ethan suggests, a clearer explanation of the current incompatibility, and what additional cache entries you would like to be able to inject may help us better understand the suggestion. Regards, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 04.12.2014 15:02, Nick Coghlan wrote:
You're right. I'm sorry for being unclear. I now have written code that compares a) a stupid custom cache, which offers the interfaces I need ("f") b) the most stupid way to combine libtco with lru_cache ("f2") c) the slightly less stupid way to combine libtco with lru_cache ("f3") A test run computes in this order: f(6), f(6), f(4) in a) only the first computation has to be done, the other two are in cache afterwards in b) nothing can be cached in c) only exact arguments can be cached, i.e. f(6) is only calculated once, but the intermediate result that was calculated on the way is not used to have f(4) in the cache, so f(4) has to be completely recomputed. The code is here: <http://nopaste.info/a82d680210_nl.html> It's a single python 3 script ready for execution. These changes, when properly split up will also find their way into the libtco git. As you can see from the code, the interface I propose just adds two functions to the cache: cache_get and cache_put. I think that any cache should be able to provide these functions, no matter how its cache strategy or how it is implemented. I'm sorry if my code is tldr, but I really can't think of an easy way of explaining it right now. I'll be happy to answer further questions though. Best Regards, Constantin
On Dec 4, 2014, at 16:49, Constantin Berhard <constantin@exxxtremesys.lu> wrote:
You realize that, if this change gets into the 3.5 stdlib, it's still not going to work with any of the many third-party memoization decorators that work today that Nick mentioned, or in 3.4 or earlier, right? So it seems like you're still going to need to provide a workaround--even if that's just including a backport of the current lru_cache in your module or recommending a third-party backport--unless you just want to document that your module requires 3.5+ if people want to also use a memoization cache. Also, it seems like you could have already written a patch for 3.5, and also put your patched version up on PyPI or included it in your module; since you're going to need to do those things even if you convince everyone, why not do it now? (This would also give you a chance to write up initial wording for the docs patch to explain what these new methods are for, which might help explain your problem, and which would also let people critique the wording early.)
A couple comments: You need better names. f? _f? fun? which of those two are the same? Have you tried it without the 'return_from' function? It might be interesting to have this be a more general 'recurse' decorator. You could have your own basic cache, and specify which methods you need for somebody to substitute in a different cache (which is a better option for all previous Pythons than making a change to 3.5). -- ~Ethan~
On 01Dec2014 17:34, Constantin Berhard <constantin@exxxtremesys.lu> wrote:
I'm kind of +1 on this, but I'd be for a different exposure. Let lru_cache expose a mapping of the cache. Once you have that mapping, expecially if it is just a dict, everything else comes for free. In fact, I'd advocate moving the LRU cache supporting object off into collections and building functools.lru_cache on top of that. Use case: I had to write my own LRU cache bcause I wasn't just wrapping a function. Having that available as a standalone object from collections which looked like a lossy mapping (i.e. things vanish from the mapping when the cache overflows) would be immensely useful. Cheers, Cameron Simpson <cs@zip.com.au> The first ninety percent of the task takes ninety percent of the time, and the last ten percent takes the other ninety percent.
On 2 December 2014 at 08:41, Cameron Simpson <cs@zip.com.au> wrote:
As far as I'm aware, this is actually a deliberate design decision. There are so many degrees of freedom in designing a cache API that without constrainting the usage model it's really quite difficult to come up with a flexible abstraction that's easier to use than just building your own custom caching class. And once you expose the underlying mapping in functools.lru_cache itself, it hugely constraints the internal implementation of that cache (since you just made a whole lot of things that are currently implementation details part of the public API). So collections.OrderedDict provides the raw building block needed to implement an LRU cache, while functools.lru_cache applies that building block to a particular use case. It's OK if folks with needs that don't quite fit the standard idiom write their own custom class to handle it - that makes it possible to keep the standard tools simple to handle the standard cases, while folks with different needs can just write something specifically tailored to their situation, rather than trying to learn and configure a more generic API. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 02.12.2014 13:57, Nick Coghlan wrote:
collections.LruCache class, which is the data structure currently used in functools.lru_cache.
Then @functools.lru_cache would become @functools.cache(collections.LruCache(maxsize=128)) Where LruCache would be quite trivially based on collections.OrderedDict
This can then be done more explicitly by exposing the underlying cache as decorated_function.cache or something like that. there are function calls that the cache decorator can't get directly notified of. Best Regards, Constantin [1] my tail call optimization lib: <https://titania.fs.uni-saarland.de/projects/libtco>
On Tue, Dec 2, 2014 at 1:20 PM, Antoine Pitrou <solipsis@pitrou.net> wrote:
collections.OrderedDict uses its own slow linked list. I suppose lru_cache is micro-optimized; also, it's thread-safe.
One of the propositions is to expose these implementations in a way that: 1. The implementation used for functools.lru_cache can be chosen/switched. 2. The current implementation in lru_cache can be used for other purposes. Grako parsers, for example don't use lru_cache in memoization because they need finer control about what gets cached. -- Juancarlo *Añez*
Yes, that is exactly correct. For example, there is a proposed C implementation that has different internal details that it surely won't want to or be able to expose.
Right. The OrderedDict makes it really easy to roll your own variants. And that is what the LRU cache used originally. Later, it evolved to use its own linked list so that it could have only one internal dictionary instead of the two used by the OrderedDict. This cut the space overhead almost in half and sped-up cache lookups considerably. Having its own structure also lets the LRU cache neatly deal with multi-threading and re-entrancy so that it does fail in odd ways when used in complex environments.
I concur. Raymond
On Dec 3, 2014, at 9:11, Raymond Hettinger <raymond.hettinger@gmail.com> wrote:
Maybe just providing the original version as a recipe in functools, as an "equivalent to..." block to show people how to roll their own, would solve the problem well enough for this thread? (Especially if 3.5 or 3.6 is going to get a C implementation of OrderedDict, which would presumably help the single-threaded speed problem, if not the space and coarse locking problems, for people who wanted to build something between the odict and the cache?) the 3.2 version is under 100 lines, so it doesn't seem too horrible to copy into the docs.
On 03.12.2014 22:22, Andrew Barnert wrote:
I need this to make my decorator compatible with lru_cache. <https://titania.fs.uni-saarland.de/projects/libtco> It's only 27 lines of code, you may read it if you want to understand my problem. (additionally 62 lines of example code) The problem is that the exception carrying the arguments->return_data information is thrown past the lru_cache decorator because it can't catch it. Best Regards, Constantin
On 03.12.2014 23:33, Ethan Furman wrote:
I don't need or want an lru_cache. I want people, who want to use my library, to be able to use the standard functools together with my lib. So I want to become compatible with lru_cache. Of course, I could provide a special version of an lru cache, which is tuned to work well with my library, but I regard that solution as unelegant. Constantin
On 4 December 2014 at 08:41, Constantin Berhard <constantin@exxxtremesys.lu> wrote:
There are *a lot* of memoisation decorators out there - functools.lru_cache is only one of them. It's highly unlikely *any* of them are going to trigger if the call throws an exception. However, it looks as if your library will add the appropriate cache entry on the next pass through the iterative loop, so it isn't clear what additional values you would like to cache. As Ethan suggests, a clearer explanation of the current incompatibility, and what additional cache entries you would like to be able to inject may help us better understand the suggestion. Regards, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 04.12.2014 15:02, Nick Coghlan wrote:
You're right. I'm sorry for being unclear. I now have written code that compares a) a stupid custom cache, which offers the interfaces I need ("f") b) the most stupid way to combine libtco with lru_cache ("f2") c) the slightly less stupid way to combine libtco with lru_cache ("f3") A test run computes in this order: f(6), f(6), f(4) in a) only the first computation has to be done, the other two are in cache afterwards in b) nothing can be cached in c) only exact arguments can be cached, i.e. f(6) is only calculated once, but the intermediate result that was calculated on the way is not used to have f(4) in the cache, so f(4) has to be completely recomputed. The code is here: <http://nopaste.info/a82d680210_nl.html> It's a single python 3 script ready for execution. These changes, when properly split up will also find their way into the libtco git. As you can see from the code, the interface I propose just adds two functions to the cache: cache_get and cache_put. I think that any cache should be able to provide these functions, no matter how its cache strategy or how it is implemented. I'm sorry if my code is tldr, but I really can't think of an easy way of explaining it right now. I'll be happy to answer further questions though. Best Regards, Constantin
On Dec 4, 2014, at 16:49, Constantin Berhard <constantin@exxxtremesys.lu> wrote:
You realize that, if this change gets into the 3.5 stdlib, it's still not going to work with any of the many third-party memoization decorators that work today that Nick mentioned, or in 3.4 or earlier, right? So it seems like you're still going to need to provide a workaround--even if that's just including a backport of the current lru_cache in your module or recommending a third-party backport--unless you just want to document that your module requires 3.5+ if people want to also use a memoization cache. Also, it seems like you could have already written a patch for 3.5, and also put your patched version up on PyPI or included it in your module; since you're going to need to do those things even if you convince everyone, why not do it now? (This would also give you a chance to write up initial wording for the docs patch to explain what these new methods are for, which might help explain your problem, and which would also let people critique the wording early.)
A couple comments: You need better names. f? _f? fun? which of those two are the same? Have you tried it without the 'return_from' function? It might be interesting to have this be a more general 'recurse' decorator. You could have your own basic cache, and specify which methods you need for somebody to substitute in a different cache (which is a better option for all previous Pythons than making a change to 3.5). -- ~Ethan~
participants (9)
-
Andrew Barnert -
Antoine Pitrou -
Cameron Simpson -
Constantin Berhard -
Ethan Furman -
Guido van Rossum -
Juancarlo Añez -
Nick Coghlan -
Raymond Hettinger