TStringList vs. THashedStringList vs. TDictionary

 Delphi  Comments Off on TStringList vs. THashedStringList vs. TDictionary
Feb 162020
 

Prompted by the topic Dictionaries, Hashing and Performance in the international Delphi Praxis forum I did some timing to compare the performance of data structures in the Delphi runtime library that can be used to store data indexed by strings:

  • a sorted, case sensitive TStringList (available since Delphi 6)
  • a sorted, case sensitive THashedStringList (available since Delphi 6)
  • a TDictionary<string,Integer> (available since a Delphi 2009)

Just in case you did not know about THashedStringList: It is a TStringList descendant declared in System.IniFiles. It’s used to speed up access to TMemIniFile. (EDIT: As Uwe Raabe pointet out, that’s no longer true. As of Delphi 10.3 (and possibly earlier, I haven’t checked) TMemIniFile also uses TDictionary<string,Integer>.)

The test adds 676 strings (‘AA’ .. ‘ZZ’) to each structure and does that 10000 times (which means that there are quite a few checks for duplicates to be done on adding). Then – again 10000 times – it does a lookup for each of these strings.

Of course that is just a simple test and it is neither a large number of entries nor long strings. I just wanted to get a feel for the performance of these structures.

Here is the main code for TStringList and THashedStringList:

procedure Tf_HashedStringListTest.DoTiming(sl: TStringList);
const
  CYCLES = 10000;
var
  k: integer;
  i: integer;
  j: integer;
  sw: TStopwatch;
  s: string;
  Idx: Integer;
begin
  sl.Sorted := True;
  sl.CaseSensitive := True;
  sl.Duplicates := dupError;
  sw := TStopwatch.StartNew;
  sl.BeginUpdate;
  for k := 1 to CYCLES do begin
    for i := Ord('A') to Ord('Z') do begin
      for j := Ord('A') to Ord('Z') do begin
        s := chr(i) + chr(j);
        if not sl.Find(s, Idx) then
          sl.AddObject(s, Pointer(i * 100 + j));
      end;
    end;
  end;
  sl.EndUpdate;
  sw.Stop;
  m_Output.Lines.Add(sl.Count.ToString + ': Add: ' + sw.Elapsed.ToString);

  sw.Reset;
  sw.Start;
  for k := 1 to CYCLES do begin
    for i := Ord('A') to Ord('Z') do begin
      for j := Ord('A') to Ord('Z') do begin
        s := chr(i) + chr(j);
        sl.IndexOf(s);
      end;
    end;
  end;
  m_Output.Lines.Add(sl.Count.ToString + ': IndexOf: ' + sw.Elapsed.ToString);
end;

And very similar for TDictionary:

procedure Tf_HashedStringListTest.DoTiming(sl: TDictionary<string, integer>);
const
  CYCLES = 10000;
var
  k: integer;
  i: integer;
  j: integer;
  sw: TStopwatch;
  s: string;
  v: integer;
begin
  sw := TStopwatch.StartNew;
  for k := 1 to CYCLES do begin
    for i := Ord('A') to Ord('Z') do begin
      for j := Ord('A') to Ord('Z') do begin
        s := chr(i) + chr(j);
        if not sl.TryGetValue(s, v) then
          sl.Add(s, i * 100 + j);
      end;
    end;
  end;
  sw.Stop;
  m_Output.Lines.Add(sl.Count.ToString + ': Add: ' + sw.Elapsed.ToString);

  sw.Reset;
  sw.Start;
  for k := 1 to CYCLES do begin
    for i := Ord('A') to Ord('Z') do begin
      for j := Ord('A') to Ord('Z') do begin
        s := chr(i) + chr(j);
        sl.Items[s];
      end;
    end;
  end;
  m_Output.Lines.Add(sl.Count.ToString + ': IndexOf: ' + sw.Elapsed.ToString);
end;

The result is not really surprising:

TDictionary is the winner by a large margin, followed by THashedStringList and then TStringList. The two string lists only differ in the IndexOf times, the adding times are very similar.

On my computer, with an AMD Phenom II XE 1090T processor, and compiled with Delphi 10.3 I get the following times:

Structure Time for Add [sec] Time for IndexOf [sec]
TStringList 7.43 7.48
THashedStringList 7.45 4.40
TDictionary 1.05 1.04

EDIT: I just found that changing the code for the THashedStringlist from using Find to using IndexOf reduced the time for adding entries to about the same time as for IndexOf. So both are about 4 seconds. This makes me wonder whether there is a bug in THashedStringList because it does not override AddObject. It simply inherits it from TStringList which for sorted lists calls Find to see if the string is already in the list. In contrast to IndexOf the Find method does not use the hash so it’s as slow as in TStringList. But maybe that is on purpose because the hashes get calculated rather frequently for all entries. I get the impression that THashedStringList is not really well implemented and nobody noticed because it was just good enough.

