Recent

Author Topic: Choice between TList and dynamic array  (Read 1398 times)

egsuh

  • Full Member
  • ***
  • Posts: 243
Choice between TList and dynamic array
« on: August 17, 2019, 03:05:42 pm »
Hi,
This is based on my gut feeling during the programming. I do not have checked actual time consuming.

There are two ways (possibly more) to operate on variant length of items --- TList and dynamic array.
I prefer dynamic array because I do not have to take care of creating and freeing it.
But some people advise to use TList, because dynamic array may be resource consuming, especially when the list gets long.
Based on my experience, creating and freeing an object takes little bit long time.

So my principle is this:
  -  TList when the life of the list is long, and there are many members in the list
  - Dynamic array when I have to frequently create and release list with small number of list members (e.g. 5, 10, 100, etc.).

What do you think on this?

howardpc

  • Hero Member
  • *****
  • Posts: 3197
Re: Choice between TList and dynamic array
« Reply #1 on: August 17, 2019, 03:44:55 pm »
Memory allocation and deallocation takes finite time whether for objects or dynamic arrays.
You may not be aware of the deallocation time for a dynamic array within the routine that uses it, however, unless you include an explicit
Code: Pascal  [Select]
  1. SetLength(dynarray, 0);
within your routine, since otherwise the compiler inserts deallocation code for the used array which runs outside your routine.

It is true that dynamic arrays use more resources if the array is sparse, since memory is allocated for every indexed item in a dynamic array, whether the item exists or not.

Whereas lists usually allocate only a pointer for each item, and additional memory for the sparse items themselves may be very small depending on the data you are listing.
« Last Edit: August 17, 2019, 03:47:29 pm by howardpc »

julkas

  • Sr. Member
  • ****
  • Posts: 424
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: Choice between TList and dynamic array
« Reply #2 on: August 17, 2019, 03:49:06 pm »
Hi,
This is based on my gut feeling during the programming. I do not have checked actual time consuming.

There are two ways (possibly more) to operate on variant length of items --- TList and dynamic array.
I prefer dynamic array because I do not have to take care of creating and freeing it.
But some people advise to use TList, because dynamic array may be resource consuming, especially when the list gets long.
Based on my experience, creating and freeing an object takes little bit long time.

So my principle is this:
  -  TList when the life of the list is long, and there are many members in the list
  - Dynamic array when I have to frequently create and release list with small number of list members (e.g. 5, 10, 100, etc.).

What do you think on this?
TList from ... ?
Compiler version ?
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

Thaddy

  • Hero Member
  • *****
  • Posts: 9276
Re: Choice between TList and dynamic array
« Reply #3 on: August 17, 2019, 03:59:24 pm »
But some people advise to use TList, because dynamic array may be resource consuming, especially when the list gets long.
It is the other way around
lists take initially more resources (pre-allocate memory)
Whereas dynamic arrays are slow on deletion and inserting because they don't pre-allocate memory.
A list is much faster, a dynamic array uses less resources, except when it needs to insert, delete, copy: 2 X the size for every insertion or delete..

To explain, google for copy-on-write semantics.
A dynamic array grows by making a full copy, which is very slow.
« Last Edit: August 17, 2019, 05:30:13 pm by Thaddy »
also related to equus asinus.

furious programming

  • Sr. Member
  • ****
  • Posts: 354
  • I click a little.
Re: Choice between TList and dynamic array
« Reply #4 on: August 17, 2019, 05:24:09 pm »
In addition, lists (including generic lists) have convenient, high-level methods for data management. Adding and deleting data do not require (manual) copying of the memory. This makes them convenient to use and the code is readable. The only exception is the need to call the constructor and destructor, and a slight overhead when it comes to the memory used. So nothing extraordinary, nothing that would interfere with anything.

I hardly ever use dynamic arrays myself. Almost, because it doesn't always make sense to use the list.
« Last Edit: August 17, 2019, 05:27:13 pm by furious programming »
Lazarus 2.0.4 with FPC 3.0.4, Windows XP (all 32-bit)

howardpc

  • Hero Member
  • *****
  • Posts: 3197
