### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

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

#### julkas

• Guest
##### FCL-STL TVector vs Generics.Collections TList append benchmark
« 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);
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.');
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 »

• 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 ?
« 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.

• 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 ?

#### 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
##### 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
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
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
##### 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 »