TimSort for Delphi without Generics

[dummzeuch 1505]

As already stated in a different thread I have adapted the TimSort implementation for FreePascal I found on github to compile with Delphi 2007 (and probably earlier, but I haven't tried it).

 

The source code is licensed under the Apache License 2.0 and available in my dzlib on OSDN.

 

Note that this currently only sorts an array of integer and is still pretty rough. I'm going to refine quite a bit.

 

There seem to be only 2 (now 2.5 😉 ) TimSort implementations in Pascal / Delphi available. (According to @David Heffernan there is also one in Spring4d.), but none that does not require generics.

[dummzeuch 1505]

My implementation now uses Pseudo Templates based on include files (please note that the linked article is ancient, so take its C++ references with a grain of salt), so it should be compatible with most Delphi versions (tested with Delphi 2007 and 10.2). The source is on OSDN in my dzlib.

 

It has been tested with sorting dynamic arrays of integers and strings, but should work with anything else that does not include reference counting (so no interfaces yet). It's much slower for strings because of the special code in the MoveItems method which allows for reference counting (for strings, should also ). Unit tests are in the UnitTests\SortingTest subdirectory of dzlib.

 

The units declaring TimSort for Integer and String arrays use the above mentioned template.

 

To get the source, use SubVersion to create a working copy from http://svn.osdn.net/svnroot/dzlib-tools/dzlib/trunk

[dummzeuch 1505]

Here are some timings:

                                         sorted     reverse        half      random
          QuicksortInteger(1000000):    0.05787     0.06269    not done     0.16328
  QuickSortPlusInteger(15)(1000000):    0.04744     0.04995     0.24928     0.14548
            TimSortInteger(1000000):    0.00214     0.00252     0.00981     0.16411
           QuicksortString(1000000):    1.36692     1.00144    not done     1.16640
   QuickSortPlusString(15)(1000000):    1.38534     0.99298     0.81605     1.23809
             TimSortString(1000000):    0.06285     0.09036     0.16268     1.86726

Sorting 1 million integers or strings respectively.

 

The strings are simply generated with IntToStr for numbers 0 to 999,999 and compared with CompareStr. This means that Sorted, Reverse and half for strings is not really correct, because '10' < '2' etc. I need to fix that, but this is not too bad a dataset for sorting tests either. (I just googled  and found that apparently there are some test datasets for sorting algorithm performance. I'll have a look into that.)

 

The numbers are the time in seconds for a single run on my computer.

 

As you can see, TimSort is faster than all of them with the exception of random data, where it is still in the same ballpark.

 

The test program is in the subdirectory Tests\SortingTests.

 

Please note that with the exception of TimSort, these sorting algoritmms are not implemented for best performance but for convenience: They are abstracted from the data and use callbacks to compare and swap items. TimSort currently works directly on the data and uses a callback only for comparison, but my goal is to abstract the algorithm from the data in a similar manner, if possible.

[dummzeuch 1505]

Fixed the string order issue.

[David Heffernan 2345]

5 hours ago, dummzeuch said:

'10' < '2'

This is perfectly reasonable. Sometimes. User should be able to choose how to compare. 

 

UPDATE: Apparently I misunderstood. Please ignore. 

Edited January 15, 2021 by David Heffernan

[Delphi-Laie 4]

OK, here my "official" answer (after my PN): In my sorting animation programm "Sortierkino" there are three Pascal (Delphi) implementations of Tim sort without any generics.

 

But I'm interested in further variants of this algorithm and other sorting algorithms, sure.

Edited January 20, 2021 by Delphi-Laie

[Attila Kovacs 629]

@Delphi-Laie This is really cool man!

 

A suggestion, don't know if it's possible, when the column count is reduced it should not shrink the window width but widen the columns.

(Maybe some value would also fit in the columns.)

 

PS: if you delete the "0" in the field "Rotation" the app AV's and dies.

Edited January 20, 2021 by Attila Kovacs

[Delphi-Laie 4]

Dear Attila Kovacs, I thank you much for your attention, interest and help!

 

 

On 1/20/2021 at 11:03 PM, Attila Kovacs said:

@Delphi-Laie This is really cool man!

Did / do you mean my program or me? I'm not really. But I have worked on this program since 2009 with several thousand programming hours.

 

On 1/20/2021 at 11:03 PM, Attila Kovacs said:

A suggestion, don't know if it's possible, when the column count is reduced it should not shrink the window width but widen the columns.

(Maybe some value would also fit in the columns.)

That is entitled / justified.

 

I have shrinked for this effort und trouble (converting the x coordinates, switch to the rectangle instruction and so on) until now. Only at very few columns - necessary for pure bogo and bozo sorts, when they should finisch - is this a drawback, in my opinion. Small and moveable windows have got advantages too. Propably I'll be too lazy in the future to change my current solution. I don't know....

 

On 1/20/2021 at 11:03 PM, Attila Kovacs said:

PS: if you delete the "0" in the field "Rotation" the app AV's and dies.

Very attentive!

 

This mistake (more a Delphi property?!) I havn't not(ic)ed before. It doesn't appear at Lazarus compilats. It has got to do (or: is connected) with the fact that this is the only / single spinedit with a negative minimum value.

 

It was a fairly, no, very subtle and hidden mistake. I needed a while (more than one hour) to detect and remove it. Now a corrected version that works better is published.

 

Kindly regards,

 

Delphi-Laie

Edited January 22, 2021 by Delphi-Laie

[Tom de Neef 12]

I have just published Delphi sorting routines that ought to be similar in speed to TIMsort, for arrays of simple types, strings and objects.

The focus has been on large (10M+) real-world situations, where there is already some order in the data.

The documentation explains how to use in case you do not want generics.

The software is free: https://sourceforge.net/projects/fast-stable-sorting-in-delphi/

Hope it is of use.

[David Heffernan 2345]

3 hours ago, Tom de Neef said:

I have just published Delphi sorting routines that ought to be similar in speed to TIMsort

What algorithm? 

[Tom de Neef 12]

Read the documentation. In the core, it is merge. The selection of sub-arrays is not via a pivot but step-forward as long as ordered, from position 0 onward.

When the source is random, simple types will be sorted with QuickSort.

[David Heffernan 2345]

52 minutes ago, Tom de Neef said:

Read the documentation. In the core, it is merge. The selection of sub-arrays is not via a pivot but step-forward as long as ordered, from position 0 onward.

When the source is random, simple types will be sorted with QuickSort.

What is the advantage over Timsort?

[Tom de Neef 12]

I have no Timsort with my Delphi's. I responded because I notice that others are seeking fast stable sort routines without generics. If they have Timsort, they can asses the relative performance.

[Stefan Glienke 2002]

1 hour ago, Tom de Neef said:

If they have Timsort, they can asses the relative performance.

Just tested with some integers (where sorting stability does not matter anyway):

- for random data non generic code is slightly faster simply because they can use the comparison operators instead of doing rather costly comparer calls (even if the comparer itself is the default one) - approx 2 times

- already sorted almost identical speed

- reversed sorted data timsort is like 8 times faster

[Tom de Neef 12]

Sorting a reversed sorted array is more from the academic world than from the real world. But I have taken the hint and modified the code so that reversed input will be treated well. 

For real-world data (like sorted arrays that have been modified and need re-sorting) and for stable sorting of objects, the speed gain over Delphi's default sorting is immense. It would be nice to see some practical tests.

[David Heffernan 2345]

22 minutes ago, Tom de Neef said:

Sorting a reversed sorted array is more from the academic world than from the real world

Sorting a reversed array is 100% from the real world. In a UI where you sort by a column ascending, and then sort by the same column descending. 

[Tom de Neef 12]

You have a point. But we're talking here about arrays with millions of elements. Who cares about speed when the array is just a few thousand elements long?

My interest comes from server code where the data involves 5 million records and where, together with all the other processing, the target response time is 300 msec.

Anyway, I hope that my contribution to the community is of some value.

[Mike Torrettinni 198]

On 1/25/2021 at 2:54 PM, Tom de Neef said:

I have just published Delphi sorting routines that ought to be similar in speed to TIMsort, for arrays of simple types, strings and objects.

The focus has been on large (10M+) real-world situations, where there is already some order in the data.

The documentation explains how to use in case you do not want generics.

The software is free: https://sourceforge.net/projects/fast-stable-sorting-in-delphi/

Hope it is of use.

Interesting. Publish this as your own thread so it can bookmarked, I bookmark anything related to performance.

[Anders Melander 1784]

2 hours ago, Mike Torrettinni said:

I bookmark anything related to performance.

I thought you said that you didn't read books... 🙂

[David Heffernan 2345]

2 hours ago, Mike Torrettinni said:

I bookmark anything related to performance.

Bookmark this: https://softwareengineering.stackexchange.com/a/80092/14432

[Stano 143]

OT: There is also "unwanted" optimization. My fresh case.

Writing to JSON file. Item by item. For 86 items, it was over 7 seconds. It made me act. So I edited it and I write all the items at once.
I realized that when I close the form, I go through it and write it to JSON. So he took advantage of the change, and had everything written down at once. I don't have to wait for the form to close at once. It's immediate  In debug mode. I couldn't figure out why the forms were closing for so long.