JDK-7153238 : (coll) Use smaller more optimistic array size increase for AbstractCollection.toArray()
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 7
  • Priority: P4
  • Status: Open
  • Resolution: Unresolved
  • OS: generic
  • CPU: generic
  • Submitted: 2012-03-12
  • Updated: 2018-09-11
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
Other
tbdUnresolved
Description
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 ----------