EDIT2: As it was only used in TMemIniFile to get fast access to the entries without needing them to be sorted, the implementation probably was good enough. My test above doesn’t check the performance of Add for an unsorted THashedStringList which is what TMemIniFile used.

If you like, you can download the full source code of my test program.

 Posted by on 2020-02-16 at 16:05

Delphi is 25 years old

 Delphi  Comments Off on Delphi is 25 years old
Feb 152020
 

Everybody seems to be blogging about Delphi having been around for 25 years, so I won’t stay back and tell some of my story.

When I finished university and started a job, Delphi was just about being “born” and I was working with Turbo Pascal and later Visual Basic. VB was great in some aspects because it allowed to easily design user interfaces and write code only where you needed it. It wasn’t after several years later that I was introduced to Delphi when I took a job at fPrint UK Ltd. (Yes, that’s what web pages looked in 1997) and moved from Germany to the UK. The time I worked there was among the best of my life. I had some great coworkers there who were expert software developers (Hello Mamta, Allan, Vitaly and Linden, if you read this. And RIP to you, Andrew). We were already using Delphi 3 by that time and it delivered everything that Visual Basic had only been promising. I was hooked for life. We also worked on Virtual Pascal, a Pascal compiler compatible to Borland Pascal and partly Delphi which had originally been Vitaly’s project. Working for fPrint later made me move to Paris (France) for a while. Back then I also made first contact with GExperts.

Fast forward to 2020. I had changed jobs frequently until 2007 due to companies I worked for being bought by others and working conditions deteriorating afterwards. I made my fist million D-Mark (and lost most of it shortly afterwards, never gaining it back). I even had to go back to programming in Visual Basic 6 for a while (and I hated it).

Today I work at TÜV Rheinland Schniering GmbH (formerly Schniering Ingenieurgesellschaft) and develop Software in Delphi for road condition surveys. It is running on our measurement vehicles and also used in the office and at customer’s sites. As software development jobs go this is way cool, and again I have some great coworkers, this time not only in software development, because we also build our own measurement hardware and even developed the elevator examination system Liftis© (software by me, hardware by my coworkers) for our parent company TÜV Rheinland.

I really wonder how my career and my life would have turned out if Delphi hadn’t been around at the time I started out. Maybe I would have ended up as a COBOL programmer for life at Debeka (which was my first employer). Or I would have written embedded software in C for some company I didn’t even get to know. At some time I even interviewed for a job at a company (I forgot the name, but it was located in Dreieich near Frankfurt, Germany) that was developing a search engine written in Delphi (Edit: I remembered: They called themselves “Twirlix” and apparently folded in 2001, shortly after my interview)

Thinking back, this has been some exciting time to be alive and for me Delphi played a significant part of it.

 Posted by on 2020-02-15 at 12:22

How the handle declarations changed in Delphi

 Delphi  Comments Off on How the handle declarations changed in Delphi
Dec 312019
 

Delphi has had a THandle type for a long time (at least since Delphi 6) but didn’t use it consistently. I just had to check those declarations for various Delphi versions in order to get rid of compile errors or warnings in GExperts. Here is what I found:

  • THandle is a type declared in the System unit.
  • INVALID_HANDLE_VALUE is a constant declared in the Windows unit.
  • THandleStream, declared in the Classes unit, has got a private field called FHandle
  • THandleStream.Create has got an AHandle parameter

You would have thought that in all those places THandle is used, but it isn’t. Sometimes it’s DWord, sometimes it’s integer, and sometimes it’s THandle. Also, the declaration of the THandle type changed from LongWord to NativeUInt at some time. Only in Delphi XE2 and later it is consistent (but hey: Everybody keeps telling me to drop GExperts support for versions older than that, so there is an easy solution 😉 ).

Delphi Version THandle INVALID_HANDLE_VALUE FHandle AHandle
6 – 2007 LongWord DWord Integer Integer
2009 – XE LongWord DWord THandle Integer
XE2 and later NativeUInt THandle THandle THandle

 
So, in order to not get any compile errors or warnings I declared two different types:

type
{$IFDEF THANDLESTREAM_CREATE_HANDLE_IS_THANDLE}
  THandleStreamCreateHandleCast = THandle;
{$ELSE}
  THandleStreamCreateHandleCast = Integer;
{$ENDIF}
{$IFDEF THANDLESTREAM_HANDLE_IS_THANDLE}
  THandleCast = THandle;
{$ELSE}
  THandleCast = Integer;
{$ENDIF}

