0

You may be familiar with Python decorators such as @lru_cache. It wraps any function and does MEMOIZATION of results improving the runtime:

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

I want to build @lru_cache decorator in C++.
My implementation have one problem - when I wrap a recursive function and call it in a wrapping class, all subsequent recursive calls have no access to the cache. And as a result, I have 0 hits. Let me illustrate (I'll skip a bit of code).

LRUCache class:

template <typename Key, typename Val>
class LRUCache
{
public:
    LRUCache( int capacity = 100 ) : capacity{ capacity } {}

    Val get( Key key ) {... }    
    void put( Key key, Val value ) {... } 
    ...

private:
    int capacity;
    std::list<std::pair<Val, Key>> CACHE;
    std::unordered_map<Key, typename std::list<std::pair<Val, Key>>::iterator> LOOKUP;
};

_LruCacheFunctionWrapper class:

template <typename Key, typename Val>
class _LruCacheFunctionWrapper
{
    struct CacheInfo {... };

public:
    _LruCacheFunctionWrapper( std::function<Val( Key )> func, int maxSize ) 
        : _wrapped{ func }
        , _cache{ maxSize }
        , _hits{ 0 }
        , _misses{ 0 }
        , _maxsize{ maxSize }
    {}

    template<typename... Args>
    Val operator()( Args... args )
    {
        auto res = _cache.get( args... );

        if( res == -1 )
        {
            ++_misses;
            res = _wrapped( args... );
            _cache.put( args..., res );
        }
        else
            ++_hits;

        return res;
    }

    CacheInfo getCacheInfo() {... }   
    void clearCache() {... }

private:
    std::function<Val( Key )> _wrapped;
    LRUCache<Key, Val> _cache;
    int _hits;
    int _misses;
    int _maxsize;
};

And lastly, the target function:

long long fib( int n )
{
    if( n < 2 )
        return n;
    return fib( n - 1 ) + fib( n - 2 );
}

You may see that the line:

res = _wrapped( args... );

is sending me into the function scope and I have to recalculate all recursive calls. How can I solve it?

Main.cpp:

_LruCacheFunctionWrapper<int, long long> wrapper( &fib, 50 );

for( auto i = 0; i < 16; ++i )
    std::cout << wrapper( i ) << " ";
user2376997
  • 501
  • 6
  • 22
  • Can you create a [minimal reproducible example](https://stackoverflow.com/help/minimal-reproducible-example) here [on godbolt](https://godbolt.org/z/oq4xbjrMW) – Jason Nov 07 '22 at 05:03
  • @JasonLiam , https://godbolt.org/z/bPrhM9za5 – user2376997 Nov 07 '22 at 05:46
  • Can you also describe how the current output differs from your expected output. Or if the output is correct but you want something else. – Jason Nov 07 '22 at 05:51
  • If there is no obvious problem with your code and you just want a review or general tips, the question might be more suitable for https://codereview.stackexchange.com/. Questions here require a clear problem statement. – Jason Nov 07 '22 at 05:57
  • The problem is that cashing is not working: fib(4) should be called after fib(3) in a loop and therefore fib(3) and fib(2) are already calculated and stored in a cache, but fib(4) is calculating all the tree steps – user2376997 Nov 07 '22 at 06:02
  • because there seem to be no mechanism to call a wrapped function in a `_LruCacheFunctionWrapper` class scope..? – user2376997 Nov 07 '22 at 06:06

0 Answers0