On Jan 12, 2010, at 6:27 PM, Marvin Humphrey wrote: > Greets, > > I've been trying to understand this comment regarding ArrayUtil.getNextSize(): > > * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... > > Maybe I'm missing something, but I can't see how the formula yields such a > growth pattern: > > return (targetSize >> 3) + (targetSize < 9 ? 3 : 6) + targetSize; > > For input values of 9 or greater, all that formula does is multiply by 1.125 > and add 6. (Values enumerated below my sig.) > > The comment appears to have originated with this Python commit: > > > http://svn.python.org/view/python/trunk/Objects/listobject.c?r1=35279&r2=35280 > > I think it was wrong then, and it's wrong now.
I wondered about it too when we put it in. The pattern is not simply what it gives for a particular sequences of numbers, which is what you provided when you gave the results of 1 to 100 as input. I made the same mistake when I looked at it. Instead, the stated series assumes an increment of 1 and a re-computation only when the value is exceeded by one. So starting at 0, the size is 0. 0 => 0 0 + 1 => 4 4 + 1 => 8 8 + 1 => 16 16 + 1 => 25 25 + 1 => 35 ... So I think the copied python comment is correct but not obviously correct. The addition of 3 or 6 only helps initially, after some point it is just noise. It has the characteristic of being less aggressive with subsequent allocations. I'm not really up on whether this is best, but it is better than the doubling algorithm that it replaced. I think your suggestion that such an algorithm might contribute to fragmented memory is interesting. I wonder if C, perl and java have different issues regarding that. -- DM