Where the conditional defines are defined as follows:

{$INCLUDE 'jedi.inc'}

// The following cond. defines address errors in various Delphi versions regarding the declaration
// of the FHandle field of THandleStream and the corresponding Create constructor parameter:
{$IFDEF DELPHI2009_UP}
// THandleStream.FHandle is declared as THandle (before that it's an Integer)
{$DEFINE THANDLESTREAM_HANDLE_IS_THANDLE}
{$ENDIF}

{$IFDEF DELPHIXE2_UP}
// AHandle is declared as THandle (otherwise it's an Integer)
{$DEFINE THANDLESTREAM_CREATE_HANDLE_IS_THANDLE}
{$ENDIF}

Really annoying but at least that takes care of these errors and warnings.

 Posted by on 2019-12-31 at 19:50

Building a project in Delphi 10.3 fails if the build script output contains “error:”

 Delphi  Comments Off on Building a project in Delphi 10.3 fails if the build script output contains “error:”
Dec 312019
 

I just had a nasty surprise with Delphi 10.3 when trying to build a project that worked fine with previous Delphi versions. The problem turned out the text one of my pre build events wrote to the output. It contained the string “error :”. Apparently Delphi 10.3 parses the output of the build events and tries to interpret it.

Try for yourself:

  • Create a batch file test.cmd with the following content:
    @echo error: bla
    
  • Add it as a pre build event to a Delphi project:
    call path\to\test.cmd
    
  • Try to compile.

If I’m right, you will get an error like:

And the Messages window will contain the following error:

[Exec Error] EXEC(1): bla

Very annoying. If this is documented, I can’t find it. I only see:

Cancel on error

Cancels the project build if a command returns a nonzero error code.

on http://docwiki.embarcadero.com/RADStudio/Rio/en/Build_Events and http://docwiki.embarcadero.com/RADStudio/Rio/en/Creating_Build_Events

 Posted by on 2019-12-31 at 13:40

DUnit Folder Iterator Extension

 Delphi, GExperts  Comments Off on DUnit Folder Iterator Extension
Dec 282019
 

In 2012 Uwe Raabe blogged about an extension to the DUnit framework he had written. He mentioned it today in the German Delphi Praxis forum.

Guess what? It’s brilliant. It does exactly what I always wanted to write (and never came around doing) for the Unit Tests of the GExperts Code Formatter.

Those tests basically consist of a set of input files in one directory and for each of the tested configurations another set of files with the expected output. It always irked me that I actually had to write some code every time I added a new test instead of simply adding another bunch of files.

Today I changed those tests to use Uwe’s unit (with a few modifications to make it compatible to Delphi 2007). And I found that there were quite a few files which didn’t even get tested at all, because I forgot to add the code.

I’m happy to report that even with these additional tests, the number of failed tests did not increase.

 Posted by on 2019-12-28 at 19:18

The annoying problem of the growing GExperts menu

 Delphi, GExperts  Comments Off on The annoying problem of the growing GExperts menu
Dec 252019
 

As I add new functionality to GExperts the menu it displays grows larger and larger. On small monitors (there are still computers with e.g. 1024×600 pixels screen size in use, usually not with the latest Delphi version though) this means that the menu has to be broken into chunks, each with a “more” entry at the end to display the next chunk.
While this has been implemented for years (decades actually) it didn’t work very well. For Delphi 6 the code was completely broken (I might have been the culprit myself) it still had some bugs with all later versions.

No more. Today I fixed those bugs and tested it with screens as small as 640×480 pixels.

Also, when moving the GExperts menu into the Tools menu, there was a problem that the maximum number of entries for a chunk was not calculated correctly which would mean that the “more” entry could end up outside the visible area. This has also been fixed.

Unfortunately this does not solve the underlying problem: The menu keeps growing. There are now a maximum of 45 + 3 Entries in that menu. The way that menu is created on demand, depending on which experts are enabled or not, does not lend itself to a sensible menu structure.

I have added a “Category” property to each expert, which so far is neither filled nor used anywhere. I plan to create only one entry per Category in the GExperts menu with sub menus for each category. Maybe I will even make those categories configurable. But that’s for another day.

 Posted by on 2019-12-25 at 18:34

Updating to Windows 10 broke Delphi 6 and 2007 again

 Delphi, Windows, Windows 10  Comments Off on Updating to Windows 10 broke Delphi 6 and 2007 again
Dec 212019
 

