[PATCH]: Performance improvement on CopyOnWriteArrayList

[Mario Torre]

Hello all!

Attached to this mail is a small patch that improves the performance in
the removeAll and retainAll methods of CopyOnWriteArrayList.

The patch simply checks if the input collection, in both method, is void
or contains elements, in the former case no action is performed on the
underlying storage, while in retainAll the list is cleared and true is
returned, so actually these methods run in constant time when a
collection with no elements is passed in.

I did a similar change in Classpath (not yet in CVS), and with the
following test the improvement is big in both cases (almost 7 seconds on
my computer):

package test;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteListPerformance
{
  /**
   * @param args
   */
  public static void main(String[] args)
  {
    List<Integer> srcList = new ArrayList<Integer>();
    for (int i = 0; i < 10000; i++)
      srcList.add(i);
    
    CopyOnWriteArrayList<Integer> list =
      new CopyOnWriteArrayList<Integer>(srcList);
 
    srcList.clear();
    
    long start = System.currentTimeMillis();
 
    list.retainAll(srcList);
    
    long stop = System.currentTimeMillis();
    
    System.out.println("starting time: " + start);
    System.out.println("end time: " + stop); 
    System.out.println("total running time: " + (stop - start) +
                       " (approx. " + ((stop - start) / 1000) + "
seconds)");
  }
}

Of course, I don't think that this method is used this way in 99% of the
cases; honestly, I think very few would pass intentionally a void list
to retainAll, but still, the check is harmless and represent a huge
improvement if someone needs it.

The patch apply to b23.

As a final note, I've already signed the SCA.

Thanks for looking,
Mario
-- 
Lima Software - http://www.limasoftware.net/
GNU Classpath Developer - http://www.classpath.org/
Fedora Ambassador - http://fedoraproject.org/wiki/MarioTorre
Jabber: neugens at jabber.org
pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF
Fingerprint: BA39 9666 94EC 8B73 27FA  FC7C 4086 63E3 80F2 40CF

Please, support open standards:
http://opendocumentfellowship.org/petition/
http://www.nosoftwarepatents.com/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: copy-on-write-array-list-performance.patch
Type: text/x-patch
Size: 866 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20071123/d207a5e8/copy-on-write-array-list-performance.patch>