Recent

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

julkas

  • Guest
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.  
« Last Edit: July 31, 2019, 11:05:55 am by julkas »

Xor-el

  • Sr. Member
  • ****
  • Posts: 412
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #1 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.

hnb

  • Sr. Member
  • ****
  • Posts: 270
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #2 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.
« Last Edit: July 31, 2019, 11:35:16 am by hnb »
Checkout NewPascal initiative and donate beer - ready to use tuned FPC compiler + Lazarus for mORMot project

best regards,
Maciej Izak

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #3 on: July 31, 2019, 11:34:12 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 ?

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #4 on: July 31, 2019, 11:35:48 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 ?
« Last Edit: July 31, 2019, 11:37:46 am by julkas »

Thaddy

  • Hero Member
  • *****
  • Posts: 10748
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #5 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?

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #6 on: July 31, 2019, 11:53:35 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
« Last Edit: July 31, 2019, 12:12:36 pm by julkas »

ASerge

  • Hero Member
  • *****
  • Posts: 1771
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #7 on: July 31, 2019, 12:13:01 pm »
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>.

Xor-el

  • Sr. Member
  • ****
  • Posts: 412
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #8 on: July 31, 2019, 12:18:33 pm »
@Xor-el Explain why I can't compare TVector and TList ?

Thaddy and hnb just said it all.

Thaddy

  • Hero Member
  • *****
  • Posts: 10748
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #9 on: July 31, 2019, 12:24:19 pm »
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.

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #10 on: July 31, 2019, 12:32:32 pm »
In this case it is a doubly linked list internally
So Generics.Collections TList is doubly linked list ?
@Thaddy please confirm !

julkas

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

avk

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

julkas

  • Guest
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #13 on: August 04, 2019, 10:53:33 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 ...

avk

  • Sr. Member
  • ****
  • Posts: 407
    • my self-education project
Re: FCL-STL TVector vs Generics.Collections TList append benchmark
« Reply #14 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.  
« Last Edit: August 04, 2019, 11:21:51 am by avk »

 

TinyPortal © 2005-2018