FCL-STL TVector vs Generics.Collections TList append benchmark

[julkas]

@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;

[k1ng]

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.

[avk]

@ 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.

[julkas]

@ 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.

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

[avk]

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

[julkas]

@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.  

[ASerge]

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.

[k1ng]

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)

[avk]

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

[julkas]

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

[ASerge]

@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.

[ASerge]

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.

[avk]

@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

[ASerge]

@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.

[julkas]

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