On 19-Dec-08, at 8:27 AM, Kay Kay (JIRA) wrote:
Meanwhile - w.r.t resize() - ( trade-off because increasing size a
lot would increase memory usage. increase a size by a smaller
factor would be resulting in a more frequent increases in size). I
believe reading some theory that the ideal increase factor is
somewhere close to ( 1 + 2^0.5) / 2 or something similar to that.
It should be benchmarked, but yes, a factor of two is typically more
memory wasteful than the performance it gains (you have a 50% chance
of wasting at least 1/4 of your memory, a 25% chance of wasting at
least 3/8th, etc.)
The method - ensureCapacity(capacity) in ArrayList (Java 6) also
seems to be a number along the lines ~ (1.5)
int newCapacity = (oldCapacity * 3)/2 + 1;
+1 seems to be move away from 0, and keep incrementing the count.
( Hmm .. That piece of code - in Java 6 ArrayList can definitely
make use of bitwise operators for the div-by-2 operation !!).
Let's not go crazy here guys. This relatively trivial calculation is
only called log(n) times, and certainly uses bit ops after the jit
gets its hands on it.
-Mike
