Insert into Dynamic Array.
lazarus / 62-General

----------------------------------------------------------------------
dbannon · 2022-04-12 07:16

In recent FPC extra ways to use dynamic arrays become available,
particularly insert and delete, see
https://lists.freepascal.org/pipermail/fpc-
pascal/2018-May/053892.html  (thanks PascalDragon !)

I am a bit puzzled as to what is happening behind the scenes however. 
We all know the danger of repeated calls to setlength() but insert
seems to be able to avoid it, my experiments indicate that it does not
call setlength each time its called, instead it seems to reserve
blocks of pointers 'occasionally' and sensibly the size of those
blocks increases as the size of the array increases.

In fact, here is a table of how big those reserved blocks are ('Len'
being current length of array)-

Len     Next Reserve
0          1
2          8
9         15
25       30
57       326
383    4,820
5,203 4,744
9,946 88,340

Now, that says to me that a dynamic array variable has some hidden
meta data. It must keep track of how much extra space the array has so
it knows when to use the pre allocated space and when to allocate some
more.

My question -

Is my assessment correct ?  Does using insert on a Dynamic Array avoid
the performance issues of calling setlength each time ?   Using insert
and delete only, I should avoid setlength() ?

My test code, maybe I have it all wrong ?

Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i procedure
TestArray();var    S : TStringArray;    i : integer;    P :
qword;begin    P := qword(pointer(S));                      // thats
Nil, 0    for i := 0 to 99999 do begin        insert('blar', S, 0);  
    if P <> qword(pointer(S)) then begin          P :=
qword(pointer(S));          writeln('Pointer changed at i=' +
inttostr(i) + ' and length=' + inttostr(length(S)));        end;   
end;end;

----------------------------------------------------------------------
bytebites · 2022-04-12 09:31

qword(pointer()) is too complicated. Pchar() does the same.

----------------------------------------------------------------------
Zvoni · 2022-04-12 09:57

Having run the test, too, incl. writeln-ing the pointer, i would guess
that it's similiar to a StringList: The allocated memory grows in
chunks.
This was my Testcode:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i program
Project1;Uses SysUtils;var    S : TStringArray;    i : integer;    P :
qword;begin    P := qword(pointer(S));                      // thats
Nil, 0    for i := 0 to 19 do begin        insert('blar', S, 0);     
 //if P <> qword(pointer(S)) then begin          P :=
