[fpc-pascal] Growing dynamic arrays performance (another thing)

L L at z505.com
Tue Jul 22 08:43:39 CEST 2008


 > Is there a canonical way to reserve memory for a dynamic array?
 >
 > When there are several slowly growing dynamical arrays I encountered
 > severe
 > performance drop (probably, they tried to overlap each other many
 > times).
 >
 > Setting estimated length and navigating with extra counter inside each
 >  of them
 > (and growing by 10%+100 elements if needed) completely solved the
 > problem.
 >
 > This issue does not seem to be resolvable without manual memory
 > preserving, is
 > it possible to do it so that range checking will work and extra
 > counters won't
 > be needed?

This issue continues to pop up over and over again in history and it 
hurts me to see programmers struggle over, and over, and over again on 
this simple problem that's been solved by L505, the super hero who 
always saves the day.

It is what the "CapArray" and "CapString" were invented for

Scarce information is available on my websites, on wikis, and mailing 
lists about the idea. See google.

An initial "capacitance" is set, and a "growby" value is set.

The array grows by a fixed amount (say 100 or 200 elements) but the 
array keeps track of the "virtual length" (current elements in use) 
while also keeping track of the actual memory length (capacitance).

Right now there are scatters and fragments of code available showing a 
prototype of this algorithm using a Record and procedures.

It would be nice to develop it as a module without tying it into the 
whole RTL and having to hack the compiler to make it easy to use just 
like an ansistring. Pascal's achilles heel is probably that the really 
useful features are built in to the compiler with magic.. When things 
are implemented as classes they are ugly (free, create, nilling, memory 
leaks,  etc).

I thought about making it a stack (old borland) object with optionally 
being heap capable (pointer to object) but didn't get around to it yet, 
nor do I know if having stack objects that can also work as heap is even 
elegant. (I avoid using classes and heap so that the stack acts as my 
garbage colleector...for the same reason an Ansistring is not a class 
and is more elegant than if it was a class.. so I'd prefer if caparray 
or capstring were not just plain old classes.. but something more special).

There's also these pages:
http://c2.com/cgi/wiki?CapArray
http://c2.com/cgi/wiki?CapString

Where I once tried to convince a bunch of idiots on C2 that an array is 
dumb and that something smarter needs to be written down on paper as a 
useful data structure and algorithm. THe responses are usually something 
along the lines of:

1. already knew that, just use MemAlloc and Realloc
2. already knew that, just use SetLength.
3. no one needs this, Python is already are better
4. use a scripting language like Ruby
5. arrays are good enough. No need.

Which, of course, people are missing the entire point.

Anyway, after this problem pops up again and again people will see the 
light eventually.



More information about the fpc-pascal mailing list