kdelibs/kdecore

Alexander Kellett kde-optimize@mail.kde.org
Thu, 20 Mar 2003 12:12:54 +0100


On Wed, Mar 19, 2003 at 11:37:52PM +0100, Tim Jansen wrote:
> Depends on the size of the array which i don't know.. 2x is ok when you have 
> 10 entries, if you have thousands that's different.

not sure if your talking about mem usage or num of allocs,
but if you realloc by a 2x each time then you decrease the 
number of needed allocs by a huge number. 

for 1000 additions:
   1000 -> 2^10 == 10 allocs
   compared to 1000 allocs
or whatever, can't remember the maths of that ;-)
for 10 additions
   10 -> 2^4 == 3 allocs
   compared to 10

a much better answer (which is used by khtml's style realloc code for example)
is to have a sensible default. needs to calc'ed by some testing of course.
thats like 0(n log n), or whatever. i need to get my theory books out again ;-)

but anyways, as matz (iirc) pointed out a 1kb 
limit or so is really needed. or else the dropoff 
system that qt string stuff uses.

mvg,
Alex