Wednesday, February 25, 2015

Merge Sort for Delphi

Today I was investigating a problem in TList sort order after calling the built-in Sort() method . A few objects were added to the list and then the Sort() method is called. In this specific case, happens that all objects were equally ranked, and once TList uses a Quick Sort algorithm, the order of elements in the list change, even though there is no need to sort them (they are equally ranked, so the comparison function/method always returns 0).

This is because Quick Sort algorithm is unstable, i.e. it does NOT keep the relative position of equally ranked elements within the list, after execution. Read more about sorting algorithms and stability here.
Lets see an example: We have a list containing only 3 objects. This object class (TMyObject) has a property named Key, used to sort the objects within the list. It also has another property named Index, where the original index within the list is kept:

List[0]: Key = 1, Index = 0;
List[1]: Key = 1, Index = 1;
List[2]: Key = 3, Index = 2;

The comparison function used is this:

function CompareItems(Data1, Data2: Pointer): Integer;
var
  Obj1, Obj2: TMyObject;
begin
  Obj1 := TMyObject(Data1);
  Obj2 := TMyObject(Data2);
  if Obj1.Key < Obj2.Key then
    Result := -1
  else
  if Obj1.Key > Obj2.Key then
    Result := 1
  else
    Result := 0;
end;

Using the built-in Quick Sort algorithm, your list may end like this:

List[0]: Key = 1, Index = 1;
List[1]: Key = 1, Index = 0;
List[2]: Key = 3, Index = 2;

As you can see, the Quick Sort algorithm may exchange elements 0 and 1 when sorting the list, because they both have Key = 1 (so the CompareItems() function will return 0 when comparing these elements).

This behavior of Quick Sort may or may not have some impact on your application. Well... In my specific problem, it HAS a severe impact. This is because the natural order of the list represents the creation order of the objects and I need this order to be preserved, if possible (if elements are equally ranked).

The best alternative seemed to be the Merge Sort algorithm, but I started looking for any fast and stable sorting algorithm for Delphi. Unfortunately, I found only a few and most of them were poorly implemented or required specialized data structures, like linked lists.

After digging a little more, I found an old Merge Sort implementation published in the - excellent - The Tomes of Delphi Algorithms and Data Structures book, by Julian Bucknall.

The implementation is a little old and needed some adjustments to make it run with newer versions of Delphi. In fact, I ended up with an implementation compatible with Delphi 2009 up to Delphi XE7. It probably will also run with older versions of Delphi, and newer versions as well.

Some interesting facts about all this sorting stuff:

  • Quick Sort has a worst-case running time of O(n2). On the other hand, Merge Sort does not have a worst-case scenario, and has a running time of n log n, every time.
  • Merge Sort requires an auxiliary list to do the sorting, when working with TList-like object classes. This imposes a higher memory requirement, but this is probably irrelevant nowadays.
  • The Merge Sort implementation is AS FAST AS Delphi's built-in implementation in most cases. In some cases, sorting HUGE lists with low dispersion, Merge Sort may be FASTER than Quick Sort.
  • Using this implementation to sort 1000000 items in my list I got:
    • Delphi's built-in Quick Sort:  0,38 seconds
    • Merge Sort:  0,34 seconds, i.e. more than 10% faster!
  • As already said, Merge Sort is STABLE. Under some circumstances this is important.

In the end, with all advantages of Merge Sort, I also created a TList and a TObjectList descendant redeclaring the Sort() method, using this same Merge Sort implementaion, instead of the default Quick Sort.

Download the merge sort Delphi units and test application here.

Wednesday, June 12, 2013

Why I use if MyString <> '' and not if Length(MyString) > 0 ?

1) if MyString <> '' then
2) if Length(MyString) > 0 then

Both forms are used to test whether a string is empty. Let's see what the Delphi compiler has to say:

Create a new project and add this code to it:

procedure Proc1;
var
   MyString: string;
begin
  if MyString <> '' then begin

  end;
end;

procedure Proc2;
var
  MyString: string;
begin
  if Length(MyString) > 0 then begin

  end;
end;

