Cached or precomputed Immutable Functions in C# / C++

Question

By "immutable function" or "immutable method", I mean a function whose result will never vary if you give it the same arguments.

I would be interested to know if anyone know of a more generic or less verbose solution when you want to cache the precomputed value(s) of an immutable function.

Let me explain what I mean with a simple example:

//Let's assume that ComputeStuff() returns a widely used value 
//and that 
//1. It is immutable (it will always return the same result)
//2. its performance is critical, and it cannot be accepted to compute
//   the result at each call, because the computation is too slow
//I show here a way to solve the problem, based on a cached result.
//(this example works in a case of a method with no arguments. 
// A hash would be required in order to store multiple precomputed results 
//depending upon the arguments)
private string mComputeStuff_Cached = null;
public string ComputeStuff()
{
  if (mComputeStuff_Cached != null)
    return mComputeStuff_Cached ;

  string result;
  //
  // ...
  //Do lots of cpu intensive computation in order to compute "result" 
  //or whatever you want to compute
  //(for example the hash of a long file)
  //...
  //

  mComputeStuff_Cached  = result;
  return mComputeStuff_Cached ;
}

Notes:
- I added the tag C++ as a solution in C++ would also interest me
- The concept of "immutable functions" is common for database developers, since a function can be defined as "immutable", or "immutable within a transaction" (this is a good way to improve the performance of the queries).

Thanks in advance

Answer 1

"Memoization" may be a useful term, here. There are a few memoization libraries out there (I could swear there was one in boost, but I can't find it at the moment). Doing a web search for "memoize" or "memoization" and your language of choice will reveal a few hits.

Here's a neat article in Wikibooks: Optimizing C++/General optimization techniques/Memoization

Answer 2

Well, using a delegate such as Func<T> can make it more re-usable without requiring polymorphism / inheritance - but there is nothing more "inbuilt" in C#:

using System;
static class Program {
    static void Main() {
        var func = CachedFunc.Create(() => int.Parse(Console.ReadLine()));

        Console.WriteLine(func.Value);
        Console.WriteLine(func.Value);
    }
}
static class CachedFunc {
    public static CachedFunc<T> Create<T>(Func<T> func) {
        return new CachedFunc<T>(func);
    }
}
class CachedFunc<T> {
    T value;
    Func<T> func;
    public CachedFunc(Func<T> func){
        if (func == null) throw new ArgumentNullException("func");
        this.func = func;
    }
    public T Value {
        get {
            if (func != null) {
                value = func();
                func = null;
            }
            return value;
        }
    }
    public static explicit operator T(CachedFunc<T> func) {
        return func.Value; }
}

Answer 3

you could try something like this:

#include <functional>
#include <type_traits>
#include <map>
#include <tuple>

//requires c++14
auto add_function_cache = [](auto fun) {
    using fun_type = decltype(fun);
    return ([=](auto... run_args){
        using fun_return_type = std::result_of_t<fun_type(decltype(run_args)...)>;
        static std::map<
            std::tuple<decltype(run_args)...>,
            fun_return_type
        > result_cache;
        std::tuple<decltype(run_args)...> tuple(run_args...);
        if (result_cache.find(tuple) == result_cache.end()) {
            fun_return_type rv = fun(run_args...);
            result_cache[tuple] = rv; 
            return rv; 
        }   
        else {
            return result_cache[tuple];
        }   
    }); 
};

template <typename R, class... Args> auto
add_function_cache_old(std::function<R(Args...)> fun)
-> std::function<R(Args...)>
{
    std::map<std::tuple<Args...>, R> cache;
    return [=](Args... args) mutable  {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end()) {
            R rv = fun(args...);
            cache[t] = rv; 
            return rv; 
        }   
        else {
            return cache[t];
        }   
    };  
};

And then use it as follows:

//function_cache - usage
auto fib_cache = add_function_cache(&fib);

//function_cache_old - usage
function<decltype(fib)> fib_fn = &fib;
auto fib_cache_old = add_function_cache_old(fib_fn);

fib_cache(10);
fib_cache(10);

The idea is to create a function that takes a function (fun) as argument and returns another function. The returned function wraps fun and provides a map form input parameters (run_args) to results. So it has the same signature as fun, tires to find the result for given parameters (run_args) in the map (cache). Then it returns the cached value or the result calculated by fun. Obviously fun's result has to be added to the cache in case of an unsuccessful look-up.

Regards

Jan

Answer 4

You can make it slightly less verbose:

private string mComputeStuff_Cached = null;
public string ComputeStuff()
{
  if (mComputeStuff_Cached == null) {
    string result;
    //
    // ...
    //Do lots of cpu intensive computation in order to compute "result" 
    //or whatever you want to compute
    //(for example the hash of a long file)
    //...
    //

    mComputeStuff_Cached  = result;
  }

  return mComputeStuff_Cached ;
}

Other notes on this type of pattern:

• If you use C++, and such a method const, then modifying members will not be possible because they are also treated as const within the context of that method. However, you can override this by marking the member(s) you need to modify as mutable.
• There is a difference between "semantic const" and "bitwise const". When an author marks something as const, they usually mean "semantic const" (which is what you mean in this case), but the compiler can only enforce "bitwise const".
• const methods usually give the caller the impression that they can be called from multiple threads simultaneously, because they have no side effects. In this type of pattern you have a "bitwise" side effect, but no "semantic" side effect. Therefore if it is possible that multiple threads could call such a method you must internally protect this initialization.

Answer 5

You can make your member variable mutable (keyword).

This will allow a const member function modify this value. I use it all the time to cache intermediate results.

Answer 6

You can rewrite this code almost verbatim in C++

class CClass
{

  private:
     std::string* mComputeStuff_Cached;

  public:
     CClass()
       mComputeStuff_Cached(NULL)
     {

     }

     ~CClass()
     {
           delete mComputeStuff_Cached;
     }


     std::string ComputeStuff()
     {
         if (mComputeStuff_Cached != NULL)
         {
             return mComputeStuff_Cached
         }
         else
         {
             std::string calcedAnswer;
             ...
             // store away answer
             mComputeStuff_Cached = new std::string(calcedAnswer);
         }
     }
};

I'm not sure if a check to see if mComputeStuff_Cached is empty() is sufficient. It could be that empty() is a legitimately cached result.

Answer 7

You could use the static keyword inside the function. It will be computed only once:

std::string GetWidelyUsedValue()
{
   static std::string value = ComputeStuff() ;
   return value ;
}

std::string ComputeStuff()
{
   // Compute the string here.
}

Answer 8

A C++ solution would be very similar to what you have outlined, differing only in the heady mix of const qualified public interface(s) and (some) mutable members:

class Computer {
    mutable string cache;
  public:
    // I wouldn't call it ComputeXXX
    // since I want to hide the implementation
    // details from my client: for the client
    // there is no change in state due to a call
    // to this function
    const string& StringVal() const {
         if (cache.empty()) {
                // compute cache
         }
         return cache;
    }
    // ...
};