Hi everyone,

I just need to touch on the knowledge base.  What tests exist that test the functionality of rtl/inc/sortbase.pp?  As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own.

Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive).

Kit

On Thu, 24 Nov 2022 18:51:12 +0000

Some times ago I wrote a couple of merge sort routines to use in BWT, the project never goes further so they remain at level of numerical values input only.
They should have a good worst case scenario.
In the merge.pas the parameter nrm has to be false when the dimension of the array is not a power of two.
There also is a check head-tail of the blocks to move in a single pass the smaller one.
The natural.pas is recursive in the initial division in blocks and allow for adaptation for inputs already sorted.
If you find them useful, you are free to made anything you want. Marco

These are nice but don't actually use the code in rtl/inc/sortbase.pp - maybe they can be adapted though.

Kit

From experience I can tell that IntroSort is fast enough.

The main performance improvement usually comes from treating anything that is a managed type such as strings as Pointers - instead of three string assignments that cause a bunch of unnecessary atomic operations you then just have 3 pointer assignments. And with anything inside of IntroSort there are just swaps that can go without any reference counting.

Indeed.  I'm just trying to think if there's a way that that can be implemented in a cross-platform way, or if there's a wa to identify if a generic type is a pointer/managed type.

Kit

Probably not unless FPC has something similar to
https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.IsManagedType (that function among a few others is compiletime evaluated).

Stefan Glienke via fpc-devel schrieb am
Mo., 28. Nov. 2022, 00:20:

It's supported since 3.2.0: https://wiki.freepascal.org/FPC_New_Features_3.2

Regards,
Sven

And now it is also documented. Tomorrow on the daily docs...

Michael.

This is something I want to experiment with now.  Still waiting on approval of the TArrayHelper sort merge request though before I start playing around with reference counts.

Just want to clarify something... if a type is managed, can it be safely typecast to a pointer in all instances and on all platforms? (The purpose being so if I wanted to swap two items, so there's no overall change in the reference counters, I can simply swap the pointers... there's no dereferencing involved!)

Kit

J. Gareth Moreton via fpc-devel schrieb am
Mo., 28. Nov. 2022, 11:01:

No, managed does not automatically mean that it's a Pointer based type. Records with management operators, Variants and Windows WideString are managed as well.

Regards,
Sven

Well that spoils that idea!  Is there any way to determine if it's pointer-based so you can swap references instead of going through the whole penalty of creating and destroying temporary objects?

Kit

In Delphi that would be the
https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind intrinsic - I could not find that one in the 3.2.0 feature list.

Nevermind - I guess there is:
https://www.freepascal.org/docs-html/rtl/system/gettypekind.html

That could work - could be interesting to experiment with.

Kit

Stefan Glienke via fpc-devel schrieb am
Mo., 28. Nov. 2022, 12:39:

In Delphi that would be the https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind intrinsic - I could not find that one in the 3.2.0 feature list.

That one is also supported since 3.2.0, though it seems I forgot to add it to the New Features List...

Regards,
Sven

But IntroSort is already implemented in
packages/rtl-extra/src/inc/sortalgs.pp. It's just not the default sorting algorithm, because it breaks existing code that implements an incorrect comparison function. E.g. if you pass a function that returns a<b=true and b<a=true, or a<b=false and b<a=false, the behavior will change, when you change the algorithm. This even broke Lazarus, it caused it to hang on startup.

Best regards,

Nikolay

Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort.  If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour.

Kit

J. Gareth Moreton wrote

Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort.  If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour.

No-one is blaming introsort.

It's about not breaking other software that depends on the sort mechanisms provided by the RTL. They were documented as using quicksort.

Since we don't control the external functions, we cannot set introsort as the default till we know for sure that all external functions are OK with that.

We of course could do that and just tell people to fix their implementation.

But that's not very friendly. From their point of view, their function is working fine (it may well be for quicksort which was the default mechanism), and we would break it.

Michael.

Hmmm, that's a problem!  Fair enough.

Kit

J. Gareth Moreton via fpc-devel schrieb am
Di., 29. Nov. 2022, 10:09:

This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*.

Regards,
Sven

If for two elements [a, b] the comparison function returns a<b=true and b<a=true

then the problem is not in stability or any other feature of the sorting algorithm but in the comparison function indeed. Or am I missing something?

Ondrej

Ondrej Pokorny via fpc-devel schrieb am
Di., 29. Nov. 2022, 11:39:

For such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "a<b=false and b<a=false" which is the case for equal elements.

Regards,
Sven

Quicksort is not inherently stable because of what happens if a value is equal to the pivot - more specifically, which of the identical values is selected as the pivot - for example, if you try to sort a list of identical values, they will inevitably change order because each stage will move all of the values to one side of the pivot (and also cause quicksort to degenerate into O(n²)).  If you want a stable sort, you need to use things like merge sort instead.

Kit

Sven Barth wrote

For such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "a<b=false and b<a=false" which is the case for equal elements.

I assume this was some kind of typo or reasoning error because "a<b=false and b<a=false" is always the case for equal elements if the compare function is correct. And Nikolay was talking about incorrect comparison functions.

Ondrej

Where exactly can that stable quicksort be found? rtl/inc/sortbase.pp looks pretty much like standard quicksort to me.

Hi,
and the FPC implementation is actually documented to not be stable in the code:

