Mario Torre writes:

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:   xxxxx@xxxxx   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/



--- openjdk/jdk/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java-orig	2007-11-23 19:34:01.000000000 +0100
+++ openjdk/jdk/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	2007-11-23 19:36:57.000000000 +0100
@@ -641,6 +641,9 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
+            if (c.size() == 0) {
+                return false;
+            }
             Object[] elements = getArray();
             int len = elements.length;
             if (len != 0) {
@@ -681,6 +684,10 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
+            if (c.size() == 0) {
+                this.clear();
+                return true;
+            }
             Object[] elements = getArray();
             int len = elements.length;
             if (len != 0) {
Posted Date : 2007-11-23 21:41:55.0

N/A

Seems reasonable.

There is often a conflict between changes that make some special case
very much faster, while making the "normal" case very slightly slower.
It is hard to evaluate the tradeoff.

The submitted change could be improved by:
- using the potentially faster c.isEmpty() instead of c.size() == 0
- no need to acquire lock in retainAll if c.isEmpty()
- if "this" and "c" are both empty, then retainAll incorrectly returns true.

Another consideration is that users that know that the argument collection
is likely to be empty, or that "this" is likely to be very large, then
they are more likely to want this particular optimization, but they can do
so by checking c.isEmpty() themselves before calling the bulk method.
(Am I talking myself out of supporting this change?)

The case for removeAll is stronger than for retainAll, since for retainAll
both code paths are of order N.

--- /tmp/geta17004	2007-11-23 14:31:48.933118600 -0800
+++ CopyOnWriteArrayList.java	2007-11-23 14:17:37.173593000 -0800
@@ -634,14 +634,16 @@
      *         is incompatible with the specified collection (optional)
      * @throws NullPointerException if this list contains a null element and the
      *         specified collection does not permit null elements (optional),
      *         or if the specified collection is null
      * @see #remove(Object)
      */
     public boolean removeAll(Collection<?> c) {
+        if (c.isEmpty())
+            return false;
 	final ReentrantLock lock = this.lock;
 	lock.lock();
 	try {
 	    Object[] elements = getArray();
 	    int len = elements.length;
 	    if (len != 0) {
 		// temp array holds those elements we know we want to keep
@@ -680,14 +682,18 @@
     public boolean retainAll(Collection<?> c) {
 	final ReentrantLock lock = this.lock;
 	lock.lock();
 	try {
 	    Object[] elements = getArray();
 	    int len = elements.length;
 	    if (len != 0) {
+                if (c.isEmpty()) {
+                    this.clear();
+                    return true;
+                }
 		// temp array holds those elements we know we want to keep
 		int newlen = 0;
 		Object[] temp = new Object[len];
 		for (int i = 0; i < len; ++i) {
 		    Object element = elements[i];
 		    if (c.contains(element))
 			temp[newlen++] = element;
Posted Date : 2007-11-23 22:33:50.0