Growing dynamic arrays performance (another thing)

classic Classic list List threaded Threaded
1 message Options
L-9
Reply | Threaded
Open this post in threaded view
|

Growing dynamic arrays performance (another thing)

L-9
 > 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.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal