When sorting a “StringList” is very costly

 Delphi, GExperts  Comments Off on When sorting a “StringList” is very costly
Jan 052021
 

The following code looks innocuous but slows down a program significantly:

type
  TJCHListSortCompare = function(Item1, Item2: Integer): Integer of object;
  TCheckListBoxWithHints = class(TCheckListBox)
  private
    procedure QuickSort(L, R: Integer; SCompare: TJCHListSortCompare);

// [...]
procedure TCheckListBoxWithHints.QuickSort(L, R: Integer; SCompare: TJCHListSortCompare);
var
  I, J, P: Integer;
  tmpObj: TObject;
  tmpStr: string;
  tmpChecked: Boolean;
begin
  repeat
    I := L;
    J := R;
    P := (L + R) shr 1;
    repeat
      while SCompare(I, P) < 0 do Inc(I);
      while SCompare(J, P) > 0 do Dec(J);
      if I <= J then
      begin
        // exchange I and J
        tmpStr           := Items[I];
        tmpObj           := Items.Objects[I];
        tmpChecked       := Self.Checked[I];

        Items[I]         := Items[J];
        Items.Objects[I] := Items.Objects[J];
        Self.Checked[I]  := Self.Checked[J];

        Items[J]         := tmpStr;
        Items.Objects[J] := tmpObj;
        Self.Checked[J]  := tmpChecked;
        if P = I then
          P := J
        else if P = J then
          P := I;

        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then QuickSort(L, J, SCompare);
    L := I;
  until I >= R;
end;

Yes it’s Quicksort and it sorts strings in a TCheckListBox’s Items property, swapping not only the strings but also the objects and the Checked values.

Now, run this with, lets say 100 entries. That shouldn’t be any problem for Quicksort, should it? But it takes about 2 seconds on my computer which is muuuuuuch longer than I expected. The same code running on a simple TStringList takes less than 1/10 of a second. Why is that?

It’s because accessing the strings and changing them each results in a Windows message to be sent, handled and checked.

TCheckListBox inherits its Items property from TCustomListBox which declares it as:

    property Items: TStrings read FItems write SetItems;

Still looks innocuous? Now, let’s see how it is actually instantiated:

  FItems := TListBoxStrings.Create;
  TListBoxStrings(FItems).ListBox := Self;

So, what is TListBoxStrings? It’s a class that descends from TStrings and provides access to the strings stored in a TCustomListBox using Windows messages. E.g.:

function TListBoxStrings.Get(Index: Integer): string;
var
  Len: Integer;
begin
  // [...]
  begin
    Len := SendMessage(ListBox.Handle, LB_GETTEXTLEN, Index, 0);
    if Len = LB_ERR then Error(SListIndexError, Index);
    SetLength(Result, Len);
    if Len <> 0 then
    begin
      Len := SendMessage(ListBox.Handle, LB_GETTEXT, Index, Longint(PChar(Result)));
      SetLength(Result, Len);
    end;
  end;
end;

To get a string, it sends two messages to the Listbox’s handle and interprets its results.

Or:

procedure TListBoxStrings.Put(Index: Integer; const S: string);
var
  I: Integer;
  TempData: Longint;
begin
  I := ListBox.ItemIndex;
  TempData := ListBox.InternalGetItemData(Index);
  ListBox.InternalSetItemData(Index, 0);
  Delete(Index);
  InsertObject(Index, S, nil);
  ListBox.InternalSetItemData(Index, TempData);
  ListBox.ItemIndex := I;
end;

In order to set a string to a new value, it first deletes it and then inserts it again.

Want to guess what Delete() does? It sends a message to the listbox’s handle. And what does InsertObject do? It sends a message to the listbox’s handle.

While all this is an ingenious way to provide simple access to the strings normally only available using the mentioned messages, it’s far from efficient when you do a lot of comparisons and some swapping, which is exactly what a sorting algorithm does.