Re: Choice between TList and dynamic array
« Reply #5 on: August 17, 2019, 10:43:40 pm »
A list is much faster, a dynamic array uses less resources, except when it needs to insert, delete, copy: 2 X the size for every insertion or delete..
A simple test does not appear to bear this assertion out.
The test program I used is given below. It is followed by typical output.
The tick counts seem reliable.I have not tested the performance of random inserts and deletes, merely allocating and filling the container, and then deallocating the memory used.
I may not be calculating the memory usages properly, however, so if someone thinks the following needs correcting, please do.
At 200,000 items the array and the list are indistinguishable in performance and memory use as far as I can see.
Code: Pascal  [Select]
  1. program ListVersusDynarray;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.   contnrs, Classes, sysutils;
  7.  
  8. type
  9.  
  10.     { TTest }
  11.  
  12.   TTest = class(TObject)
  13.   public
  14.     Number: Int64;
  15.     Float: Double;
  16.     Name: AnsiString;
  17.     constructor Create(aNumber: Int64);
  18.     function GetMemSize: PtrUInt;
  19.     end;
  20.  
  21.   TTestDynArray = array of TTest;
  22.  
  23.   function MemSizeAnsiString(const aStr: AnsiString): PtrUInt;
  24.   begin
  25.     Result := Length(aStr);
  26.     if Length(aStr) > 0 then
  27.       Inc(Result, SizeOf(Pointer)*4);
  28.   end;
  29.  
  30.   function MemSizeObjList(const aList: TFPObjectList): PtrUInt;
  31.     var
  32.         i: Integer;
  33.   begin
  34.     case Assigned(aList) of
  35.       False: Exit(0);
  36.       True: begin
  37.               Result := PtrUInt(aList.InstanceSize);
  38.               for i := 0 to aList.Count-1 do
  39.                 Inc(Result, TTest(aList[i]).GetMemSize);
  40.             end;
  41.         end;
  42.   end;
  43.  
  44.   function MemSizeTestDynarray(const anArray: TTestDynArray): PtrUInt;
  45.   var
  46.     test: TTest;
  47.   begin
  48.     Result := SizeOf(Pointer)*4;
  49.     for test in anArray do
  50.       Inc(Result, test.GetMemSize);
  51.   end;
  52.  
  53. type
  54.  
  55.   TContainerKind = (ckArray, ckList);
  56.  
  57.     { TComparer }
  58.  
  59.   TComparer = class(TObject)
  60.   private
  61.     FList: TFPObjectList;
  62.     FArray: TTestDynArray;
  63.   public
  64.     constructor Create;
  65.     function SetupTearDownTicks(itemCount: DWORD; aContainerKind: TContainerKind; out memSize: PtrUInt): DWord;
  66.     end;
  67.  
  68. { TTest }
  69.  
  70. constructor TTest.Create(aNumber: Int64);
  71. begin
  72.   Number := aNumber;
  73.   Float := aNumber;
  74.   Str(Float:14:2, Name);
  75. end;
  76.  
  77. function TTest.GetMemSize: PtrUInt;
  78. begin
  79.   Exit(PtrUInt(InstanceSize) + SizeOf(Number) + SizeOf(Float) + MemSizeAnsiString(Name));
  80. end;
  81.  
  82. { TComparer }
  83.  
  84. constructor TComparer.Create;
  85. begin
  86.   Randomize;
  87. end;
  88.  
  89. function TComparer.SetupTearDownTicks(itemCount: DWORD;
  90.         aContainerKind: TContainerKind; out memSize: PtrUInt): DWord;
  91. var
  92.   start: QWord;
  93.   i: DWord;
  94. begin
  95.   case aContainerKind of   // measure memory allocated
  96.     ckArray: begin
  97.                    SetLength(FArray, itemCount);
  98.                    for i := 0 to itemCount-1 do
  99.                      FArray[i] := TTest.Create(Random(itemCount));
  100.                memSize := MemSizeTestDynarray(FArray);
  101.                    for i := 0 to itemCount-1 do
  102.                     FArray[i].Free;
  103.                    SetLength(FArray, 0);
  104.              end;
  105.     ckList: begin
  106.                   FList := TFPObjectList.Create(True);
  107.                   FList.Capacity := itemCount;
  108.                   for i := 0 to itemCount-1 do
  109.                     FList.Add(TTest.Create(Random(itemCount)));
  110.               memSize := MemSizeObjList(FList);
  111.                   FList.Free;
  112.             end;
  113.   end;
  114.  
  115.   start := GetTickCount64;    // measure ticks elapsed for allocation/deallocation
  116.   case aContainerKind of
  117.     ckArray: begin
  118.                SetLength(FArray, itemCount);
  119.                for i := 0 to itemCount-1 do
  120.                  FArray[i] := TTest.Create(Random(itemCount));
  121.                for i := 0 to itemCount-1 do
  122.                  FArray[i].Free;
  123.                SetLength(FArray, 0);
  124.              end;
  125.     ckList:  begin
  126.                FList := TFPObjectList.Create(True);
  127.                FList.Capacity := itemCount;
  128.                for i := 0 to itemCount-1 do
  129.                  FList.Add(TTest.Create(Random(itemCount)));
  130.                FList.Free;
  131.              end;
  132.   end;
  133.   Result := GetTickCount64 - start;
  134. end;
  135.  
  136. var
  137.   comparer: TComparer;
  138.   count: DWord;
  139.     ck: TContainerKind;
  140.     i: Integer;
  141.     sz: PtrUInt;
  142.  
  143. begin
  144.   comparer := TComparer.Create;
  145.  
  146.   for i := 1 to 10 do
  147.     begin
  148.         count := i * 20000;
  149.         for ck in TContainerKind do
  150.           WriteLn('count=',count:6,' for ',ck:8,': ',comparer.SetupTearDownTicks(count, ck, sz):3,' ticks; memory used=',sz);
  151.     end;
  152.  
  153.   comparer.Free;
  154.  
  155.   ReadLn;
  156. end.
