Lazarus

Programming => General => Topic started by: julkas on July 31, 2019, 10:55:12 am

Title: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on July 31, 2019, 10:55:12 am

Here is my simple bench - appending LongInt to the end. TVector is winner

Code: Pascal  [Select][+][-]

1. program fclvsgc;
2. {$mode delphi}
3.  
4. uses SysUtils, Classes,
5.     gvector,
6.     Generics.Defaults, Generics.Collections;
7.  
8. type
9.   TIntVect = TVector<LongInt>;
10.  
11. var
12.   scv: TIntVect;
13.   scl: Generics.Collections.TList<LongInt>;
14.   i: LongInt;
15.   key, cnt: LongInt;
16.   start: QWord;
17.  
18. procedure PopulateVector(s: LongInt);
19. begin
20.   start := GetTickCount64();
21.   scv := TIntVect.Create;
22.   for i := 1 to s do
23.   begin
24.     key := Random(2147483647);
25.     scv.PushBack(key);
26.   end;
27.   FreeAndNil(scv);
28.   WriteLn('Vector populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.')
29. end;
30.  
31. procedure PopulateList(s: LongInt);
32. begin
33.   start := GetTickCount64();
34.   scl := Generics.Collections.TList<LongInt>.Create;
35.   for i := 1 to s do
36.   begin
37.     key := Random(2147483647);
38.     scl.Add(key);
39.   end;
40.   FreeAndNil(scl);
41.   WriteLn('List   populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.')
42. end;
43.  
44. begin
45.   cnt := 100000;
46.   PopulateVector(cnt);
47.   PopulateList(cnt);
48.   cnt := 10*cnt;
49.   PopulateVector(cnt);
50.   PopulateList(cnt);
51.   cnt := 10*cnt;
52.   PopulateVector(cnt);
53.   PopulateList(cnt);
54.   cnt := 10*cnt;
55.   PopulateVector(cnt);
56.   PopulateList(cnt);
57.   cnt := 10*cnt;
58.   PopulateVector(cnt);
59.   PopulateList(cnt);
60.   WriteLn('End.');
61.   ReadLn;
62. end.

Output -

Code: Text  [Select][+][-]

1. Vector populated - 100000 keys in 0 ticks.
2. List   populated - 100000 keys in 16 ticks.
3. Vector populated - 1000000 keys in 0 ticks.
4. List   populated - 1000000 keys in 15 ticks.
5. Vector populated - 10000000 keys in 125 ticks.
6. List   populated - 10000000 keys in 203 ticks.
7. Vector populated - 100000000 keys in 1125 ticks.
8. List   populated - 100000000 keys in 2172 ticks.
9. Vector populated - 1000000000 keys in 10531 ticks.
10. List   populated - 1000000000 keys in 20235 ticks.
11. End.
12.  

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: Xor-el on July 31, 2019, 11:23:54 am

I really do not think this is a fair comparison.
You need to compare fgl's TFPGList with generics.collections not gvector's TVector with generics.collections.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: hnb on July 31, 2019, 11:33:10 am

TList<T> has notifications and virtual methods, meanwhile TVector<T> doesn't have any virtual methods nor notifications but has many inline methods (it is "just" wrapper around dynamic array). The purpose of both collections is different.

I am sure that you should add raw dynamic array to this benchmark. I am sure that dynamic array will be the winner.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on July 31, 2019, 11:34:12 am

Quote from: Xor-el on July 31, 2019, 11:23:54 am

I really do not think this is a fair comparison.
You need to compare fgl's TFPGList with generics.collections not gvector's TVector with generics.collections.

@Xor-el Explain why I can't compare TVector and TList ?

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on July 31, 2019, 11:35:48 am

Quote from: hnb on July 31, 2019, 11:33:10 am

This benchmark has not much sense. TList<T> has notifications and virtual methods, meanwhile TVector<T> doesn't have any virtual methods nor notifications but has many inline methods (it is "just" wrapper around dynamic array). The purpose of both collections is different.

I am sure that you should add raw dynamic array to this benchmark. I am sure that dynamic array will be the winner.

what is the the purpose of TList ? When use TList and when use TVector ?

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: Thaddy on July 31, 2019, 11:45:51 am

Basics:
A list is not a vector.
A list is for  storage and retrieve. And optimized for that.
A vector is intended for calculation. And optimized for that.

Does that explain it for you?

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on July 31, 2019, 11:53:35 am

Quote from: Thaddy on July 31, 2019, 11:45:51 am

Basics:
A list is not a vector.
A list is for  storage and retrieve. And optimized for that.
A vector is intended for calculation. And optimized for that.

Does that explain it for you?

