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 +1,7 @@
 /*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * 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,12 +103,24 @@
         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.
+     * 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,11 +146,12 @@
 
     /**
      * Constructs an empty list with an initial capacity of ten.
      */
     public ArrayList() {
-        this(10);
+        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,12 +173,11 @@
      * 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) {
+        if (size < elementData.length) {
             elementData = Arrays.copyOf(elementData, size);
         }
     }
 
     /**

@@ -174,16 +186,33 @@
      * specified by the minimum capacity argument.
      *
      * @param   minCapacity   the desired minimum capacity
      */
     public void ensureCapacity(int minCapacity) {
-        if (minCapacity > 0)
-            ensureCapacityInternal(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,11 +477,11 @@
 
         int numMoved = size - index - 1;
         if (numMoved > 0)
             System.arraycopy(elementData, index+1, elementData, index,
                              numMoved);
-        elementData[--size] = null; // Let gc do its work
+        elementData[--size] = null; // clear to let GC do its work
 
         return oldValue;
     }
 
     /**

@@ -493,21 +522,21 @@
         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
+        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++;
 
-        // Let gc do its work
+        // clear to let GC do its work
         for (int i = 0; i < size; i++)
             elementData[i] = null;
 
         size = 0;
     }

@@ -584,14 +613,16 @@
         modCount++;
         int numMoved = size - toIndex;
         System.arraycopy(elementData, toIndex, elementData, fromIndex,
                          numMoved);
 
-        // Let gc do its work
+        // clear to let GC do its work
         int newSize = size - (toIndex-fromIndex);
-        while (size != newSize)
-            elementData[--size] = null;
+        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,10 +706,11 @@
                                  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,40 +731,48 @@
         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 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++)
+        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 array length and allocate array
-        int arrayLength = s.readInt();
-        Object[] a = elementData = new Object[arrayLength];
+        // 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++)
+            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