So, what can be done?

First, don’t work on the Items property directly but take a copy of it. Also, don’t swap the Checked property values (which also use messages) directly but take a copy of these too (in particular since some of the Compare functions passed to the sorting code also test the Checked property). Then sort the copy and assign it back to the listbox’s Items and Checked properties:

var
  cnt: Integer;
  tmpList: TStringList;
  ChkArr: TBoolArray;
  i: Integer;
//[...]
  tmpList := TStringList.Create;
  try
    tmpList.AddStrings(Items);
    SetLength(ChkArr, cnt);
    for i := 0 to cnt - 1 do
      ChkArr[i] := Checked[i];
    QuickSort(tmpList, ChkArr, 0, cnt - 1, Compare);
    Items.BeginUpdate;
    try
      Items := tmpList;
      for i := 0 to cnt - 1 do
        Checked[i] := ChkArr[i];
    finally
      Items.EndUpdate;
    end;
  finally
    tmpList.Free;
  end;

This code is from the GExperts Project Option Sets expert. This is one of the experts I had never used before and was shocked that, when I opened the dialog, it took several seconds before anything was shown. The reason turned out that the sorting described above was executed not only once but even twice in the FormShow event. After the changes I outlined above and reducing it to sort only once, it was down to less than half a second. That still felt like eternity, but was a significant improvement.

After I added some more tweaks, e.g. use a lookup list into an array of several hundred entries rather than linear search to find a particular string, the dialog now opens nearly instantly (on my computer).

If you want to discuss this article, you can do so in the corresponding post in the international Delphi Praxis forum.

 Posted by on 2021-01-05 at 16:16

New Explicit Properties Filter expert in GExperts

 Delphi, GExperts  Comments Off on New Explicit Properties Filter expert in GExperts
Dec 272020
 

I never understood the benefit of writing the ExplicitLeft / Top / Width / Height properties for TControl and descendants, which were added in Delphi 2007, to the dfm files. They store the control’s position and size before its Align property was set to something like alClient or alRight, so they can be restored later. That’s useful if you change these by accident or double click on the Align property to go through the possible values, but as soon as you save the form, you don’t really need them any more. Even worse, they seem to change often with no apparent reason and therefore clutter a dfm file’s diff with changes that nobody is interested in.

That’s probably why Andreas Hausladen added the option “Do not store the Explicit* properties into the DFM” (under “Form Designer”) to his DDevExtensions plugin. I have enabled that option since I found it. Unfortunately Andreas has not yet released a Delphi 10.4 version of DDevExtensions (and his other useful tools) because there is no Community Edition of Delphi 10.4 yet and he no longer has access to the latest Delphi versions (From what I read in the forums he chose not to accept a free license from Embarcadero, probably due to some strings attached to that offer.) Whatever the reason: Having those annoying properties back has irked me for a while now.

Achim Kalwa has written a plugin that removes them, but I didn’t want to install an additional plugin just for this functionality.

So I eventually came around adding it to GExperts. It’s a bit hidden because it does have a menu entry, only a configuration dialog:

In addition it’s not active by default so it won’t conflict with DDevExtensions if that’s also active.

So, if you want to use this new expert, you will have to explicitly activate it. It also allows you to selectively write some of the ExplicitXxx properties anyway, but I doubt that anybody will ever use that.

There is no GExperts release with this Expert yet. If you don’t want to wait, you’ll have to compile your own DLL.

If you want to discuss this article, go to the related post in the international DelphiPraxis forum.

 Posted by on 2020-12-27 at 12:02

Migrating GExperts settings

 Delphi, GExperts  Comments Off on Migrating GExperts settings
Nov 302020
 

Somebody just asked me whether there is a simple way to migrate GExperts settings from Delphi XE7 to a new version.

The short answer is: No, but some experts (or rather: some functionality, because not everything is wrapped into an expert) have an ex- and import function.

