ArrayList.ensureCapacity should expand the default capacity empty array

[Martin Buchholz]

Thanks Alex,
I filed
https://bugs.openjdk.java.net/browse/JDK-8206945
I've had similar thoughts for years, but none have ended up in the actual
code.
I haven't seem the approach you used in your reallocate.

On Thu, Jul 5, 2018 at 10:04 AM, Alex Foster <alexfoster at hotmail.ca> wrote:

> 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;
>     }
>
>