twm's blog

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:

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.

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 😉 ).

 
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.

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.