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

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;
    }
    // ...
};

Answer 2

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 3

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 4

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 5

"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 6

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 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.
}