Since Microsoft will end the free support for Windows 7 in January 2020, we are updating all our computers to Windows 10 (I would really have liked to avoid that. Windows 7 is definitely not the best Windows ever but its annoyances are known. Windows 10 started to annoy me with new so called “features” immediately after the installation finished. But hey, that’s what you get when you make a living developing software for this stinking pile of sh*t. sorry excuse for an operating system.)

Anyway: As before, when I updated from Windows 8 to Windows 8.1, the Windows 10 update broke my Delphi 6 and 2007 installations. Fortunately my workarounds / fixes for Windows 8.1 also work for Windows 10. Also fortunately I blogged about them

so I could look them up.

 Posted by on 2019-12-21 at 15:07

Accessing bitmap pixels with less ScanLine[] calls in Delphi

 Delphi  Comments Off on Accessing bitmap pixels with less ScanLine[] calls in Delphi
Dec 122019
 

As you will find in the documentation and on the web the usual way to access the pixels of a Bitmap in Delphi is using the Scanline[] array property. Something like this:

type
  TRgbTriple = packed record
    // do not change the order of the fields, do not add any fields
    Blue: Byte;
    Green: Byte;
    Red: Byte;
  end;

  TRgbTripleArray = packed array[0..MaxInt div SizeOf(TRgbTriple) - 1] of TRgbTriple;
  PRgbTripleArray = ^TRgbTripleArray;

procedure ConvertBmp(_InBmp, _OutBmp: TBitmap);
var
  x, y: Integer;
  Pixel: TRgbTriple;
begin
  Assert(_InBmp.PixelFormat = pf24bit);
  _OutBmp.SetSize(_InBmp.Width, _InBmp.Height);
  _OutBmp.PixelFormat := pf24bit;
  for y := 0 to Height - 1 do begin
    for x := 0 to Width - 1 do begin
      Pixel := PRgbTripleArray(_InBmp.Scanline[y])^[x];
      doSomething(Pixel);
      PRgbTripleArray(_OutBmp.Scanline[y])^[x] := Pixel;
    end;
  end;
end;

This code first checks that the input bitmap is using 24 bits per pixel, then sets the output bitmap to do the same. Then it enumerates through all the lines in the input bitmap and then all the pixels in that line, reads them does “something” with them and finally writes them to the corresponding pixel in the output bitmap.

Let’s assume a small VGA sized bitmap, so we get 480 lines with 640 pixels each. In total that makes 2 * 640 * 480 calls to ScanLine[], each taking a short time (There are multiple function calls in the getter method.).

Call that code for several bitmaps and you will end up with a huge amount of time spent in the calls to ScanLine[]. (Don’t just take my word for it, go ahead and time it!)

The first optimization that can be done is calling ScanLine[] only once for each line of each bitmap:

var
  InScanLine: PRgbTripleArray;
  OutScanLine: PRgbTripleArray;
// ...
  for y := 0 to Height - 1 do begin
    InScanLine := PRgbTripleArray(_InBmp.Scanline[y]);
    OutScanline := PRgbTripleArray(_OutBmp.Scanline[y]);
    for x := 0 to Width - 1 do begin
      Pixel := InScanLine^[x];
      doSomething(Pixel);
      OutScanLine^[x] := Pixel;
    end;
  end;

This reduces the number of calls to ScanLine by a factor of 640, which you will find is quite significant. (Again: Time it!)

But we still can do more. What if we only needed 4 calls in total rather than 2 * 480 ?

All we need to do is calculating the line addresses ourself. To do that we simply need two addresses, the one of the first and the one of the second line:

// if you are using Delphi 2007 or older you need to correct the NativeInt declaration from 8 bytes to 4 bytes:
{$IF SizeOf(Pointer) = 4}
type
  NativeInt = Integer;
{$IFEND}

function AddToPtr(const _Ptr: Pointer; _Offset: NativeInt): Pointer; inline;
begin
  Result := Pointer(NativeInt(_Ptr) + _Offset);
end;

function PtrDiff(const _Ptr1, _Ptr2: Pointer): NativeInt; inline;
begin
  Result := NativeInt(_Ptr1) - NativeInt(_Ptr2);
end;

var
  BytesPerPixel: NativeInt;
  InScanLine0: Pointer;
  InBytesPerLine: NativeInt;
  OutScanLine0: Pointer;
  InBytesPerLine: NativeInt;
  InPixel: PRgbTriple;
  OutPixel: PRgbTriple;
