Различные типы поточно-безопасных наборов в Java - PullRequest
Новая
       21

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

121 голосов
/ 17 июля 2011

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

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (Set set)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap (new ConcurrentHashMap ())

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

Эти примеры взяты из Шаблон параллелизма: реализации параллельного набора в Java 6

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

Ответы [ 4 ]

190 голосов
/ 17 июля 2011

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

Используйте это только для действительно маленьких наборов, которые будут часто читаться (повторяться) и изменяться редко,(Наборы слушателей Swings могут быть примером, но на самом деле это не наборы, и их следует использовать только из EDT.)

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

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

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

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

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

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

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

19 голосов
/ 17 января 2014

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

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

public abstract class CopyOnWriteSet<E> implements Set<E> {

    private final AtomicReference<Set<E>> ref;

    protected CopyOnWriteSet( Collection<? extends E> c ) {
        ref = new AtomicReference<Set<E>>( new HashSet<E>( c ) );
    }

    @Override
    public boolean contains( Object o ) {
        return ref.get().contains( o );
    }

    @Override
    public boolean add( E e ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( current.contains( e ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.add( e );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

    @Override
    public boolean remove( Object o ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( !current.contains( o ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.remove( o );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

}
10 голосов
/ 17 июля 2011

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

  • CopyOnWriteArraySet создает новую копию базового массива каждый раз, когда вы изменяете коллекцию, поэтому запись выполняется медленно, а итераторы выполняются быстро и согласованно.) использует синхронизированные вызовы методов старой школы, чтобы сделать поток безопасным.Это будет неэффективная версия.
  • ConcurrentSkipListSet предлагает записи с производительностью с несовместимыми пакетными операциями (addAll, removeAll и т. Д.) И итераторами.семантика ConcurrentHashMap, которая, я считаю, не обязательно оптимизирована для чтения или записи, но, как и ConcurrentSkipListSet, имеет несовместимые пакетные операции.
1 голос
/ 13 октября 2018

Параллельный набор слабых ссылок

Еще один поворот - потокобезопасный набор слабых ссылок .

Такой набор удобен для отслеживания подписчиков в сценарии pub-sub . Когда подписчик выходит из области действия в других местах и, следовательно, стремится стать кандидатом на сборку мусора, подписчику не нужно беспокоиться о изящной отписке. Слабая ссылка позволяет подписчику завершить переход к кандидату на сборку мусора. Когда мусор в конечном итоге собирается, запись в наборе удаляется.

Хотя такой набор не предоставляется непосредственно с классами, входящими в комплект, вы можете создать его с помощью нескольких вызовов.

Сначала мы начнем с создания Set слабых ссылок, используя класс WeakHashMap. Это показано в документации класса для Collections.newSetFromMap. 

Set< YourClassGoesHere > weakHashSet = 
    Collections
    .newSetFromMap(
        new WeakHashMap< YourClassGoesHere , Boolean >()
    )
;

Значение карты, Boolean, здесь не имеет значения, так как ключ карты составляет нашу Set.

В сценарии, таком как pub-sub, нам нужна безопасность потоков, если подписчики и издатели работают в отдельных потоках (вполне вероятно, что так и есть).

Пройдите еще один шаг, обернув его как синхронизированный набор, чтобы сделать этот набор потокобезопасным. Введите в Collections.synchronizedSet. 

this.subscribers =
        Collections.synchronizedSet(
                Collections.newSetFromMap(
                        new WeakHashMap <>()  // Parameterized types `< YourClassGoesHere , Boolean >` are inferred, no need to specify.
                )
        );

Теперь мы можем добавлять и удалять подписчиков из нашего получившегося Set. И любые «исчезающие» подписчики будут в конечном итоге автоматически удалены после выполнения сборки мусора. Когда это произойдет, зависит от реализации вашего сборщика мусора в JVM и зависит от ситуации времени выполнения. Для обсуждения и примера того, когда и как базовый WeakHashMap очищает записи с истекшим сроком, см. Этот вопрос, * Всегда ли WeakHashMap постоянно растет, или он очищает ключи мусора? *.

...