CODEWITHSUNDEEP
c++optimizationc++11polymorphismshared-ptr
A.L.
A.L.

Reputation: 1201

Cache Optimization and Polymorphism

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:

  1. Define a Update method that calculates its internal data with a given pair of doubles x and y; and
  2. 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.

Upvotes: 3

Views: 294

Answers (2)

Puppy
Puppy

Reputation: 146930

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.

Upvotes: 6

Denis Ermolin
Denis Ermolin

Reputation: 5546

Before optimizing - measure. Then if you really perform many calculations with same value - then create this cache object. I'd like to hide cache checking and updating in CacheFG::get(x, y) and use it like const auto value = cache->get(x,y).

Upvotes: 2

Related Questions