No. Can you give practical example ?
I know that TVector is C++ std::vector analog. What is analog of TList in C++ or any other language ?
I found this about Delphi - https://www.pascalgamedevelopment.com/showthread.php?5797-c-vector-delphi

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: ASerge on July 31, 2019, 12:13:01 pm

Quote from: julkas on July 31, 2019, 10:55:12 am

Here is my simple bench - appending LongInt to the end. TVector is winner

Thanks. Conclusion - if do not need additional features of TList<T> and speed is important, use TVector<T>.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: Xor-el on July 31, 2019, 12:18:33 pm

Quote from: julkas on July 31, 2019, 11:34:12 am

@Xor-el Explain why I can't compare TVector and TList ?

Thaddy and hnb just said it all.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: Thaddy on July 31, 2019, 12:24:19 pm

Quote from: julkas on July 31, 2019, 11:53:35 am

I know that TVector is C++ std::vector analog. What is analog of TList in C++ or any other language ?

A list? Basics. In this case it is a doubly linked list internally, so it has superior search, sort and insert/delete as opposed to a vector on unsorted data.
A vector assumes direction forward (or backward) in all cases.. Because of that, a vector has superior calculation if implemented correctly, but access to individual members is likely to be slower if not sequential.

In this particular case, a vector is faster indeed.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on July 31, 2019, 12:32:32 pm

Quote from: Thaddy on July 31, 2019, 12:24:19 pm

In this case it is a doubly linked list internally

So Generics.Collections TList is doubly linked list ?
@Thaddy please confirm !

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on July 31, 2019, 05:13:58 pm

I think I found main reason. I have tested only two fcl-stl classes - TVector (pushback) and TStack (push). TStack container is simple TVector object with some inline methods. It's two time slower than TVector! So may be it's Pascal generics management issue? It's wants further testing and discussion.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: avk on August 04, 2019, 10:27:37 am

@julkas, I just tried to exclude from the benchmark the time spent on data generation:

Code: Pascal  [Select][+][-]

