CopyOnWriteArrayList as thread-safe ArrayList

Working with collections in multi-threading environment is a little bit tricky. But fortunately, Java offers some objects able to store data in thread-safe way. One of them is CopyOnWriteArrayList, introduced with Java 5.

Data Engineering Design Patterns

Looking for a book that defines and solves most common data engineering problems? I'm currently writing one on that topic and the first chapters are already available in πŸ‘‰ Early Release on the O'Reilly platform

I also help solve your data engineering problems πŸ‘‰ contact@waitingforcode.com πŸ“©

This article describes CopyOnWriteArrayList object, able to store data in concurrent environment. Its first part presents more generally the way of working of this List implementation. The second part shows how it works through some unit test cases.

What is CopyOnWriteArrayList ?

java.util.concurrent.CopyOnWriteArrayList is a thread-safe implementation of List interface. Its thread-safety is guaranteed thanks to making new array each time when one element is modified (added, removed). And CopyOnWriteArrayList uses the data of this array in reading operations. To see this difference we can look at source code of writing operations in ArrayList and CopyOnWriteArrayList. Let's begin with ArrayList:

public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount
  elementData[size++] = e;
  return true;
}

And now, we can take a look at add method from CopyOnWriteArrayList:

public void add(int index, E element) {
  final ReentrantLock lock = this.lock;
  lock.lock();
  try {
    Object[] elements = getArray();
    int len = elements.length;
    if (index > len || index < 0)
      throw new IndexOutOfBoundsException("Index: "+index+
                                          ", Size: "+len);
    Object[] newElements;
    int numMoved = len - index;
    if (numMoved == 0)
      newElements = Arrays.copyOf(elements, len + 1);
    else {
      newElements = new Object[len + 1];
      System.arraycopy(elements, 0, newElements, 0, index);
      System.arraycopy(elements, index, newElements, index + 1,
                      numMoved);
    }
    newElements[index] = element;
    setArray(newElements);
  } finally {
    lock.unlock();
  }
}

As you can see, CopyOnWriteArrayList makes each time new underlying array by copying already existent items and adding new one to them. ArrayList only extends the storage capacity and adds the element to the array. Other writing operations work in the same way in CopyOnWriteArrayList. And it's even true in the case of sorting where ArrayList fails when another thread tries to modify collection being sorted.

Thanks to array copy, we can be sure that iteration on data is made on immutable and valid in given moment fragment of data potentially modified at the same moment by another thread. However, it has some cost. Copying array can produce important performance issues when, for example, lists reads are less often than modifications.

In additionally, the implementation of ListIterator of CopyOnWriteArrayList doesn't allow the execution of any writing operations. Each invocation of add, set or remove method will throw an UnsupportedOperationException. It's not the case of ArrayList ListIterator which allows the execution of writing methods but with the risk of throwing ConcurrentModificationException.

CopyOnWriteArrayList example

Now it's the time to see both, CopyOnWriteArrayList and ArrayList, in action. Through several test cases we will able to observe the differences between them in reading, sorting and writing operations:

public class CopyOnWriteArrayListTest {

  private List<String> initialLetters;

  @Before
  public void initData() {
    this.initialLetters = Lists.newArrayList("A", "B", "C", "D");
  }

  @Test
  public void should_throw_concurrent_exception_on_iterating_concurrently_modified_array_lists() throws InterruptedException {
    CountDownLatch latch = new CountDownLatch(2);
    List<String> names = new ArrayList<>(initialLetters);

    LetterAdder letterAdder1 = new LetterAdder(new String[]{"E", "F", "G", "H"}, names, latch);
    LetterAdder letterAdder2 = new LetterAdder(new String[]{"I", "J", "K", "L"}, names, latch);
    new Thread(() -> {
      while(true) {
        try {
            names.add(System.nanoTime()+" aa");
        } catch (Exception e) {
        }
      }
    }).start();
    new Thread(letterAdder1).start();
    new Thread(letterAdder2).start();
    latch.await(5, TimeUnit.SECONDS);

    assertThat(letterAdder1.isWasConcurrentException() || letterAdder2.isWasConcurrentException()).isTrue();
  }

