How can I share expensive computations among classes?

Question

As an example, I have this case, in which the classes A and B perform the same expensive calculation, the function expensiveFunction. This function is "pure", in that I can guarantee that it will give the same result given the same input. The client may use both classes (or more similar classes) with the same input, and I would wish that the expensensive function is only calculated once. However, the client may also only use one class for a given input.

Code example:

class A {
public:
    A(const InputData& input) {
        res = expensiveFunction(input);
    }
    void foo(); //Use the expensive result
private:
    ExpensiveResult res;
};

class B {
public:
    B(const InputData& input) {
        res = expensiveFunction(input); //Same function as in A
    }
    double bar(); //Use the expensive result
private:
    ExpensiveResult res;
};

int main() {
    //Get some input
    //...
    A a(input);
    B b(input);

    //Do stuff with a and b

    //More input

    A a2(otherInput);
    //...
}

In some languages, due to referential transparency and memoization, it can safely compute it only once for a given input.

What I have thought of is using some sort factory method/class, or give a function object/functor/supension to the A and B classes that stores the result.

What are some good design ideas to solve this problem?

I own all of the code, so I can change the client or the service classes if necessary.

I would define a class that would be super to A and B, and contain `res` and the `expensiveFunction`. Then I would add a cache mechanism based on whatever you can use to identify the input. — njzk2, Sep 29 '14 at 14:23
You could also define a separated function in a class that would handle the cache for you. — njzk2, Sep 29 '14 at 14:24
This is a good idea, but I don't think the input is easily identifiable. In my case, it is a huge `std::vector` of 3D points. — Sebastian Mendez, Sep 29 '14 at 14:25
Maybe I could tag the input vector with a unique string to identify and do the caching. — Sebastian Mendez, Sep 29 '14 at 14:26
You say `with the same input [...] is only calculated once`. That implies that you must find a way to assert the notion of `same input`. It can be literally the same (same pointer) (although the content may have changed), or some sort of other verification. It mostly needs to be faster than `expensiveFunction`. — njzk2, Sep 29 '14 at 14:27
I think, the question is, why do you want to handle the function for the client and not just expose the function as no-friend no-member function? If the function is ultimately a pure function just leave to the client the duty to call it efficiently. — Alessandro Teruzzi, Sep 29 '14 at 16:03
@AlessandroTeruzzi we had it like that in an earlier version, but the requirements changed, and we should also be able to fetch pre-computed results from a database, so we thought it would be better to encapsulate the exact way of calculating it and hide it from the client. — Sebastian Mendez, Sep 29 '14 at 17:26
@AlessandroTeruzzi there are also other "groups" of classes, say classes `C`, `D`, and `E` that use `anotherExpensiveFunction`, and thought it would be overwhelming to expose all of the functions to the client. — Sebastian Mendez, Sep 29 '14 at 17:28

Nikita · Accepted Answer · 2014-09-29T15:01:49.413

2

You can memoize just inside of your function

COutput expensive(CInput input) {
    static std::map<CInput, COutput> memoized_result;
    auto resit = memoized_result.find(input);
    if (resit == memoized_result.end()) {
        // ... do calculations
        output = expensiveCalculation(input);
        resit = memoized_result.insert(std::make_pair(input, output));
    }
    return resit->second;
}

The result of your computation is stored in the static map (memoized_result), and persisted between function calls.

If input is too expensive to use as a key in the map, you can create a separate class for handling computation result, and share it between all clients:

#include <memory>
using namespace std;
class ExpensiveResult {
    public:
    ExpensiveResult(int input) {
        out_ = input+1;
    }
    int out_;
};

class BaseCompResultUser {
public:
    BaseCompResultUser(const std::shared_ptr<ExpensiveResult>& res) {
        res_ = res;
    }

private:
    std::shared_ptr<ExpensiveResult> res_;
};

class A : public BaseCompResultUser {
public:
    A(const std::shared_ptr<ExpensiveResult>& r) : BaseCompResultUser(r) { }
};

class B : public BaseCompResultUser {
public:
    B(const std::shared_ptr<ExpensiveResult>& r) : BaseCompResultUser(r) { }
};

