Expanding lru_cache to allow caching data without a function call

Proposed Feature

This is a proposal to support a new method for functions with the lru_cache annotation in order to allow users to add data to the cache without invoking the underlying function. This method is referred to as cache_put(returned_value, *args, **kwargs) --> None in this proposal.

Use Cases

Avoid Expensive Calls When Data Is Already Present in the Program

If the result of a function call can be inferred from data that already exists in a program then a user could optimize their code by writing that data to a function’s cache without calling the actual function.

In the following pseudocode a costly database query is avoided by caching the known output of get_manager_of_user() before that function is ever called.

# For example purposes only, please don't add SQL injection to your codebase

@functools.lru_cache
def get_manager_of_user(user):
	return db.get(f"SELECT MANAGER WHERE USER = {user};")["MANAGER"]

def get_all_data_on_user(user):
	data = db.get(f"SELECT * WHERE USER = {user};")
	get_manager_of_user.cache_put(returned_value=data["MANAGER"], args=(user,))
	return data

if __name__ == "__main__":
    print(get_all_data_on_user("foo"))
    print(get_manager_of_user("foo"))
    assert db.total_calls == 1

Add a Base Case During Memoization

Adding a base case to this recursive fibonacci sequence function is more efficient compared to an implementation with memoization that checks for the base case every time the function is invoked.

@functools.lru_cache(maxsize=None)
def fib(n):
    return fib(n-1) + fib(n-2)

fib.cache_put(returned_value=0, args=(0,))
fib.cache_put(returned_value=1, args=(1,))

assert fib(7) == 13
1 Like

Encouraging this seems like a bad idea since it’s an easy way to get hard-to-spot infinite recursion if people accidentally get their base case removed from the cache (or refactoring moves around calls, or a later programmer forgets something, or …).

It can also lead to values being returned that aren’t obvious from the implementation - “Go to declaration” becomes less useful for these functions since you also have to lookup all uses of cache_put and verify that they are correct.

And in fact, your example already contains an infinite recursion case that most naive implementations of fib would catch: fib(-1).

But I do find the first usecase convincing, so overall I am torn. Maybe we just need to communicate clearly that calling cache_clear should not break your program? (and therefore not use the second example you provided)

1 Like

That’s more than fair, I would agree that the first use case is stronger and the second use case can be dangerous.

Good idea, I would support modifying the lru_cache documentation to contain that warning.

For the second use case, an initial_data parameter on the decorator itself seems like a better design fit. It could also be saved for restoration after the cache is dynamically cleared.

The proposed method makes sense for the first use case, though.

1 Like

That’s great when maxsze is None, but it just needs a little bit of work otherwise. A dict that will work with the rest of the machinery needs to be created here, loosely like:

initial_data = initial_data or {}
cache = {make_key() : make_link(v) for k, v in initial_data.items()} .

Key making code (- it could be _HashedSeq)
Value making code ([last, root, key, result])

I’ve not thought about how make_link should be implemented, and it would be fortunate if it can be contained neatly in a dict comp as above. The implementation for it, would need to ensure the linked list tracking the LRU ordering is correct afterwards. It could be argued that instead of writing more code for make_link that works with the old, and it’s best to reuse the existing code, and create a .cache_put, as Jack suggested.

This could then also be used to iterate over an extra initial_data arg.

I’m willing to refactor the second with lock block into a first draft of a .cache_put (the hits and misses counts indicate exactly what it should contain).

Have I overlooked something I should first know?

I think that this is just outside of scope of lru_cache(). lru_cache() is for caching the result of a slow function. Your cases are different, because you want to cache not a result of a function.

In your first case you can simply use double caching. Place it either after the lru_cache() cache:

@functools.lru_cache
def get_manager_of_user(user):
        if user in internal_cache:
            return internal_cache[user]
	return db.get(f"SELECT MANAGER WHERE USER = {user};")["MANAGER"]

or before it:

def get_manager_of_user(user):
        if user in external_cache:
            return external_cache[user]
	return _get_manager_of_user(user)

@functools.lru_cache
def _get_manager_of_user(user):
	return db.get(f"SELECT MANAGER WHERE USER = {user};")["MANAGER"]

In your second case you can use a similar code, but it may be simpler and faster to just test n <= 1.

Not every caching problem should be solved with lru_cache().

1 Like

Yep.

I couldn’t resist taking stab at the Python code. Unfortunately, only afterwards did I notice, that there is a C implementation for functools:

try:
    from _functools import _lru_cache_wrapper
except ImportError:
    pass

Doh!

I’m more than happy to contribute this anywhere really, (or publish it on PyPi myself if you really want this feature Jake). But it will need a lot more work than I realised, getting this feature into the core library.

1 Like

With double caching the same result could occupy memory in both caches, i.e. not memory efficient.

If a direct access to the lru_cache is undesired, I guess it is better not to base a solution on the lru_cache at all.

Just a small detail - IMO the .cache_put() should accept arguments in the same way as the decorated function except the value being inserted prepended as the very first and positional only argument.

@lru_cache
def foo(arg1, arg2, flag=False):
    ...