qword(pointer(S));          writeln('Pointer P='+Inttostr(p)+' changed
at i=' + inttostr(i) + ' and length=' + inttostr(length(S)));       
//end;    end;    Readln;end.Result:
Code: [Select]Pointer P=22873808 changed at i=0 and length=1
Pointer P=22742736 changed at i=1 and length=2
Pointer P=22742736 changed at i=2 and length=3
Pointer P=22742736 changed at i=3 and length=4
Pointer P=22742736 changed at i=4 and length=5
Pointer P=22742736 changed at i=5 and length=6
Pointer P=22742736 changed at i=6 and length=7
Pointer P=22742736 changed at i=7 and length=8
Pointer P=22742736 changed at i=8 and length=9
Pointer P=22906600 changed at i=9 and length=10
Pointer P=22906600 changed at i=10 and length=11
Pointer P=22906600 changed at i=11 and length=12
Pointer P=22906600 changed at i=12 and length=13
Pointer P=22906600 changed at i=13 and length=14
Pointer P=22906600 changed at i=14 and length=15
Pointer P=22906600 changed at i=15 and length=16
Pointer P=22906600 changed at i=16 and length=17
Pointer P=22906600 changed at i=17 and length=18
Pointer P=22906600 changed at i=18 and length=19
Pointer P=22906600 changed at i=19 and length=20
EDIT: Just found this on the Wiki-Page for SetLength
https://wiki.freepascal.org/Dynamic_array
QuoteThe procedure allocates memory for as many records of the base
type as specified, plus some management data.So at a guess, this
"management data" contains stuff like Count, Element-type, Base-
Address, reserved memory and similiar

----------------------------------------------------------------------
Warfley · 2022-04-12 10:07

The code for insert is:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i procedure
fpc_dynarray_insert(var p : pointer;source : SizeInt;data :
pointer;count : SizeInt;pti : pointer);compilerproc;  var    newhigh, 
  i : tdynarrayindex;    size : sizeint;    realp,    newp :
pdynarray;    ti : pointer;    elesize : sizeint;   
eletype,eletypemngd : pointer;  begin    if not assigned(data) or    
  (count=0) then      exit;     if assigned(p) then     
realp:=pdynarray(p-sizeof(tdynarray))    else      realp:=nil;   
newp:=realp;     { cap insert index }    if assigned(p) then     
begin        if source<0 then          source:=0        else if
source>realp^.high+1 then          source:=realp^.high+1;      end   
else      source:=0;     { skip kind and name }{$ifdef VER3_0}   
 ti:=aligntoptr(Pointer(pti)+2+PByte(pti)[1]);{$else VER3_0}   
 ti:=aligntoqword(Pointer(pti)+2+PByte(pti)[1]);{$endif VER3_0}    
elesize:=pdynarraytypedata(ti)^.elSize;   
eletype:=pdynarraytypedata(ti)^.elType2^;    { only set if type needs
initialization }    if assigned(pdynarraytypedata(ti)^.elType) then  
  eletypemngd:=pdynarraytypedata(ti)^.elType^    else     
eletypemngd:=nil;     { determine new memory size }    if assigned(p)
then      newhigh:=realp^.high+count    else      newhigh:=count-1;  
size:=elesize*(newhigh+1)+sizeof(tdynarray);     if assigned(p) then 
   begin        if realp^.refcount<>1 then          begin            {
make an unique copy }            getmem(newp,size);           
fillchar(newp^,sizeof(tdynarray),0);             { copy leading
elements }            if source>0 then             
move(p^,(pointer(newp)+sizeof(tdynarray))^,source*elesize);          
{ insert new elements }            move(data^,(pointer(newp)+sizeof(td
ynarray)+source*elesize)^,count*elesize);            { copy trailing
elements }            if realp^.high-source+1>0 then              move
((p+source*elesize)^,(pointer(newp)+sizeof(tdynarray)+(source+count)*e
lesize)^,(realp^.high-source+1)*elesize);             { increment ref.
count of managed members }            if assigned(eletypemngd) then  
          for i:=0 to newhigh do               
int_addref(pointer(newp)+sizeof(tdynarray)+elesize*i,eletypemngd);   
        { a declock(ref. count) isn't enough here }            { it
could be that the in MT environments  }            { in the mean time
the refcount was       }            { decremented                    
       }             { it is, because it doesn't really matter }     
     { if the array is now removed             }           
fpc_dynarray_clear(p,pti);          end        else          begin   
       { resize the array }            reallocmem(realp,size);       
    { p might no longer be correct }           
p:=pointer(realp)+sizeof(tdynarray);             { move the trailing
part after the inserted data }            if source<=realp^.high then 
           
move((p+source*elesize)^,(p+(source+count)*elesize)^,(realp^.high-
source+1)*elesize);             { move the inserted data to the
destination }           
move(data^,(p+source*elesize)^,count*elesize);             { increase
reference counts of inserted elements }            if
assigned(eletypemngd) then              begin                for
i:=source to source+count-1 do                 
int_addref(p+i*elesize,eletypemngd);              end;            
newp:=realp;          end;      end    else      begin        {
allocate new array }        getmem(newp,size);       
fillchar(newp^,sizeof(tdynarray),0);         { insert data }       
move(data^,(pointer(newp)+sizeof(tdynarray))^,count*elesize);        
{ increase reference counts of inserted elements }        if
assigned(eletypemngd) then          begin            for i:=0 to
count-1 do             
int_addref(pointer(newp)+sizeof(tdynarray)+i*elesize,eletypemngd);   
     end;      end;     p:=pointer(newp)+sizeof(tdynarray);   
newp^.refcount:=1;    newp^.high:=newhigh;  end;
As you can see, it always calls reallocmem for the new size (which is
exactly as large as to fit exactly one more element in). So there is
no geometric growth in the insert logic

The reason you see this is due to the behavior of the memory manager.
Which allows you growing your memory region without having to move the
elements.
As a comparison, do the same test with the c memory manager (include
cmem as very first unit) and you see:
Code: Text  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i Pointer
changed at i=0 and length=1Pointer changed at i=1 and length=2Pointer
changed at i=933 and length=934Pointer changed at i=935 and
length=936Pointer changed at i=937 and length=938Pointer changed at
i=939 and length=940Pointer changed at i=941 and length=942Pointer
changed at i=943 and length=944Pointer changed at i=945 and
length=946Pointer changed at i=947 and length=948Pointer changed at
i=949 and length=950Pointer changed at i=951 and length=952Pointer
changed at i=953 and length=954Pointer changed at i=955 and
length=956Pointer changed at i=957 and length=958Pointer changed at
i=959 and length=960[...]
So this behavior is soly dependent on the memory manager. And
therefore also probably dependent on the current state of allocations
(so called heap fragmentation). So this is not something you should
rely on. If you have an inner loop adding large amounts of elements,
build the geometric growth yourself

----------------------------------------------------------------------
howardpc · 2022-04-12 10:09

Likewise you see the difference with (and without) using heaptrc.

----------------------------------------------------------------------
Zvoni · 2022-04-12 10:14

Quote from: Warfley on April 12, 2022, 12:07:24 pmAs you can see, it
always calls reallocmem for the new size (which is exactly as large as
to fit exactly one more element in). So there is no geometric growth
in the insert logic
OK, You will have to explain that one (and i admit: I have no idea
about stuff like this. You know what curiosity did to the cat?..  )
If i read the source-code correctly, reallocmem only gets called if
realp^.refcount = 1
How is that "always calls"?

----------------------------------------------------------------------
Warfley · 2022-04-12 10:21

It is "always called" in the scenario looked at here, namely that a
single array is appended over and over.
Arrays implement lazy copy, meaning they are copied by reference, but
if they are changed, it is ensured that you are working on a unique
copy. This is ensured through the reference counter.
So when refcount is not 1, i.e. there are two arrays using the same
memory, getmem and move is called to ensure a fresh copy is created,
so only the array at hand is changed and the other reference to the
same array is unchanged. Similarly, if there is no array at the moment
that can be reallocated, a new array is created using getmem.

But as the question here was about inserting to a single array, for
this case, only the refcount=1 case is of any relevance

----------------------------------------------------------------------
Zvoni · 2022-04-12 10:44

Quote from: Warfley on April 12, 2022, 12:21:54 pmIt is "always
called" in the scenario looked at here, namely that a single array is
appended over and over.
Arrays implement lazy copy, meaning they are copied by reference, but
if they are changed, it is ensured that you are working on a unique
copy. This is ensured through the reference counter.
So when refcount is not 1, i.e. there are two arrays using the same
memory, getmem and move is called to ensure a fresh copy is created,
so only the array at hand is changed and the other reference to the
same array is unchanged. Similarly, if there is no array at the moment
that can be reallocated, a new array is created using getmem.

But as the question here was about inserting to a single array, for
this case, only the refcount=1 case is of any relevance
Ahhh, OK. Got it.
Thx.
So, basically a DynArray doesn't grow in chunks, but the Memory-
Manager knows, if it still has room left after the last/highest
element.
(EDIT: Which would be dbannons assumption, if i read it correctly)

----------------------------------------------------------------------
dbannon · 2022-04-12 10:46

Quote from: Warfley on April 12, 2022, 12:07:24 pm...
So this behavior is soly dependent on the memory manager. And
therefore also probably dependent on the current state of allocations
(so called heap fragmentation). So this is not something you should
rely on. If you have an inner loop adding large amounts of elements,
build the geometric growth yourself

Yes, you are right, cmem gives a quite different result but
interestingly, about the same time to run.

But, and this rocked me, doing setlength and then assigning in the
loop is massively faster !  160ms v 3mS type faster. So, my question
very very firmly answered.

Thanks Warfley, very useful answer, thanks Zvoni and howardpc for your
interest too !

Davo

----------------------------------------------------------------------
Warfley · 2022-04-12 11:13

Yes the C memory manager is ridiculusly fast, this is because a, it is
extremly simple, basically it does not try to be smart but simply
gives you the first memory region that is large enough to hold your
data. The standard memory manager on the other hand has much more
complex behavior, trying to group up similar sized objects. For
example:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i var  p1,
p2, p3: Pointer;begin  p1 := GetMem(4);  p2 := GetMem(70);  p3 :=
GetMem(3000);  WriteLn('p1->p2: ', p2 - p1);  WriteLn('p2->p3: ', p3 -
p2);  ReadLn;endWithout cmem:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i p1->p2:
32792p2->p3: 32808So the three memory regions are 32 kb away from each
other, so  basically the memory manager has it's own memory regions
for different orders of magnitude of sizes
With cmem:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i p1->p2:
32p2->p3: 104These are very close together, so cmem just has one
memory regions and adds the elements wherever they fit (the large jump
of 32 is because the c memory manager will not allocate memory less
than 32 bytes).

And because it is simpler, it tends to be faster as less logic has to
be executed. The second, probably more important, the c memory manager
is provided by the system libc, which is provided by you os and
extremely optimised, like special optimised versions for different CPU
versions.
Thats why even it has to do much more allocations it is still quite
fast.

But as I like to say, the best kind of work is the one you don't have
to do, so preallocating memory is usually the way to go. While it is
of course nice to just write something like:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i for i in
items do  arr += [i];The much more efficient way is to do:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i len :=
0;SetLength(arr, 32);for i in items dobegin  if len >= Length(arr)
then    SetLength(arr, Length(arr)*2);  arr[len] := i; 
Inc(len);end;SetLength(arr, len);It is much more code, but can
certainly be much more efficient

----------------------------------------------------------------------
dbannon · 2022-04-14 03:23

I thought I'd get some performance numbers. And the results were
interesting enough to be worth sharing IMHO !  Simple test code that
'adds' a small string to a dynamic array or a TstringList using both
default and cmem memory manager, linux. Between 30K and 10M times.

The code -
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i Const
Iterations = 3000000;procedure TestArrays();var    SL : TStringList; 
 SA : TStringArray;    i : integer;    Tick : qword;begin   
setlength(SA, 0);     Tick := Gettickcount64();    setlength(SA,
Iterations);    for i := 0 to Iterations-1 do begin        SA[i] :=
'blar';    end;    setlength(SA, 0);    writeln('Preallocate Array = '
+ inttostr(Gettickcount64() - Tick) + 'mS');     Tick :=
Gettickcount64();    for i := 0 to Iterations do begin       
setlength(SA, i+1);        SA[i] := 'blar';    end;    setlength(SA,
0);    writeln('Allocate Array InLoop = ' + inttostr(Gettickcount64()
- Tick) + 'mS');     Tick := Gettickcount64();    for i := 0 to
Iterations do begin        insert('blar', SA, high(SA));    end;   
setlength(SA, 0);    writeln('Insert into Array = ' +
inttostr(Gettickcount64() - Tick) + 'mS');     Tick :=
Gettickcount64();    SL := TStringList.create;    for i := 0 to
Iterations do begin        SL.Add('blar');    end;    SL.Free;   
writeln('StringList = ' + inttostr(Gettickcount64() - Tick) +
'mS');end;
cmem
Code: [Select]      Pre   InLoop  Insert  StringList
30k     1       6       7      4
100K    5      19      15      6
300K   13      35      17     10
1M     38      46      44     35
3M     62     112     127     97
10M   130     600     620    451
 Default Memory Manager
Code: [Select]      Pre   InLoop  Insert  StringList
30K     1       4       6      4
100K    4      15      15      8
300K   14,     46      24     14
1M     38     215     217     52
3M     65    1790    1855    141
10M   124   19677   19797    511
Release Mode. All numbers are mS, lower the better. Less than 30K
items challenged resolution of GetTickCount64. Note the non-linearity.
Pre = Pre allocate space in the array using setlength.
InLoop = Adjust size of Array in each iteration of loop.
Insert  = use the Insert Intrinsic that appeared in FPC3.2.0


Picking a few datapoints of interest -

In all cases, using insert or adjusting setlength in the loop was at
least 4 times slower than pre allocating for the array.

The memory manager made little difference to the Preallocated Array
model but cmem was massively faster in the Insert and In Loop Array
models for the bigger data structures. Cmem was a little faster for
the StringList too.

The PreAllocate Array was mostly faster than the StringList and often
substantially so. But remarkably, using cmem the StringList did creep
ahead slightly in the 300K to 1M items range.

If you know how big your data structure will be and don't need the
extensive features of a TStringList, a dynamic array is probably a
good choice. And, maybe, self managing the allocation is worth
consideration ?

Thanks Warfley for making me look at it properly !

Davo