A DESCRIPTION OF THE REQUEST :
Since all indexes of an Object array are set to null when created, the Copies list could override toArray() method to create a new Object[size()] if the value object of the CopiesList is null. In the non-null case the method should use Arrays.fill().

For toArray(Object[]), if the given array is smaller than size() then a new array of the given component type can be created and returned if the value object of the CopiesList is null. If the given array has room for the number of copies then Arrays.fill() should be used instead of the AbstractCollection implementation.

Bug ID 4147188 (evaluation), 4476673 (evaluation), and 4766057 (description)
show that copies list and null are used to set the capacity of a collection.
The ArrayList, LinkedList, and Vector use the toArray() and toArray(T[])
methods to copy values from the given collection to newly created collection
via addAll or the copy constructor. The purpose of this RFE is to boost the
performance when sizing a collection. This is a common operation that takes
place in a lot of applications.

//Example 1 ============================
List l = new ArrayList(10);
l.addAll(Collections.nCopies(16, null);
//========================================

The addAll method will call toArray() on the copies list.
CopiesList.toArray() will create a new array of length 16. Each index is
already set to null when the array is created but the AbstractCollection
implementation is naive and will create an Iterator and will loop 16 times
setting each index to null. The newly created array was "effectively"
unchanged after loop ran thus, in the null case there is no need for
CopiesList.toArray() to waste time creating an Iterator and performing a
loop. The performance of example 1 will improve in the null case if
CopiesList.toArray() is replaced with a smart implementation that does not
create an Iterator and performs an array fill only if needed. Here is the
proposed improvement to be added to the CopiesList.

public Object[] toArray() {
  final Object[] a = new Object[n];
  if(element != null) { //fill if need be.
    Arrays.fill(a, 0, n, element);
  }
  return a;
}



//Example 2=============================================
List l = new ArrayList(Collections.nCopies(16, null));
//==================================================

The ArrayList(Collection c) constructor will invoke CopiesList.toArray(T[])
to fill the newly created collection. The CopiesList uses the
AbstractCollection implementation which is naïve and will create an Iterator
and fill the array passed in or create a new array and fill it. If the
element value of the CopiesList is null and the given array is smaller than
the size of the copies list then the
The performance of example 2 will improve if CopiesList.toArray(T[]) is
replaced with a smart implementation that does not create an Iterator and
performs an array fill only when needed. Here is the proposed improvement
to be added to the CopiesList.

public <T> T[] toArray(T[] a) {
  final int n = this.n; //use local.
  if(a.length < n) {
    a = (T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), n);
    if(element != null) { //fill if need be.
      Arrays.fill(a, 0, n, element);
    }
  }
  else { //always have to fill to enforce the Collection interface.
    Arrays.fill(a, 0, n, element);
    if(a.length > n) {
      a[n] = null;
    }
  }
  return a;
}

This will result in a small improvement in the current ArrayList(Collection
c) because an Iterator is not created but fill takes place because of the
110% growth policy. Depending upon how bugs 4759223 and 4918916 are
addressed, the performance of example 1 and 2 could approach the speed of
Vector.setSize(int) in the null case. Arrays.fill does extra bounds
checking that is not need in this solution as CopiesList ensures that the
indexes are inbounds just by enforcing the Collections interface. The calls
to fill could also be replaced with a simple loop.


Bellow are the results of my custom copies list that I benchmarked with and
without the new toArray() methods.

AddAll null Example 1
Type CAP custom Imp Abstract Imp
ArrayList 1000000 30ms 95ms
LinkedList 1000000 523ms 570ms
 
Copy constructor null Example 2
Type CAP custom Imp Abstract Imp
ArrayList 1000000 29ms 70ms
LinkedList 1000000 501ms 523ms

AddAll non-null
Type CAP custom Imp Abstract Imp
ArrayList 1000000 38ms 95ms
LinkedList 1000000 523ms 570ms

Copy constructor non-null
Type CAP custom Imp Abstract Imp
ArrayList 1000000 30ms 70ms
LinkedList 1000000 558ms 600ms


JUSTIFICATION :
The changes above would reduce the number of objects created (Iterators) and reduce the number of copies (fills) that occur in the common case of null.


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
A boost in performance for null case. Minor overhead in non-null case.
Reduction in number of objects created.
The ArrayList.addAll() methods should see an increase in performance.
ACTUAL -
Not tested.

---------- BEGIN SOURCE ----------
List l = new ArrayList(10);
l.addAll(Collections.nCopies(16, null);

/*===========================*/

List x = new ArrayList(Collections.nCopies(n, null));

---------- END SOURCE ----------
###@###.### 2005-05-24 05:38:14 GMT