On Wed, Mar 10, 2010 at 01:58, Goktug Gokdogan <gokdo...@gmail.com> wrote: > Similarly, > BitSet.ensureCapacity
I don't think BitSet has this problem, because the bits are stored in longs, so the array can never overflow. But don't believe me - prove me wrong! > AbstractStringBuilder.expandCapacity Yup. > Vector.ensureCapacityHelper Yup. The scope of this fix is growing... > methods need to have similar checks and/or throw proper exceptions. > > By the way, I did not understand why IdentityHashMap and HashMap have > different MAXIMUM_CAPACITY and different logic to handle resize and > overflow. These two classes store their data in completely different ways. In particular, HashMap need never fail because of overflow ; Integer.MAX_VALUE buckets should be enough for anybody! Webrev regenerated. http://cr.openjdk.java.net/~martin/webrevs/openjdk7/ArrayResize/ Martin > > On Mon, Mar 8, 2010 at 8:10 PM, Martin Buchholz <marti...@google.com> wrote: >> >> [Chris or Alan, please review and file a bug] >> >> OK, guys, >> >> Here's a patch: >> >> http://cr.openjdk.java.net/~martin/webrevs/openjdk7/ArrayResize/ >> >> Martin >> >> On Fri, Mar 5, 2010 at 02:48, Kevin L. Stern <kevin.l.st...@gmail.com> >> wrote: >> > Hi Martin, >> > >> > Thank you for your reply. If I may, PriorityQueue appears to employ the >> > simple strategy that I suggested above in its grow method: >> > >> > int newCapacity = ((oldCapacity < 64)? >> > ((oldCapacity + 1) * 2): >> > ((oldCapacity / 2) * 3)); >> > if (newCapacity < 0) // overflow >> > newCapacity = Integer.MAX_VALUE; >> > >> > It might be desirable to set a common strategy for capacity increase for >> > all >> > collections. >> > >> > Regards, >> > >> > Kevin >> > >> > On Fri, Mar 5, 2010 at 3:04 AM, Martin Buchholz <marti...@google.com> >> > wrote: >> >> >> >> Hi Kevin, >> >> >> >> As you've noticed, creating objects within a factor of two of >> >> their natural limits is a good way to expose lurking bugs. >> >> >> >> I'm the one responsible for the algorithm in ArrayList. >> >> I'm a bit embarrassed, looking at that code today. >> >> We could set the array size to Integer.MAX_VALUE, >> >> but then you might hit an independent buglet in hotspot >> >> that you cannot allocate an array with Integer.MAX_VALUE >> >> elements, but Integer.MAX_VALUE - 5 (or so) works. >> >> >> >> It occurs to me that increasing the size by 50% is better done by >> >> int newCapacity = oldCapacity + (oldCapacity >> 1) + 1; >> >> >> >> I agree with the plan of setting the capacity to something near >> >> MAX_VALUE on overflow, and throw OutOfMemoryError on next resize. >> >> >> >> These bugs are not known. >> >> Chris Hegarty, could you file a bug for us? >> >> >> >> Martin >> >> >> >> On Wed, Mar 3, 2010 at 17:41, Kevin L. Stern <kevin.l.st...@gmail.com> >> >> wrote: >> >> > Greetings, >> >> > >> >> > I've noticed bugs in java.util.ArrayList, java.util.Hashtable and >> >> > java.io.ByteArrayOutputStream which arise when the capacities of the >> >> > data >> >> > structures reach a particular threshold. More below. >> >> > >> >> > When the capacity of an ArrayList reaches (2/3)*Integer.MAX_VALUE its >> >> > size >> >> > reaches its capacity and an add or an insert operation is invoked, >> >> > the >> >> > capacity is increased by only one element. Notice that in the >> >> > following >> >> > excerpt from ArrayList.ensureCapacity the new capacity is set to >> >> > (3/2) * >> >> > oldCapacity + 1 unless this value would not suffice to accommodate >> >> > the >> >> > required capacity in which case it is set to the required capacity. >> >> > If >> >> > the >> >> > current capacity is at least (2/3)*Integer.MAX_VALUE, then >> >> > (oldCapacity >> >> > * >> >> > 3)/2 + 1 overflows and resolves to a negative number resulting in the >> >> > new >> >> > capacity being set to the required capacity. The major consequence >> >> > of >> >> > this >> >> > is that each subsequent add/insert operation results in a full resize >> >> > of >> >> > the >> >> > ArrayList causing performance to degrade significantly. >> >> > >> >> > int newCapacity = (oldCapacity * 3)/2 + 1; >> >> > if (newCapacity < minCapacity) >> >> > newCapacity = minCapacity; >> >> > >> >> > Hashtable breaks entirely when the size of its backing array reaches >> >> > (1/2) * >> >> > Integer.MAX_VALUE and a rehash is necessary as is evident from the >> >> > following >> >> > excerpt from rehash. Notice that rehash will attempt to create an >> >> > array >> >> > of >> >> > negative size if the size of the backing array reaches (1/2) * >> >> > Integer.MAX_VALUE since oldCapacity * 2 + 1 overflows and resolves to >> >> > a >> >> > negative number. >> >> > >> >> > int newCapacity = oldCapacity * 2 + 1; >> >> > HashtableEntry newTable[] = new HashtableEntry[newCapacity]; >> >> > >> >> > When the capacity of the backing array in a ByteArrayOutputStream >> >> > reaches >> >> > (1/2) * Integer.MAX_VALUE its size reaches its capacity and a write >> >> > operation is invoked, the capacity of the backing array is increased >> >> > only by >> >> > the required number of elements. Notice that in the following >> >> > excerpt >> >> > from >> >> > ByteArrayOutputStream.write(int) the new backing array capacity is >> >> > set >> >> > to 2 >> >> > * buf.length unless this value would not suffice to accommodate the >> >> > required >> >> > capacity in which case it is set to the required capacity. If the >> >> > current >> >> > backing array capacity is at least (1/2) * Integer.MAX_VALUE + 1, >> >> > then >> >> > buf.length << 1 overflows and resolves to a negative number resulting >> >> > in >> >> > the >> >> > new capacity being set to the required capacity. The major >> >> > consequence >> >> > of >> >> > this, like with ArrayList, is that each subsequent write operation >> >> > results >> >> > in a full resize of the ByteArrayOutputStream causing performance to >> >> > degrade >> >> > significantly. >> >> > >> >> > int newcount = count + 1; >> >> > if (newcount > buf.length) { >> >> > buf = Arrays.copyOf(buf, Math.max(buf.length << 1, >> >> > newcount)); >> >> > } >> >> > >> >> > It is interesting to note that any statements about the amortized >> >> > time >> >> > complexity of add/insert operations, such as the one in the ArrayList >> >> > javadoc, are invalidated by the performance related bugs. One >> >> > solution >> >> > to >> >> > the above situations is to set the new capacity of the backing array >> >> > to >> >> > Integer.MAX_VALUE when the initial size calculation results in a >> >> > negative >> >> > number during a resize. >> >> > >> >> > Apologies if these bugs are already known. >> >> > >> >> > Regards, >> >> > >> >> > Kevin >> >> > >> > >> > > >
