C++ LRUCache decorator | call a non-member function in a class scope

98 Views Asked by At

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 ) << " ";
0

There are 0 best solutions below