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