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!

Answer 2

In my work I use Bold for Delphi that can manage unlimited complex structures of cached values depending on each other. Usually each variable only holds a small part of the problem. In this framework that is called derived attributes. Derived because the value is not saved in the database, It just depends on on other derived attributes or persistant attributes in the database.

The code behind such attribute is written in Delphi as a procedure or in OCL (Object Constraint Language) in the model. If you write it as Delphi code you have to subscribe to the depending variables. So if attribute C depends on A and B then whenever A or B changes the code for recalc C is called automatically when C is read. So the first time C is read A and B is also read (maybe from the database). As long as A and B is not changed you can read C and got very fast performance. For complex calculations this can save quite a lot of CPU-time.

The downside and bad news is that Bold is not offically supported anymore and you cannot buy it either. I suppose you can get if you ask enough people, but I don't know where you can download it. Around 2005-2006 it was downloadable for free from Borland but not anymore. It is not ready for D2009 as someone have to port it to Unicode.

Another option is ECO with dot.net from Capable Objects. ECO is a plugin in Visual Studio. It is a supported framwork that have the same idea and author as Bold for Delphi. Many things are also improved, for example databinding is used for the GUI-components. Both Bold and ECO use a model as a central point with classes, attributes and links. Those can be persisted in a database or a xml-file. With the free version of ECO the model can have max 12 classes, but as I remember there is no other limits.

Bold and ECO contains lot more than derived attributes that makes you more productive and allow you to think on the problem instead of technical details of database or in your case how to cache values. You are welcome with more questions about those frameworks!

Edit: There is actually a download link for Embarcadero registred users for Bold for Delphi for D7, quite old... I know there was updates for D2005, ad D2006.