Одновременное слияние списков - что лучше: CopyOnWriteArrayList или ConcurrentLinkedQueue?

Поддержка. Есть несколько потоков, выполняющих задачи запроса, каждый из которых будет возвращать list в качестве результата. Какая структура данных будет быстрее объединять результаты?

ConcurrentLinkedQueue

Неограниченная потокобезопасная очередь на основе связанных узлов. Эта очередь упорядочивает элементы FIFO (first-in-first-out). Голова очереди - это элемент, который находится в очереди дольше всех. Хвост очереди - это тот элемент, который находился в очереди самое короткое время. Новые элементы вставляются в конец очереди, и операции извлечения очереди получают элементы в начале очереди. ConcurrentLinkedQueue - подходящий выбор, когда многие потоки будут совместно использовать доступ к общей коллекции. Как и большинство других реализаций параллельных коллекций, этот класс не позволяет использовать нулевые элементы. В этой реализации используется эффективный алгоритм "без ожидания", основанный на алгоритме, описанном в книге Магед М. Майкл и Майкла Л. Скотта в книге "Простые, быстрые и практические неблокирующие и блокирующие параллельные алгоритмы очереди".

CopyOnWriteArrayList

Как следует из названия, CopyOnWriteArrayList создает копию базового ArrayList с каждой операцией мутации, например. добавить или установить. Обычно CopyOnWriteArrayList очень дорого обходится, потому что он включает в себя дорогостоящее копирование массива с каждой операцией записи, но он очень эффективен, если у вас есть список, в котором количество итераций превышает количество мутаций, например в основном вам нужно перебирать ArrayList и не изменять его слишком часто.


java multithreading concurrency java.util.concurrent copyonwritearraylist
person zhumengzhu    schedule 19.09.2016    source источник
comment
Что вы думаете?   -  person Kayaman    schedule 19.09.2016
comment
Весь подход, когда несколько потоков объединяют свои выходные данные в общую структуру данных, ошибочен. Оптимальные системы никогда этого не делают; вместо этого у них есть нисходящий поток, который принимает частичные результаты из нескольких потоков в параллельной очереди, а затем объединяется в одной пакетной операции.   -  person Marko Topolnik    schedule 19.09.2016
comment
@MarkoTopolnik это исключит сценарий, в котором у вас есть долгоживущие потоки и вы хотите проверять результаты по мере их создания, вместо того, чтобы ждать окончательной пакетной операции.   -  person tucuxi    schedule 19.09.2016
comment
@tucuxi Учитывая описание OP, это было бы прекрасно. Выполняются два запроса, каждый из которых возвращает список.   -  person Marko Topolnik    schedule 19.09.2016
comment
Поддержите там метод запроса List<City> getCityListByIds(List<Long> idList), idList может быть очень большим, поэтому запрос может быть очень медленным. Поэтому я разделил большой list на несколько маленьких list и преобразовал их в Callable задачи, а затем отправил их в ThreadPoolExecutor. Вот почему у меня такой вопрос. Извините за мой плохой английский. @MarkoTopolnik @tucuxi   -  person zhumengzhu    schedule 19.09.2016
comment
Вы в значительной степени описываете, в чем API Java Streams лучше всего: распараллеливание данных. Тебе стоит попробовать это использовать.   -  person Marko Topolnik    schedule 19.09.2016
comment
@Kayaman Я думаю, ConcurrentLinkedQueue может быть быстрее, поэтому провожу простой тест. Но результат показывает, что CopyOnWriteArrayList быстрее. Я не уверен, что мой тестовый код был правильным, потому что вы знаете, что написать правильный параллельный тест сложно и сложно.   -  person zhumengzhu    schedule 19.09.2016
comment
@Marko Topolnik Java Streams API кажется особенностью Java 8, сейчас я могу использовать только Java 7 в своей работе.   -  person zhumengzhu    schedule 19.09.2016
comment
Зачем вам нужна параллельная структура данных для объединения этих списков, как предлагает @MarkoTopolnik? Вы можете сэкономить на одновременном доступе, возвращая подсписки городов и объединяя их в простой ArrayList в своем методе getCityListByIds. Это также будет тратить меньше памяти, чем реализация CopyOnWriteList.   -  person bashnesnos    schedule 19.09.2016
comment
Да, вы можете собрать все частичные результаты из Futures и объединить их в поток, инициировавший запрос.   -  person Marko Topolnik    schedule 19.09.2016
comment
@bashnesnos При объединении результатов в основной поток необходимо дождаться завершения всех задач. Просто подумал, что слияние в подпоток может быть быстрее.   -  person zhumengzhu    schedule 19.09.2016
comment
Проверьте ExecutorCompletionService, вы можете собрать результаты, как только они будут готовы, все в основном потоке.   -  person Marko Topolnik    schedule 19.09.2016
comment
Подумайте об этом так: в любом случае вам нужно дождаться завершения всех ваших подпотоков, поскольку ваши результаты не готовы. Таким образом, вы пытаетесь сэкономить на объединении списков одновременно в своих подпотоках, а не на объединении в основном потоке. В любом случае параллельные операции будут стоить дороже из-за затрат на синхронизацию, и вы можете объединить результаты в своем основном потоке, как только любой из ваших подпотоков будет завершен (например, проверив Future.isDone () в цикле), чтобы вы не пропустите слишком много времени, ожидая завершения всех ваших потоков, прежде чем вы сможете начать слияние.   -  person bashnesnos    schedule 21.09.2016
comment
Вопрос в основном академический, если OP не объясняет, какой длины будут списки результатов, насколько велик будет список конечных результатов и другие практические ограничения. Даже тогда, если единственное решение - между CLQ и COWAL, почему бы не провести несколько раз на нагрузке, аналогичной наблюдаемой, и выбрать лучшую?   -  person tucuxi    schedule 26.02.2018

Ответы (2)


arrow_upward
4
arrow_downward

ConcurrentLinkedQueue позволяет писать без ожидания и очень эффективно. Он будет медленнее, чем CopyOnWriteArrayList для чтения, но ненамного. Для этого потребуется немного больше места (меньше указателей вокруг).

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

Слияние (при условии, что вы не заботитесь об упорядочивании или дублировании) - это операция только для записи, поэтому вам следует выбрать ConcurrentLinkedQueue.

person tucuxi    schedule 19.09.2016
comment
Да, я не забочусь о заказах или дубликатах. - person zhumengzhu; 19.09.2016
comment
Я только что прочитал исходный код CopyOnWriteArrayList. И да, для записи требуются полные копии. Но когда мы копируем список, мы будем использовать метод addAll(), который будет использовать System.arraycopy() API для пакетного копирования массива, это очень эффективно. - person zhumengzhu; 19.09.2016

arrow_upward
2
arrow_downward

Если ваши задачи запроса действительно возвращают список, тогда будет намного быстрее объединить результаты в одном потоке с использованием обычного ArrayList.

person Matt Timmermans    schedule 19.09.2016
comment
Я понял, что потоки одновременно пытались заполнить список результатов - person tucuxi; 19.09.2016
comment
@tucuxi В результате каждая задача возвращает list. - person zhumengzhu; 19.09.2016