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

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

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (установить набор)

3) ConcurrentSkipListSet

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

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

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

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

111 голосов | спросил Ben 17 J000000Sunday11 2011, 01:35:20

4 ответа


0

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

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

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

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

3) ConcurrentSkipListSet - это одновременно SortedSet

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

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

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

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

ответил Paŭlo Ebermann 17 J000000Sunday11 2011, 02:27:33
0

Можно комбинировать производительность 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;
            }
        }
    }

}
ответил Oleg Estekhin 17 Jpm1000000pmFri, 17 Jan 2014 20:41:56 +040014 2014, 20:41:56
0

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

  • CopyOnWriteArraySet создает новую копию базового массива каждый раз, когда вы изменяете коллекцию, поэтому записи выполняются медленно, а итераторы - быстры и согласованы.
  • Collections.synchronizedSet () использует вызовы синхронизированных методов старой школы для обеспечения безопасности потока Set. Это будет неэффективная версия.
  • ConcurrentSkipListSet предлагает эффективные записи с несовместимыми пакетными операциями (addAll, removeAll и т. д.) и итераторами.
  • Collections.newSetFromMap (новый ConcurrentHashMap ()) имеет семантику ConcurrentHashMap, которая, я считаю, не обязательно оптимизирована для чтения или записи, но, как и ConcurrentSkipListSet, имеет несовместимые пакетные операции.
ответил Ryan Stewart 17 J000000Sunday11 2011, 01:59:26
0

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

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

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

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

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

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

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

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

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

ответил Basil Bourque 13 +03002018-10-13T22:17:54+03:00312018bEurope/MoscowSat, 13 Oct 2018 22:17:54 +0300 2018, 22:17:54

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132