1. program fclvsgc;
2.  
3. {$mode delphi}
4.  
5. uses
6.   SysUtils, Classes,
7.   gvector,
8.   Generics.Defaults, Generics.Collections;
9.  
10. type
11.   TVect = TVector<LongInt>;
12.   TData = array of Integer;
13.  
14. var
15.   scv: TVect;
16.   scl: Generics.Collections.TList<LongInt>;
17.   i: LongInt;
18.   cnt: LongInt;
19.   start: QWord;
20.  
21. function GenData(s: LongInt): TData;
22. var
23.   I: Integer;
24. begin
25.   SetLength(Result, s);
26.   for I := 0 to High(Result) do
27.     Result[I] := Random(2147483647);
28. end;
29.  
30. procedure PopulateVector(s: LongInt);
31. var
32.   Data: TData;
33. begin
34.   Data := GenData(s);
35.   scv := TVect.Create;
36.   start := GetTickCount64();
37.   for i in Data do
38.     scv.PushBack(i);
39.   WriteLn('Vector  populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
40.   FreeAndNil(scv);
41. end;
42.  
43. procedure PopulateList(s: LongInt);
44. var
45.   Data: TData;
46. begin
47.   Data := GenData(s);
48.   scl := Generics.Collections.TList<LongInt>.Create;
49.   start := GetTickCount64();
50.   for i in Data do
51.     scl.Add(i);
52.   WriteLn('List    populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
53.   FreeAndNil(scl);
54. end;
55.  
56. begin
57.   cnt := 100000;
58.   PopulateVector(cnt);
59.   PopulateList(cnt);
60.  
61.   cnt := 10*cnt;
62.   PopulateVector(cnt);
63.   PopulateList(cnt);
64.  
65.   cnt := 10*cnt;
66.   PopulateVector(cnt);
67.   PopulateList(cnt);
68.  
69.   cnt := 10*cnt;
70.   PopulateVector(cnt);
71.   PopulateList(cnt);
72.  
73.   cnt := 5*cnt;
74.   PopulateVector(cnt);
75.   PopulateList(cnt);
76.  
77.   WriteLn('End.');
78. end.
79.  

And I can’t confirm your conclusion, the results show another(FPC 3.3.1):

Code: Text  [Select][+][-]

1. Vector  populated - 100000 keys in 0 ticks.
2. List    populated - 100000 keys in 0 ticks.
3. Vector  populated - 1000000 keys in 0 ticks.
4. List    populated - 1000000 keys in 0 ticks.
5. Vector  populated - 10000000 keys in 172 ticks.
6. List    populated - 10000000 keys in 125 ticks.
7. Vector  populated - 100000000 keys in 2044 ticks.
8. List    populated - 100000000 keys in 1294 ticks.
9. Vector  populated - 500000000 keys in 15163 ticks.
10. List    populated - 500000000 keys in 6505 ticks.
11. End.
12.  

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on August 04, 2019, 10:53:33 am

Quote from: avk on August 04, 2019, 10:27:37 am

@julkas, I just tried to exclude from the benchmark the time spent on data generation:

Code: Pascal  [Select][+][-]

1. program fclvsgc;
2.  
3. {$mode delphi}
4.  
5. uses
6.   SysUtils, Classes,
7.   gvector,
8.   Generics.Defaults, Generics.Collections;
9.  
10. type
11.   TVect = TVector<LongInt>;
12.   TData = array of Integer;
13.  
14. var
15.   scv: TVect;
16.   scl: Generics.Collections.TList<LongInt>;
17.   i: LongInt;
18.   cnt: LongInt;
19.   start: QWord;
20.  
21. function GenData(s: LongInt): TData;
22. var
23.   I: Integer;
24. begin
25.   SetLength(Result, s);
26.   for I := 0 to High(Result) do
27.     Result[I] := Random(2147483647);
28. end;
29.  
30. procedure PopulateVector(s: LongInt);
31. var
32.   Data: TData;
33. begin
34.   Data := GenData(s);
35.   scv := TVect.Create;
36.   start := GetTickCount64();
37.   for i in Data do
38.     scv.PushBack(i);
39.   WriteLn('Vector  populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
40.   FreeAndNil(scv);
41. end;
42.  
43. procedure PopulateList(s: LongInt);
44. var
45.   Data: TData;
46. begin
47.   Data := GenData(s);
48.   scl := Generics.Collections.TList<LongInt>.Create;
49.   start := GetTickCount64();
50.   for i in Data do
51.     scl.Add(i);
52.   WriteLn('List    populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
53.   FreeAndNil(scl);
54. end;
55.  
56. begin
57.   cnt := 100000;
58.   PopulateVector(cnt);
59.   PopulateList(cnt);
60.  
61.   cnt := 10*cnt;
62.   PopulateVector(cnt);
63.   PopulateList(cnt);
64.  
65.   cnt := 10*cnt;
66.   PopulateVector(cnt);
67.   PopulateList(cnt);
68.  
69.   cnt := 10*cnt;
70.   PopulateVector(cnt);
71.   PopulateList(cnt);
72.  
73.   cnt := 5*cnt;
74.   PopulateVector(cnt);
75.   PopulateList(cnt);
76.  
77.   WriteLn('End.');
78. end.
79.  

And I can’t confirm your conclusion, the results show another(FPC 3.3.1):

Code: Text  [Select][+][-]

1. Vector  populated - 100000 keys in 0 ticks.
2. List    populated - 100000 keys in 0 ticks.
3. Vector  populated - 1000000 keys in 0 ticks.
4. List    populated - 1000000 keys in 0 ticks.
5. Vector  populated - 10000000 keys in 172 ticks.
6. List    populated - 10000000 keys in 125 ticks.
7. Vector  populated - 100000000 keys in 2044 ticks.
8. List    populated - 100000000 keys in 1294 ticks.
9. Vector  populated - 500000000 keys in 15163 ticks.
10. List    populated - 500000000 keys in 6505 ticks.
11. End.
12.  

@avk Good. But what makes so big diff ? My bench uses same logic for loop for both classes ...

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: avk on August 04, 2019, 11:05:06 am

@julkas, can you show body of your(3.0.4) version of gvector.TVector.IncreaseCapacity?
Mine(3.3.1) looks like this:

Code: Pascal  [Select][+][-]

1. procedure TVector.IncreaseCapacity();
2. const
3.   // if size is small, multiply by 2;
4.   // if size bigger but <256M, inc by 1/8*size;
5.   // otherwise inc by 1/16*size
6.   cSizeSmall = 1*1024*1024;
7.   cSizeBig = 256*1024*1024;
8. var
9.   DataSize:SizeUInt;
10. begin
11.   DataSize:=FCapacity*SizeOf(T);
12.   if FCapacity=0 then
13.     FCapacity:=4
14.   else
15.   if DataSize<cSizeSmall then
16.     FCapacity:=FCapacity*2
17.   else
18.   if DataSize<cSizeBig then
19.     FCapacity:=FCapacity+FCapacity div 8
20.   else
21.     FCapacity:=FCapacity+FCapacity div 16;
22.   SetLength(FData, FCapacity);
23. end;
24.  

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on August 04, 2019, 11:30:44 am

Quote from: avk on August 04, 2019, 11:05:06 am

@julkas, can you show body of your(3.0.4) version of gvector.TVector.IncreaseCapacity?
Mine(3.3.1) looks like this:

Code: Pascal  [Select][+][-]

1. procedure TVector.IncreaseCapacity();
2. const
3.   // if size is small, multiply by 2;
4.   // if size bigger but <256M, inc by 1/8*size;
5.   // otherwise inc by 1/16*size
6.   cSizeSmall = 1*1024*1024;
7.   cSizeBig = 256*1024*1024;
8. var
9.   DataSize:SizeUInt;
10. begin
11.   DataSize:=FCapacity*SizeOf(T);
12.   if FCapacity=0 then
13.     FCapacity:=4
14.   else
15.   if DataSize<cSizeSmall then
16.     FCapacity:=FCapacity*2
17.   else
18.   if DataSize<cSizeBig then
19.     FCapacity:=FCapacity+FCapacity div 8
20.   else
21.     FCapacity:=FCapacity+FCapacity div 16;
22.   SetLength(FData, FCapacity);
23. end;
24.  

All my tests done on Lazarus 2.0.0 / FPC 3.0.4 and Generics.Collections cloned from https://github.com/maciej-izak/generics.collections
gvector.TVector.IncreaseCapacity -

Code: Pascal  [Select][+][-]

1. procedure TVector.IncreaseCapacity();
2. begin
3.   if FCapacity=0 then
4.     FCapacity:=1
5.   else
6.     FCapacity:=FCapacity*2;
7.   SetLength(FData, FCapacity);
8. end;

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: k1ng on August 04, 2019, 11:32:46 am

Quote from: avk on August 04, 2019, 10:27:37 am

procedure PopulateList(s: LongInt);
var
  Data: TData;
begin
  Data := GenData(s);
  scl := Generics.Collections.TList<LongInt>.Create;
  start := GetTickCount64();
  for i in Data do
    scl.Add(i);
  WriteLn('List    populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
  FreeAndNil(scl);
end;

As you know the number of items to be added, you can do

Code: Pascal  [Select][+][-]

1.   scl := Generics.Collections.TList<LongInt>.Create;
2.   scl.Capacity := s;
3.   start := GetTickCount64();

That might give another performance boost.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: avk on August 04, 2019, 11:44:55 am

@ k1ng, thanks, but I'm just trying to simulate the case when the number of added items is not known in advance.

@julkas, well, that’s the reason for such a big difference. Someone has already taken care to fix the mess you discovered. :-X

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on August 04, 2019, 11:48:55 am

Quote from: avk on August 04, 2019, 11:44:55 am

@ k1ng, thanks, but I'm just trying to simulate the case when the number of added items is not known in advance.

@julkas, well, that’s the reason for such a big difference. Someone has already taken care to fix the mess you discovered. :-X

@avk Why TData = array of Integer; ?
I think - TData = array of LongInt;

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: avk on August 04, 2019, 11:53:39 am

I suppose (provided {$ mode delphi}) there is no difference.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on August 04, 2019, 12:04:46 pm

@avk Test on Win32 Vista, CPU - E2200, RAM - 3GB
Your logic (test grow factor - 5) gives -

Code: Text  [Select][+][-]

1. Vector  populated - 10000 keys in 0 ticks.
2. List    populated - 10000 keys in 0 ticks.
3. Vector  populated - 50000 keys in 0 ticks.
4. List    populated - 50000 keys in 0 ticks.
5. Vector  populated - 250000 keys in 16 ticks.
6. List    populated - 250000 keys in 15 ticks.
7. Vector  populated - 1250000 keys in 31 ticks.
8. List    populated - 1250000 keys in 32 ticks.
9. Vector  populated - 6250000 keys in 110 ticks.
10. List    populated - 6250000 keys in 187 ticks.
11. Vector  populated - 31250000 keys in 515 ticks.
12. List    populated - 31250000 keys in 1045 ticks.
13. End.
14.  

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: ASerge on August 04, 2019, 12:25:35 pm

Quote from: k1ng on August 04, 2019, 11:32:46 am

As you know the number of items to be added, you can do

Code: Pascal  [Select][+][-]

1.   scl.Capacity := s;
2.  

That might give another performance boost.

Test with this behavior (include simple array of)

Code: Pascal  [Select][+][-]

1. {$MODE OBJFPC}
2. {$APPTYPE CONSOLE}
3.  
4. uses
5.   SysUtils, gvector, Generics.Collections;
6.  
7. type
8.   TLongIntVector = specialize TVector<LongInt>;
9.   TLongIntList = specialize TList<LongInt>;
10.   TLongIntArray = specialize TArray<LongInt>;
11.   TData = TLongIntArray;
12.  
13.   TMeasureProc = procedure(const Data: TData);
14.  
15. procedure Measure(const Desc: string; Proc: TMeasureProc; const Data: TData);
16. var
17.   Start, Elapsed: QWord;
18. begin
19.   Start := GetTickCount64;
20.   Proc(Data);
21.   Elapsed := GetTickCount64 - Start;
22.   WriteLn(Desc, 'in ', Elapsed, ' ticks.');
23. end;
24.  
25. function GenData(Count: SizeInt): TData;
26. var
27.   i: SizeInt;
28. begin
29.   SetLength(Result, Count);
30.   for i := 0 to High(Result) do
31.     Result[i] := Random(MaxLongInt);
32. end;
33.  
34. procedure PopulateVector(const Data: TData);
35. var
36.   Vector: TLongIntVector;
37.   N: LongInt;
38. begin
39.   Vector := TLongIntVector.Create;
40.   try
41.     Vector.Reserve(Length(Data));
42.     for N in Data do
43.       Vector.PushBack(N);
44.   finally
45.     Vector.Free;
46.   end;
47. end;
48.  
49. procedure PopulateList(const Data: TData);
50. var
51.   List: TLongIntList;
52.   N: LongInt;
53. begin
54.   List := TLongIntList.Create;
55.   try
56.     List.Capacity := Length(Data);
57.     for N in Data do
58.       List.Add(N);
59.   finally
60.     List.Free;
61.   end;
62. end;
63.  
64. procedure PopulateArray(const Data: TData);
65. var
66.   A: TLongIntArray;
67.   i: SizeInt;
68. begin
69.   A := TLongIntArray.Create;
70.   SetLength(A, Length(Data));
71.   for i := Low(Data) to High(Data) do
72.     A[i] := Data[i]
73. end;
74.  
75. var
76.   Count: LongInt = Round(1E6);
77.   Data: TData;
78. begin
79.   repeat
80.     Count := Count * 3;
81.     Data := GenData(Count);
82.     Writeln('Populating ', Length(Data), ' keys...');
83.     Measure('    Array  ', @PopulateArray, Data);
84.     Measure('    Vector ', @PopulateVector, Data);
85.     Measure('    List   ', @PopulateList, Data);
86.   until Count >= MaxLongInt div 16;
87.   WriteLn('End.');
88.   ReadLn;
89. end.

Result (FPC 3.3.1 x64, Windows 7):

Code: Text  [Select][+][-]

1. Populating 3000000 keys...
2.     Array  in 15 ticks.
3.     Vector in 16 ticks.
4.     List   in 47 ticks.
5. Populating 9000000 keys...
6.     Array  in 15 ticks.
7.     Vector in 47 ticks.
8.     List   in 156 ticks.
9. Populating 27000000 keys...
10.     Array  in 63 ticks.
11.     Vector in 124 ticks.
12.     List   in 484 ticks.
13. Populating 81000000 keys...
14.     Array  in 203 ticks.
15.     Vector in 405 ticks.
16.     List   in 1404 ticks.
17. Populating 243000000 keys...
18.     Array  in 593 ticks.
19.     Vector in 1201 ticks.
20.     List   in 4227 ticks.
21. End.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: k1ng on August 04, 2019, 12:32:43 pm

Quote from: ASerge on August 04, 2019, 12:25:35 pm

Code: Pascal  [Select][+][-]

1. {$MODE OBJFPC}

Your code is a complete different mode, so I guess it's not comparable at all with the previous posted codes.

@julkas
Interesting that TList and TVector having the same ticks until 1250000 keys but then TList is really slower. (last line by a factor of 2) :o

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: avk on August 04, 2019, 12:35:07 pm

@ASerge, if the number of added elements is known in advance, then there’s nothing to talk about.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on August 04, 2019, 12:39:11 pm

Note - I cloned https://github.com/maciej-izak/generics.collections today with latest updates.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: ASerge on August 04, 2019, 12:42:58 pm

Quote from: avk on August 04, 2019, 12:35:07 pm

@ASerge, if the number of added elements is known in advance, then there’s nothing to talk about.

I commented out lines 41, 56 and 83 in my source, and result is:

Code: Text  [Select][+][-]

1. Populating 3000000 keys...
2.     Vector in 62 ticks.
3.     List   in 62 ticks.
4. Populating 9000000 keys...
5.     Vector in 203 ticks.
6.     List   in 187 ticks.
7. Populating 27000000 keys...
8.     Vector in 546 ticks.
9.     List   in 624 ticks.
10. Populating 81000000 keys...
11.     Vector in 1748 ticks.
12.     List   in 1684 ticks.
13. Populating 243000000 keys...
14.     Vector in 7426 ticks.
15.     List   in 5382 ticks.
16. End.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: ASerge on August 04, 2019, 12:45:44 pm

Quote from: k1ng on August 04, 2019, 12:32:43 pm

Your code is a complete different mode, so I guess it's not comparable at all with the previous posted codes.

Due to the fact that RTL is compiled in OBJFPC mode, it is more logical to test it in the same mode.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: avk on August 04, 2019, 01:07:17 pm

@ASerge, suspect you're using 3.0.4? So this is the point.

Code: Pascal  [Select][+][-]

1. program fclvsgc;
2.  
3. {$mode delphi}
4.  
5. uses
6.   SysUtils, Classes,
7.   gvector,
8.   Generics.Defaults, Generics.Collections;
9.  
10. type
11.   TVect = TVector<LongInt>;
12.   TData = array of Integer;
13.  
14. var
15.   scv: TVect;
16.   scl: Generics.Collections.TList<LongInt>;
17.   i: LongInt;
18.   cnt: LongInt;
19.   start: QWord;
20.  
21. function GenData(s: LongInt): TData;
22. var
23.   I: Integer;
24. begin
25.   SetLength(Result, s);
26.   for I := 0 to High(Result) do
27.     Result[I] := Random(2147483647);
28. end;
29.  
30. procedure PopulateVector(s: LongInt);
31. var
32.   Data: TData;
33. begin
34.   Data := GenData(s);
35.   scv := TVect.Create;
36.   scv.Reserve(s);
37.   start := GetTickCount64();
38.   for i in Data do
39.     scv.PushBack(i);
40.   WriteLn('Vector  populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
41.   FreeAndNil(scv);
42. end;
43.  
44. procedure PopulateList(s: LongInt);
45. var
46.   Data: TData;
47. begin
48.   Data := GenData(s);
49.   scl := Generics.Collections.TList<LongInt>.Create;
50.   scl.Capacity := s;
51.   start := GetTickCount64();
52.   for i in Data do
53.     scl.Add(i);
54.   WriteLn('List    populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
55.   FreeAndNil(scl);
56. end;
57.  
58. begin
59.   cnt := 100000;
60.   PopulateVector(cnt);
61.   PopulateList(cnt);
62.  
63.   cnt := 10*cnt;
64.   PopulateVector(cnt);
65.   PopulateList(cnt);
66.  
67.   cnt := 10*cnt;
68.   PopulateVector(cnt);
69.   PopulateList(cnt);
70.  
71.   cnt := 10*cnt;
72.   PopulateVector(cnt);
73.   PopulateList(cnt);
74.  
75.   cnt := 5*cnt;
76.   PopulateVector(cnt);
77.   PopulateList(cnt);
78.  
79.   WriteLn('End.');
80. end.
81.  

result:

Code: Text  [Select][+][-]

1. Vector  populated - 100000 keys in 0 ticks.
2. List    populated - 100000 keys in 0 ticks.
3. Vector  populated - 1000000 keys in 0 ticks.
4. List    populated - 1000000 keys in 15 ticks.
5. Vector  populated - 10000000 keys in 31 ticks.
6. List    populated - 10000000 keys in 78 ticks.
7. Vector  populated - 100000000 keys in 218 ticks.
8. List    populated - 100000000 keys in 670 ticks.
9. Vector  populated - 500000000 keys in 1092 ticks.
10. List    populated - 500000000 keys in 3354 ticks.
11. End.
12.  

compare with https://forum.lazarus.freepascal.org/index.php/topic,46254.msg329480.html#msg329480 (https://forum.lazarus.freepascal.org/index.php/topic,46254.msg329480.html#msg329480)

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: ASerge on August 04, 2019, 04:45:46 pm

Quote from: avk on August 04, 2019, 01:07:17 pm

@ASerge, suspect you're using 3.0.4? So this is the point.

FPC 3.3.1 rev 42572.
I use smaller values, because I have a slower processor, as you can see from the results. In addition, a large number does not fit in memory, i.e. a swap file is used, which is unacceptable for measurements.
Here is with numbers as you have:

Code: Text  [Select][+][-]

1. Populating 1000000 keys...
2.     Vector in 15 ticks.
3.     List   in 47 ticks.
4. Populating 10000000 keys...
5.     Vector in 280 ticks.
6.     List   in 344 ticks.
7. Populating 100000000 keys...
8.     Vector in 3338 ticks.
9.     List   in 3541 ticks.
10. Populating 500000000 keys...
11.     Vector in 33041 ticks.
12.     List   in 34382 ticks.
13. End.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on August 04, 2019, 05:05:29 pm

Any Delphi (Community) vs FP Generics.Collections bench, test?

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: k1ng on August 04, 2019, 05:43:37 pm

Quote from: ASerge on August 04, 2019, 12:45:44 pm

Quote from: k1ng on August 04, 2019, 12:32:43 pm

Your code is a complete different mode, so I guess it's not comparable at all with the previous posted codes.

Due to the fact that RTL is compiled in OBJFPC mode, it is more logical to test it in the same mode.

But the initial post uses $mode Delphi, so I'm sure he did that because he needs Delphi compatibility as most people do.


Delphi 10.3.2 - 32bit

Code: Text  [Select][+][-]

1. List    populated - 100000 keys in 0 ticks.
2. List    populated - 1000000 keys in 0 ticks.
3. List    populated - 10000000 keys in 47 ticks.
4. List    populated - 100000000 keys in 438 ticks.
5. -- out of memory for last combo

Delphi 10.3.2 - 64bit

Code: Text  [Select][+][-]

1. List    populated - 100000 keys in 0 ticks.
2. List    populated - 1000000 keys in 0 ticks.
3. List    populated - 10000000 keys in 47 ticks.
4. List    populated - 100000000 keys in 453 ticks.
5. List    populated - 500000000 keys in 2328 ticks.

ported code to work in Delphi:

Code: Pascal  [Select][+][-]

1. program fclvsgc;
2.  
3. {$apptype CONSOLE}
4.  
5. uses
6.   SysUtils, Classes, windows,
7.   Generics.Defaults, Generics.Collections;
8.  
9. type
10.   TData = array of Integer;
11.  
12. var
13.   scl: Generics.Collections.TList<LongInt>;
14.   i: LongInt;
15.   cnt: LongInt;
16.   start: UInt64;
17.  
18. function GenData(s: LongInt): TData;
19. var
20.   I: Integer;
21. begin
22.   SetLength(Result, s);
23.   for I := 0 to High(Result) do
24.     Result[I] := Random(2147483647);
25. end;
26.  
27. procedure PopulateList(s: LongInt);
28. var
29.   Data: TData;
30. begin
31.   Data := GenData(s);
32.   scl := Generics.Collections.TList<LongInt>.Create;
33.   scl.Capacity := s;
34.   start := GetTickCount64();
35.   for i in Data do
36.     scl.Add(i);
37.   WriteLn('List    populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
38.   FreeAndNil(scl);
39. end;
40.  
41. begin
42.   cnt := 100000;
43.   PopulateList(cnt);
44.  
45.   cnt := 10*cnt;
46.   PopulateList(cnt);
47.  
48.   cnt := 10*cnt;
49.   PopulateList(cnt);
50.  
51.   cnt := 10*cnt;
52.   PopulateList(cnt);
53.  
54.   cnt := 5*cnt;
55.   PopulateList(cnt);
56.  
57.   WriteLn('End.');
58.   readln;
59. end.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: julkas on August 04, 2019, 05:51:27 pm

Quote from: k1ng on August 04, 2019, 05:43:37 pm

Quote from: ASerge on August 04, 2019, 12:45:44 pm

Quote from: k1ng on August 04, 2019, 12:32:43 pm

Your code is a complete different mode, so I guess it's not comparable at all with the previous posted codes.

Due to the fact that RTL is compiled in OBJFPC mode, it is more logical to test it in the same mode.

But the initial post uses $mode Delphi, so I'm sure he did that because he needs Delphi compatibility as most people do.


Delphi 10.3.2 - 32bit

Code: Text  [Select][+][-]

1. List    populated - 100000 keys in 0 ticks.
2. List    populated - 1000000 keys in 0 ticks.
3. List    populated - 10000000 keys in 47 ticks.
4. List    populated - 100000000 keys in 438 ticks.
5. -- out of memory for last combo

Delphi 10.3.2 - 64bit

Code: Text  [Select][+][-]

1. List    populated - 100000 keys in 0 ticks.
2. List    populated - 1000000 keys in 0 ticks.
3. List    populated - 10000000 keys in 47 ticks.
4. List    populated - 100000000 keys in 453 ticks.
5. List    populated - 500000000 keys in 2328 ticks.

ported code to work in Delphi:

Code: Pascal  [Select][+][-]

1. program fclvsgc;
2.  
3. {$apptype CONSOLE}
4.  
5. uses
6.   SysUtils, Classes, windows,
7.   Generics.Defaults, Generics.Collections;
8.  
9. type
10.   TData = array of Integer;
11.  
12. var
13.   scl: Generics.Collections.TList<LongInt>;
14.   i: LongInt;
15.   cnt: LongInt;
16.   start: UInt64;
17.  
18. function GenData(s: LongInt): TData;
19. var
20.   I: Integer;
21. begin
22.   SetLength(Result, s);
23.   for I := 0 to High(Result) do
24.     Result[I] := Random(2147483647);
25. end;
26.  
27. procedure PopulateList(s: LongInt);
28. var
29.   Data: TData;
30. begin
31.   Data := GenData(s);
32.   scl := Generics.Collections.TList<LongInt>.Create;
33.   scl.Capacity := s;
34.   start := GetTickCount64();
35.   for i in Data do
36.     scl.Add(i);
37.   WriteLn('List    populated - ', s, ' keys in ', GetTickCount64() - start, ' ticks.');
38.   FreeAndNil(scl);
39. end;
40.  
41. begin
42.   cnt := 100000;
43.   PopulateList(cnt);
44.  
45.   cnt := 10*cnt;
46.   PopulateList(cnt);
47.  
48.   cnt := 10*cnt;
49.   PopulateList(cnt);
50.  
51.   cnt := 10*cnt;
52.   PopulateList(cnt);
53.  
54.   cnt := 5*cnt;
55.   PopulateList(cnt);
56.  
57.   WriteLn('End.');
58.   readln;
59. end.

@k1ng +1.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: avk on August 04, 2019, 06:59:22 pm

Quote from: ASerge on August 04, 2019, 04:45:46 pm

...FPC 3.3.1 rev 42572...

@ASerge, thanks, I see this.
And I just found out that on the way from 3.0.4 to 3.3.1 TVector got some dubious improvements.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: ASerge on August 04, 2019, 08:25:54 pm

Quote from: julkas on August 04, 2019, 05:05:29 pm

Any Delphi (Community) vs FP Generics.Collections bench, test?

This code:

Code: Pascal  [Select][+][-]

1. {$IFDEF FPC}
2.   {$MODE DELPHI}
3. {$ENDIF}
4. {$APPTYPE CONSOLE}
5.  
6. uses
7.   Windows, SysUtils, Generics.Collections;
8.  
9. type
10.   TLongIntList = TList<LongInt>;
11.   TLongIntArray = TArray<LongInt>;
12.   TData = TLongIntArray;
13.  
14.   TMeasureProc = procedure(const Data: TData);
15.  
16. procedure Measure(const Desc: string; Proc: TMeasureProc; const Data: TData);
17. var
18.   Start, Elapsed: UInt64;
19. begin
20.   Start := GetTickCount64;
21.   Proc(Data);
22.   Elapsed := GetTickCount64 - Start;
23.   Writeln(Desc, 'in ', Elapsed, ' ticks.');
24. end;
25.  
26. function GenData(Count: NativeInt): TData;
27. var
28.   i: NativeInt;
29. begin
30.   SetLength(Result, Count);
31.   for i := 0 to High(Result) do
32.     Result[i] := Random(MaxLongInt);
33. end;
34.  
35. procedure PopulateList(const Data: TData);
36. var
37.   List: TLongIntList;
38.   N: LongInt;
39. begin
40.   List := TLongIntList.Create;
41.   try
42. //    List.Capacity := Length(Data);
43.     for N in Data do
44.       List.Add(N);
45.   finally
46.     List.Free;
47.   end;
48. end;
49.  
50. procedure PopulateArray(const Data: TData);
51. var
52.   A: TLongIntArray;
53.   i: NativeInt;
54. begin
55.   SetLength(A, Length(Data));
56.   for i := Low(Data) to High(Data) do
57.     A[i] := Data[i]
58. end;
59.  
60. var
61.   Count: LongInt = Round(1E6);
62.   Data: TData;
63. begin
64.   repeat
65.     Count := Count * 3;
66.     Data := GenData(Count);
67.     Writeln('Populating ', Length(Data), ' keys...');
68. //    Measure('    Array  ', @PopulateArray, Data);
69.     Measure('    List   ', PopulateList, Data);
70.   until Count >= MaxLongInt div 16;
71.   WriteLn('End.');
72.   ReadLn;
73. end.

Delphi Community 10.3 x64 (Optimization on):

Code: Text  [Select][+][-]

1. Populating 3000000 keys...
2.     List   in 47 ticks.
3. Populating 9000000 keys...
4.     List   in 124 ticks.
5. Populating 27000000 keys...
6.     List   in 343 ticks.
7. Populating 81000000 keys...
8.     List   in 1139 ticks.
9. Populating 243000000 keys...
10.     List   in 3167 ticks.
11. End.

FPC 3.1.1 x64 (Optimization level 3)

Code: Text  [Select][+][-]

1. Populating 3000000 keys...
2.     List   in 78 ticks.
3. Populating 9000000 keys...
4.     List   in 203 ticks.
5. Populating 27000000 keys...
6.     List   in 624 ticks.
7. Populating 81000000 keys...
8.     List   in 1732 ticks.
9. Populating 243000000 keys...
10.     List   in 5336 ticks.
11. End.

Title: Re: FCL-STL TVector vs Generics.Collections TList append benchmark
Post by: PascalDragon on August 05, 2019, 09:27:26 am

Quote from: ASerge on August 04, 2019, 12:45:44 pm

Quote from: k1ng on August 04, 2019, 12:32:43 pm

Your code is a complete different mode, so I guess it's not comparable at all with the previous posted codes.

Due to the fact that RTL is compiled in OBJFPC mode, it is more logical to test it in the same mode.

That should only matter for parsing not for the generated code (with very small exceptions regarding type conversions and such).