Generic musings

Delphi (as Pascal descendant) has always had powerful type system. Consider the following sample code implementing simple insertion sort algorithm (I use Delphi 2009):

unit InsSort;

interface

type
  TItem = Integer;
  TArray = array of TItem;

procedure InsertionSort(var A: TArray);

implementation

procedure InsertionSort(var A: TArray);
var
  I, J: Integer;
  Item: TItem;

begin
  for I:= 1 + Low(A) to High(A) do begin
    Item:= A[I];
    J:= I - 1;
    while (J >= Low(A)) and (A[J] > Item) do begin
      A[J + 1]:= A[J];
      Dec(J);
    end;
    A[J + 1]:= Item;
  end;
end;

The above code sorts integer array; if we need to sort array of strings, all we have to do is to switch TItem type declaration from Integer to string:

type
  TItem = string;

If our task is to sort both integer and string arrays we should have two separate source code units (though they differ just by one word). Clearly that is code duplication that can’t be solved in plain Pascal. But Delphi has generics, let us try generics. Naive

  procedure InsertionSort<TItem>(var A: array of TItem);

does not compile, we need class to use generics; we also need some means to compare generic types, so I have written the following simple generic class:

type
  TArray<TItem> = class
    class function Compare(const L, R: TItem): Integer; static;
    class procedure InsertionSort(var A: array of TItem); static;
  end;

implementation

uses SysUtils, TypInfo;

class function TArray<TItem>.Compare(const L, R: TItem): Integer;
var
  P: PTypeInfo;

begin
  P:= TypeInfo(TItem);
  case P^.Kind of
    tkInteger: begin
      if PInteger(@L)^ < PInteger(@R)^ then Result:= -1
      else if PInteger(@L)^ > PInteger(@R)^ then Result:= 1
      else Result:= 0;
    end;
    tkUString: Result:= CompareStr(PString(@L)^, PString(@R)^);
  end;
end;

class procedure TArray<TItem>.InsertionSort(var A: array of TItem);
var
  I, J: Integer;
  Item: TItem;

begin
  for I:= 1 + Low(A) to High(A) do begin
    Item:= A[I];
    J:= I - 1;
//    while (J >= Low(A)) and (A[J] > Item) do begin
    while (J >= Low(A)) and (Compare(A[J], Item) > 0) do begin
      A[J + 1]:= A[J];
      Dec(J);
    end;
    A[J + 1]:= Item;
  end;
end;

It works but it looks ugly. Think also of crazy overhead of generic comparison, especially for plain types like Integers that are normally compared by just a single assembler instruction. Delphi 2009 Rtl (Generics.Defaults.pas unit) provides more elegant (and more lengthy) solution based on IComparer generic interface, but it boils down to the same inefficient runtime type information usage.

But why we need the ‘Compare’ function at all? By the time the compiler generates code for generic TItem type the compiler should already know actual type to substitute for TItem, and using the actual type it can compile the elegant line

    while .. (A[J] > Item) ..

much more efficiently than the ugly

    while .. (Compare(A[J], Item) > 0) ..

The idea of direct efficient Generic comparison also invokes Haskell’s ‘type class’ concept. The ‘Type class’ is something very different from OOP class. In Haskell every type is an instance of many type classes. For example integer type is an instance of ‘Eq’ type class because integers can be compared for equality, of ‘Ord’ type class because all comparison operation (<, <=, >, >=) are applicable to integers, of ‘Show’ type class because integers can be converted to string, etc. In our case the generic TItem type should be an instance of ‘Ord’ type class.

Advertisements

7 thoughts on “Generic musings

  1. In our case the generic TItem type should be an instance of ‘Ord’ type class.

    I disagree, because the same operator might be used by different type families (e.g + is used by integers, sets and strings, and with a different meaning each time). What we need are operator contraints, the syntax for which could echo that for operator overloading –

    type
      TArray<TItem: class operator Add, class operator Subtract> = record
    

    By itself, TItem could then be instantiated as an integer, float, set, or custom record type that overloads the Add and Subtract operators.

    • @Chris – Why different operator meaning matters?

      In the context of the post operator constraint is the same as type class – I can say that TItem from you example is an instance of ‘Add’ and ‘Subtract’ type classes. I just playing with Haskell concept of the type class which is absent in Delphi.

      And the point of the post is – if TItem is instantiated as Integer, then the compiler should generate ‘add’ machine code as normal Integer addition (just a single ADD assembler instruction if possible), not through the current RTTI overhead.

      • Why different operator meaning matters?

        Not being familar with Haskell, I’m hearing the phrase ‘type class’ to mean a group of things. Maybe that’s wrong though? I prefer to talk of operator constraints since we want to constrain on an item-by-item basis – not on whether a type is of a certain kind, but whether it has an A, B and C, or just an A, or a B and a C, etc. Any predefined grouping will by definition take away flexibility.

        And the point of the post is – if TItem is instantiated as Integer, then the compiler should generate ‘add’ machine code as normal Integer addition (just a single ADD assembler instruction if possible), not through the current RTTI overhead.

        For sure. However, as Stefan says, your example code makes it worse by calling on RTTI for each Compare call. Cf. my version of the same thing – deliberately similar to Generics.Defaults, but using metaclasses to keep the code releatively clean: http://delphihaven.wordpress.com/2011/03/18/generic-arithmetic/. Mind you, even forgetting the TypeInfo stuff, just the virtual method calls have quite a big speed cost…

  2. While I agree to the need of more types of constraints I disagree on your example.

    Your code actually makes it much worse than it is when using Generics.Defaults comparer. If you do the TArray.Sort from Generics.Collections it gets the comparer function in the beginning and then just calls it while you check for the type every time you call the compare method.

    • My code is really ugly as I said in the post, Generics.Defaults comparer it more elegant, but in fact where is a little difference between them – they work through RTTI and awfully inefficient.

      • The only RTTI involved is when TComparer<T>.Default method is called and that is one single time. Go and debug

        TArray.Sort<Integer>(myIntArray);
        

        There are just calls to Compare_I4 in that case. I agree there is a bit of overhead for the interface and method call but not as much as you expect.

  3. Pingback: Generic musings 2 « The Programming Works

Leave a 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s