Approaches for caching calculated values

Question

In a Delphi application we are working on we have a big structure of related objects. Some of the properties of these objects have values which are calculated at runtime and I am looking for a way to cache the results for the more intensive calculations. An approach which I use is saving the value in a private member the first time it is calculated. Here's a short example:

unit Unit1;

interface

type
  TMyObject = class
  private
    FObject1, FObject2: TMyOtherObject;
    FMyCalculatedValue: Integer;
      function GetMyCalculatedValue: Integer;
  public
    property MyCalculatedValue: Integer read GetMyCalculatedValue;
  end;

implementation

  function TMyObject.GetMyCalculatedValue: Integer;
  begin
    if FMyCalculatedValue = 0 then
    begin
      FMyCalculatedValue :=
        FObject1.OtherCalculatedValue + // This is also calculated
        FObject2.OtherValue;
    end;

    Result := FMyCalculatedValue;
  end;

end.

It is not uncommon that the objects used for the calculation change and the cached value should be reset and recalculated. So far we addressed this issue by using the observer pattern: objects implement an OnChange event so that others can subscribe, get notified when they change and reset cached values. This approach works but has some downsides:

• It takes a lot of memory to manage subscriptions.
• It doesn't scale well when a cached value depends on lots of objects (a list for example).
• The dependency is not very specific (even if a cache value depends only on one property it will be reset also when other properties change).
• Managing subscriptions impacts the overall performance and is hard to maintain (objects are deleted, moved, ...).
• It is not clear how to deal with calculations depending on other calculated values.

And finally the question: can you suggest other approaches for implementing cached calculated values?

Answer 1

If you want to avoid the Observer Pattern, you might try to use a hashing approach.

The idea would be that you 'hash' the arguments, and check if this match the 'hash' for which the state is saved. If it does not, then you recompute (and thus save the new hash as key).

I know I make it sound like I just thought about it, but in fact it is used by well-known softwares.

For example, SCons (Makefile alternative) does it to check if the target needs to be re-built preferably to a timestamp approach.

We have used SCons for over a year now, and we never detected any problem of target that was not rebuilt, so their hash works well!