foo.cache_put(known_value, val1, val2, flag=True)
#         foo(             val1, val2, flag=True)
# matching signature       ^^^^^^^^^^^^^^^^^^^^^

What if foo itself has a kwarg called known_value? It should be the first positional arg in *args.

No problem there. A positional-only argument (PEP-570) is always given without a name, that’s why no conflict with a keyword argument name could exist.

What about an optional parameter for lru_cache to init the cache?

user = "foo"
data = {user: db.get(f"SELECT * WHERE USER = {user};")

@functools.lru_cache(initial_cache = data)
def get_manager_of_user(user):
	return db.get(f"SELECT MANAGER WHERE USER = {user};")["MANAGER"]

How much memory? dict uses 30-50 bytes per item. Until you prepopulate the cache with million of items, this should not make any difference on modern computers. The key and the value usually occupy more memory, and they are shared.

And it does not even occupy memory in the lru_cache() cache if you check the cache before calling the lru_cache() decorated function.

I agree memory it’s not a problem with double caching. The problem I see is that if you want to invalidate the cache, you must invalidate both. It’s slighter more complicated.

I getcha - thanks. It took me a second attempt to read “positional only”.

I like an initial_data API too for pre-population, but it’s more complicated than passing in a dict in practise.

Under the hood, in order to implement the LRU part in the name lru_cache, when maxsize is specified as an int, there’s also a linked list formed by a list of the next and previous lists, the key, and the actual return value. So the existing code for filling the cache on a cache miss might as well be re-used. That’s what I did in my suggested pure-Python implementation above.

An arbitrary function wrapped by lru_cache may also accept non-hashable args. There is tried and tested existing code in functools to handle this, but the user passing in a dict will not work out of the box nicely with it, in all the cases it is required to support. Instead of a dict, I chose a list of tuples of possible arg tuples and kwargs str-keyed dicts, with the return values.

What the C implementation does I haven’t even looked at, but I can’t imagine it’s much simpler. If it is at all.

I use this pattern too, and it’d be great if there was a tool to make using it a breeze. But similarly to Serhiy, it does not necessarily imply that a new feature implementing a pre-populated or user-fillable cache, must be supported in functools.lru_cache. It can be its own thing instead.

How much? It depends. In best case both caches refer to the same object (C1[x] is C2[x]). In slightly worse case each cache has its own copy (C1[x] == C2[x], but not C1[x] is C2[x]), because the caches are getting their values not in exactly the same way (use-case #1 in the original post). In worst case the objects are big and in large quantitiy.

I agree that modern computers will not have any problems with it, but there exists a better way.

It could happen under these circumstances:
1.the decorated function is called first (get_manager_of_user); the resulting value is then inserted into the lru_cache.
2.the other function is called (get_all_data_on_user for the same user). As a side-effect it gets the same value as above. As it is not possible to check the contents of the lru_cache, it will be inserted into the secondary cache. Thus both caches will have the same value.

Since lru_cache works on any callable, including a class, whose __call__ method can be customized with a metaclass, one possible workaround to sneak data into lru_cache’s cache is to temporarily patch the __call__ method of the metaclass with a dummy function that returns the desired cached value, and then call the dummy function with the corresponding arguments just so lru_cache can cache it without actually calling the wrapped function:

from functools import lru_cache
from unittest.mock import patch

def precacheable_lru_cache(maxsize=128, typed=False):
    def decorator(func):
        class PrecacheableMeta(type):
            def __call__(cls, *args, **kwargs):
                return func(*args, **kwargs)

        @lru_cache(maxsize, typed)
        class Precacheable(metaclass=PrecacheableMeta):
            pass

        def cache_put(return_value, *args, **kwargs):
            def dummy(cls, *args, **kwargs):
                return return_value
            with patch.object(PrecacheableMeta, '__call__', dummy):
                Precacheable(*args, **kwargs)

        Precacheable.cache_put = cache_put
        return Precacheable
    return decorator

so that the following assertion will pass:

@precacheable_lru_cache(maxsize=None)
def fib(n):
    return fib(n-1) + fib(n-2)

fib.cache_put(0, 0)
fib.cache_put(1, 1)

assert fib(7) == 13

Demo here

2 Likes

On second thought, since the class above is no more than a wrapper, we might as well just use a wrapper function that either calls the wrapped function or return the value being cached depending on the mode:

from functools import lru_cache

def precacheable_lru_cache(maxsize=128, typed=False):
    def decorator(func):
        @lru_cache(maxsize, typed)
        def wrapper(*args, **kwargs):
            if value is wrapping:
                return func(*args, **kwargs)
            return value

        def cache_put(return_value, *args, **kwargs):
            nonlocal value
            value = return_value
            wrapper(*args, **kwargs)
            value = wrapping

        value = wrapping = object()
        wrapper.cache_put = cache_put
        return wrapper
    return decorator

Demo here

Cunning and educational as ever, Ben. I can understand how the second example would work if cache_put was named “make_cache_putter”. Otherwise, why is the body of set_value not part of cache_put itself (and target added to its args), but instead returned by it?

1 Like