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
_______________________________________________
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
