How does the python @cache decorator work?

user_14613136 0
Viewed 340

I recently learned about the cache decorator in Python and was surprised how well it worked and how easily it could be applied to any function. Like many others before me I tried to replicate this behavior in C++ without success ( tried to recursively calculate the Fib sequence ). The problem was that the internal calls didn't get cached. This is not a problem if I modify the original function , but I want it to be a decorator so that it can be applied anywhere. I am trying to decipher the Python @cache decorator from the source code but couldn't make out a lot, to figure out how I can ( IF it is even possible ) to replicate this behavior elsewhere.

Is there a way to cache the internal calls also ?

This is a simple way to add memoisation to the fib function. What i want is to build a decorator so that i can wrap any function. Just like the one in Python.

class CacheFib {
public:
  CacheFib() {}
  unsigned long long fib(int n) {

    auto hit = cache_pool.find(n);
    if (hit != cache_pool.end()) {
      return hit->second;
    } else if (n <= 1) {
      return n;
    } else {
      auto miss = this->fib(n - 1) + this->fib(n - 2);
      cache_pool.insert({n, miss});
      return miss;
    }
  }
  std::map<int, int> cache_pool;
};

This approach caches the actual call, meaning that if i call cachedFib(40) , twice the second time it will be O(1).It doesn't actually cache the internal calls to help with performance.

// A PROTOTYPE IMPLEMENTATION 
template <typename Func> class CacheDecorator {
public:
  CacheDecorator(Func fun) : function(fun) {}
  int operator()(int n) {
    auto hit = cache_pool.find(n);
    if (hit != cache_pool.end()) {
      return hit->second;
    } else {
      auto miss = function(n);
      cache_pool.insert({n, miss});
      return miss;
    }
  }
  std::function<Func> function;
  std::map<int, int> cache_pool;
};
int fib(int n) {
  if (n == 0 || n == 1) {
    return n;
  } else
    return fib(n - 1) + fib(n - 2);
} 
//main
auto cachedFib = CacheDecorator<decltype(fib)>(fib);
cachedFib(**);

Also any information on the @cache decorator or any C++ implementation ideas would be helpful.

python-decorators decorator caching python c++
2 Answers

So, as you're finding out, Python and C++ are different languages.

The key difference in this context is that in Python, the function name fib is looked up at run-time, even for the recursive call; meanwhile, in C++, the function name is looked up at compile-time, so by the time your CacheDecorator gets to it, it's too late.

A few possibilities:

  • Move the lookup of fib to run-time; you can do this either by using an explicit function pointer, or by making it a dynamic method. Either of those would mean coding the fib function differently.

  • Some sort of terrible, platform-dependent hack to overwrite either the function address table or the beginning of the function itself. This is going to be deep magic, particularly in the face of optimisations; the compiler might write out multiple copies of the function, or it might turn a recursive call into a loop, for example.

  • Move the implementation of the CacheDecorator to compile-time, as a pre-processor macro. That's probably the best way to preserve the intent of a python decorator.

  • Ideally, write Python in Python and C++ in C++; the languages each have their own idioms, which don't generally translate to each other in a one-to-one fashion.

    Trying to write Python-style code in C++ will always result in code that's somewhat alien, even in cases where it is possible. Much better to become fluent in the idioms of the language you're using.

user_6833290

I think that internal calls are not being cached because once the CacheDecorator is invoked, the CacheDecorator::operator() is only invoked once. After that, the CacheDecorator::function is recursively invoked. This is problematic because you want to check the cache at every recursive call of CacheDecorator::function; however, this does not occur because your cache checking code is in CacheDecorator::operator(). Consequently, the first and only time CacheDecorator::operator() is invoked is when you invoke it in main, which is also the first and only time the cache is checked. I also think that you would only encounter your issue if the passed in function uses recursion to compute its return value.

I may have made a mistake, but that's what I think the issue is.

I think that one way to fix this would be to accumulate and return a vector/map of computed values. Once your CacheDecorator::function is complete, you can then cache the returned vector/map. This would require you to modify your fib function, so this may not be a good solution. This modification also does not perfectly replicate Python's @cache decorator functionality since the programmer is essentially expected to store pre-computed values.

user_192011130
Related