[fpc-pascal] performance when resizing a dynamic array

[Adriaan van Os]

Martin Schreiber wrote:
> On 12/04/2016 11:28 AM, Graeme Geldenhuys wrote:
>> Hi,
>>
>> If I use an array to hold a list of say Integers. Is there any serious
>> performance penalty for resizing (growing) the dynamic array as I add
>> items. My point being, I don't know the number of elements I'll need
>> beforehand.
>>
> The problem with enlarging big dynamic arrays is that AFAIK there always
> is a move operation of the whole existing data. Libc realloc() on the
> other hand only relocates the pointer of a virtual memory block if possible.

It depends on the memory manager you use, e.g. if you use the system memory manager instead of fpc.

Linux has mremap <http://man7.org/linux/man-pages/man2/mremap.2.html> which makes an efficient 
realloc possible (see the source code for malloc in glibc).

Mac OS X has no mremap but at least it can do a realloc, either in-place or by using vm_copy. The 
Mach kernel has vm_remap, but Apple is not smart enough to use it (as of OS X 10.8.5).

Windows neither has a mremap nor a realloc, which implies that on every resize a new block has to 
be allocated, with all bytes physically moved to the new location. The Windows memory manager is 
absurdly inefficient <http://www.mgroeber.de/misc/windows_heap.html>.

Because of this, it may even be fastest to execute your code twice, the first time just to know the 
number of elements of the array.

> Maybe a good old linked list implementation is the best performer then.
> Back to the Pascal of the 80's and 90's.  :) 

There is nothing 80's or 90's about intelligent and advanced data structures. Every data structure 
has its built-in limitations when it comes to speed and one should choose the right one based on 
its characteristics <http://microbizz.nl/difftrees.pdf>.

Regards,

Adriaan van Os