Typical output:
count= 20000 for ckArray :  26 ticks; memory used=1880032
count= 20000 for ckList  :  25 ticks; memory used=1880024
count= 40000 for ckArray :  50 ticks; memory used=3760032
count= 40000 for ckList  :  49 ticks; memory used=3760024
count= 60000 for ckArray :  75 ticks; memory used=5640032
count= 60000 for ckList  :  73 ticks; memory used=5640024
count= 80000 for ckArray :  99 ticks; memory used=7520032
count= 80000 for ckList  :  97 ticks; memory used=7520024
count=100000 for ckArray : 123 ticks; memory used=9400032
count=100000 for ckList  : 122 ticks; memory used=9400024
count=120000 for ckArray : 148 ticks; memory used=11280032
count=120000 for ckList  : 146 ticks; memory used=11280024
count=140000 for ckArray : 172 ticks; memory used=13160032
count=140000 for ckList  : 170 ticks; memory used=13160024
count=160000 for ckArray : 196 ticks; memory used=15040032
count=160000 for ckList  : 195 ticks; memory used=15040024
count=180000 for ckArray : 221 ticks; memory used=16920032
count=180000 for ckList  : 219 ticks; memory used=16920024
count=200000 for ckArray : 245 ticks; memory used=18800032
count=200000 for ckList  : 244 ticks; memory used=18800024

« Last Edit: August 17, 2019, 10:47:19 pm by howardpc »

k1ng

  • New Member
  • *
  • Posts: 36
Re: Choice between TList and dynamic array
« Reply #6 on: August 17, 2019, 11:48:09 pm »
@howardpc
FPC version?
Why don't you use a generic list?

howardpc

  • Hero Member
  • *****
  • Posts: 3197
Re: Choice between TList and dynamic array
« Reply #7 on: August 18, 2019, 10:03:03 am »
FPC version?
3.0.4, the version supplied with the latest Lazarus release
Quote
Why don't you use a generic list?
Why not indeed. On the other hand why?
Neither egsuh nor Thaddy mention generic lists. The notion of a generic list was mentioned in passing only by furious programming.
I am simply offering a simple comparison based on the OP's question.
By all means add a generic list. I doubt that the result will be significantly different either in performance or memory usage, but the proof of the pudding is in the eating, not in theoretical assertions.

julkas

  • Sr. Member
  • ****
  • Posts: 424
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: Choice between TList and dynamic array
« Reply #8 on: August 18, 2019, 11:10:49 am »
I don't know about what TList (generics.collections ?) are you talking,
but the answer is -
if you want TList functionality - use TList
else dynamic array.
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