I also started to write a general ex- and import function for GExperts but never finished it. Real life tends to intrude on open source programming. 😉

The long answer would be: Yes, you can do that by copying the registry entries and configuration files:

  • Export the GExperts registry key to a file
  • Edit that file to match the new Delphi version
  • Import the edited file into the registry.

The GExperts registry key is located under the registry key of the corresponding Delphi version. For XE7 that would be

HKEY_CURRENT_USER\SOFTWARE\Embarcadero\BDS\15.0\GExperts-1.3

The exported file will contain many sections in the form

[HKEY_CURRENT_USER\SOFTWARE\Embarcadero\BDS\15.0\GExperts-1.3]

[HKEY_CURRENT_USER\SOFTWARE\Embarcadero\BDS\15.0\GExperts-1.3\ASCIIChart]
"Font Size"=dword:0000000a
"Font Name"="Tahoma"
"Font Base"=dword:00000000
"Edit Display Text"="±"
"Show Hex"="0"
"Zoom Font Size"=dword:00000020
"Show Hint"="1"
"Left"=dword:000002a9
"Top"=dword:0000016b
"Width"=dword:0000022e
"Height"=dword:000001b2
"TotalCallCount"=dword:00000000

Here you will have to change the BDS version (15.0) to the version of your new Delphi.

In addition there are multiple entries that refer to the Delphi installation directory, e.g.:

[HKEY_CURRENT_USER\SOFTWARE\Embarcadero\BDS\15.0\GExperts-1.3\Grep\DirectoryList]
"Count"=dword:00000003
"GrepDir0"="C:\\Delphi\\DelphiXE7\\Source\\VCL"
"GrepDir1"="C:\\Delphi\\DelphiXE7\\Source\\rtl"
"GrepDir2"="C:\\Delphi\\DelphiXE7\\Source\\fmx"

or

[HKEY_CURRENT_USER\SOFTWARE\Embarcadero\BDS\15.0\GExperts-1.3\Misc]
"VCLPath"="C:\\Delphi\\DelphiXE7\\Source\\VCL\\"
"ConfigPath"="C:\\Users\\twm\\AppData\\Roaming\\GExperts\\RAD Studio XE 7\\"
"HelpFile"="D:\\source\\_sourceforge\\gexperts\\editorexpert\\GExperts.chm"
"AlphabetizeMenu"="1"
"EditorExpertsEnabled"="1"
"PlaceGxMainMenuInToolsMenu"="0"
"EditorEnhancementsEnabled"="0"
"EnableCustomFont"="0"
"HideWindowMenu"="0"
"MoveComponentMenu"="0"
"CachingPath"="C:\\Users\\twm\\AppData\\Local\\Gexperts\\RAD Studio XE 7\\"

You will have to change all these and if you get them wrong, GExperts might not work after you have imported them.

In addition, some of the experts store additional configuration files in the ConfigPath (which is configured in the last section shown above). You will also have to copy these files.

But not all is lost:
You probably know which experts you regularly use and are worth migrating the settings, so delete everything but these settings, edit them and the triple check them. That’s easier and less error prone than summarily editing all of them. Then only import the settings for these experts. Again: Don’t forget the files the experts might have stored in the configuration directory.

 Posted by on 2020-11-30 at 14:28

GExperts 1.3.17 experimental twm 2020-10-23 released

 Delphi, GExperts  Comments Off on GExperts 1.3.17 experimental twm 2020-10-23 released
Oct 232020
 

Guess what? The new GExperts release is here.

There are lots of bug fixes and a few new features in the new version.

The major new feature is the Filter Exceptions expert. Please be warned that there was a bug when developing for non-Windows targets. It might have been fixed, but I can’t test it and nobody else bothered to volunteer to test it. So there you go: Now you will be a tester, if you like it or not. If you encounter this problem, please file a bug report!

There is also a small improvement in PE Information tool (I won’t call it an expert any more because it’s now a stand alone executable that GExperts only calls.)