Put a breakpoint in front of both lines containing a if statement and run the program. When the program hits the breakpoint open the window: View -> Debug Windows - CPU Windows -> Disassembly. (I'm using Delphi XE3 here, but recent versions has the same functionality). Then we see this:

The code for the first if statement is this:

Unit1.pas.35: if MyString <> '' then begin

005ACE55 837DFC00 cmp dword ptr [ebp-$04],$00

The code for the second if statement is this:

Unit1.pas.49: if Length(MyString) > 0 then begin

005ACEF5 8B45FC mov eax,[ebp-$04]
005ACEF8 8945F4 mov [ebp-$0c],eax
005ACEFB 837DF400 cmp dword ptr [ebp-$0c],$00
005ACEFF 740B jz $005acf0c
005ACF01 8B45F4 mov eax,[ebp-$0c]
005ACF04 83E804 sub eax,$04
005ACF07 8B00 mov eax,[eax]
005ACF09 8945F4 mov [ebp-$0c],eax
005ACF0C 837DF400 cmp dword ptr [ebp-$0c],$00

One assembly instruction for the first, and five (or nine) for the second. If MyString is empty, the jump instruction (jz) will skip part of the code.

Time measures prove that the first form is faster than the second. Using Delphi XE3 (x86), if MyString is empty, the first form is slightly faster. If MyString is not empty (even 1 char in size), the first form is much faster (100% or more).





Tuesday, February 26, 2013

Why Mr. Delphi Hater should be called Mr. Dumbass Hater

Mr. Hater is a well known Delphi-related FUD spreader. From times to times some colleague or friend send me a link pointing to one of his infamous posts.
Mr. "dumbass" Hater pretends to be some kind of Delphi user defender, some kind of Batman of the Delphi community, but he turned out to be more like the Jokerman. His correspondents from the north pole, Atlantis and Bermuda triangle always send him "hot" information that he "generously" shares with us poor mortals. Unfortunately, he don't have a clue about most of the things that he intends to review or analyze. I think that positive criticisms are necessary, but what he does has nothing to do with it.

The last post that I read was this: http://delphihaters.blogspot.de/2013/01/delphi-hidden-settings.html

Some options are really funny, I must admit. The funnier part though is that Mr. Dumbass didn't publish my genuine question/comment about IntraWeb. All that I asked him was:

1) Provide me a test case where an IntraWeb application uses 2 Gb of memory without any explanation and without memory leaks caused by user code.

2) Provide me a test case where an IntraWeb application can't handle Unicode by default (HTML rendering/uploaded and downloaded file names/whatever)

3) Provide me a test case where an IntraWeb application takes forever to render a page (no need to take forever though. Just more than expected and I would be satisfied)

I'm not asking much from such a programming guru, right? But the comment wasn't approved by Mr. D. Can't you find/create such examples, Mr. D?

Another genuine question, Mr. D:
Why someone that keeps spreading FUD in the dark has a MODERATED blog??? You are blogging anonymously, so why do you want me to identify myself when adding comments to your blog?

My psychologist would say that Mr. Dumbass has some kind of complex with strange name. His crusade against IntraWeb, for instance, is more than a personal point of view. Not satisfied spreading FUD about Delphi and related products he also attacks the companies and the people behind it, what I find to be unacceptable. Probably someone really hurt Mr. Dumbass and he just can't live with that... Why don't you accept Delphi podcast invitation and tell us who did it to you, Mr. D?

PS: This is my personal point of view about the subject and is not endorsed or has nothing to do with Embarcadero, Atozed or whatever.



Wednesday, December 19, 2012

ShellExecute as administrator + Drag and Drop in Windows 7

This is a little tip that took me sometime to figure it out:
This kind of issue happened when I was debugging a IntraWeb application created with Delphi XE3 in Windows 7. I often run Delphi XE3 as local administrator. I know, I know... but sometimes it is required for proper ISAPI debugging.
This application renders a control that supports drag and drop from Windows Explorer, when the browser also supports it (Firefox, Chorme, etc.). The issue then is: When you start the browser using ShellExecute (or CreateProcess for that matter), from Delphi XE3 (or any other version or software) running with administrator credentials, the browser is also running as administrator, right? But Windows Explorer IS NOT. So, drag and drop from Windows Explorer to Firefox, for instance, won't work. Applications running with elevated privileges and applications running as regular user just won't do drag and drop... Simple, yes?

