Caching expensive data in C++ - function-scoped statics vs mutable member variables

Question

Hi,

I've got a relatively expensive data-fetching operation that I want to cache the results of. This operation is called from const methods, roughly like this:

double AdjustData(double d, int key) const {
  double factor = LongRunningOperationToFetchFactor(key);
  return factor * d;
}

I'd like AdjustData to remain const, but I want to cache out the factor so I only fetch it the first time. At present I'm using a mutable map<int, double> to store the result (the map being from key to factor), but I'm thinking using a function-scoped static might be a better solution - this factor is only needed by this function, and is irrelevant to the rest of the class.

Does that seem like a good way to go? Are there any better options? What things might I think about, particularly with regard to thread-safety.

Thanks,

Dom

Answer 1

Unless I don't understand, it seems obvious to me that you want to make this a static:

double AdjustData(double d) const {
   static const double kAdjustFactor = LongRunningOperationToFetchFactor();
   return kAdjustFactor * d;
}

That way you only fetch the factor once.

Answer 2

You can use the singleton pattern(1) to with a class that performs the long-running operation and caches the result. This instance could then be used in const member functions of other classes. Consider mutual exclusion to protect inserts and extractions from the map data structure for thread safety. If multi-threaded performance is a huge issue, then you can flag keys as in progress to prevent multiple threads from calculating the same key simultaneously.

#include <cstdlib>
#include <iostream>
#include <map>

using namespace std;

class FactorMaker {
    map<int, double> cache;

    double longRunningFetch(int key)
    {
        const double factor = static_cast<double> (rand()) / RAND_MAX;
        cout << "calculating factor for key " << key << endl;
        // lock
        cache.insert(make_pair(key, factor));
        // unlock
        return factor;
    }

public:
    double getFactor(int key) {
        // lock
        map<int, double>::iterator it = cache.find(key);
        // unlock
        return (cache.end() == it) ? longRunningFetch(key) : it->second;
    }
};

FactorMaker & getFactorMaker()
{
    static FactorMaker instance;
    return instance;
}

class UsesFactors {
public:
    UsesFactors() {}

    void printFactor(int key) const
    {
        cout << getFactorMaker().getFactor(key) << endl;
    }
};

int main(int argc, char *argv[])
{
    const UsesFactors obj;

    for (int i = 0; i < 10; ++i)
        obj.printFactor(i);

    for (int i = 0; i < 10; ++i)
        obj.printFactor(i);

    return EXIT_SUCCESS;
}

(1) The singleton pattern can be grossly missed. So, please refrain from going crazy with it if you are seeing it for the first time.

Answer 3

I would wrap the implementation of LongRunningOperationToFetchFactor with something like this. I am using Boost scoped locks but you can so something similar with other locking frameworks.

#include <boost/thread/thread.hpp>
#include <boost/thread/mutex.hpp>
#include <map>

using namespace std;

static boost::mutex myMutex;
static map<int,double> results;

double CachedLongRunningOperationToFetchFactor( int key )
{

   {
       boost::mutex::scoped_lock lock(myMutex);

       map<int,double>::iterator iter = results.find(key);
       if ( iter != results.end() )
       {
          return (*iter).second;
       }
   }
   // not in the Cache calculate it
   result = LongRunningOperationToFetchFactor( key );
   {
       // we need to lock the map again
       boost::mutex::scoped_lock lock(myMutex);
       // it could be that another thread already calculated the result but
       // map assignment does not care.
       results[key] = result;
   }
   return result;
}

If this really is a long running operation then the cost of locking the Mutex should be minimal.

It was not quite clear from you question but if the function LongRunningOperationToFetchFactor is a member function of you class then you want the map the be mutable map in that same class. I single static mutex for access is still fast enough though.

Answer 4

I would not make this cache a local static. The mutable map is the solution for caching results. Otherwise it will make your function useless, as different objects of your class will share the same cache, as the local static cache is the same for all objects. You can use the local static if the result does not depend on the object though. But then i would ask myself why the function is a non-static member of your object, if it does not need to access any state of it.

As you say it should be thread-safe - if different threads can call the member function on the same object, you probably want to use a mutex. boost::thread is a good library to use.