Very Interesting! How to use in TList<T>.Sort() ??

[tueddy]

Hello,

this is a very interesting fastcode project! I assume that this can avoid a big bottlenecks, but i'm not that generics expert. I just heavy use standard generic lists.. My question: How to use it in generic TList.Sort()? I have already made the comparer global to avoid allocation on every call. This is my code:

var //compare by ZOrder ZOrderComparer: IComparer;

begin if not Assigned(ZOrderComparer) then ZOrderComparer:= TComparer.Construct( function (const Item1, Item2 : TCustomGraphic) : integer begin Result := Item1.ZOrder - Item2.ZOrder; end );

FList.Sort(ZOrderComparer);

end;

Adding FastDefaults to uses clause bring incompatible types IComparer and TComparer I wonder how to add or use FastDefaults here?

Thanks in advance Dirk

[JBontes]

You write a class helper for TList that adds a new sort method. The issue is that the RTL uses a plain quicksort. I'm working on a faster version. That's still a work in progress. Have a look at the sorter for tarray. The tlist sorter should work in the same way.

The comparisons are a big part of the sorting runtime, hence the need for faster sorters. The other part is using a smarter sorting algorithm. Combine quicksort with insertion sort (for small partitions) and use modern variants of quicksort like 3 partition quicksort or some other flavor. Have a look at quickersort and quickersort-test.

The comparers are incompatible because I use a different approach. However I plan to make a faster version of system.generics.defaults available as well.

I can make the sort of tlist, but want to determine the best sort method first.

On 24 Jun 2015, at 22:15, tueddy notifications@github.com wrote:

Hello,

this is a very interesting fastcode project! I assume that this can avoid a big bottlenecks, but i'm not that generics expert. I just heavy use standard generic lists.. My question: How to use it in generic TList.Sort()? I have already made the comparer global to avoid allocation on every call. This is my code:

var //compare by ZOrder ZOrderComparer: IComparer;

begin if not Assigned(ZOrderComparer) then ZOrderComparer:= TComparer.Construct( function (const Item1, Item2 : TCustomGraphic) : integer begin Result := Item1.ZOrder - Item2.ZOrder; end );

FList.Sort(ZOrderComparer); end;

Adding FastDefaults to uses clause bring incompatible types IComparer and TComparer I wonder how to add or use FastDefaults here?

Thanks in advance Dirk

— Reply to this email directly or view it on GitHub.

[tueddy]

Hi,

thanks for your answer! Now i see, missing is generic classhelper for TList! But i'm unable to write such a generic thing, sorry. I made a simple benchmark using 1.) TList.Sort(IComparer) 2.) A Quicksort procedure without generics

Sorting the list without using the generic (interface based) is > 3times faster without any special tuning. This is an amazing performance boost because a have to sort large lists often. Looking forward for such a TList-helper-thing..

Best regards Dirk

[JBontes]

I've added System.Generics.FastDefaults. A dropin replacement for System.Generics.Defaults. It works exactly the same (only faster :-) . And obviously the RTL QC's are fixed.

[tueddy]

Hi,

FastDefaults compiles now without any error, that’s fine! But I cannot see any speed improvement, am I miss something? Attached is my sample project:

Sort a generic list: 1500 msec Directly use quicksort: 500 msec FastDefaults: 1500msec

Best regards Dirk

