Rediscover queues in Java

“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Hello, I’m looking at the mountains.

Last time we talked about what happens when you use ArrayList in multiple threads. This time we’ll talk about common lists: Vector, ArrayList, CopyOnWriteArrayList, SynchronizedList.

Vector

Vector was provided in JDK 1.0, and although it was not marked Deprecated, it is virtually no longer in use. The main reason is that the performance is poor and does not meet requirements.

Vector is an array based implementation that uses the synchronized keyword for almost all operations. This type of synchronization can lock a single operation. For example, multiple threads executing add at the same time will block the operation synchronously. But when multiple threads execute add and remove, they don’t block.

However, most scenarios that require queues to be locked want to lock the entire queue, not just a single operation. That is, Vector is not what we expected, but it adds an additional performance overhead for synchronous operations. Therefore, ArrayList can be used for scenarios that are not necessary, and CopyOnWriteArrayList and SynchronizedList can be used for scenarios that require synchronization of queues even in multi-threaded scenarios.

ArrayList

ArrayList was introduced in JDK 1.1. As the successor to Vector (ArrayList is implemented in almost the same way as Vector), ArrayList removes synchronized from methods altogether, does not synchronize at all, and is not thread-safe.

Its non-thread-safe nature is also reflected in the rapid failure of iterators. After use the iterator and a listIterator create an iterator, and if there is to modify the original ArrayList queue (add or remove), iterator when iteration ConcurrentModificationException anomalies. During the iteration process, the iterator checks whether the number of changes in the queue modCount is equal to the snapshot expectedModCount that falls when the iterator is created. If the number is equal, the code is as follows:

private class Itr implements Iterator<E> {
    // This code is extracted from the ArrayList
    // Leave only the check method, skip the other code, interested can view from the source
    final void checkForComodification(a) {
        if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

The third point is that in multithreaded scenarios, adding elements can result in data loss or array out-of-bounds exceptions. What happens when you use an ArrayList in multithreaded scenarios is described in more detail than is needed here.

SynchronizedList

SynchronizedList is the Collections of the static inner class, the use of the Collections. SynchronizedList () static method to create, is a combined List class implements the encapsulation. Most of its methods are synchronized (mutex){… } mutex is the same object defined in a queue, so when we lock a Vector, we lock the entire queue. So if more than one thread operates on the add and remove methods at the same time, synchronous execution will be blocked.

Iterators fail quickly in ArrayList, as noted in the source code below: To use iterators, users need to manually synchronize.

static class SynchronizedList<E>
    extends SynchronizedCollection<E>
    implements List<E> {
    
    // The code is taken from Collections, leaving out a lot of code

    public void add(int index, E element) {
        synchronized (mutex) {list.add(index, element);}
    }

    public ListIterator<E> listIterator(a) {
        return list.listIterator(); // Must be manually synched by user
    }

    public ListIterator<E> listIterator(int index) {
        return list.listIterator(index); // Must be manually synched by user}}Copy the code

When synchronizing manually, it is important to note that since we are concerned with global synchronization, when setting synchronization in the iterator, it is important to ensure that the locked object is the same as the object in methods like add. This will be explained later, but I won’t expand it here.

CopyOnWriteArrayList

CopyOnWriteArrayList is available starting with JDK 1.5.

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess.Cloneable.java.io.Serializable {

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;

    // This code is copied from CopyOnWriteArrayList, omitting a lot of code

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally{ lock.unlock(); }}public boolean addAll(Collection<? extends E> c) { Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ? ((CopyOnWriteArrayList<? >)c).getArray() : c.toArray();if (cs.length == 0)
            return false;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (len == 0 && cs.getClass() == Object[].class)
                setArray(cs);
            else {
                Object[] newElements = Arrays.copyOf(elements, len + cs.length);
                System.arraycopy(cs, 0, newElements, len, cs.length);
                setArray(newElements);
            }
            return true;
        } finally{ lock.unlock(); }}private E get(Object[] a, int index) {
        return (E) a[index];
    }

    / * * * {@inheritDoc}
     *
     * @throws IndexOutOfBoundsException {@inheritDoc} * /
    public E get(int index) {
        returnget(getArray(), index); }}Copy the code

As you can see, CopyOnWriteArrayList synchronizes with ReentrantLock, which performs better than synchronized until synchronized optimization. CopyOnWriteArrayList is also implemented with arrays, but with the volatile keyword in front of the array, which makes arrays visible in multithreaded scenarios more secure. More importantly, CopyOnWriteArrayList reconstructs the array object when the add element is added, replacing the original array reference. Compared with ArrayList, this method reduces space, but also increases the performance overhead of array assignment. When get fetches an element, there is no lock and the data is returned.

The iterator of CopyOnWriteArrayList is implemented via COWIterator, which assigns a snapshot of the array in the current queue to the array reference in the iterator. If the original queue changes, the array in the queue will point to another reference, while the array in the iterator will not change. Therefore, in multithreaded execution, the iterator can also modify the data in the queue by traversing the number group. This way to ensure thread safety at the same time, there may be data inconsistency, can only be used to pay more attention to the use of.

static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next. */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) { cursor = initialCursor; snapshot = elements; }}Copy the code

