Различные типы streamобезопасных наборов в Java

Кажется, что существует множество различных реализаций и способов создания streamобезопасных наборов в Java. Некоторые примеры include

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (Set set)

3) Неизвестный исполнитель

4) Collections.newSetFromMap (новый ConcurrentHashMap ())

5) Другие наборы, сгенерированные способом, аналогичным (4)

Эти примеры взяты из шаблона параллелизма: параллельные установки в Java 6

Может ли кто-то просто объяснить различия, преимущества и недостатки этих примеров и других? У меня возникли проблемы с пониманием и поддержанием прямо из Java Std Docs.

    1) CopyOnWriteArraySet – довольно простая реализация – в ней в основном есть список элементов в массиве, и при изменении списка он копирует массив. Итерации и другие обращения, которые выполняются в это время, продолжаются со старым массивом, избегая необходимости синхронизации между читателями и писателями (хотя сама запись должна быть синхронизирована). Обычно быстро выполняемые операции (особенно contains() ) здесь довольно медленные, так как массивы будут выполняться в линейном времени.

    Используйте это только для действительно маленьких наборов, которые будут часто читаться (повторяться) и редко меняться. (Swinger listener-sets будет примером, но они на самом деле не наборы, и в любом случае их следует использовать только от EDT.)

    2) Collections.synchronizedSet просто переносит синхронизированный блок вокруг каждого метода исходного набора. Вы не должны напрямую обращаться к исходному набору. Это означает, что никакие два метода набора не могут выполняться одновременно (один будет блокироваться до тех пор, пока другой не закончится) – это поточно-безопасный, но у вас не будет параллелизма, если несколько streamов действительно используют набор. Если вы используете iterator, вам, как правило, по-прежнему необходимо синхронизировать внешнее, чтобы избежать ConcurrentModificationExceptions при изменении набора между вызовами iteratorа. Производительность будет похожа на производительность исходного набора (но с некоторыми накладными расходами на синхронизацию и блокирование при одновременном использовании).

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

    3) ConcurrentSkipListSet – это параллельная реализация SortedSet , с большинством основных операций в O (log n). Он позволяет одновременное добавление / удаление и чтение / итерацию, где итерация может или не может сообщать об изменениях с момента создания iteratorа. Объемные операции – это просто несколько одиночных вызовов, а не атомарно – другие streamи могут наблюдать только некоторые из них.

    Очевидно, вы можете использовать это, только если у вас есть общий порядок на ваших элементах. Это выглядит как идеальный кандидат для ситуаций с высокой параллелизмом, для не слишком больших наборов (из-за O (log n)).

    4) Для ConcurrentHashMap (и набора, полученных из него): Здесь наиболее основные параметры (в среднем, если у вас есть хороший и быстрый hashCode() ) в O (1) (но может выродиться до O (n)), как для HashMap / HashSet. Существует ограниченный параллелизм для записи (таблица разделена на разделы, и доступ на запись будет синхронизирован на нужном разделе), в то время как доступ на чтение полностью параллелен самому себе и streamам записи (но может еще не увидеть результаты изменений, которые в настоящее время являются написано). Итератор может или не может видеть изменения с момента его создания, а массовые операции не являются атомарными. Масштабирование происходит медленно (как для HashMap / HashSet), поэтому старайтесь избегать этого, оценивая необходимый размер при создании (и используя примерно 1/3 из этого, поскольку он изменяет размер при заполнении 3/4).

    Используйте это, когда у вас есть большие наборы, хорошая (и быстрая) хеш-функция и вы можете оценить заданный размер и необходимый параллелизм перед созданием карты.

    5) Существуют ли другие параллельные реализации карт, которые можно использовать здесь?

    Можно комбинировать CopyOnWriteArraySet contains() HashSet с связанными с параллелизмом свойствами CopyOnWriteArraySet с помощью AtomicReference и заменять весь набор на каждую модификацию.

    Эскиз реализации:

     public abstract class CopyOnWriteSet implements Set { private final AtomicReference> ref; protected CopyOnWriteSet( Collection c ) { ref = new AtomicReference>( new HashSet( c ) ); } @Override public boolean contains( Object o ) { return ref.get().contains( o ); } @Override public boolean add( E e ) { while ( true ) { Set current = ref.get(); if ( current.contains( e ) ) { return false; } Set modified = new HashSet( current ); modified.add( e ); if ( ref.compareAndSet( current, modified ) ) { return true; } } } @Override public boolean remove( Object o ) { while ( true ) { Set current = ref.get(); if ( !current.contains( o ) ) { return false; } Set modified = new HashSet( current ); modified.remove( o ); if ( ref.compareAndSet( current, modified ) ) { return true; } } } } 

    Если Javadocs не помогают, вы, вероятно, должны просто найти книгу или статью для чтения о структурах данных. С одного взгляда:

    • CopyOnWriteArraySet создает новую копию базового массива каждый раз, когда вы мутируете коллекцию, поэтому записи медленны, а iteratorы – быстрые и последовательные.
    • Collections.synchronizedSet () использует вызовы с синхронизированными вызовами старой школы, чтобы сделать Set threadsafe. Это будет невысокая версия.
    • ConcurrentSkipListSet предлагает исполняемые записи с непоследовательными пакетными операциями (addAll, removeAll и т. Д.) И iteratorами.
    • Collections.newSetFromMap (новый ConcurrentHashMap ()) имеет семантику ConcurrentHashMap, которая, как мне кажется, не обязательно оптимизирована для чтения или записи, но, как и ConcurrentSkipListSet, имеет непоследовательные пакетные операции.
    Давайте будем гением компьютера.