Is there an improved alternative to Java CopyOnWriteArrayList implementation and how can I request a change to Java spec?

Question

CopyOnWriteArrayList almost has the behavior I want, and if unnecessary copies were removed it would be exactly what I am looking for. In particular, it could act exactly like ArrayList for adds made to the end of the ArrayList - i.e., there is no reason to actually make a new copy every single time which is so wasteful. It could just virtually restrict the end of the ArrayList to capture the snapshot for the readers, and update the end after the new items are added.

This enhancement seems like it would be worth having since for many applications the most common type of addition would be to the end of the ArrayList - which is even a reason for choosing to use an ArrayList to begin with.

There also would be no extra overhead since it could only not copy when appending and although it would still have to check if a re-size is necessary ArrayList has to do this anyways.

1. Is there any alternative implementation or data structure that has this behavior without the unnecessary copies for additions at the end (i.e., thread-safe and optimized to allow frequent reads with writes only being additions at the end of the list)?

2. How can I submit a change request to request a change to the Java specification to eliminate copies for additions to the end of a CopyOnWriteArrayList (unless a re-size is necessary)?

I'd really liked to see this changed with the core Java libraries rather than maintaining and using my own custom code.

Answer 1

To answer your questions:

1. I'm not aware of an alternative implementation that is a fully functional list.

2. If your idea is truly viable, I can think of a number of ways to proceed:

   • You can submit "requests for enhancement" (RFE) through the Java Bugs Database. However, in this case I doubt that you will get a positive response. (Certainly, not a timely one!)

   • You could create an RFE issue on Guava or Apache Commons issues tracker. This might be more fruitful, though it depends on convincing them ...

   • You could submit a patch to the OpenJDK team with an implementation of your idea. I can't say what the result might be ...

   • You could submit a patch (as above) to Guava or Apache Commons via their respective issues trackers. This is the approach that is most likely to succeed, though it still depends on convincing "them" that it is technically sound, and "a good thing".

   • You could just put the code for your proposed alternative implementation on Github, and see what happens.

---

However, all of this presupposes that your idea is actually going to work. Based on the scant information you have provided, I'm doubtful. I suspect that there may be issues with incomplete encapsulation, concurrency and/or not implementing the List abstraction fully / correctly.

I suggest that you put your code on Github so that other people can take a good hard look at it.

Answer 2

CopyOnWriteArrayList has a performance drawback because it creates a copy of the underlying array of the list on write operations. The array copying is making the write operations slow. May be, CopyOnWriteArrayList is advantageous for a usage of a List with high read rate and low write rate.

Eventually I started coding my own implementation using the java.util.concurrent.locks,ReadWriteLock. I did my implementation simply by maintaining object level ReadWriteLock instance, and gaining the read lock in the read operations and gaining the write lock in the write operations. The code looks like this.

public class ConcurrentList< T > implements List< T >
{
    private final ReadWriteLock  readWriteLock = new ReentrantReadWriteLock();
    private final List< T > list;

    public ConcurrentList( List<T> list )
    {
        this.list = list;
    }

    public boolean remove( Object o )
    {
        readWriteLock.writeLock().lock();
        boolean ret;
        try
        {
            ret = list.remove( o );
        }
        finally
        {
            readWriteLock.writeLock().unlock();
        }
        return ret;
    }

    public boolean add( T t )
    {
        readWriteLock.writeLock().lock();
        boolean ret;
        try
        {
            ret = list.add( t );
        }
        finally
        {
            readWriteLock.writeLock().unlock();
        }
        return ret;
    }

    public void clear()
    {
        readWriteLock.writeLock().lock();
        try
        {
            list.clear();
        }
        finally
        {
            readWriteLock.writeLock().unlock();
        }
    }


    public int size()
    {
        readWriteLock.readLock().lock();
        try
        {
            return list.size();
        }
        finally
        {
            readWriteLock.readLock().unlock();
        }
    }

    public boolean contains( Object o )
    {
        readWriteLock.readLock().lock();
        try
        {
            return list.contains( o );
        }
        finally
        {
            readWriteLock.readLock().unlock();
        }
    }

    public T get( int index )
    {
        readWriteLock.readLock().lock();
        try
        {
            return list.get( index );
        }
        finally
        {
            readWriteLock.readLock().unlock();
        }
    }

//etc
}

The performance improvement observed was notable.

Total time taken for 5000 reads + 5000 write ( read write ratio is 1:1) by 10 threads were

• ArrayList - 16450 ns( not thread safe)
• ConcurrentList - 20999 ns
• Vector -35696 ns
• CopyOnWriteArrayList - 197032 ns

please follow this link for more info about the test case used for obtaining above results

However, in order to avoid ConcurrentModificationException when using the Iterator, I just created a copy of the current List and returned the iterator of that. This means this list does not return and Iterator which can modify the original List. Well, for me, this is o.k. for the moment.

public Iterator<T> iterator()
    {
        readWriteLock.readLock().lock();
        try
        {
            return new ArrayList<T>( list ).iterator();
        }
        finally
        {
            readWriteLock.readLock().unlock();
        }
    }

After some googling I found out that CopyOnWriteArrayList has a similar implementaion, as it does not return an Iterator which can modify the original List. Javadoc says,

The returned iterator provides a snapshot of the state of the list when the iterator was constructed. No synchronization is needed while traversing the iterator. The iterator does NOT support the remove method.

Answer 3

Sounds like you're looking for a BlockingDeque, and in particular an ArrayBlockingQueue.

You may also want a ConcurrentLinkedQueue, which uses a "wait-free" algorithm (aka non-blocking) and may therefore be faster in many circumstances. It's only a Queue (not a Dequeue) and thus you can only insert/remove at the head of the collection, but it sounds like that might be good for your use case. But in exchange for the wait-free algorithm, it has to use a linked list rather than an array internally, and that means more memory (including more garbage when you pop items) and worse memory locality. The wait-free algorithm also relies on a compare and set (CAS) loop, which means that while it's faster in the "normal" case, it can actually be slower under high contention, as each thread needs to try its CAS several times before it wins and is able to move forward.

My guess is that the reason that lists don't get as much love in java.util.concurrent is that a list is an inherently racy data structure in most use cases other iteration. For instance, something like if (!list.isEmpty()) { return list.get(0); } is racy unless it's surrounded by a synchronized block, in which case you don't need an inherently thread-safe structure. What you really need is a "list-type" interface that only allows operations at the ends -- and that's exactly what Queue and Deque are.

Answer 4

there is no reason to actually make a new copy every single time which is so wasteful.

This is how it works. It works by replacing the previous array with new array in a compare and swap action. It is a key part of the thread safety design that you always have a new array even if all you do is replace an entry.

thread-safe and optimized to allow frequent reads with writes only being additions at the end of the list

This is heavily optimised for reads, any other solution will be faster for writes, but slower for reads and you have to decide which one you really want.

You can have a custom data structure which will be the best of both worlds, but it not longer a generic solution which is what CopyOnWriteArrayList and ArrayDeque provide.

How can I submit a change request to request a change to the Java specification to eliminate copies for additions to the end of a CopyOnWriteArrayList (unless a re-size is necessary)?

You can do this through the bugs database, but what you propose is a fundamental change in how the data structure works. I suggest proposing a new/different data structure which works the way you want. In the mean time I suggest implementing it yourself as a working example as you will get want you want faster.

I would start with an AtomicReferenceArray as this can be used to perform the low level actions you need. The only problem with it is it is not resizable so you would need to determine the maximum size you would every need.