// ...
  BytesPerPixel := SizeOf(Pixel)  
  InScanLine0 := InBmp.ScanLine[0];
  InBytesPerLine := NativeInt(_InBmp.ScanLine[1]) - NativeInt(InScanLine0);
  OutScanLine0 := _OutputBmp.ScanLine[0];
  OutBytesPerLine := NativeInt(_OutBmp.ScanLine[1]) - NativeInt(OutScanLine0);
  OutPixel := OutScanLine0;
  for y := 0 to Height - 1 do begin
    for x := 0 to Width - 1 do begin
      InPixel := AddToPtr(InScanLine0, InBytesPerLine * y + x * BytesPerPixel);
      Pixel := InPixel^;
      doSomething(Pixel);
      OutPixel := AddToPtr(OutScanLine0, OutBytesPerLine * y + x * BytesPerPixel);
      OutPixel^ := Pixel;
    end;
  end;

What we do here is calculate the difference between the first two scan lines and use it to calculate the address of each scan line in the bitmap.

Note: Most of the time this difference will be negative because on Windows Bitmaps usually are stored bottom to top.

There are two inlined helper functions AddToPtr and PtrDiff who do the pointer arithmetic by converting the pointer to NativeInt and back.

Note that the NativeInt declaration in Delphi 2007 and older is wrong. That’s why we redeclare it as 4 bytes in the conditional define above if SizeOf(Pointer) is 4 bytes (32 bits). The code should also work for 64 bits, but I haven’t tried it.

 Posted by on 2019-12-12 at 18:34

Assigning an ImageMagick wand picture to a Delphi TBitmap

 Delphi  Comments Off on Assigning an ImageMagick wand picture to a Delphi TBitmap
Dec 062019
 

I could not find this anywhere so I had to experiment:

I mentioned PascalMagick before and that it’s part of the FreePascal RTL.

The following assigns an image that has been processed with the Magick Wand API of ImageMagick to a Delphi TBitmap.

First, we need to convert the image to bitmap format using MagickSetFormat:

  Status := MagickSetImageFormat(FWand, PAnsiChar('BMP'));
  // check status here

Then we get it as a blob by calling MagickGetImageBlob.

var
  Size: Cardinal;
  blob: Pointer;
begin
  blob := MagickGetImageBlob(FWand, @Size);
  // check if blob is assigned

Note that the memory for the blob is allocated by the dll, we will have to pass it to MagickRelinquishMemory to free it later.

The easiest way I found to assign some memory to a TBitmap is TBitmap.LoadFromStream. The stream in this case could be a TMemoryStream, but unfortunately there is no way to create a TMemoryStream for an existing memory block. So I wrote a descendant of TCustomMemoryStream that provides this functionality.

type
  TdzMagickBlob = class(TCustomMemoryStream)
  public
    constructor Create(_Memory: Pointer; _Size: Cardinal);
    destructor Destroy; override;
  end;

constructor TdzMagickBlob.Create(_Memory: Pointer; _Size: Cardinal);
begin
  inherited Create;
  SetPointer(_Memory, _Size);
end;

destructor TdzMagickBlob.Destroy;
begin
  if Size <> 0 then
    MagickRelinquishMemory(Memory);
  inherited;
end;

Remember what I said above about passing the blob back to the dll to free the memory? That’s what the destructor does.

Now we only need to load the bitmap from the stream:

  bmp := TBitmap.Create;

  blobStream := TdzMagickBlob.Create(blob, size);
  try
    blobStream.Position := 0;
    bmp.LoadFromStream(blobStream);
  finally
    FreeAndNil(blobStream);
  end;

There we go: The image has been assigned to the TBitmap object.

I would have liked to omit the stream and directly assign the memory to TBitmap.Scanline[], but I found no easy way to do that.

This is part of the object oriented layer I wrote for encapsulating (some of) the MagickWand functionality. I will put this code into my dzlib later.

 Posted by on 2019-12-06 at 09:54

Working on the GExperts Code Formatter again

 Delphi, GExperts  Comments Off on Working on the GExperts Code Formatter again
Nov 302019
 

The code formatter can now handle inline variable declarations. That was actually just a simple change (fixes bugs #157 and #158 (and the duplicate #165))

Now I’m trying to get it to format function declarations like this:

function RegisterClipboardFormatW(lpszFormat: PWideChar): UINT; stdcall;
  external user32 Name 'RegisterClipboardFormatW';

or something as simple as this;

procedure bla;
  overload;
  forward;

Currently it doesn’t indent the additional lines. It works fine for method declarations though.

This turns out to be much more complicated than I thought. In my attempts to fix this, I have multiple times broken other test cases. Good thing there’s unit tests and source code management.

By pure chance I found a nasty side effect in the code.

 Posted by on 2019-11-30 at 20:23