Generic musings 2

It was pointed out in the comments to my previous post that my simple generic sorting routine contains additional overhead compared to TArray Rtl code (Generic.Collections & Generic.Defaults units) because RTTI is used inside the loop. Yes, that is true. Let us improve the code by taking RTTI check away from the loop, while keeping the code simple (without using over-weighted and tricky IComparer interface).

Simple tasks should have simple solutions. Now when I look at it the solution seems quite obvious, still I spent some hours trying to find it – generics are weird for beginner. The last step that led to working code was to declare generic procedural type TCompare inside generic class TArray, without it the code would not compile:

unit GenericSort;

interface

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

function CompareInt(const L, R: Integer): Integer;

implementation

uses SysUtils, TypInfo;

class procedure TArray.InternalSort(var A: array of T; Compare: TCompare);
var
  I, J: Integer;
  Item: T;
  P: PTypeInfo;

begin
  for I:= 1 + Low(A) to High(A) do begin
    Item:= A[I];
    J:= I - 1;
    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;

function CompareInt(const L, R: Integer): Integer;
begin
 if L < R then Result:= -1
  else if L > R then Result:= 1
  else Result:= 0;
end;

class procedure TArray.InsertionSort(var A: array of T);
var
  P: PTypeInfo;

begin
  P:= TypeInfo(T);
  case P^.Kind of
    tkInteger: InternalSort(A, @CompareInt);
    tkUString: InternalSort(A, @CompareStr);
  end;
end;

end.

Note that the function ‘CompareInt’ is declared in interface section. If you comment out interface declaration you get compile error

[DCC Error] GenericSort.pas(54): E2506 Method of parameterized type declared in interface section must not use local symbol ‘CompareInt’.

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.

Installing Virtual Treeview

Delphi component’s package installation procedure has always been a mess. If you don’t rely on self-made “automated” installations that just copy compiled binaries and do some registry patches that could easily destroy your Delphi installation beyond repair you should do everything manually from IDE. It takes time, and if you have a lot of packages it takes a lot of time.

To make the situation even worse the package configuration information is now scattered among 3 files – *.dpk, *.dproj and *.res; and these files contains both important package configuration and absolutely irrelevant private information about package developer’s system. As a result package developers usually supply *.dpk file only, leaving it to a package user to create the missing configuration data. And of course you have a lot of chances to forget some important setting…

Well, enough ranting. I have recently reinstalled Windows (and Delphi 2009) on my notebook and now slowly installing component packages. Here is a story of Virtual Treeview package installation. I hope the following will help me next time I install Virtual Treeview package and also help those who install Virtual Treeview package for the first time.

1. Checkout latest Virtual TreeView build from “http://virtual-treeview.googlecode.com/svn/trunk/&#8221; to “C:\Packages\VTree” folder.
2. Delete ‘Delphi-deprecated’ subfolder. It is obsolete and about to be removed in some future version.
3. Run Delphi IDE (Delphi 2009 in my case).
4. Open runtime package “c:\Packages\VTree\Packages\Delphi 2009\VirtualTreesR.dpk” (File-> Open Project..). You will be prompted to upgrade the project – click “OK”.

5. Rightclick on “VirtualTreesR.bpl” in the Project Manager panel and select “Options” from the context menu.

Now we should configure the package. First we should select a directory to store the compiled units (*.dcu). We have two options – either to add a new path to “Library Path” list or to use a path already available in “Library Path” list. I prefer the second, so I set “Unit output directory” to $(BDSCOMMONDIR)\Dcp:

$(BDSCOMMONDIR) = “c:\Users\Public\Documents\RAD Studio\6.0” on my system with Delphi 2009.

Next important (and frequently missed) setting is “Symbol reference info”. It should be set to “Definitions only” – otherwise code navigation in package units (Ctrl-Click) will not work.

One more nesessary setting is LIB Suffix; LIB Suffix is 120 for Delphi 2009:

I have made all settings for “Base” configuration. I have not applied any settings to “Debug” configuration, so “Base” and “Debug” configuration are identical and I can use any. To be sure we can check active build configuration in “Configuration Manager” (it is “Debug” by default).

I assume that “Release” configuration is more suitable for Build machine while “Debug” configuration is more appropriate for developer system.

Now we can compile the configured package. Rightclick on “VirtualTreesR.bpl” in the Project Manager panel and select “Compile” … to see the compiler error message:

[DCC Fatal Error] VirtualTrees.pas(461): F1026 File not found: ‘Compilers.inc’

The Virtual Treeview developers’ fault. ‘Compilers.inc’ is lying in “c:\Packages\VTree\Common”. The simplest solution is to copy “c:\Packages\VTree\Common\Compilers.inc” to c:\Packages\VTree\Source\Compilers.inc”

After copying ‘Compilers.inc’ file the package compiles. Now close the runtime package (File-> Close All) and open designtime package “c:\Packages\VTree\Packages\Delphi 2009\VirtualTreesD.dpk”.

Designtime package settings are the same as runtime package settings, with little differences:

Rightclick on “VirtualTreesD.bpl” in the Project Manager panel and select “Compile” … to see the compiler error message again:

[DCC Fatal Error] VirtualTreesReg.pas(8): F1026 File not found: ‘Compilers.inc’

Copy “c:\Packages\VTree\Common\Compilers.inc” to “c:\Packages\VTree\Design\Compilers.inc” and compile again. Now the package compiles OK.

Rightclick on “VirtualTreesD.bpl” in the Project Manager panel and select “Install”:

Close the designtime package (File-> Close All).

We have successfully installed Virtual Treeview components to the component palette, but that is not all. Create new VCL Forms application, drop TVirtualStringTree component on the form and try to compile application:

[DCC Error] E1026 File not found: ‘VirtualTrees.res’

It appears that ‘VirtualTrees.res’ file should be placed in a directory in “Library Path” list. The solution is to copy the file to $(BDSCOMMONDIR)\Dcp. This can be done manually, but it could also be done automatically if, for example, a runtime package was configured with post-build event

copy “c:\Packages\VTree\Source\VirtualTrees.res” “c:\Users\Public\Documents\RAD Studio\6.0\Dcp\VirtualTrees.res”

After copying “VirtualTrees.res” (manually or by recompiling “VirtualTreesR.dpk” with post-build event) the application compiles.

The last thing to do is to enable code navigation – add “c:\Packages\VTree\Source” directory to “Browsing Path”:

That is all for me; someone else may prefer slightly different package settings, I like these.

The thing I don’t like is a lot of tedious mechanical work to install a component package. Installing Virtual Treeview is easy because it is just one runtime and one designtime package; installing dozens of packages is real nightmare. The perfect solution for me is a single standard user-customizable package configuration file supported by Delphi and provided by every component vendor. No stupid mouse clicks in dialogs, just plain text file that you can edit in Notepad and use many times in IDE or with some command-line utility. Well, that is a dream.