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 <[email protected]> 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; > } > >