{
QuickSort

Average performance: O(n log n)
Worst performance: O(n*n)
Extra memory use: O(log n) on the stack
Stable: no
Additional notes: Uses the middle element asthe pivot. This makes it work well also on already sorted sequences, which can occur often in practice. As expected from QuickSort, it works best on random sequencesand is usually the fastest algorithm to sort them. It is, however, possible for a malicious user to craft special sequences, which trigger its worst O(n*n)case. They can also occur in practice, although they are veryunlikely. If this is not an
acceptable risk (e.g.for high risk applications,
security-conscious applications or applications with hard real-time requirements),another sorting algorithm must be used.
}

and one can see that it is indeed not stable, if you sort ['a','b','A']  case-insensitively, it becomes ['A', 'a','b']

If you want a stable sort, you need to use things like merge sort instead.

I wanted a stable sort and implemented merge sort, and it was far too slow to be usable.

Now I use the sortbase quicksort, but sort an array of pointers to the actual array, so the compare function can compare the indices for equal elements.

Cheers,
Benito

That is not a very good IntroSort to be honest. It is missing using InsertionSort for small numbers and it does not do the median-of-3 pivot selection.

More like a variation of that: TimSort - but that's rather a beast to implement properly and efficient.

This is why I hope my own improvement to the version in TArrayHelper could be used instead:

https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334

Now that I know where Introsort is in the sortalgs.pp unit, I'll see about improving Introsort there too.

Regarding a stable sort, what does GCC's "std::stable_sort" use? https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m5s - it resembles merge sort.  (The algorithm before it in the video, "std::sort", is introsort, but it postpones doing the insertion sort until the very end, which doesn't work in practice because of caching issues)

Kit

Usually it is heapsort that is picked as alternative to quicksort if stable algo is needed.

How so? Heapsort isn't stable either.  Is there a variant I'm not aware of?

Kit

Yes, I made a mistake, due to being in a hurry, while writing this email. I meant other properties, such as:

(a<a) never being true,

if (a<b) and (b<c) then (a<c),

a<b always returning the same result for the same a and b.

Nikolay

Nikolay Nikolov wrote

if (a<b) and (b<c) then (a<c),

That's the big one that sorting algorithms rely on... the transitive law.  If that is violated, then you cannot guarantee a sorted result.

It doesn't matter if (a < b) or (b < a) return False for equal elements, or use (a <=b) or (b <= a) instead, as long as it's consistent.  Also have to watch out for more subtle instances of it, like "if (a < b) then DoX else DoY;" and then having "if (b < a) then DoZ else DoQ;".

While I do wish people would fix any bugs that are found in their own code, sometimes we do have to accept that this isn't always possible.  I think the most famous example I can think of is with SimCity 2000... there was a critical bug in it where memory was used after it was deallocated.  Under DOS and Windows 3.1, this wasn't an issue because the memory wouldn't be reused by another application, but under Windows 95 this assumption could no longer hold.  So, under the guidance of Raymond Chen, Microsoft programmed Windows 95 to delay actually releasing that block of memory... only for SimCity 2000!

Kit

Yes. Horrible. :)

Another example is Quake 2 or 3 (I forgot which one) having a buffer overflow vulnerability, because of copying (strcpy) the OpenGL extensions string to a C fixed size buffer (char buf[1024] or something like that). After a certain point, OpenGL video cards became so advanced and got so many extensions, that the string, returned by the graphics card simply became too long for that buffer, thus causing Quake to crash instantly on startup. But since nobody wants to buy a video card, that doesn't run Quake, graphics card vendors had to implement a hack - the detect the Quake .exe and report a different, shorter, extensions string.

Nikolay

On Tue, 29 Nov 2022 15:54:03 +0100
Benito van der Zander via fpc-devel

If the current QuickSort is not stable, is there an another argument for keeping it as default?

Mattias

Familarity mostly.  More people are familiar with quicksort than introsort.  Are there any explicit code examples where quicksort succeeds and introsort fails?  I'm told even Lazarus crashes (or used to crash), so I'll be interested to see what code causes (or caused) it.

If the pivot is one of the values with a duplicate key, then there is a chance that the other identical values will change order, and I don't think there's a fast away to avoid this situation.  But if needs be, here's a worked example to show quicksort is not stable, say our data is:

3 2 1 4a 4b 4c 7 5 6

Choosing the median of three gives us 4b.  Assuming we're using an "(a < b) = True" comparison to put items into the left partition:

[3 2 1 *4b* 4a 4c 7 5 6]

Recursing:

[1 *2* 3] 4b [4a 4c 5 *6* 7]

1 2 3 4b [*4c* 4a 5] 6 7  (The pivot choice here depends on the order of checking the three values... here it's doing "l < m" (False), "m < r" (True) then "l < r" (True))

1 2 3 4b 4c 4a 5 6 7

Thus, the middle items are not in the same order.

Kit

On Tue, 29 Nov 2022 23:57:14 +0000
"J. Gareth Moreton via fpc-devel"

+1

[...]

Mattias

J. Gareth Moreton wrote

Familarity mostly.  More people are familiar with quicksort than introsort. Are there any explicit code examples where quicksort succeeds and introsort fails?  I'm told even Lazarus crashes (or used to crash), so I'll be interested to see what code causes (or caused) it.

IIRC, Lazarus had a comparison function that returned a<a = false, which caused an infinite loop, not a crash. I don't remember the details, you should examine the source control history. The problem was fixed a long time ago in Lazarus, however it was decided not to change the default algorithm, but rather provide a plugable mechanism for changing the algorithm, hence the sortalgs unit provides several different options. FPC developers didn't want to have the bug tracker be filled with bug reports, caused by that (people would first assume it's a bug in the new FPC version if their code fails on a new FPC version, but works in the previous version).

Nikolay

Sorry, I meant to say a<a = true.

Nikolay