-
Enhancement
-
Resolution: Unresolved
-
P4
-
7
-
generic
-
generic
A DESCRIPTION OF THE REQUEST :
In concurrent environment the content of a collection can grow while the iterator is filling the output array in processing method toArray(). In this case a new little bigger array must be allocated. In current implementation the new array becomes 50 % bigger as the before provided array. This seems to pessimistic, so a smaller increase should be more appropriate.
JUSTIFICATION :
To big array unnecessarily waste memory resources and increase the chance to reach the maximum array size which anyway must be trimmed later.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Calculate the size for the new internal array by finishToArray() in a reasonable relation to the real collection's size, e.g. the before provided size plus twice the difference between the current size and the current collection's size().
ACTUAL -
The internal array becomes 50 % bigger than the before provided array.
---------- BEGIN SOURCE ----------
public <T> T[] toArray(T[] a) {
// Estimate size of array; be prepared to see more or fewer elements
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array.newInstance
(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
int i = 0;
while (i < r.length) {
if (!it.hasNext()) { // fewer elements than expected
if (a == r) {
a[i] = null; // null-terminate
} else if (a.length < i) {
return Arrays.copyOf(r, i);
} else {
System.arraycopy(r, 0, a, 0, Math.min(++i, a.length()); // ensure null-termination
}
return a;
}
r[i++] = (T)it.next();
}
return finishToArray(r, i, it);
}
/**
* Reallocates the array being used within toArray when the iterator
* returned more elements than expected, and finishes filling it from
* the iterator.
*
* @param r the array, replete with previously stored elements
* @param i the current index
* @param it the in-progress iterator over this collection
* @return array containing the elements in the given array, plus any
* further elements returned by the iterator, trimmed to size
*/
private <T> T[] finishToArray(T[] r, int i, Iterator<E> it) {
for (int cap = i; it.hasNext(); i++) {
if (i == cap) {
cap = secureArraySize(i, i + (Math.max(0, size() - i) << 1) + 1);
//cap = secureArraySize(i, i + (i >> 4) + 1); // alternative !
r = Arrays.copyOf(r, cap);
}
r[i] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* @param old the current size of the array
* @param size the requested size (must not be bigger than the old size)
*/
private int secureArraySize(int old, int size) {
// overflow-conscious code
assert (size <= old);
if (size - MAX_ARRAY_SIZE <= 0)
return size;
if (++old < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
return (old > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
---------- END SOURCE ----------
In concurrent environment the content of a collection can grow while the iterator is filling the output array in processing method toArray(). In this case a new little bigger array must be allocated. In current implementation the new array becomes 50 % bigger as the before provided array. This seems to pessimistic, so a smaller increase should be more appropriate.
JUSTIFICATION :
To big array unnecessarily waste memory resources and increase the chance to reach the maximum array size which anyway must be trimmed later.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Calculate the size for the new internal array by finishToArray() in a reasonable relation to the real collection's size, e.g. the before provided size plus twice the difference between the current size and the current collection's size().
ACTUAL -
The internal array becomes 50 % bigger than the before provided array.
---------- BEGIN SOURCE ----------
public <T> T[] toArray(T[] a) {
// Estimate size of array; be prepared to see more or fewer elements
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array.newInstance
(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
int i = 0;
while (i < r.length) {
if (!it.hasNext()) { // fewer elements than expected
if (a == r) {
a[i] = null; // null-terminate
} else if (a.length < i) {
return Arrays.copyOf(r, i);
} else {
System.arraycopy(r, 0, a, 0, Math.min(++i, a.length()); // ensure null-termination
}
return a;
}
r[i++] = (T)it.next();
}
return finishToArray(r, i, it);
}
/**
* Reallocates the array being used within toArray when the iterator
* returned more elements than expected, and finishes filling it from
* the iterator.
*
* @param r the array, replete with previously stored elements
* @param i the current index
* @param it the in-progress iterator over this collection
* @return array containing the elements in the given array, plus any
* further elements returned by the iterator, trimmed to size
*/
private <T> T[] finishToArray(T[] r, int i, Iterator<E> it) {
for (int cap = i; it.hasNext(); i++) {
if (i == cap) {
cap = secureArraySize(i, i + (Math.max(0, size() - i) << 1) + 1);
//cap = secureArraySize(i, i + (i >> 4) + 1); // alternative !
r = Arrays.copyOf(r, cap);
}
r[i] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* @param old the current size of the array
* @param size the requested size (must not be bigger than the old size)
*/
private int secureArraySize(int old, int size) {
// overflow-conscious code
assert (size <= old);
if (size - MAX_ARRAY_SIZE <= 0)
return size;
if (++old < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
return (old > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
---------- END SOURCE ----------
- relates to
-
JDK-7153247 Provide public method to insure secure maximum array size
-
- Open
-