Patterns · Tips & Tricks · Uncategorized

Mapping Delphi Types to Indices at Compile Time

Say what now? In this post I will show you how you can use generics and class variables to generate unique incrementing indices for any Delphi type. For example, the Integer type could map to index 1 and the TStream type to index 2 etc. The values of these indices will be determined (partially) at compile time.

Use Cases

But why would you need something like this? Granted, the number of use cases may be limited, but there are some useful ones. You can use this technique any time you need to associate some information with a particular Delphi type in a fast and memory efficient way.

For example, a while ago I played around with creating an Entity Component System library for Delphi.

In case you are unfamiliar with Entity Components Systems, here is a highly simplified (and not very accurate) description: An ECS is a programming paradigm where Entities are kinda like classes, Components are kinda like properties and Systems are like a bunch of methods. But without classes, properties and methods, and optimized for performance.
Confused or intrigued? Let me know if you want to know more.

The implementation requires that I keep track of which components are associated with which entities. A component is just a particular Delphi type in this case. There can be many, many entities and each entity can have any combination of components associated with it. The library needs to be able to quickly check if an entity supports a particular component.

A “traditional” approach to do this would be for each entity to maintain a dictionary that maps a component type to a Boolean that indicates whether the entity supports the component or not. For example, this could be a TDictionary<PTypeInfo, Boolean>, where the key is the type information for a component.

However, if you have lots of entities, each with its own dictionary, then this approach can be slow and use quite a bit of memory. Even though dictionaries are generally fast because they are based on hash tables, querying dictionaries thousands of times per second (which is not uncommon for an ECS) can have a considerable impact.

But what if each component type you care about has a simple index, starting at 0 and incrementing for each component type in use. Then the dictionary could be replaced with a simple array, as in array [0..MAX_TYPES-1] of Boolean. Or better yet, if there only a limited number of component types, say 64 or less, then the dictionary can be replaced with a single UInt64, where each bit represents a specific component type. This not only takes far less memory, but checking whether a component type is supported is as easy as checking if a specific bit is set, which is very fast.

A Simple Implementation

Generating type indices is actually pretty simple and only requires a few lines of code. The trick lies in using a combination of a generic type and static class variable:

type
  TTypeIndex<T> = class // static
  private
    class var FValue: Integer;
  public
    class constructor Create;

    class property Value: Integer read FValue;
  end;

var
  GNextTypeIndex: Integer = 0;

{ TTypeIndex<T> }

class constructor TTypeIndex<T>.Create;
begin
  FValue := GNextTypeIndex;
  Inc(GNextTypeIndex);
end;

You can find this code (and other code used in this post) in our JustAddCode repository on GitHub.

This code may look a bit unusual, but I will explain it in a bit. You can use the code like this:

WriteLn('Index for type Integer: ', TTypeIndex<Integer>.Value);
WriteLn('Index for type String: ', TTypeIndex<String>.Value);
WriteLn('Index for type TStream: ', TTypeIndex<TStream>.Value);
WriteLn('Index for type String: ', TTypeIndex<String>.Value);

Which will generate the following output:

Index for type Integer: 0
Index for type String: 1
Index for type TStream: 2
Index for type String: 1

Note that you never create an instance of the TTypeIndex<T> class. It is a static class and you only need its class property Value.

Each type will have its own unique integer index, starting at 0. Every time you request the index for the same type, you get the same value (as you should, as you can see for the String type in the example). Requesting the type index is also extremely fast: it is just a single access to a static class variable, which is as efficient as loading a global variable.

As can be expected, type aliases (like the TIntegerAlias type in the example below) return the same index as their aliased type. If you need a unique index for another Integer type, then you can declare it as a distinct type instead of an alias (see TDistinctInteger below).

type
  TIntegerAlias = Integer;
  TDistinctInteger = type Integer;

WriteLn('Index for type TIntegerAlias: ',
  TTypeIndex<TIntegerAlias>.Value);

WriteLn('Index for type TDistinctInteger: ', 
  TTypeIndex<TDistinctInteger>.Value);

Which results in:

Index for type TIntegerAlias: 0     // Same index as Integer
Index for type TDistinctInteger: 3

How Does It Work?

The key to this technique is the static class variable FValue. Because TTypeIndex<T> is a generic class, there is a different instance of FValue for each instantiated type of TTypeIndex<T>.

As far as I remember, that has not always been the case. As I recall (but please correct me if I am wrong), in the first Delphi versions with support for generics, static class variables would be shared across all instantiated types. That is, there would be only one instance of FValue in this case, that would be shared with each specific version of TTypeIndex<T>. If that was still the case, then the technique discussed in this article would not work.

The compiler keeps track of which instantiated types are used in the code. In this example, there are 4 instantiated types: TTypeIndex<Integer>, TTypeIndex<String>, TTypeIndex<TStream> and TTypeIndex<TDistinctInteger>. Thus this means that there are 4 instances of the FValue class variable. And likewise, this means that the class constructor will get called 4 times at application startup, once for each instantiated type. It is there that we assign the FValue class variable for the type and increment a global index for the next type.

So it is not technically true that the type indices are assigned at compile time; they are assigned at runtime at application startup. But the determination which types get index values is made at compile time since the compiler will insert the class constructor code for each instantiated type.

A Simple Type Map

Now to get back to our ECS example: we need to know (fast) if a particular component type is supported by a particular entity. So instead of using a TDictionary<PTypeInfo, Boolean>, we can now use a single unsigned integer to do the trick. In the following example, we use a 32-bit integer so we can support at most 32 different component types. If that is not enough for your purposes, then you can use a 64-bit integer instead, or a combination of multiple integers if needed. But for most situations, a 32-bit or 64-bit integer would do nicely. This example code wraps the unsigned integer into a record for ease of use:

