dynamic arrays (was: Re: lint on V.3)

[P E Smee]

In article <14064 at bloom-beacon.MIT.EDU> scs at adam.pika.mit.edu (Steve Summit) writes:
>1. Many people feel that the allocation of the array should be
>   grown by multiplicative factors, not additive:
>
>	nalloc *= 2;
>
>   The drawback here is that you may allocate much more than you
>   need, and an intermediate allocation may fail unnecessarily,
>   so the code should probably be changed so it "backs off" and
>   tries again.  The additive approach, although it could be
>   O(n**2) in data movement for some realloc implementations, has
>   proved to be efficient enough for my uses.

It was suggested some years ago (about 15-20, I think) that growing
things like this based on the Fibonacci series provided, on average, a
better balance between the two problems of allocating too much and so
wasting space, and on the other hand allocating too little and so having
to do lots of reallocs.  Don't know if it has been seriously looked at
since.  (The Fibonacci series, if you've never heard of it, is the one
where each successive number is the sum of the two preceeding numbers,
with the 0th and 1st members defined as being 1.  So, 1, 1, 2, 3, 5, 8,
13, 21, ...)

The idea being that if your first block was 1X units long, and you needed
more, you'd realloc to 2X units, then to 3X units, then to 5X units, and
so on.  (Or looked at the other way, at the first growth you'd ADD 1X
more units, at the second growth ADD 1X more units, then ADD 2X more
units, etc.)

-- 
 Paul Smee               |    JANET: Smee at uk.ac.bristol
 Computer Centre         |   BITNET: Smee%uk.ac.bristol at ukacrl.bitnet
 University of Bristol   | Internet: Smee%uk.ac.bristol at nsfnet-relay.ac.uk
 (Phone: +44 272 303132) |     UUCP: ...!mcvax!ukc!gdr.bath.ac.uk!exspes