src/share/classes/java/util/ArrayList.java
Print this page
rev 6039 : 8011200: (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, 2010, 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);
}
*** 449,459 ****
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;
}
/**
--- 478,488 ----
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;
}
/**
*** 494,514 ****
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;
}
--- 523,543 ----
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;
}
*** 585,598 ****
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
--- 614,629 ----
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
*** 676,685 ****
--- 707,717 ----
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;
*** 700,739 ****
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
--- 732,779 ----
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