type
  TTypeMap = record
  private
    FBits: UInt32;
  public
    procedure Init; inline;
    procedure Include<T>; inline;
    procedure Exclude<T>; inline;
    function Has<T>: Boolean; inline;
  end;

{ TTypeMap }

procedure TTypeMap.Init;
begin
  FBits := 0;
end;

procedure TTypeMap.Include<T>;
var
  Index: Integer;
begin
  Index := TTypeIndex<T>.Value;
  Assert(Index < 32);
  FBits := FBits or (1 shl Index);
end;

procedure TTypeMap.Exclude<T>;
var
  Index: Integer;
begin
  Index := TTypeIndex<T>.Value;
  Assert(Index < 32);
  FBits := FBits and not (1 shl Index);
end;

function TTypeMap.Has<T>: Boolean;
var
  Index: Integer;
begin
  Index := TTypeIndex<T>.Value;
  Assert(Index < 32);
  Result := ((FBits and (1 shl Index)) <> 0);
end;

This is just boilerplate code to set or clear bits, or to check if a bit is set. It uses the TTypeIndex<T> utility we created earlier. We use assertions to check if the type index is in range. If you use too many types, you will be notified at runtime. You can then decide to switch to a UInt64 instead, or some other model.

You can use the type map like this:

var
  TypeMap: TTypeMap;

TypeMap.Init;

{ "Register" Integer and TStream types }
TypeMap.Include<Integer>;
TypeMap.Include<TStream>;

Assert(TypeMap.Has<Integer>);
Assert(TypeMap.Has<TStream>);
Assert(not TypeMap.Has<String>);

{ "Unregister" Integer type }
TypeMap.Exclude<Integer>;

Assert(not TypeMap.Has<Integer>);
Assert(TypeMap.Has<TStream>);

A Two Level Type Index

That is basically all you need to generate type indices. But as a bonus, I will conclude this post with a slightly more advanced scenario where you can have different type indices per “category” of types. This can be useful if you don’t want one single global TTypeIndex<T>, but if you want to create different indices for different purposes. For example, in the ECS scenario, you may want a set of type indices for component types and a different set of type indices for system types. It can also be useful if 32 or 64 types are not enough; in that case, you can use multiple categories where each category can support 32 or 64 type indices.

This may be better explained using an example. The public interface of the TTypeIndex class now looks like this.

type
  TTypeIndex<TCategory> = class // static
  public
    class function Get<T>: Integer; inline; static;
  end;

There are two generic type identifiers now: TCategory is the main type identifier that defines a certain category of type indices. And there is a generic method called Get<T> now, where T is the type for which we want to retrieve its index (similar to the type T in the TTypeIndex<T> example presented earlier).

This class can be used as follows:

type
  TCategory1 = type Integer;
  TCategory2 = type Integer;

WriteLn('Type index for category 1, type Integer: ',
  TTypeIndex<TCategory1>.Get<Integer>);

WriteLn('Type index for category 1, type Single: ',
  TTypeIndex<TCategory1>.Get<Single>);

WriteLn('Type index for category 1, type String: ',
  TTypeIndex<TCategory1>.Get<String>);

WriteLn('Type index for category 1, type Single: ',
  TTypeIndex<TCategory1>.Get<Single>);

WriteLn('Type index for category 2, type Single: ',
  TTypeIndex<TCategory2>.Get<Single>);

Here we use two categories of type indices. We declared two distinct types for this (TCategory1 and TCategory2). The underlying types are not important here; these types are just used to distinguish categories.

The output of this code is:

Type index for category 1, type Integer: 0
Type index for category 1, type Single: 1
Type index for category 1, type String: 2
Type index for category 1, type Single: 1
Type index for category 2, type Single: 0

Now, the type index for type Single is different for the two categories.

The implementation of this TTypeIndex is a bit more complex, but interesting:

type
  TTypeIndex<TCategory> = class // static
  private type
    TIndex<T> = class // static
    private 
      class var FValue: Integer;
    public
      class constructor Create;
    end;
  private
    class var FNextIndex: Integer;
  public
    class constructor Create;
  public
    class function Get<T>: Integer; inline; static;
  end;

{ TTypeIndex<TCategory> }

class constructor TTypeIndex<TCategory>.Create;
begin
  FNextIndex := 0;
end;

class function TTypeIndex<TCategory>.Get<T>: Integer;
begin
  Result := TIndex<T>.FValue;
end;

{ TTypeIndex<TCategory>.TIndex<T> }

class constructor TTypeIndex<TCategory>.TIndex<T>.Create;
begin
  FValue := FNextIndex;
  Inc(FNextIndex);
end;

We use an additional trick in the Delphi bag here: the nested type TIndex<T>. Other than that, the same principles discussed earlier apply here: every instantiated type of TTypeIndex<TCategory> has its own instance of the FNextIndex class variable, which is initialized to 0 in its class constructor.

Likewise, every instantiated type of TTypeIndex<TCategory>.TIndex<T> has its own instance of the FValue class variable. However, it also has access to the FNextIndex class variable of its container type. Since that variable is specific to a particular TCategory we can use it to generate FValue in the class constructor. (FNextIndex is similar in this regard to the global GNextTypeIndex variable in the first example).

Try It Out

I think this is an interesting way to use a combination of Delphi language features to achieve something that would otherwise only be possible in languages like C++ with the use of meta programming.

If you want to try it out for yourself, then you can start with a couple of examples in our JustAddCode GitHub repository.

Let me know if you come up with other interesting use cases for this technique!

One thought on “Mapping Delphi Types to Indices at Compile Time

Leave a Reply to Serj Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s