Выбор лучшего списка параллелизма в Java [закрыто]

100

В моем пуле потоков есть фиксированное количество потоков. Эти потоки должны часто писать и читать из общего списка.

Итак, какая структура данных в java.util.concurrentпакете (лучше List, должна быть без монитора) лучше всего в этом случае?

java concurrency 象 嘉 道
источник
5
Это зависит от того, что вы хотите делать с коллекцией. См. Мой пост в блоге (хотя он про .Net, концепции те же). Вы вряд ли сможете написать правильный потокобезопасный код с расширением List.
SLaks
1
Теперь я использую CopyOnWriteArrayList , но исключение ConcurrentModificationException по-прежнему иногда возникает.
象 嘉 道
2
Включите дополнительную информацию о том, что вы делаете с коллекцией, чтобы люди могли ответить лучше, иначе это просто предположение.
mattsh
2
ConcurrentModificationExceptionНе может исходить от проблемы синхронизации; он также возникает, например, в цикле for для коллекции, когда вы пытаетесь удалить элемент из коллекции.
toto2
1
Я знаю, что это не входит в комплект, но кто-нибудь пробовал Vector?
WesternGun

Ответы:

99

лучше бы быть List

Только List внедрение в java.util.concurrentэтом CopyOnWriteArrayList . Также есть возможность синхронизировать список, как упоминает Трэвис Уэбб.

Тем не менее, вы уверены, что вам это нужно List? Существует гораздо больше вариантов для одновременных Queues и Maps (и вы можете создавать Sets из Maps), и эти структуры, как правило, имеют наибольший смысл для многих типов вещей, которые вы хотите делать с общей структурой данных.

Для очередей у ​​вас есть огромное количество вариантов, и какой из них наиболее подходит, зависит от того, как вам нужно его использовать:

ColinD
источник
15
CopyOnWriteArrayListимеет недостаток в том, что он очень дорог при записи (но дешев при чтении). Если вы выполняете много операций записи, вам лучше использовать синхронизированный список или очередь.
Питер Лоури
69

Любую коллекцию Java можно сделать потокобезопасной, например:

List newList = Collections.synchronizedList(oldList);

Или создать новый список потоковой безопасности:

List newList = Collections.synchronizedList(new ArrayList());

http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

Трэвис Уэбб
источник
7
По этой причине вы не найдете реализаций списков в java.util.concurrent - хм, есть ConcurrentHashMapдаже несмотря на то, что есть Collections.synchronizedMapметод.
aioobe
7
Прочтите Javadocs дальше ConcurrentHashMap. Детали реализации синхронизации различны. использование synchronizedметодов в Collectionsосновном просто оборачивает класс в монитор Java. ConcurrentHashMapиспользует более умные функции параллелизма.
Travis Webb
1
Ага. Тем не менее, это делает ваше последнее предложение недействительным.
aioobe
1
Если использовать монитор, производительность программы действительно плохая :-(
象 嘉 道
6
Чтобы добавить, итерация по newList не является потокобезопасной. !!
bluelurker
9

Если размер списка фиксирован, вы можете использовать AtomicReferenceArray . Это позволит вам выполнять индексированные обновления слота. При необходимости вы можете написать представление списка.

Бен Манес
источник
6

ConcurrentLinkedQueueиспользует очередь без блокировок (на основе более новой инструкции CAS ).

eSniff
источник
7
... который не реализует Listинтерфейс.
aioobe
1
eSniff, как бы вы приступили к реализации List.set(int index, Object element)с ConcurrentLinkedQueue?
John Vint
4
Большинство Listспецифических методов либо не будут реализованы с использованием Queue(например, добавить / установить по определенному индексу), либо могут быть реализованы, но будут неэффективными (получить из индекса). Так что я не думаю, что вы действительно можете обернуть это. Тем не менее, я думаю, что предложение о создании файла - Queueэто нормально, поскольку ОП на самом деле не объяснил, зачем им нужен List.
ColinD
1
@ColinD - вот ответ, который я искал. Есть веские причины, по которым CLQ нельзя заключить в список. Хотя я согласен, не могу исключить интерфейс очереди.
Джон Винт
1
❗️ Стоит отметить, что: «Помните, что, в отличие от большинства коллекций, метод размера НЕ является операцией с постоянным временем. Из-за асинхронного характера этих очередей определение текущего количества элементов требует обхода элементов».
βξhrαng
6

Возможно, вам стоит взглянуть на ConcurrentDoublyLinkedList, написанный Дугом Ли на основе «Практического двусвязного списка без блокировок» Пола Мартина. Он не реализует интерфейс java.util.List, но предлагает большинство методов, которые вы бы использовали в List.

Согласно javadoc:

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

притворства
источник
3

Если установлено достаточно, можно использовать ConcurrentSkipListSet . (Его реализация основана на ConcurrentSkipListMap, который реализует список пропуска .)

Ожидаемые средние временные затраты составляют log (n) для операций включения, добавления и удаления; метод размера не является операцией с постоянным временем.

анре
источник