Compare CopyOnWriteArrayList with SynchronizedList

CopyOnWriteArrayList and SynchronizedList both implement synchronization using different strategies with different priorities.

CopyOnWriteArrayList focuses on read and write separation. When data write operations (add or remove) occur, locks will be added and each thread will block execution. During execution, data copies will be created and object references replaced. If there is a concurrent read operation (get or iterator), the read operation reads old data, either as a snapshot of historical data or as cached data. This can lead to inconsistent data when simultaneous reads and writes occur, but the data will eventually be consistent. This approach is almost identical to the database read-write separation schema, and many of its features can be compared.

SynchronizedList focuses on data consistency, meaning that when a write (add or remove) occurs, a lock is attached, threads block execution, and the same lock blocks get.

CopyOnWriteArrayList is more efficient than SynchronizedList, and SynchronizedList is more efficient than CopyOnWriteArrayList. So CopyOnWriteArrayList is more efficient in both write and read scenarios. Using the results of an online test:

Compare CopyOnWriteArrayList with SynchronizedList

At the end of the article to summarize

1. synchronizedThe performance of the keyword is poor before JDK 8. You can see the synchronization code implemented after JDK1.5ReentrantLockThe implementation.
2. In multithreaded scenarios, in addition to synchronization, you also need to consider data visibility, which can be passedvolatileKeyword implementation.
3. ArrayListThere is no synchronization at all and it is not thread-safe
4. CopyOnWriteArrayListandSynchronizedListBelongs to a thread-safe queue
5. CopyOnWriteArrayListAchieve read/write separation, suitable for the scenario where less writing is required and more reading is required
6. SynchronizedListData consistency is required. The queue is locked globally. Read operations are also locked
7. VectorOnly in iterator traversal performance is poor, if the global lock queue is not considered, pure read and write operation performance andSynchronizedListNot much.

Recommended reading

• There are anti-pattern interface constants in the JDK
• What do we need to pay attention to when Java Import imports packages?
• Java Concurrency Basics (1) : Synchronized
• Java Concurrency Basics (2) : The main thread waits for the child thread to terminate
• Java Concurrency basics (iii) : Talk more about CountDownLatch
• Java Concurrency Basics (4) : CyclicBarrier
• Java concurrency basics (5) : multithreaded sequential printing for interview practice
• What happens if you have to use an ArrayList in multiple threads?
• What happens if you have to use an ArrayList in multiple threads? (Chapter 2)
• Rediscover queues in Java
• Java difference between Vector and SynchronizedList
• This article describes 24 operations for Java8 Stream Collectors
• Java8 Optional 6 kinds of operations

---

Hello, I’m looking at the mountains. Swim in the code, play to enjoy life. If this article is helpful to you, please like, bookmark, follow. Welcome to follow the public account “Mountain Hut”, discover a different world.