k1ng

  • New Member
  • *
  • Posts: 36
Re: Choice between TList and dynamic array
« Reply #9 on: August 18, 2019, 12:23:56 pm »
@howardpc
It's important to mention the FPC version as there was a huge change in auto growing of lists in 3.2:
https://wiki.freepascal.org/User_Changes_3.2#TList_auto-growth  8-)

The use of generics is much more convenient and should be the preferred way in 2019! ;)

Thaddy

  • Hero Member
  • *****
  • Posts: 9276
Re: Choice between TList and dynamic array
« Reply #10 on: August 18, 2019, 12:27:52 pm »
[
Anyway you are not testing insertion and deletion, but simple access, since you use a known size. Since the underlying structure is an array, no wonder they compare.
You should at least have written it like this:
Code: Pascal  [Select]
  1.   case aContainerKind of
  2.     ckArray: begin
  3.                SetLength(FArray,0);  // test real performance if length is not known
  4.                for i := 0 to itemCount-1 do
  5.                  insert(TTest.Create(Random(itemCount)),FArray,high(FArray));
  6.                for i := 0 to itemCount-1 do
  7.                  FArray[i].Free;
  8.                SetLength(FArray, 0);
  9.              end;
  10.     ckList:  begin
  11.                FList := Tlist.Create(True);
  12.                for i := 0 to itemCount-1 do
  13.                  FList.Add(TTest.Create(Random(itemCount))); // equivalent to insert(High())
  14.                FList.Free;
  15.              end;
  16.   end;
Because that is a fair test in real-life performance and shows the list is faster. (By a lesser margin than I expected, though, although that may depend on application);

And my gut feeling is you knew that! >:D

This is the scenario Sven and I had in mind when we wrote that a list is faster.
« Last Edit: August 18, 2019, 01:28:13 pm by Thaddy »
also related to equus asinus.

julkas

  • Sr. Member
  • ****
  • Posts: 424
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: Choice between TList and dynamic array
« Reply #11 on: August 18, 2019, 02:29:03 pm »
Even with dynamic array you can implement nice and useful DS and algos.
Here my short (you can add Find func.) impl. of Binary Array Set. See -
Quote
This data structure is described in Introduction to Algorithms 2nd and 3rd editions, chapter 17 “Amortized Analysis”, problem 17-2 “Making binary search dynamic” (page 473 in the 3rd edition).
Code: Pascal  [Select]
  1. program binarrset;
  2.  
  3. {$mode DELPHI}
  4. type
  5.   TIntArray = array of Integer;
  6.  
  7.   TBinArrSet = record
  8.     Data: array of TIntArray;
  9.     (* Adds x to the Set *)
  10.     procedure Add(x: Integer);
  11.     (* Returns sorted array *)
  12.     function ToArray(): TIntArray;
  13.     procedure Release();
  14.   end;
  15.  
  16.   function Merge(const left, right: TIntArray): TIntArray;
  17.   var
  18.     i, j, k: Integer;
  19.   begin
  20.     i := Low(left);
  21.     j := Low(right);
  22.     SetLength(Result, Length(left) + Length(right));
  23.     k := Low(Result);
  24.     while (i <= High(left)) and (j <= High(right)) do
  25.     begin
  26.       if right[j] < left[i] then
  27.       begin
  28.         Result[k] := right[j];
  29.         Inc(j);
  30.       end
  31.       else
  32.       begin
  33.         Result[k] := left[i];
  34.         Inc(i);
  35.       end;
  36.       Inc(k);
  37.     end;
  38.  
  39.     while i <= High(left) do
  40.     begin
  41.       Result[k] := left[i];
  42.       Inc(i);
  43.       Inc(k);
  44.     end;
  45.     while j <= High(right) do
  46.     begin
  47.       Result[k] := right[j];
  48.       Inc(j);
  49.       Inc(k);
  50.     end;
  51.   end;
  52.  
  53.   procedure TBinArrSet.Add(x: Integer);
  54.   var
  55.     c, t: TIntArray;
  56.     i: Integer;
  57.   begin
  58.     SetLength(c, 1);
  59.     c[0] := x;
  60.     for i := Low(Data) to High(Data) do
  61.       if Data[i] = nil then
  62.       begin
  63.         Data[i] := c;
  64.         Exit;
  65.       end
  66.       else
  67.       begin
  68.         t := c;
  69.         c := Merge(t, Data[i]);
  70.         SetLength(t, 0);
  71.         Setlength(Data[i], 0);
  72.       end;
  73.     SetLength(Data, Length(Data) + 1);
  74.     Data[High(Data)] := c;
  75.   end;
  76.  
  77.   function TBinArrSet.ToArray(): TIntArray;
  78.   var
  79.     t: TIntArray;
  80.     i: Integer;
  81.   begin
  82.     SetLength(Result, 0);
  83.     for i := Low(Data) to High(Data) do
  84.     begin
  85.       t := Result;
  86.       Result := merge(t, Data[i]);
  87.       SetLength(t, 0);
  88.     end;
  89.   end;
  90.  
  91.   procedure TBinArrSet.Release();
  92.   var
  93.     i: Integer;
  94.   begin
  95.     for i := Low(Data) to High(Data) do
  96.       SetLength(Data[i], 0);
  97.     SetLength(Data, 0);
  98.   end;
  99.  
  100. var
  101.   bas: TBinArrSet;
  102.   r: TIntArray;
  103.   i: Integer;
  104.  
  105. begin
  106.   for i := 10 downto 0 do
  107.     bas.Add(i);
  108.   r := bas.ToArray;
  109.   for i := Low(r) to High(r) do
  110.     WriteLn(r[i]);
  111.   ReadLn;
  112.   bas.Release;
  113. end.
More info here - https://www.nayuki.io/page/binary-array-set
« Last Edit: August 19, 2019, 03:44:54 pm by julkas »
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

PascalDragon

  • Hero Member
  • *****
  • Posts: 700
  • Compiler Developer
Re: Choice between TList and dynamic array
« Reply #12 on: August 18, 2019, 08:44:58 pm »
Hi,
This is based on my gut feeling during the programming. I do not have checked actual time consuming.

There are two ways (possibly more) to operate on variant length of items --- TList and dynamic array.
I prefer dynamic array because I do not have to take care of creating and freeing it.
But some people advise to use TList, because dynamic array may be resource consuming, especially when the list gets long.
Based on my experience, creating and freeing an object takes little bit long time.

So my principle is this:
  -  TList when the life of the list is long, and there are many members in the list
  - Dynamic array when I have to frequently create and release list with small number of list members (e.g. 5, 10, 100, etc.).

What do you think on this?
Arrays are only really problematic if you change their amount all the time (e.g. adding single elements in a loop) as the array will need to be reallocated each time. Lists usually have some capacity so that the internal data does not need to be reallocated each time an element is added.
Internally reallocating an array uses ReAllocMem and that recently got an improvement on selected platforms. ;) (though this is only true if there is a single reference to the array as otherwise a copy will be done)