Also, the installer is now based on InnoSetup 5.6.1 which was the last version compatible with Windows XP. So, installing GExperts on Windows XP (VMs) should work again.

I hope this time the installers won’t be wrongly detected as malware by virus scanners. Sorry about that.

Please note that GExperts for Delphi 10.4 requires Update 1!

The new version is available for download on the GExperts download page.

If you want to discuss this article, you can do so in the corresponding post in the international Delphi Praxis forum.

 Posted by on 2020-10-23 at 18:07

Bug and possible fix for GExperts Filter Exceptions expert – testers needed

 Delphi, GExperts  Comments Off on Bug and possible fix for GExperts Filter Exceptions expert – testers needed
Sep 272020
 

Mahdi Safsafi has proposed a fix for the bug in the GExperts Filter Exceptions expert, which occurs when developing for non Windows targets (first reported on Embarcadero’s quality portal ). I have implemented this fix and it doesn’t have any adverse effects on for Windows targets. But neither he nor I can test it for non Windows targets since we don’t develop for these. That means we need testers. If you want to help, please post a comment on the bug report on SourceForge.

 Posted by on 2020-09-27 at 13:27

GExperts for Delphi 10.4.1

 Delphi, GExperts  Comments Off on GExperts for Delphi 10.4.1
Sep 052020
 

I have received a few reports about bugs in GExperts in Delphi 10.4.1 that do not occur in Delphi 10.4. Here is a GExperts DLL that was compiled with Delphi 10.4.1. Maybe it will solve some of theses problems.

Simply extract the DLL and put it into the GExperts installation directory, replacing the original one.

Let me know on Delphi Praxis whether this fixes the problems.

 Posted by on 2020-09-05 at 11:36

Filtering and sorting for the GExperts PE Information Exports list

 Delphi, GExperts  Comments Off on Filtering and sorting for the GExperts PE Information Exports list
Aug 092020
 

The GExperts PE Information tool just got a small improvement:

The Exports list can now be sorted by clicking on the column header and filtered on the export name by simply typing text.

The Escape key resets the filter.

If you want to discuss this article, you can do so in the corresponding post in the international Delphi Praxis forum.

 Posted by on 2020-08-09 at 14:44

New Filter Exceptions expert in GExperts

 Delphi, GExperts  Comments Off on New Filter Exceptions expert in GExperts
Jul 132020
 

I my last GExperts related blog post I wrote about the new “Close Exception Notification” expert which I just had added to GExperts. It was a hack that hooked the Exception Notification dialog.

This spawned a discussion in the international Delphi Praxis forum and resulted in a rewrite of the expert. It’s now called “Filter Exception” expert and instead of hooking the dialog it directly hooks into the code that shows this dialog. Thus it prevents the dialog from being shown for filtered exceptions.

I have to thank Mahdi Safsafi of Delphi Detours Library fame for the detective work that lead to to this hooking code.

In that same discussion Der schöne GĂŒnther suggested to add a project scope to the filtering. I have implemented that too.

So now the expert can filter on:

  • Project name, which is a regular expression.
  • Exception class
  • Exception message, which again is a regular expression

I have added all those exceptions that the Delphi IDE raises on every startup to my filter. It filters on the Project = “GExperts.*”, the exception classes and the messages it shows.

That means it will no longer annoy me with them while I am debugging GExperts but will still show them for other projects.

The filter details look like this:

It’s also possible to add a filter for the current debug session only, which means that it will be deleted automatically once the debug session ends.

Unfortunately hooking of the code is only available for Delphi 2005 and later. Older versions still have got to hook the Exception Notification dialog.

If you want to test this new functionality, you’ll have to compile your own dll. Try it, it’s not rocket science!

If you want to discuss this article, you can do so in the corresponding post in the international Delphi Praxis forum.

 Posted by on 2020-07-13 at 16:59