Cache Optimization and Polymorphism

c++, c++11, optimization, polymorphism, shared-ptr

Solution

Why create your own class? There's no need for you to fail to re-create the interface of `unordered_map`. This functionality can be added as a re-usable algorithm based on `std::function` and `std::unordered_map`. It's been a while since I worked with variadic templates, but I hope you get the idea.

template<typename Ret, typename... Args> 
std::function<Ret(Args...)> memoize(std::function<Ret(Args...)> t) {
    std::unordered_map<std::tuple<Args...>, Ret> cache;
    return [=](Args... a) mutable -> Ret {
        if (cache.find(std::make_tuple(a...)) != cache.end())
            return cache[std::make_tuple(a...)];
        else
            return cache[std::make_tuple(a...)] = t(a...);
    };
}

I don't recall, offhand, whether `std::hash` natively supports tuples. If not, you might need to add it, or use `std::map` which does natively support them.

Edit: Hmm, I didn't notice that you wanted to share the cache. Well, this shouldn't be too difficult a problem, just stick an `unordered_map` member in Calculator and pass it in by reference, but the semantics of doing so seem a bit... odd.

Edit again: Just the most recent value? Even simpler.

template<typename Ret, typename... Args> 
std::function<Ret(Args...)> memoize_last(std::function<Ret(Args...)> t) {
    std::tuple<Args...> cache;
    Ret result;
    return [=](Args... a) mutable -> Ret {
        if (std::tie(a...) == cache)
            return result;
        cache = std::make_tuple(a...);
        return result = t(a...);
    };
}

If you want to share between several Functions, then the alteration is the same- just declare it in the class and pass in as reference.

Problem

Suppose I have a calculator class that implements the Strategy Pattern using `std::function` objects as follows (see Scott Meyers, Effective C++: 55 Specific Ways to Improve Your Programs and Designs): ``` class Calculator { public: ... std::vector<double> Calculate(double x, double y) { std::vector<double> res; for(const Function& f : functions) res.push_back(f(x,y)); return res; } private: std::vector<Function> functions; }; ``` where ``` typedef std::function<double(double,double)> Function; ``` Here is the problem I am facing: suppose functions `f` and `g`, both of type `Function`, perform expensive and identical calculations internally to get the final result. In order to improve efficiency, one could wrap all the common data in a `struct`, compute it once and provide to them as an argument. However, this design has several flaws. For example, this would cause a change in the signature of `Function`, which can result in unnecessary arguments being passed to some function implementations. Moreover, these common and internal data are no longer hidden from other components in the code, which can harm code simplicity. I would like to discuss the following optimization strategy: implement a class `CacheFG` that: - Define a `Update` method that calculates its internal data with a given pair of doubles `x` and `y`; and - Define a `Check` method to determine if its current internal data was calculated with a given pair of doubles `x` and `y`. What one could do then is to make `f` and `g` to share a common instance of the class `CacheFG`, which could be done using the `std::shared_ptr` construct. So, below would be the creation of `f` and `g` functions using auxiliary functions `f_aux` and `g_aux`. ``` double f_aux(double x, double y, const std::shared_ptr<CacheFG>& cache) { if(not cache->Check(x,y)) cache->Update(x,y); ... } std::shared_ptr<CacheFG> cache; Function f = std::bind(f_aux, _1, _2, cache); Function g = std::bind(g_aux, _1, _2, cache); ``` My questions are: (1) is this a safe approach for optimization? (2) is there a better approach for solving this problem? Edit: After a few answers, I found out that my intention here is to implement a memoization technique in C++. I remark that only the last calculated state is enough for my purposes. Thanks to DeadMG, I will now write here just an improvement over his approach. His idea consists of using a memoization technique with variadic templates. I just offer a slight modification, where I use the construct `std::decay<Args>::type` to ensure the definition of a `tuple` with non-reference types only. Otherwise, functions with const-reference arguments would cause compilation errors. ``` template<typename Ret, typename... Args> std::function<Ret(Args...)> MemoizeLast(std::function<Ret(Args...)> f) { std::tuple<typename std::decay<Args>::type...> cache; Ret result = Ret(); return [=](Args... args) mutable -> Ret { if(std::tie(args...) == cache) return Ret(result); cache = std::make_tuple(args...); return result = f(args...); }; } ``` In order to prevent the move of `result`, a copy of it is returned (`return Ret(result)`) when the provided `args` is the one cached.

Original source