howardpc

  • Hero Member
  • *****
  • Posts: 3197
Re: Choice between TList and dynamic array
« Reply #13 on: August 19, 2019, 10:36:54 am »
Even with dynamic array you can implement nice and useful DS and algos.
Here my short (you can add Find func.) impl. of Binary Array Set.
@julkas
Thanks for pointing out this little-known data structure, which I had not encountered before.
Pascal sets are such a fundamental and useful language feature, but have the limitations of holding no more than 256 elements, and lack built-in routines for counting the number of elements present, or for listing the sorted elements, which means you have to write such routines yourself every time you need them.

The binary array set removes these limitations.  As you indicate it is fairly simple to add functions for Contains() and GetCount().  Thanks again.
Is there a generic implementation of this anywhere for Pascal?

julkas

  • Sr. Member
  • ****
  • Posts: 424
  • KISS principle / Lazarus 2.0.0 / FPC 3.0.4
Re: Choice between TList and dynamic array
« Reply #14 on: August 19, 2019, 11:50:57 am »
Is there a generic implementation of this anywhere for Pascal?
I don't know. I always use array of array Integer in my code.
C++ generic - https://www.nayuki.io/res/binary-array-set/BinaryArraySet.hpp

I lost const in my example. Fixed.
« Last Edit: August 19, 2019, 03:44:09 pm by julkas »
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;