Since recently there was the discussion about the QuickSort implementation in Delphi suffering from the worst case performance and possible stack overflow I looked into IntroSort (see https://en.wikipedia.org/wiki/Introsort) and the Microsoft implementation (see http://blog.teamleadnet.com/2013/08/introsort-algorithm-in-net-45-internal.html)
Since recently there was the discussion about the QuickSort implementation in Delphi suffering from the worst case performance and possible stack overflow I looked into IntroSort (see https://en.wikipedia.org/wiki/Introsort) and the Microsoft implementation (see http://blog.teamleadnet.com/2013/08/introsort-algorithm-in-net-45-internal.html)
Here is my current implementation - there might be some room of improvement (currently just testing with long array of Integer which performs approx 30% faster on random data) and only is a bit slower on reverse ordered input than the RTL implementation:
https://bitbucket.org/snippets/sglienke/64LG6b/introsort
Please let me know your feedback and improvement suggestions.
Here is my current implementation - there might be some room of improvement (currently just testing with long array of Integer which performs approx 30% faster on random data) and only is a bit slower on reverse ordered input than the RTL implementation:
https://bitbucket.org/snippets/sglienke/64LG6b/introsort
Please let me know your feedback and improvement suggestions.
/sub
ReplyDeleteI think SortThreeItems method can be improved. This uses 3 comparisons and a max of 2 permutations:
ReplyDeleteclass procedure TArray.SortThreeItems(const comparer: IComparer; left,
mid, right: Pointer);
type
PT = ^T;
var
temp: T;
begin
// find smallest element and move to 1st position
if comparer.Compare(PT(left)^, PT(mid)^) < 0 then
begin
if comparer.Compare(PT(right)^, PT(left)^) < 0 then
begin
temp := PT(left)^;
PT(left)^ := PT(right)^;
PT(right)^ := temp;
end;
end
else
begin
if comparer.Compare(PT(mid)^, PT(right)^) < 0 then
begin
temp := PT(left)^;
PT(left)^ := PT(mid)^;
PT(mid)^ := temp;
end
else
begin
temp := PT(left)^;
PT(left)^ := PT(right)^;
PT(right)^ := temp;
end;
end;
// compare the 2nd and 3rd elements and swap if needed
if comparer.Compare(PT(right)^, PT(mid)^) < 0 then
begin
temp := PT(mid)^;
PT(mid)^ := PT(right)^;
PT(right)^ := temp;
end;
end;
/sub
ReplyDelete/sub
ReplyDeleteAttila Kovacs https://github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/Array.cs#L1971
ReplyDeleteAlexandre Machado Interesting. When keeping the method inline its a bit slower but when I remove inline its noticeably faster. When using this version https://stackoverflow.com/a/31939937/587106 in theory it should be even faster but then it slows down.
ReplyDeleteAfter all back and forth at least for Integer the original version with inline performs fastest (not noticeably much but still)
Why not Timsort?
ReplyDeleteLinas Naginionis Because I said so. And because the .NET implementation is not the stock introsort but has some nice optimizations. Maybe I will try out TimSort next - I like that it is stable and pretty faster on almost and reverse sorted.
ReplyDeleteUpdate: I looked into TimSort and what worries me is the heap allocations needed as it is not inplace.
/sub
ReplyDeleteAttila Kovacs #1 I already fixed that - however I refactored a bit so High is correct now.
ReplyDelete#2 I already refactored that method and added an optimized Swap method taking var parameters, so no pointers required.
Attila Kovacs Reverse order does not suddenly become any slower. That would only happen when I change the algorithm at all which I did not. Also Swap is not using any stack except a few register pushes - in fact it is being inlined mostly. Also what about it is ugly? It is optimized to not cause unnecessary addref/release galore for strings or interfaces. If you make any claims about performance show the benchmark and the numbers please.
ReplyDeleteI just committed the latest version to the Spring4D develop branch which will be the next minor release (1.2.1)
ReplyDelete