Von: JBontes [mailto:notifications@github.com] Gesendet: Samstag, 11. Juli 2015 18:33 An: JBontes/FastCode Cc: Dirk Carstensen Betreff: Re: [FastCode] Very Interesting! How to use in TList.Sort() ?? (#1)

I've added System.Generics.FastDefaults. A dropin replacement for System.Generics.Defaults. It works exactly the same (only faster :-) . And obviously the RTL QC's are fixed.

— Reply to this email directly or view it on GitHubhttps://github.com/JBontes/FastCode/issues/1#issuecomment-120637965.

[JBontes]

I don't see any attachment.

[tueddy]

I cannot add attachment here, so this is my testcode:

unit Unit5;

interface

uses System.SysUtils, System.Types, System.UITypes, System.Classes, System.Variants, FMX.Types, FMX.Controls, FMX.Forms, FMX.Graphics, FMX.Dialogs, FMX.ScrollBox, FMX.Memo, FMX.Controls.Presentation, FMX.StdCtrls;

type TForm5 = class(TForm) ButtonGenericSort: TButton; Memo1: TMemo; ButtonSortQuick: TButton; procedure ButtonGenericSortClick(Sender: TObject); procedure ButtonSortQuickClick(Sender: TObject); private { Private-Deklarationen } public { Public-Deklarationen } end;

var Form5: TForm5;

implementation

{$R *.fmx} {$T+}

uses System.Generics.Collections, System.Generics.Defaults, System.Diagnostics;

type TMyObject = class(TObject) public ID: Integer; end;

procedure TForm5.ButtonGenericSortClick(Sender: TObject); var G: TMyObject; L: TList; I: Integer; SW: TStopwatch; begin L:= TList.Create; try for I:= 0 to 1000000 do begin G:= TMyObject.Create; G.ID:= Random(1000000); L.Add(G); end; // SW:= TStopwatch.StartNew; L.Sort(TComparer.Construct( function (const Item1, Item2 : TMyObject) : integer begin Result := Item1.ID - Item2.ID; end )); Memo1.Lines.Add('Generics.Defaults: ' + IntToStr(SW.ElapsedMilliseconds)); for I:= 0 to 20 do Memo1.Lines.Add(IntToStr(L[I].ID)); finally L.Free; end; end;

type TCompareFunction = function(const L, R: TMyObject): Integer;

procedure QuickSort(const AList: TList; L, R: Integer; SCompare: TCompareFunction); var I, J, P: Integer; begin repeat I := L; J := R; P := (L + R) shr 1; repeat while SCompare(AList.List[I], AList.List[P]) < 0 do Inc(I); while SCompare(AList.List[J], AList.List[P]) > 0 do Dec(J); if I <= J then begin if I <> J then begin AList.Exchange(I, J); end; 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(AList, L, J, SCompare); L := I; until I >= R; end;

function CompareFunc(const Item1, Item2 : TMyObject) : integer; begin Result := Item1.ID - Item2.ID; end;

procedure TForm5.ButtonSortQuickClick(Sender: TObject); var G: TMyObject; L: TList; I: Integer; SW: TStopwatch; begin L:= TList.Create; try for I:= 0 to 1000000 do begin G:= TMyObject.Create; G.ID:= Random(1000000); L.Add(G); end; // SW:= TStopwatch.StartNew; QuickSort(L, 0, L.Count -1, CompareFunc); Memo1.Lines.Add('QuickSort: ' + IntToStr(SW.ElapsedMilliseconds)); for I:= 0 to 20 do Memo1.Lines.Add(IntToStr(L[I].ID)); finally L.Free; end;

end; end.

Von: JBontes [mailto:notifications@github.com] Gesendet: Sonntag, 12. Juli 2015 14:33 An: JBontes/FastCode Cc: Dirk Carstensen Betreff: Re: [FastCode] Very Interesting! How to use in TList.Sort() ?? (#1)

I don't see any attachment.

— Reply to this email directly or view it on GitHubhttps://github.com/JBontes/FastCode/issues/1#issuecomment-120718015.

[JBontes]

where’s the code that uses fastdefaults? please post that and I'll see where the problem is. note there’s little I can do to speed up the comparisons of integers. for that you need the inline comparers. also I'm working on a faster quicksort, the current one it a bit long in the tooth. it's in the string routines that the main gains are.

[tueddy]

where’s the code that uses fastdefaults? I've replaced System.Generics.Defaults with System.Generics.FastDefaults

note there’s little I can do to speed up the comparisons of integers. As far as i understand the bottleneck is ICompare interface invoke. My regular Quicksort method is 3 times faster and do the same compare method. Just avoids IComparer interface.

I assume that just replacing the generic method with System.Generics.FastDefaults speeds up the things?

Best regards Dirk

[JBontes]

Not for integers, IF I must use interfaces, the compare of integers cannot be speed up. It's just a (result:= A-B) This is why I have the inline comparers in FastDefaults.pas However that requires you to rewrite your code (Nothing comes for free).

Yes the invoke is a virtual method call, causing 2 memory lookups. An inline call just uses the registers directly.

I'm also working on a smarter sort. -- Johan

---

From: tueddy [mailto:notifications@github.com] To: JBontes/FastCode [mailto:FastCode@noreply.github.com] Cc: JBontes [mailto:johan@digitsolutions.nl] Sent: Sun, 12 Jul 2015 20:00:51 +0100 Subject: Re: [FastCode] Very Interesting! How to use in TList.Sort() ?? (#1)

where’s the code that uses fastdefaults? I've replaced System.Generics.Defaults with System.Generics.FastDefaults

note there’s little I can do to speed up the comparisons of integers. As far as i understand the bottleneck is ICompare interface invoke. My regular Quicksort method is 3 times faster and do the same compare method. Just avoids IComparer interface.

I assume that just replacing the generic method with System.Generics.FastDefaults speeds up the things?

Best regards Dirk

— Reply to this email directly or view it on GitHub.

[tueddy]

Thanks for your fast response! So i will use my quicksort and looking forward for your interesting project! Best regards Dirk