src/share/classes/java/util/ArrayList.java

Print this page
rev 6845 : 80111200: (coll) Optimize empty HashMap and ArrayList
Reviewed-by: mduigou, alanb, bchristi, martin
Contributed-by: Sergey Linetskiy <sergey.linetskiy@oracle.com>, John Rose <john.r.rose@oracle.com>, Mike Duigou <mike.duigou@oracle.com>

*** 1,7 **** /* ! * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this --- 1,7 ---- /* ! * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this
*** 103,114 **** implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** * The array buffer into which the elements of the ArrayList are stored. ! * The capacity of the ArrayList is the length of this array buffer. */ private transient Object[] elementData; /** * The size of the ArrayList (the number of elements it contains). --- 103,126 ---- implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** + * Default initial capacity. + */ + private static final int DEFAULT_CAPACITY= 10; + + /** + * Shared empty array instance used for empty instances. + */ + private static final Object[] EMPTY_ELEMENTDATA = {}; + + /** * The array buffer into which the elements of the ArrayList are stored. ! * The capacity of the ArrayList is the length of this array buffer. Any ! * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to ! * DEFAULT_CAPACITY when the first element is added. */ private transient Object[] elementData; /** * The size of the ArrayList (the number of elements it contains).
*** 134,144 **** /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { ! this(10); } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's --- 146,157 ---- /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { ! super(); ! this.elementData = EMPTY_ELEMENTDATA; } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's
*** 160,171 **** * list's current size. An application can use this operation to minimize * the storage of an <tt>ArrayList</tt> instance. */ public void trimToSize() { modCount++; ! int oldCapacity = elementData.length; ! if (size < oldCapacity) { elementData = Arrays.copyOf(elementData, size); } } /** --- 173,183 ---- * list's current size. An application can use this operation to minimize * the storage of an <tt>ArrayList</tt> instance. */ public void trimToSize() { modCount++; ! if (size < elementData.length) { elementData = Arrays.copyOf(elementData, size); } } /**
*** 174,189 **** * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { ! if (minCapacity > 0) ! ensureCapacityInternal(minCapacity); } private void ensureCapacityInternal(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } --- 186,218 ---- * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { ! int minExpand = (elementData != EMPTY_ELEMENTDATA) ! // any size if real element table ! ? 0 ! // larger than default for empty table. It's already supposed to be ! // at default size. ! : DEFAULT_CAPACITY; ! ! if (minCapacity > minExpand) { ! ensureExplicitCapacity(minCapacity); ! } } private void ensureCapacityInternal(int minCapacity) { + if (elementData == EMPTY_ELEMENTDATA) { + minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); + } + + ensureExplicitCapacity(minCapacity); + } + + private void ensureExplicitCapacity(int minCapacity) { modCount++; + // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
*** 448,458 **** int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); ! elementData[--size] = null; // Let gc do its work return oldValue; } /** --- 477,487 ---- int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); ! elementData[--size] = null; // clear to let GC do its work return oldValue; } /**
*** 493,513 **** modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); ! elementData[--size] = null; // Let gc do its work } /** * Removes all of the elements from this list. The list will * be empty after this call returns. */ public void clear() { modCount++; ! // Let gc do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } --- 522,542 ---- modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); ! elementData[--size] = null; // clear to let GC do its work } /** * Removes all of the elements from this list. The list will * be empty after this call returns. */ public void clear() { modCount++; ! // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
*** 584,597 **** modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); ! // Let gc do its work int newSize = size - (toIndex-fromIndex); ! while (size != newSize) ! elementData[--size] = null; } /** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is --- 613,628 ---- modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); ! // clear to let GC do its work int newSize = size - (toIndex-fromIndex); ! for (int i = newSize; i < size; i++) { ! elementData[i] = null; ! } ! size = newSize; } /** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is
*** 675,684 **** --- 706,716 ---- elementData, w, size - r); w += size - r; } if (w != size) { + // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true;
*** 699,738 **** throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); ! // Write out array length ! s.writeInt(elementData.length); // Write out all elements in the proper order. ! for (int i=0; i<size; i++) s.writeObject(elementData[i]); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } - } /** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in size, and any hidden stuff s.defaultReadObject(); ! // Read in array length and allocate array ! int arrayLength = s.readInt(); ! Object[] a = elementData = new Object[arrayLength]; // Read in all elements in the proper order. ! for (int i=0; i<size; i++) a[i] = s.readObject(); } /** * Returns a list iterator over the elements in this list (in proper * sequence), starting at the specified position in the list. * The specified index indicates the first element that would be --- 731,778 ---- throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); ! // Write out size as capacity for behavioural compatibility with clone() ! s.writeInt(size); // Write out all elements in the proper order. ! for (int i=0; i<size; i++) { s.writeObject(elementData[i]); + } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } /** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { + elementData = EMPTY_ELEMENTDATA; + // Read in size, and any hidden stuff s.defaultReadObject(); ! // Read in capacity ! s.readInt(); // ignored ! ! if (size > 0) { ! // be like clone(), allocate array based upon size not capacity ! ensureCapacityInternal(size); + Object[] a = elementData; // Read in all elements in the proper order. ! for (int i=0; i<size; i++) { a[i] = s.readObject(); } + } + } /** * Returns a list iterator over the elements in this list (in proper * sequence), starting at the specified position in the list. * The specified index indicates the first element that would be