int main() {
    std::shared_ptr<ExpensiveResult> res(new ExpensiveResult(1));
    A a(res);
    B b(res);
    return 0;
}

This will force sharing computation result between objects.

edited Sep 29 '14 at 15:01

answered Sep 29 '14 at 14:27

Nikita

950
8
19

the whole problem, IIUC, is to implement `memoized_result.find` – njzk2 Sep 29 '14 at 14:29
It is a function of a standard container – Nikita Sep 29 '14 at 14:29
yes, but how does it work? How does it recognize that 2 `std::vector` are the same? (especially since it is a mutable type and since 2 different instances can contain the same data and therefore should probably be considered equal) – njzk2 Sep 29 '14 at 14:32
Yes, as njzk2 says, the problem is that the input is a large and complex data structure (in this case a `std::vector`). Comparing a large vector to many others for equality could potentially be very expensive, couldn't it? – Sebastian Mendez Sep 29 '14 at 14:36
If you're using std::vector, then std::map will use operator< and operator> to compare keys. – Nikita Sep 29 '14 at 14:37
@njzk2: If by mutable you mean non-const, I edited the question to reflect that they are indeed non-mutable. – Sebastian Mendez Sep 29 '14 at 14:37
1

@nikitoz: Just `operator<`, actually. Of course if you have a faster way to compare inputs (e.g. by comparing some tag), you can implement your own less-than comparator and pass that as a template argument to `std::map`. (Alternatively, you can implement your own `operator==` and `std::hash` and use `std::unordered_map`. Hash tables rock.) Overall this is a good approach; +1 – Nemo Sep 29 '14 at 14:52

score 1 · Answer 2 · answered Sep 29 '14 at 15:01

1

I think that the object-oriented way of solving it is for the expensiveFunction to be a member function of InputData (or some wrapper of InputData) and then your problem pretty much goes away. You just make ExpensiveResult a mutable cache in InputData:

class InputData {
 private:
  mutable std::shared_ptr<ExpensiveResult> result_;
 public:
  InputData() : result_(nullptr) {}

  std::shared_ptr<ExpensiveResult> expensiveFunction() const {

    if (!result_) {
      // calculate expensive result...
      result_ = std::make_shared<ExpensiveResult>();
    }
    return result_;
  }
};

The expensive calculation is only done the first time expensiveFunction is called. You might have to add some locking if this is being called in a multi-threaded way.

answered Sep 29 '14 at 15:01

Chris Drew

14,926
3
34
54

If the `InputData` instances are created independently, and the goal is to memoize and share the result when two of them happen to wind up equal, then this approach will not work. The most general approach would be to create a templated Memoizer class that you can wrap around any function... – Nemo Sep 29 '14 at 15:03
I think this is the best solution to the listed problem. The result is tied to the input, so store it with the input - and since the question only cares about sharing between classes that are created in the same scope (main), don't expand the scope of the cache beyond this, which would introduce all the new problems and complexities associated with static data and mapping. – ajclinto Sep 29 '14 at 15:11
@Nemo True. It wasn't quite clear from the question if that was the goal. If that's confirmed, I'll delete my answer. – Chris Drew Sep 29 '14 at 15:12
@ajclinto: Static variables are not required, and a generic "memoizer" class is actually pretty straightforward. See http://stackoverflow.com/q/17805969/ – Nemo Sep 29 '14 at 15:47

score 1 · Answer 3 · answered Sep 29 '14 at 15:07

1

If ExpensiveFunction does the same thing in A and B, it hardly seems like a true member of either. Why not a function?

int main() {
//Get some input
//...
res = expensiveFunction (input) ;
A a(res);
B b(res);

//Do stuff with a and b

//...
}

answered Sep 29 '14 at 15:07

user3344003

20,574
3
26
62

I don't think there is any evidence that `expensiveFunction` is a member of `A` or `B`. But you are right that there is nothing to stop you calculating the expensive result first. – Chris Drew Sep 29 '14 at 15:10

How can I share expensive computations among classes?

3 Answers3