ArrayList.ensureCapacity should expand the default capacity empty array

[Alex Foster]

Hi,


I think that ensureCapacity should actually ensure the capacity by expanding the default capacity empty array, otherwise you could end up with a situation like this:

        List<ArrayList<Object>> ls = getLists();// Large list of ArrayLists
        ls.forEach(l -> l.ensureCapacity(10));
        //later...
        ArrayList<Object> a = ls.get(0);
        if(a.size() < 10) a.add(null); // throws OutOfMemoryError when array is allocated

I think it's still OK to not allocate the array directly in the no-arg constructor because if users actually care about the capacity they can call the constructor with an initialCapacity argument or ensureCapacity, but maybe a note should be added that it can be allocated lazily?

Also it's debatable if ensureCapacity should call grow or just resize the array to exactly the minCapacity argument, which might save space if the exact size needed is known, or maybe to max(minCapacity, DEFAULT_CAPACITY) if elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA which would use more space but otherwise ensureCapacity could cause you to end up with lower than default capacity (which might be wanted).

diff --git a/src/java.base/share/classes/java/util/ArrayList.java b/src/java.base/share/classes/java/util/ArrayList.java
--- a/src/java.base/share/classes/java/util/ArrayList.java
+++ b/src/java.base/share/classes/java/util/ArrayList.java
@@ -210,11 +210,9 @@
      * @param minCapacity the desired minimum capacity
      */
     public void ensureCapacity(int minCapacity) {
-        if (minCapacity > elementData.length
-            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
-                 && minCapacity <= DEFAULT_CAPACITY)) {
+        if (minCapacity > elementData.length) {
             modCount++;
-            grow(minCapacity);
+            elementData = Arrays.copyOf(elementData, minCapacity);
         }
     }

I noticed this while writing a similar method for ArrayDeque which could also be added to ArrayList:

    /**
     * Attempts to reallocate the backing array so that is has space for as close as
     * possible to, but not less than, minSize elements unless it already has space
     * for between minSize and maxSize elements. If the size() of this ArrayDeque is
     * greater than minSize then size() will be treated as minSize.
     *
     * <p>This method can be used to achieve the same result as {@link ArrayList#trimToSize}
     * by calling {@code reallocate(0, 0)} or {@link ArrayList#ensureCapacity(n)} by calling
     * {@code reallocate(n, Integer.MAX_VALUE)}.
     *
     * @param minSize the requested minimum capacity
     * @param maxSize the requested maximum capacity
     * @return the new (or unchanged) capacity
     * @throws IllegalArgumentException if minSize > maxSize (size() may be greater than maxSize
     * without throwing an exception)
     * @throws OutOfMemoryError if there is not enough memory available to allocate
     * the array or the array would be larger than an implementation defined limit
     */
    public int reallocate(int minSize, int maxSize){
        if(minSize > maxSize) throw new IllegalArgumentException(minSize + " > " + maxSize);
        int c = elements.length - 1, s = size();
        if(c < minSize){
            if(minSize + 1 < 0) throw new OutOfMemoryError();
        } else {
            if(c <= maxSize) return c;
            if(s > minSize){
                if(c == (minSize = s)) return c;
            }
        }
        elements = minSize == 0 ? EMPTY : copyElements(new Object[minSize + 1], head, tail);
        head = 0;
        tail = s;
        return minSize;
    }