  @Test
  public void should_not_throw_any_exception_for_concurrently_modified_copyonwritearraylist() throws InterruptedException {
    CountDownLatch latch = new CountDownLatch(2);
    List<String> names = new CopyOnWriteArrayList<>(initialLetters);

    LetterAdder letterAdder1 = new LetterAdder(new String[]{"E", "F", "G", "H"}, names, latch);
    LetterAdder letterAdder2 = new LetterAdder(new String[]{"I", "J", "K", "L"}, names, latch);
    new Thread(letterAdder1).start();
    new Thread(letterAdder2).start();
    latch.await(5, TimeUnit.SECONDS);

    assertThat(names).containsOnlyOnce("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L");
    assertThat(!letterAdder1.isWasConcurrentException() && !letterAdder2.isWasConcurrentException()).isTrue();
  }

  @Test(expected = UnsupportedOperationException.class)
  public void should_not_execute_removal_operation_on_copyonwritearraylist() {
    List<String> names = new CopyOnWriteArrayList<>(initialLetters);
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      iterator.remove();
    }
  }

  @Test(expected = UnsupportedOperationException.class)
  public void should_not_allow_to_add_new_items_on_copyonwritearraylist_listiterator() {
    List<String> names = new CopyOnWriteArrayList<>(initialLetters);
    ListIterator<String> iterator = names.listIterator();
    while (iterator.hasNext()) {
      iterator.add("X");
    }
  }

  @Test
  public void should_be_able_to_sort_items_on_copyonwritearraylist() throws InterruptedException {
    List<String> names = new CopyOnWriteArrayList<>(initialLetters);
    new Thread(() -> {while(true) { names.add(System.nanoTime()+" aa"); }}).start();
    Thread.sleep(2000);
    names.sort(Comparator.<String>reverseOrder());
  }

  @Test(expected = ConcurrentModificationException.class)
  public void should_not_be_able_to_sort_items_on_arraylist() throws InterruptedException {
    List<String> names = new ArrayList<>(initialLetters);
    new Thread(() -> {while(true) { names.add(System.nanoTime()+" aa"); }}).start();
    Thread.sleep(1000);
    names.sort(Comparator.<String>reverseOrder());
  }

  private static final class LetterAdder implements Runnable {

    private String[] lettersToAdd = new String[5];

    private List<String> names;

    private CountDownLatch latch;

    private boolean wasConcurrentException;

    private int start;

    public LetterAdder(String[] lettersToAdd, List<String> names, CountDownLatch latch) {
      this.lettersToAdd = lettersToAdd;
      this.names = names;
      this.latch = latch;
    }

    @Override
    public void run() {
      try {
        Thread.sleep(1000);
      } catch (InterruptedException e) {
        e.printStackTrace();
        wasConcurrentException = false;
      }
      continueIfAllowed();
      continueIfAllowed();

      try {
        Thread.sleep(1000);
      } catch (InterruptedException e) {
        e.printStackTrace();
        wasConcurrentException = false;
      }

      continueIfAllowed();
      continueIfAllowed();

      latch.countDown();
    }

    private void continueIfAllowed() {
      if (!wasConcurrentException) {
        names.add(lettersToAdd[start++]);
        wasConcurrentException = iterateThroughList(names);
      }
    }

    private boolean iterateThroughList(List<String> elementsToIterate) {
      Iterator<String> iterator = elementsToIterate.iterator();
      try {
        while (iterator.hasNext()) {
          String nextName = iterator.next();
          System.out.print(nextName);
        }
      } catch (ConcurrentModificationException cme) {
        cme.printStackTrace();
        return true;
      }
      return false;
    }

    public boolean isWasConcurrentException() {
      return wasConcurrentException;
    }
  }
}

CopyOnWriteArrayList helps to work with collections in multi-threading environment. It allows to execute sorting, reading and writing operations on "snapshot" data corresponding to data present at the moment of invoked operation. However, it can lead to performance problems because snapshots are made every time by creating new array. Note also that CopyOnWriteArrayList is not a single class from "copy-on-write" family. Another one is CopyOnWriteArraySet which under-the-hood uses... CopyOnWriteArrayList.


If you liked it, you should read:

πŸ“š Newsletter Get new posts, recommended reading and other exclusive information every week. SPAM free - no 3rd party ads, only the information about waitingforcode!