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

Question

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

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

1) CopyOnWriteArraySet

2) коллекций.synchronizedSet (Set set)

3) ConcurrentSkipListSet

4) коллекций.newSetFromMap (new ConcurrentHashMap ())

5) Другие наборы генерируются таким же образом, как (4)

эти примеры приходят от шаблон параллелизма: параллельные реализации набора в Java 6

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

1053 3

java concurrency set

3 ответов:

Comments

Ничего не найдено.

Paŭlo Ebermann · Accepted Answer · 2015-11-25 20:02:00

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

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

2) Collections.synchronizedSet просто обернет синхронизированный блок вокруг каждого метода исходного набора. Вы не должны напрямую обращаться к исходному набору. Это означает, что никакие два метода набора не могут выполняться одновременно (один блокируется до другого finishes)-это потокобезопасно, но у вас не будет параллелизма, если несколько потоков действительно используют набор. При использовании итератора обычно требуется внешняя синхронизация, чтобы избежать 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) существуют ли другие параллельные реализации карт, которые можно было бы использовать здесь?

Oleg Estekhin · Accepted Answer · 2016-09-05 05:50:26

можно комбинировать 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;
            }
        }
    }

}

Ryan Stewart · Accepted Answer · 2011-07-17 04:09:01

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

CopyOnWriteArraySet создает новую копию базового массива каждый раз, когда вы мутируете коллекцию, поэтому записи медленны, а итераторы быстры и последовательны.

сборники.synchronizedSet () использует вызовы методов старой школы synchronized, чтобы сделать набор потокобезопасным. Это было бы низкоэффективным версия.

ConcurrentSkipListSet предлагает производительные записи с несогласованными пакетными операциями (addAll, removeAll и т. д.) и итераторы.

сборники.newSetFromMap (new ConcurrentHashMap ()) имеет семантику ConcurrentHashMap, которая, как я считаю, не обязательно оптимизирована для чтения или записи, но, как и ConcurrentSkipListSet, имеет несогласованные пакетные операции.