[fpc-pascal] performance when resizing a dynamic array

[Jürgen Hestermann]

Am 2016-12-04 um 14:09 schrieb Graeme Geldenhuys:
 > On 2016-12-04 11:30, Martin Schreiber wrote:
 >> That happens with every reallocmem() with FPC memory manager so using a
 >> getmem() block instead of a dynamic array has no advantage in this
 > Maybe a good old linked list implementation is the best performer then.
 > Back to the Pascal of the 80's and 90's. :)

I think that it's not worth the hassle to use linked lists.
Whenever I thought that it would speed up things (i.e. inserting)
I always went back to dynamic arrays because of the following:

1.) Linked lists need a lot more memory (depending on how it is linked).

2.) You cannot see the number of elements directly in linked lists
(or you need to keep track of this which can be an annoying and error prone task).

3.) With dynamic arrays you can easily pick the n-th element without having
to run through the whole list from the beginning (or end).
Sorting is much easier with an array.
It keeps code simpler in any respect.

4.) When performance is an issue (when you have *very* many elements
(millions) *and* the size of each element is much larger than the
size of a pointer) then I always use an array of pointers (to data).
Moving around elements (i.e. when sorting) then only involves moving pointers.
Of course, you need to new() each element but then the allocated data is fixed
and only the pointer needs to be moved in case of changes.
Deleting (or inserting) can be done with move:

-------------------------------------------------------------------
procedure DeleteIndexInFArray(const index      : SizeInt;
                                     var FArray : FileArrayTyp);

begin // DeleteIndexInFArray
if index<High(FArray) then
    move(FArray[index+1],
         FArray[index],
         Sizeof(FArray[index])*(High(FArray)-index));
SetLength(FArray,Length(FArray)-1);
-------------------------------------------------------------------

This way on average you move Length(FArray)/2*sizeof(pointer) bytes when
deleting (or inserting) and this with a very efficient function (move).

I love dynamic arrays and I never found that performance was an issue.