Разница между CopyOnWriteArrayList и synchronizedList

В соответствии с моим пониманием параллельные классы коллекций предпочитают более синхронизированные коллекции, потому что классы параллельной коллекции не берут блокировки для всего объекта коллекции. Вместо этого они берут блокировки на небольшом сегменте объекта коллекции.

Но когда я проверил метод add CopyOnWriteArrayList, мы приобретаем блокировку для полного объекта коллекции. Тогда как получилось CopyOnWriteArrayList лучше, чем список, возвращаемый Collections.synchronizedList? Единственное отличие, которое я вижу в методе add CopyOnWriteArrayList, заключается в том, что мы создаем копию этого массива каждый раз, когда вызывается метод add.

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();
    }
}

Ответ 1

Для операции записи (добавления) CopyOnWriteArrayList использует ReentrantLock и создает резервную копию данных, а базовая ссылка на volatile array обновляется через setArray (Любая операция чтения в списке во время до того, как setArray вернет старые данные перед добавлением). Более того, CopyOnWriteArrayList обеспечивает отказоустойчивый итератор моментального снимка и не бросает ConcurrentModifficationException при записи/добавлении.

Но когда я проверил метод добавления метода CopyOnWriteArrayList.class, мы обнаруживаем блокировку на полном объекте коллекции. Затем, как получилось, CopyOnWriteArrayList лучше, чем synchronizedList. Единственное отличие, которое я вижу в методе добавления CopyOnWriteArrayList, заключается в том, что мы создаем копию этого массива каждый раз при вызове метода add.

Нет, блокировка не находится во всем объекте Collection. Как указано выше, это ReentrantLock и отличается от внутренней блокировки объекта.
Метод add всегда создает копию существующего массива и выполняет модификацию на копии, а затем, наконец, обновляет волатильную ссылку массива, указывая на этот новый массив. И поэтому у нас есть имя "CopyOnWriteArrayList" - делает копию при записи в нее. Это также позволяет избежать ConcurrentModificationException

Ответ 2

1) get и другие операции чтения на CopyOnWriteArrayList не синхронизируются.

2) CopyOnWriteArrayList Итератор никогда throws ConcurrentModificationException, в то время как итератор Collections.synchronizedList может его выбросить.

Ответ 3

В соответствии с моим пониманием параллельные классы сбора предпочитают более синхронизированную сборку, потому что параллельные классы коллекций не занимают блокировки для полного объекта коллекции. Вместо этого он блокирует небольшой сегмент объекта коллекции.

Это верно для некоторых коллекций, но не для всех. Карта, возвращаемая Collections.synchronizedMap, блокирует всю карту вокруг каждой операции, тогда как ConcurrentHashMap блокирует только один хэш-бит для некоторых операций или может использовать неблокирующий алгоритм для других.

Для других коллекций используемые алгоритмы и, следовательно, компромиссы, различны. Это особенно верно в отношении списков, возвращаемых Collections.synchronizedList по сравнению с CopyOnWriteArrayList. Как вы отметили, обе synchronizedList и CopyOnWriteArrayList блокируют весь массив во время операций записи. Так почему же разные?

Разница возникает, если вы смотрите на другие операции, такие как итерация по каждому элементу коллекции. В документации для Collections.synchronizedList говорится:

Обязательно, чтобы пользователь вручную выполнял синхронизацию по возвращенному списку при итерации по нему:

    List list = Collections.synchronizedList(new ArrayList());
    ...
    synchronized (list) {
        Iterator i = list.iterator(); // Must be in synchronized block
        while (i.hasNext())
            foo(i.next());
    }

Несоблюдение этого совета может привести к детерминированному поведению.

Другими словами, итерация по synchronizedList не является не потокобезопасной, если вы не заблокируете ее вручную. Обратите внимание, что при использовании этого метода все операции с другими потоками в этом списке, включая итерации, получение, набор, добавление и удаление, блокируются. Только один поток за раз может сделать что-нибудь с этой коллекцией.

В отличие от этого, doc для CopyOnWriteArrayList говорит,

Метод итератора стиля "моментальный снимок" использует ссылку на состояние массива в точке, в которой был создан итератор. Этот массив никогда не изменяется во время жизни итератора, поэтому помехи невозможны, и итератору гарантировано не бросать ConcurrentModificationException. Итератор не будет отображать добавления, удаления или изменения в списке с момента создания итератора.

Операции других потоков в этом списке могут выполняться одновременно, но на итерацию не влияют изменения, сделанные другими потоками. Таким образом, даже несмотря на то, что операции записи блокируют весь список, CopyOnWriteArrayList все еще может обеспечить более высокую пропускную способность, чем обычный synchronizedList. (При условии, что существует большая доля чтений и обходов для записи.)