Thursday, July 12, 2012

My IntraWeb optimizations are not required anymore

Yes! If you are using the latest 12.2.6 IntraWeb version you won't need my "speed patches" anymore because IntraWeb 12.2.6 are using these same faster routines, and more! :-)

You may download the new IntraWeb 12.2.6 version from here (follow the Test Releases link)

http://www.atozed.com/IntraWeb/Download/Download.EN.aspx

Enjoy!

Sunday, April 15, 2012

Debug ISAPI extensions in Windows 7 and IIS 7.5 using Delphi XE2

Many things have changed in IIS from version 6 to 7 (and 7.5 that comes with Windows 7). If you are not familiarized with IIS 7 (and 7.5) debugging, maybe this post may help you. In fact, debugging ISAPI in Winodws 7 is easy if you follow a few steps:

Setting up IIS

First, you have to create a new application in IIS and set it up as usual. Two things are important during IIS and application setup:

1) In IIS, create the web application under Default Web Site.

2) Every application under Default Web Site should be using the same application pool, DefaultAppPool.

If you ignore these two rules, you will have additional configuration steps to run w3wp later.

Setting up the application in Delphi XE2

1) First and more important: Run Delphi XE2 as administrator! If you don't, Delphi may not be able to start the IIS Worker process (W3WP.exe).

2) In Delphi XE2 Ide, choose Run -> Parameters. Inform Host application and Parameters as you can see in the following picture:



W3WP.exe is the IIS Worker Process executable, and we will run it interactively to debug the ISAPI app. If you didn´t follow rules (1) and (2) of IIS Setup, then you will have to do additional configuration:
- Inform the web site using the parameter: -s "TheSiteId"
- Inform the application pool using the parameter: -ap "TheAppPoolName"
(This doesn't work with IIS 7 and above. The -ap parameter is not recognized by w3wp, so it's better to stay with tip (2) above)

Ready to go

Now that everything is ready, you have to stop the WWW publication service (W3SVC). You may use "net stop W3SVC" from an elevated command prompt, or use the Windows services console. Once the W3SVC is stopped, just run the application from Delphi XE2 IDE and call it from your browser. When the application is loaded all your breakpoints will be activated and you can easily debug the application.

Additional notes

I´ve found some references saying that you have to set the linking options "Map file -> Detailed" and "Include remote symbols -> On", in your project options. Well, in fact, the debuggin of ISAPI apps as explained here works perfeclty without the map file and the remote symbols.

Monday, April 9, 2012

Faster IntToStr functions for Delphi 32 bits

Last week I was trying to use the excellent "Enhanced Run time library" from A. Bouchez, in a Delphi 2006 project. Unfortunately, due copyright restrictions, the modifications are released as a code patch and for Delphi 7 only. Use all the modifications in a Delphi 2006 project is not an easy task. So I decided to use some of its code in another unit, patching the RTL original functions with new code, as I did a lot lately ;-)
The first two functions ported are faster IntToStr functions written 100% in assembly. The functions are 500 up to 1000% faster than original RTL functions, depending on the compiler (almost 1000% faster in Delphi 2006, almost 500% faster in Delphi XE2 - 32 bits). The code cannot be used in XE2 64 bit projects, because ASM 64 is a different beast. Maybe I will port other functions as well (things that don't violate copyright material), but many of them are already addressed in RtlVclOptimize (from Andreas Hausladen).
I created an unit called uCBRTLPatch.pas, containing two functions:
function FastIntToStr(Value: Integer): string;
function FastInt64ToStr(Value: Int64): string;

These functions will replace (patch) original IntToStr functions in runtime (for Integer and Int64 parameters).
To use it, you just have to add uCBRTLPatch.pas to your .DPR uses clause and you are done. You can donwload uCBRTLPatch.pas here.

Enjoy!