Tuesday, January 29, 2019

Caching with class variables

Recently I was extending a swiss-army-knife helper record we are using at work and I noticed a small piece of suboptimal code. At first I let it be as I couldn’t think of a simple way of improving the code – and the problem was really not so big that it should be fixed with a complicated solution. At some point, however, a simple and elegant solution appeared to me and I like it so much that I want to share it with the world ;)

Instead of showing our helper record in full, I have extracted just a small part of functionality, enough to do a simple demo. The Check method takes an integer, makes sure that it can be cast into an enumerated type or set T and returns the cast type:

type
  Range<T> = record
  private
    class function MaxIntVal: Integer; static; inline;
    class function MinIntVal: Integer; static; inline;
  public
    class function Check(const value: Integer): T; static;
  end;

class function Range<T>.Check(const value: Integer): T;
begin
  if (value < MinIntVal) or (value > MaxIntVal) then
    raise Exception.CreateFmt(
      'Value %d lies outside allowed range for %s (%d .. %d)',
      [value, PTypeInfo(TypeInfo(T)).Name, MinIntVal, MaxIntVal]);
  Move(value, Result, SizeOf(Result));
end;
Calling Range<TEnum>(i) works the same as executing TEnum(i) with an added bonus of checking for under- and overflows. The following code fragment shows how this function could be used:

type
  TEnum = (en1, en2, en3);
  TEnumSet = set of TEnum;

var
  en: TEnum;
  ens: TEnumSet;

en := Range<TEnum>.Check(2); // OK, en = en3
en := Range<TEnum>.Check(3); // exception

ens := Range<TEnumSet>.Check(0); // OK, ens = []
ens := Range<TEnumSet>.Check(8); // exception
The Check function uses following two helper functions to determine lowest and highest possible value for type T:

class function Range<T>.MaxIntVal: Integer;
var
  ti: PTypeInfo;
  typeData: PTypeData;
  isSet: Boolean;
  i: Integer;
begin
  ti := TypeInfo(T);
  isSet := ti.Kind = tkSet;
  if isSet then
    ti := GetTypeData(ti).CompType^;
  typeData := GetTypeData(ti);
  if isSet then
  begin
    Result := 0;
    for i := typeData.MinValue to typeData.MaxValue do
      Result := Result or (1 shl i);
  end
  else
    Result := typeData.MaxValue;
end;

class function Range<T>.MinIntVal: Integer;
var
  ti: PTypeInfo;
  typeData: PTypeData;
begin
  ti := TypeInfo(T);
  if ti.Kind = tkSet then
    ti := GetTypeData(ti).CompType^;
  typeData := GetTypeData(ti);
  Result:= typeData.MinValue;
end;
The suboptimal behaviour comes from the fact that MinIntVal and MaxIntVal are calculated each time Check is called. As type T doesn’t change while the program is being executed, it would suffice to call these two functions once and cache the result. The problem with this solution, however, is twofold. Firstly, this cache would have to exist somewhere. Some part of code would have to manage it. Secondly, it would have to be quite fast. MinIntVal and MaxIntVal, as implemented now, are not very slow and looking up that data in a cache could easily be slower than the current code.
As it turns out, we can fix both problems simply by using class variables, properties, and methods functionality of the Delphi language:

type
  TypeInfoCache<T> = class
  class var
    FMinIntVal: Integer;
    FMaxIntVal: Integer;
  public
    class constructor Create;
    class property MaxIntVal: Integer read FMaxIntVal;
    class property MinIntVal: Integer read FMinIntVal;
  end;

class constructor TypeInfoCache<T>.Create;
var
  ti: PTypeInfo;
  typeData: PTypeData;
  isSet: Boolean;
  i: Integer;
begin
  ti := TypeInfo(T);
  isSet := ti.Kind = tkSet;
  if isSet then
    ti := GetTypeData(ti).CompType^;
  typeData := GetTypeData(ti);
  FMinIntVal := typeData.MinValue;

  if isSet then
  begin
    FMaxIntVal := 0;
    for i := typeData.MinValue to typeData.MaxValue do
      FMaxIntVal := FMaxIntVal or (1 shl i);
  end
  else
    FMaxIntVal := typeData.MaxValue;
end;
A class constructor is called only once for each type T used in the code. It is also called automatically and we don’t have to take care of that. Moving the code that calculates min/max values for a type T into a class constructor therefore solves the first problem. To make sure that class part of the TypeInfoCache<T> was created, we merely have to access it, nothing more. The code in Range<T> can be replaced with simple one-liners:

class function Range<T>.MaxIntVal: Integer;
begin
  Result := TypeInfoCache<T>.MaxIntVal;
end;

class function Range<T>.MinIntVal: Integer;
begin
  Result := TypeInfoCache<T>.MinIntVal;
end;
This also solves the second problem, as the access to a class variables doesn’t require any complications usually associated with a dictionary access. Accessing MinIntVal, for example, is a simple call into method that executes few mov instructions.
A demonstration project for this new improved solution is available here.
This approach is very limited in use – it can only be used to associate data with a type T – but neatly illustrates the power of the Delphi language.




5 comments:

  1. Indeed, nice.

    Kind of a trend in modern languages to have a pair of class + singular object with the same name.

    That perhaps can be used instead of "non-inheritable class variables" that are typically used by hijacking VMT

    ReplyDelete
  2. > raise Exception.CreateFmt

    why not standard ERangeError ?

    ReplyDelete
    Replies
    1. Whatever. Definitely not the point of this exercise.

      Delete
  3. Nice idea to have some kind of type traits class that gets initialized by a class constructor.

    ReplyDelete
  4. Thanks for sharing! I can get the point (the caching part), however, I'm having difficulty understanding the part that calculates the max value for a set - especially the use of `shl`, anyone care to explain a little bit :)
    `
    if isSet then
    begin
    FMaxIntVal := 0;
    for i := typeData.MinValue to typeData.MaxValue do
    FMaxIntVal := FMaxIntVal or (1 shl i);
    end
    `

    ReplyDelete