In PriorityQueue: let's result newCapacity in 0xFFFF.FFFC =-4 then "if (newCapacity - MAX_ARRAY_SIZE > 0)" ---> false then Arrays.copyOf(queue, newCapacity) ---> ArrayIndexOutOfBoundsException
Am I wrong ? 2.) Why don't you prefer a system-wide constant for MAX_ARRAY_SIZE ??? -Ulf Am 09.03.2010 03:10, schrieb Martin Buchholz:
[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<[email protected]> 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<[email protected]> 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<[email protected]> 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
