[fpc-pascal] performance when resizing a dynamic array
Adriaan van Os
fpc at microbizz.nl
Sun Dec 4 15:48:26 CET 2016
Martin Schreiber wrote:
> On 12/04/2016 11:28 AM, Graeme Geldenhuys wrote:
>> 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
> 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>.
Adriaan van Os
More information about the fpc-pascal