Recent

Author Topic: FCL-STL TVector vs Generics.Collections TList append benchmark  (Read 2680 times)

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #15 on: August 04, 2019, 11:30:44 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;

k1ng

  • New Member
  • *
  • Posts: 37
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #16 on: August 04, 2019, 11:32:46 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.

avk

  • Sr. Member
  • ****
  • Posts: 411
    • my self-education project
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #17 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

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #18 on: August 04, 2019, 11:48: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;

avk

  • Sr. Member
  • ****
  • Posts: 411
    • my self-education project
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #19 on: August 04, 2019, 11:53:39 am »
I suppose (provided {$ mode delphi}) there is no difference.

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #20 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.  
« Last Edit: August 04, 2019, 12:16:09 pm by julkas »

ASerge

  • Hero Member
  • *****
  • Posts: 1784
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #21 on: August 04, 2019, 12:25:35 pm »
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

  • New Member
  • *
  • Posts: 37
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #22 on: August 04, 2019, 12:32:43 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
« Last Edit: August 04, 2019, 12:35:58 pm by k1ng »

avk

  • Sr. Member
  • ****
  • Posts: 411
    • my self-education project
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #23 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.

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #24 on: August 04, 2019, 12:39:11 pm »
Note - I cloned https://github.com/maciej-izak/generics.collections today with latest updates.

ASerge

  • Hero Member
  • *****
  • Posts: 1784
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #25 on: August 04, 2019, 12:42:58 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.

ASerge

  • Hero Member
  • *****
  • Posts: 1784
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #26 on: August 04, 2019, 12:45:44 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.

avk

  • Sr. Member
  • ****
  • Posts: 411
    • my self-education project
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #27 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
« Last Edit: August 04, 2019, 01:33:33 pm by avk »

ASerge

  • Hero Member
  • *****
  • Posts: 1784
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #28 on: August 04, 2019, 04:45:46 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.

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #29 on: August 04, 2019, 05:05:29 pm »
Any Delphi (Community) vs FP Generics.Collections bench, test?

 

TinyPortal © 2005-2018