Dynamic cache

A static cache that can only grow has only a limited use. We could, for example, use it to store RTTI properties of types, as access to the RTTI is relatively slow. In most cases, however, a limited-size cache that stores only N most recently used values is more appropriate.

Writing such a cache is quite a tricky operation. First and foremost, we need quick access to a value associated with a specific input (let's call that input a key). In Chapter 1, About Performance, we found out that the best way to do that is a hash table (or, in Delphi terms, TDictionary), which has O(1) lookup time.

So that's solved, our cache will store data in a dictionary. But we also have to remove the values from the dictionary (as this cache has a limited size) and there lies the big problem!

When a cache is full (when it reaches some pre-set size) we would like to remove the oldest element from the cache. We could, for example, replace the value part of the dictionary with a pair (date/time, value) where date/time would contain the last modification time of this key, but finding the oldest key in the cache then becomes an O(n) operation (in the worst case we have to scan all (date/time, value) pairs) which is something that we would like to avoid.

Another alternative would be a sorted list of all keys. When we need to update a key, we can find it with O(log n) steps and insert it at the beginning in O(1) steps (but this is an expensive step as it needs to move other elements around in memory). To get the oldest element, we can just check the last element in the list (very fast O(1)). However, we can do even better than that.

Let's look again at the requirements. We need a data structure that satisfies the following criteria:

• Data is kept in modification order. In other words, when you insert an item into the structure, that item becomes the first element in the structure.

• When you update an item, it moves to the front (it becomes the first element).

Whenever you need a data structure with these conditions, the answer is always a doubly-linked list. This is a list of items where each item contains some value, plus two pointers - one pointing to the previous element and one to the next one. The first element doesn't have a predecessor and the last element doesn't have a successor. These two links point to a special value (for example, nil).

A doubly-linked list

Removing an element from such a list is very fast. You just have to change a few pointers. The same goes for insertion into such a list.

I have implemented a very fast cache, TDHPCache<K,V>, based around a hash table and doubly-linked list. You can find it in the DHPCache unit, together with a simple test app, CacheDemo.

TDHPCache is a generic cache class with two type parameters—the key K and value V. Its public interface implements only a few functions:

TDHPCache<K,V> = class
public
  constructor Create(ANumElements: Integer; AOwnsValues: boolean = false);
  destructor Destroy; override;
  function TryGetValue(const key: K; var value: V): boolean;
  procedure Update(const key: K; const value: V);
end;

The Create constructor creates a cache with the specified maximum size. The cache can optionally own values that you insert into the cache, which allows you to cache objects.

The TryGetValue function tries to retrieve a value associated with the specified key. Success or failure is indicated through the Boolean result.

The Update procedure stores the value in the cache and associates it with the specified key. It also makes sure that the key is now first in the list of most recently used keys. 

Internally, all keys and values are stored in a doubly-linked list. As we know the maximum size of this list (ANumElements parameter passed to the constructor), we can create it as a simple array of elements of (internal) type TListElement:

strict private type
  TListElement = record
    Next : Integer;
    Prev : Integer;
    Key : K;
    Value: V;
  end;
var
  FCache : TDictionary<K,Integer>;
  FKeys : TArray<TListElement>;
  FFreeList : Integer;
  FHead : Integer;
  FTail : Integer;

This list is not using Delphi pointers to link elements. Instead, each Next and Prev field simply contains an index into the FKeys array or -1 if there is no next/previous item. (-1 in this case corresponds to a nil pointer.)

Two lists are actually stored in this array. One element is always in exactly one of those two lists, so parallel storage is not a problem.

The first list contains all unused items. The FFreeList field points to the first element in this list. When a TDHPCache class is created, the BuildLinkedList method (not shown here) adds all elements of FKeys to this list.

The second list contains all used (cached) items. The FHead field points to the first (most recently modified) element in this list and the FTail field points to the last (oldest) element in this list. At the beginning, this list is empty and both FHead and FTail contain -1.

The cache also uses a FCache dictionary, which maps keys into array indexes.

To retrieve a value, TryGetValue calls FCache.TryGetValue to get the array index associated with the key. If that function returns True, the associated value is read from the FKeys array. Both operations execute in O(1) time, which makes the whole function O(1):

function TDHPCache<K, V>.TryGetValue(const key: K; var value: V): boolean;
var
  element: Integer;
begin
  Result := FCache.TryGetValue(key, element);
  if Result then
    value := FKeys[element].Value;
end;

Updating a value is a bit more complicated. The function first tries to find the key in the cache. If found, the value in the FKeys is updated. Both operations are O(1).

The code looks a bit more complicated because it must handle destruction of the old value when the cache owns its values:

procedure TDHPCache<K, V>.UpdateElement(element: Integer; const key: K; const value: V);
var
  oldValue: V;
begin
  if not FOwnsValues then
    FKeys[element].Value := value
  else
  begin
    oldValue := FKeys[element].Value;
    if PObject(@value)^ <> PObject(@oldValue)^ then
    begin
      FKeys[element].Value := value;
      PObject(@oldValue)^.DisposeOf;
    end;
  end;
  MoveToFront(element);
end;

procedure TDHPCache<K, V>.Update(const key: K; const value: V);
var
  element: Integer;
begin
  if FCache.TryGetValue(key, element) then
    UpdateElement(element, key, value)
  else
    AddElement(key, value);
end;

The AddElement gets executed when a new (key, value) pair is added to the cache. First it checks whether the list is full. This can be done simply by checking the FFreeList pointer—if it points to an array element, the list is not yet full. Then the code either removes the oldest element from the list (discussed in the following) or allocates a new element from the free list. The latter is done by moving a few pointers around in O(1) time.

Next, a new element is inserted at the beginning of the list. Again, just a few pointers are moved and the code runs in O(1).

Finally, key and value are updated and (key, index) mapping is inserted into the dictionary, which is again an O(1) operation:

procedure TDHPCache<K, V>.AddElement(const key: K; const value: V);
var
  element: integer;
begin
  if IsFull then
    element := RemoveOldest
  else
    element := GetFree;
  InsertInFront(element);
  FKeys[element].Key := key;
  FKeys[element].Value := value;
  FCache.Add(key, element);
end;

The only unsolved part is the RemoveOldest function. It will firstly remove the last element from the list (Unlink(FTail)), which is a simple O(1) operation. Then it will remove the (key, index) mapping from the cache (O(1)) and destroy the old value if the cache owns its values:

function TDHPCache<K, V>.RemoveOldest: Integer;
var
  element: Integer;
begin
  if FTail < 0 then
    raise Exception.Create('TDHPCache<K, V>.RemoveOldest: List is empty!');
  Result := FTail;
  Unlink(FTail);
  FCache.Remove(FKeys[Result].Key);
  if FOwnsValues then
    PObject(@FKeys[Result].Value)^.DisposeOf;
end;

As you can see, we have created a data structure which can insert, update, delete (when it is full), and retrieve elements all in O(1). In Chapter 1, About Performance, however, I stated that there is always a trade-off and that not all operations can be fast in one data structure. What is going on here?

The answer is that we are gaining speed by duplicating the data, namely the keys. Each key is stored twice—once in the doubly—linked list and once in the dictionary. If you remove one copy of this key, some operations will slow down.