Потокобезопасные коллекции java

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

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

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

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

3 ответа:

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) существуют ли другие параллельные реализации карт, которые можно было бы использовать здесь?

10 советов по многопоточному программированию на Java

Переводы, 31 мая 2015 в 14:35

Рассказывает Дж. Пол, автор блога Java Revisited

Написание параллельного кода – непростая задача, а проверка его корректности – задача еще сложнее. Несмотря на то, что Java предоставляет обширную поддержку многопоточности и синхронизации на уровне языка и API, на деле же оказывается, что написание корректного многопоточного Java-кода зависит от опыта и усердности конкретного программиста. Ниже изложен набор советов, которые помогут вам качественно повысить уровень вашего многопоточного кода на Java. Некоторые из вас, возможно, уже знакомы с этими советами, но никогда не помешает освежать их в памяти раз в пару лет.

Многие из этих советов появились в процессе обучения и практического программирования, а также после прочтения книг «Java concurrency in practice» и «Effective Java». Я советую прочитать первую каждому Java-программисту два раза; да, всё правильно, ДВА раза. Параллелизм – запутанная и сложная для понимания тема (как, например, для некоторых – рекурсия), и после однократного прочтения вы можете не до конца всё понять.

Единственная цель использования параллелизма – создание масштабируемых и быстрых приложений, но при этом всегда следует помнить, что скорость не должна становиться помехой корректности. Ваша Java-програма должна удовлетворять своему инварианту независимо от того, запущена ли она в однопоточном или многотопочном виде. Если вы новичок в параллельном программировании, для начала ознакомьтесь с различными проблемами, возникающими при параллельном запуске программ (например: взаимная блокировка, состояние гонки, ресурсный голод и т.д.).

1. Используйте локальные переменные

Всегда старайтесь использовать локальные переменные вместо полей класса или статических полей. Иногда разработчики используют поля класса, чтобы сэкономить память и переиспользовать переменные, полагая, что создание локальной переменной при каждом вызове метода может потребовать большого количества дополнительной памяти. Одним из примеров такого использования может послужить коллекция (Collection), объявленная как статическое поле и переиспользуемая с помощью метода clear(). Это переводит класс в общее состояние, которого он иметь не должен, т.к. изначально создавался для параллельного использования в нескольких потоках. В коде ниже метод execute() вызывается из разных потоков, а для реализации нового функционала потребовалась временная коллекция. В оригинальном коде была использована статическая коллекция (List), и намерение разработчика были ясны — очищать коллекцию в конце метода execute() , чтобы потом можно было её заново использовать. Разработчик полагал, что его код потокобезопасен, потому что CopyOnWriteArrayList потокобезопасен. Но это не так — метод execute() вызывается из разных потоков, и один из потоков может получить доступ к данным, записанным другим потоком в общий список. Синхронизация, предоставляемая CopyOnWriteArrayList в данном случае недостаточна для обеспечения инвариантности метода execute() .

Проблема: Данные одного сообщения попадут в другое, если два вызова execute() «пересекаются», т.е. первый поток добавит id из первого сообщения, затем второй поток добавит id из второго сообщения (это произойдёт ещё до очистки списка), таким образом данные одного из сообщений будут повреждены.

Варианты решений:

1. Добавить блок синхронизации в ту часть кода, где поток добавляет что-то во временный список и очищает его. Таким образом, другой поток не сможет получить доступ к списку, пока первый не закончит работу с ним. В таком случае эта часть кода будет однопоточной, что уменьшит производительность приложения в целом.
2. Использовать локальный список в место поля класса. Да, это увеличит затраты памяти, но избавит от блока синхронизации и сделает код более читаемым. Также вам не придётся беспокоиться о временных объектах – о них позаботится сборщик мусора.

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

2. Предпочитайте неизменяемые классы изменяемым

Самая широко известная практика в многопоточном программировании на Java – использование неизменяемых (immutable) классов. Неизменяемые классы, такие как String, Integer и другие упрощают написание параллельного кода в Java, т.к. вам не придётся беспокоиться о состоянии объектов данных классов. Неизменяемые классы уменьшают количество элементов синхронизации в коде. Объект неизменяемого класса, будучи однажды созданным, не может быть изменён. Самый лучший пример такого класса – строка ( java.lang.String ). Любая операция изменения строки в Java (перевод в верхний регистр, взятие подстроки и пр.) приведёт к созданию нового объекта String для результата операции, оставив исходную строку нетронутой.

3. Сокращайте области синхронизации

Любой код внутри области синхронизации не может быть исполнен параллельно, и если в вашей программе 5% кода находится в блоках синхронизации, то, согласно закону Амдала, производительность всего приложения не может быть улучшена более, чем в 20 раз. Главная причина этого в том, что 5% кода всегда выполняется последовательно. Вы можете уменьшить это количество, сокращая области синхронизации – попробуйте использовать их только для критических секций. Лучший пример сокращения областей синхронизации – блокировка с двойной проверкой, которую можно реализовать в Java 1.5 и выше с помощью volatile переменных.

4. Используйте пул потоков

Создание потока (Thread) — дорогая операция. Если вы хотите создать масштабируемое Java-приложение, вам нужно использовать пул потоков. Помимо тяжеловесности операции создания, управление потокам вручную порождает много повторяющегося кода, который, перемешиваясь с бизнес-логикой, уменьшает читаемость кода в целом. Управление потоками – задача фреймворка, будь то инструмент Java или любой другой, который вы захотите использовать. В JDK есть хорошо организованный, богатый и полностью протестированный фреймворк, известный как Executor framework, который можно использовать везде, где потребуется пул потоков.

5. Используйте утилиты синхронизации вместо wait() и notify()

В Java 1.5 появилось множество утилит синхронизации, таких как CyclicBarrier, CountDownLatch и Semaphore. Вам всегда следует сначала изучить, что есть в JDK для синхронизации, прежде чем использовать wait() и notify() . Будет намного проще реализовать шаблон читатель-писатель с помощью BlockingQueue, чем через wait() и notify() . Также намного проще будет подождать 5 потоков для завершения вычислений, используя CountDownLatch, чем реализовывать то же самое через wait() и notify() . Изучите пакет java.util.concurrent , чтобы писать параллельный код на Java лучшим образом.

6. Используйте BlockingQueue для реализации Producer-Consumer

Этот совет следует из предыдущего, но я выделил его отдельно ввиду его важности для параллельных приложений, используемых в реальном мире. Решение многих проблем многопоточности основано на шаблоне Producer-Consumer, и BlockingQueue – лучший способ реализации его в Java. В отличие от Exchanger, который может быть использовать в случае одного писателя и читателя, BlockingQueue может быть использована для правильной обработки нескольких писателей и читателей.

7. Используйте потокобезопасные коллекции вместо коллекций с блокированием доступа

Потокобезопасные коллекции предоставляют большую масштабируемость и производительность, чем их аналоги с блокированием доступа ( Collections.synchronizedCollection и пр.). СoncurrentHashMap, которая, по моему мнению, является самой популярной потокобезопасной коллекцией, демострирует лучшую производителность, чем блокировочные HashMap или Hashtable, в случае, когда количество читателей превосходит количество писателей. Другое преимущество потокобезопасных коллекций состоит в том, что они реализованы с помощью нового механизма блокировки ( java.util.concurrent.locks.Lock ) и используют нативные механизмы сихнронизации, предоставленные низлежащим аппаратным обеспечением и JVM. Вдобавок используйте CopyOnWriteArrayList вместо Collections.synchronizedList , если чтение из списка происходит чаще, чем его изменение.

8. Используйте семафоры для создания ограничений

Чтобы создать надёжную и стабильную систему, у вас должны быть ограничения на ресурсы (базы данных, файловую систему, сокеты и т.д.). Ваш код ни в коем случае не должен создавать и/или использовать бесконечное количество ресурсов. Семафоры ( java.util.concurrent.Semaphore ) — хороший выбор для создания ограничений на использование дорогих ресурсов, таких как подключения к базе данных (кстати, в этом случае можно использовать пул подключений). Семафоры помогут создать ограничения и заблокируют потоки в случае недоступности ресурса.

9. Используйте блоки синхронизации вместо блокированных методов

Данный совет расширяет совет по сокращению областей синхрониации. Использование блоков синхронизации – один из методов сокращения области синхронизации, что также позволяет выполнить блокировку на объекте, отличном от текущего, представленного указателем this . Первым кандитатом должна быть атомарная переменная, затем volatile переменная, если они удовлетворяют ваши требования к синхронизации. Если вам требуется взаимное исключение, используйте в первую очередь ReentrantLock, либо блок synchronized . Если вы новичок в параллельном программировании, и не разрабатываете какое-либо жизненно важное приложение, можете просто использовать блок synchronized — так будет безопаснее и проще.

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

Как показано в первом совете, статические переменные, будучи использованными в параллельном коде, могут привести к возникновению множества проблем. Если вы всё-таки используете статическую переменную, убедитесь, что это константа либо неизменяемая коллекция. Если вы думаете о том, чтобы переиспользовать коллекцию с целью экономии памяти, вернитесь ещё раз к первому совету.

11. Используйте Lock вместо synchronized

Последний, бонусный совет, следует использовать с осторожностью. Интерфейс Lock — мощный инструмент, но его сила влечёт и большую ответственность. Различные объекты Lock на операции чтения и записи позволяют реализовывать масштабируемые структуры данных, такие как ConcurrentHashMap, но при этом требуют большой осторожности при своём программировании. В отличие от блока synchronized, поток не освобождает блокировку автоматически. Вам придётся явно вызывать unlock() , чтобы снять блокировку. Хорошей практикой является вызов этого метода в блоке finally, чтобы блокировка завершалась при любых условиях:

Заключение

Вам были представлены советы по написанию многопоточного кода на Java. Ещё раз повторюсь, никогда не помешает перечитывать «Java concurrency in practice» и «Effective Java» время от времени. Также можно вырабатывать нужный для параллельного програмирования способ мышления, просто читая чужой код и пытаясь визуализировать проблемы во время разработки. В завершение спросите себя, каких правил вы придерживаетесь, когда разрабатываете многопоточные приложения на Java?

Параллельные классы коллекций

ConcurrentHashMap и CopyOnWriteArrayList предлагают потокобезопасность и улучшенную масштабируемость

Серия контента:

Этот контент является частью # из серии # статей: Теория и практика Java

Этот контент является частью серии: Теория и практика Java

Следите за выходом новых статей этой серии.

Первым ассоциативным классом коллекций, который появился библиотеке классов Java, был Hashtable , который являлся частью JDK 1.0. Hashtable предоставлял легкую в использовании, потокобезопасную реализацию ассоциативной map-таблицы и, конечно, был удобен. Однако потокобезопасность обошлась дорого — все методы в Hashtable были синхронизированы. В то время за синхронизацию без конкуренции приходилось расплачиваться производительностью. Преемник Hashtable , HashMap , появившийся как часть Collections framework в JDK 1.2, решал проблему потокобезопасности, предоставляя несинхронизированный базовый класс и синхронизированное обрамление, Collections.synchronizedMap . Разделение базовой функциональности и потокобезопасности в Collections.synchronizedMap позволило получить синхронизацию пользователям, которым она была нужна, а тем, кому она не нужна, не приходилось платить за неё цену.

Упрощённый подход к синхронизации, использованный и в Hashtable и в synchronizedMap , — синхронизация каждого метода с Hashtable или с синхронизированным объектом обрамления Map — имеет два основных недостатка. Он является препятствием для масштабируемости, потому что к хеш-таблице может одновременно обращаться только один поток. Одновременно с этим, недостаточно обеспечить настоящую безопасность потоков, при этом множество распространённых составных операций всё ещё требует дополнительной синхронизации. Хотя простые операции вроде get() и put() могут выполняться безопасно без дополнительной синхронизации, существуют несколько распространённых последовательностей операций, таких как iterate или put-if-absent, которые всё же нуждаются во внешней синхронизации, чтобы избежать конкуренции за данные.

Условная потокобезопасность

Синхронизированные обрамления коллекций synchronizedMap и synchronizedList иногда называют условно потокобезопасными — все операции в отдельности потокобезопасны, но последовательности операций, где управляющий поток зависит от результатов предыдущих операций, могут быть причиной конкуренции за данные. Первый отрывок в Листинге 1 демонстрирует распросранённую идиому put-if-absent (запись-если-пусто) — если элемент ещё не существует в Map -таблице, добавить его. К сожалению, как уже говорилось, у другого потока существует возможность вставить значение с повторяющимся ключом между моментами возврата из метода containsKey() и вызова метода put() . Если вы хотите гарантировать, что вставка выполняется строго один раз, вам необходимо заключить пару выражений в синхронизированный блок, который синхронизируется с Map m .

Другие примеры в Листинге 1 связаны с повторением. В первом примере результаты List.size() могли стать недействительными во время выполнения цикла, потому что другой поток мог удалить элементы из списка. Если ситуация сложилась неудачно, и элемент был удален другим потоком сразу же после начала последнего повторения цикла, то List.get() возвратит null и doSomething() скорее всего выбросит NullPointerException . Что вам можно сделать, чтобы избежать этого? Если другой поток может обращаться к List , в то время, когда вы выполняете его перебор, вы должны заблокировать весь List на время перебора, заключив его в блок synchronized , синхронизирующийся с List l . Это решает проблемы с конкуренцией за данные, но в дальнейшем скажется на параллелизме, поскольку блокировка всего List во время перебора может надолго заблокировать доступ к списку другим потокам.

В Collections framework были введены итераторы для обхода списка или другой коллекции, которые оптимизируют процесс перебора элементов коллекции. Однако итераторы, реализованные в классах коллекций java.util , часто подвержены сбоям, что означает, что если один поток изменяет коллекцию в то время, когда другой пропускает её через Iterator , очередной вызов Iterator.hasNext() или Iterator.next() выбросит ConcurrentModificationException . Как и с предыдущим примером, если вы хотите предотвратить ConcurrentModificationException , вам надо целиком блокировать List в то время, когда вы выполняете повторения, заключив его внутрь блока synchronized , который синхронизируется с List l . (В качестве альтернативы, вы можете вызвать List.toArray() и делать перебор в массиве без синхронизации, но это может быть дорого, если список достаточно большой.)

Листинг 1. Типичный случай конкуренции в синхронизированных map-таблицах

Ложное чувство уверенности

Условная безопасность потоков, обеспечиваемая synchronizedList и synchronizedMap представляет скрытую угрозу — разработчики полагают, что, раз эти коллекции синхронизированы, значит, они полностью потокобезопасны, и пренебрегают должной синхронизацией составных операций. В результате, хотя эти программы и работают при лёгкой нагрузке, но при серьёзной нагрузке они могут начать выкидывать NullPointerException или ConcurrentModificationException .

Проблемы масштабируемости

Масштабируемость показывает, как меняется пропускная способность приложения при увеличении рабочей нагрузки и доступных вычислительных ресурсов. Масштабируемая программа может выдержать пропорционально большую нагрузку при большем количестве процессоров, памяти или пропускной способности ввода/вывода. Блокировка ресурса общего пользования ради монопольного доступа представляет собой проблему для масштабируемости — она не позволяет другим потокам получить доступ к этому ресурсу даже при наличии простаивающих процессоров для планирования этих потоков. Для достижения масштабируемости мы должны исключить или сократить нашу зависимость от монопольных блокировок ресурсов.

Ещё большая проблема с синхронизированным обрамлением коллекций и ранними классами Hashtable и Vector состоит в том, что они синхронизируются с единственной блокировкой. Это означает, что одновременно только один поток может иметь доступ к коллекции, и если один поток находится в процессе чтения Map -таблицы, все остальные потоки, которые хотят прочитать из неё или записать в неё, вынуждены ждать. Наиболее распространённые операции с Map -таблицей, get() и put() , могут требовать больших вычислений, чем это может показаться, — при обходе хеш-бакета в поисках специфического значения ключа get() может потребоваться вызов Object.equals() для большого количества кандидатов. Если функция hashCode() , используемая классом ключа, не распределяет значения равномерно по всему ряду хэшей или же имеет большое количество коллизий хэша, отдельные цепочки бакетов могут оказаться намного длиннее других, а прохождение длинной цепочки хэшей и вызов equals() на определённом проценте его элементов могут быть слишком медленными. Проблема высокой стоимости get() и put() при таких условиях выражается не только в том, что доступ будет медленным, но и в том, что всем другим потокам блокируется доступ к Map -таблице пока происходит обход этой цепочки хэшей.

Тот факт, что get() в некоторых случаях может требовать значительного времени на выполнение, ещё больше усугубляется проблемой условной безопасности потоков, обсуждавшейся выше. Условия конкуренции, иллюстрируемые в Листинге 1, часто делают необходимым, чтобы единичная блокировка коллекции удерживалась гораздо большее время, чем требуется на выполнение единичной операции. Если вы собираетесь удерживать блокировку коллекции в течение всего перебора, то другие потоки могут замереть в ожидании блокировки коллекции на длительное время.

Пример: Простая кэш-память

Одно из наиболее распространённых применений для Map в серверных приложениях — реализация кэш-памяти. Серверные приложения могут кэшировать содержимое файлов, сгенерированные страницы, результаты запросов к базам данных, деревья DOM, ассоциированные с анализируемыми XML-файлами и многие другие типы данных. Основное назначение кэш-памяти — сокращение времени обслуживания и увеличение пропускной способности за счёт использования результатов предыдущего вычисления. Типичная особенность рабочей нагрузки кэш-памяти состоит в том, что попадания встречаются гораздо чаще, чем обновления, поэтому (в идеале) кэш-память обеспечивает очень хорошую производительность для get() . Кэш-память, тормозящая производительность приложения, даже хуже, чем полное отсутствие кэш-памяти.

Если вы использовали synchronizedMap для реализации кэш-памяти, вы вносите в ваше приложение потенциальную проблему масштабируемости. Одновременно только один поток может иметь доступ к Map , и это распространяется на все потоки, которые могут извлекать значение из Map -таблицы, равно как и на потоки, которые желают вставить новую пару (key, value) в map-таблицу.

Сокращение размеров блокировок

Один из подходов к улучшению параллелизма HashMap при сохранении потокобезопасности состоит в том, чтобы обходиться без единой блокировки всей таблицы и использовать блокировки для каждого бакета хэшей (или, в более общем случае, пула блокировок, где каждая блокировка защищает несколько бакетов). Это означает, что сразу несколько потоков могут обращаться к различным частям Map одновременно, без соперничества за единственную на всю коллекцию блокировку. Этот подход сразу же улучшает масштабируемость операций вставки, извлечения и удаления. К сожалению, такой параллелизм имеет свою цену — сложнее становится реализовывать методы, работающие с целой коллекцией, такие как size() или isEmpty() , потому что для этого может потребоваться получение сразу множества блокировок или появляется риск вернуть неточный результат. Тем не менее, для ситуаций вроде реализации кэш-памяти это представляет разумный компромисс — операции извлечения и вставки часты, тогда как операции size() и isEmpty() — значитель менее частые.

ConcurrentHashMap

Класс ConcurrentHashMap из util.concurrent (который также появится в пакете java.util.concurrent в JDK 1.5) — это потокобезопасная реализация Map , предоставляющая намного большую степень параллелизма, чем synchronizedMap . Сразу много операций чтения могут почти всегда выполняться параллельно, одновременные чтения и записи могут обычно выполняться параллельно, а сразу несколько одновременных записей могут зачастую выполняться параллельно. (Соответственный класс ConcurrentReaderHashMap предлагает аналогичный параллелизм для множественных операций чтений, но допускает лишь одну активную операцию записи.) ConcurrentHashMap спроектирован для оптимизации операций извлечения; на деле, успешные операции get() обычно успешно выполняются безо всяких блокировок. Достижение потокобезопасности без блокировок является сложным и требует глубокого понимания деталей Модели Памяти Java (Java Memory Model). Реализация ConcurrentHashMap и остальная часть util.concurrent были в значительной степени проанализированы экспертами по параллелизму на предмет корректности и безопасности потоков. Мы рассмотрим детали реализации ConcurrentHashMap в статье в следующем месяце.

ConcurrentHashMap добивается более высокой степени параллелизма, слегка смягчая обещания, которые даются тем, кто её вызывает. Операция извлечения возвратит значение, вставленное самой последней завершившейся операцией вставки, а также может возвратить значение, добавленное операцией вставки, выполняемой в настоящее время (но она никогда не возвратит бессмыслицы). Итераторы , возвращаемые ConcurrentHashMap.iterator() возвратят каждый элемент не более одного раза и никогда не выкинут ConcurrentModificationException , но могут отображать или не отображать вставки или удаления, имевшие место со времени, когда итератор был сконструирован. Блокировки целой таблицы не требуются (да и невозможны) для обеспечения потокобезопасности при переборе коллекции. ConcurrentHashMap может использоваться для замены synchronizedMap или Hashtable в любом приложении, которое не основано на способности делать блокировку всей таблицы для предотвращения модификаций.

Данные компромиссы позволяют ConcurrentHashMap обеспечивать намного более высокую масштабируемость, чем Hashtable , не ставя под угрозу его эффективность для широкого множества распространённых случаев, таких как кэш-память с общим доступом.

Насколько лучше?

Таблица 1 приблизительно показывает отличия в масштабируемости между Hashtable и ConcurrentHashMap . При каждом запуске n потоков параллельно выполняли жёсткий цикл, в котором они извлекали произвольные значения ключа из Hashtable или из ConcurrentHashMap при 80 процентах неуспеха, выполняя операцию put() , и 1 проценте успешных извлечений при выполнении remove() . Тесты проводились на двухпроцессорной системе на базе Xeon под управлением системы Linux. Данные показывают время выполнения в миллисекундах для 10,000,000 итераций, приведённые к однопоточному случаю для ConcurrentHashMap . Вы можете видеть, что производительность ConcurrentHashMap остаётся масштабируемой до множества потоков, тогда как производительность Hashtable почти сразу падает при наличии конкуренции за блокировку.

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

Таблица 1. Масштабируемость Hashtable по сравнению с ConcurrentHashMap

Yuriy Tkach Blog

A blog on software engineering, programming technologies, application design, and just simple, but yet interesting life problems.

Thursday, September 19, 2013

Многопоточные коллекции в Java

Начиная с версии Java 5 в пакете java.util.concurrent появились реализации коллекций для эффективной работы в многопоточных приложения. Эти коллекции используют различные неблокирующие алгоритмы для достижения высокой скорости чтения/записи значений. Синхронизированный доступ происходит крайне редко и в целом не влияет на производительность. Почти. В зависимости от реализации. 🙂 Рассмотрению таких коллекций посвящен данный урок.

Со списками все просто: единственная существующая concurrent реализация — это CopyOnWriteArrayList . Из названия можно догадаться, как она работает — при изменении создается новая копия списка и, соответственно, происходит блокировка. При чтении блокировок нет. Следовательно, при частых операциях записи или удаления элементов работать будет медленнее, чем даже Collections.synchronizedList() , в котором блокируются все операции, но при этом нет копирования списка. На данном уроке Вы сможете на практике увидеть скороть и медлительность работы этой реализации. Вы напишите мультипоточное приложение, которое определит время чтения/записи значений в разные конкурентные списки.

Учитывая особенности работы CopyOnWriteArrayList , имеет смысл выбирать данную реализацию, только если Вам действительно необходим индексный доступ к элементам, либо в коллекции возможно хранение дубликатов. Данное утверждение справедливо не только к мультипоточным реализациям, а к любым спискам вообще. Если же элементы в коллекции уникальны, и Вам достаточно последовательного доступа, тогда вполне подойдет Set .

Concurrent реализаций интерфейса Set существует две. Первая — это CopyOnWriteArraySet . Свойства такие же, как и у аналогичного списка. Вторая реализация — это ConcurrentSkipListSet . Последняя основана на интересной структуре данных — слоёный список ( SkipList ). Подробнее на русском языке Вы можете прочитать на algolist.ru и википедии. Я скажу лишь, что она представляет собой связный список, где вставка и удаление элементов происходит достаточно быстро. Такая структура данных также хорошо подходит для неблокирующего доступа несколькими потоками, ведь, например, для вставки достаточно заблокировать изменение двух соседних элементов в связном списке. В дополнении ко всему, набор ConcurrentSkipListSet хранит значения в отсортированном виде, реализуя интерфейс NavigableSet . При этом, конечно, не стоит забывать о Comparator -е, который будет сравнивать элементы, или интерфейсе Comparable , который они могут реализовывать.

Для использования Map в многопоточной среде существуют два класса — ConcurrentSkipListMap и ConcurrentHashMap . Первая реализация подобна аналогичной для Set . Вторая подобна HashMap , где все пространство значений разбито на независимые области, каждая из которых представляет собой хеш-таблицу. При вставке элемента блокируется только одна область, позволяя параллельные чтение/запись в другие области. Используя этот класс, необходимо помнить о занимаемой памяти, так как для эффектиной работы с несколькими потоками, количество и размеры этих областей быстро растут. Еще одним полезным свойством обоих этих Map есть то, что они реализуют интерфейс ConcurrentMap . В нем представлены методы на основе неблокирующих алгоритмов, позволяющие безопасным образом выполнять проверку и изменение значений в рамках одной атомарной операции. Подобным образом работают атомарные переменные, такие как AtomicInteger и др. Подробнее о них я рассказывал на втором уроке из курса Advanced Java Concurrency.

В качестве домашнего задания для данного урока предлагаю добавить немного “параллелизма” в приложение, написанное для предыдущих уроков:

• Во-первых, добавьте параллельную загрузку всех праздников в отсортированный Set . Прочитав файл с помощью org.apache.commons.io.FileUtils.readLines(file, encoding) , передайте различные области списка нескольким потокам, которые будут парсить праздники и добавлять их в Set .
• Во-вторых, одновременно с загрузкой и парсингом праздников выполните подсчет количества праздников для каждого дня и каждого месяца. Для этого используйте отдельные Map для хранения того, сколько праздников будет в каждом дне и каждом месяце.
• В результате выполнения программы выведите наиболее и наименее “праздничный” день, а также количество праздников в каждом месяце.

Ну и, конечно, видео данной урока:

Какие коллекции Java синхронизированы (потокобезопасны), а какие нет?

Какие все коллекции Java синхронизированы и не синхронизированы

Пример: HashSet не синхронизирован

9 ответов

Существует три группы коллекций.

• Коллекция Java 1.0, которая в основном относится к устаревшим классам. Сюда входят Hashtable, Vector, Stack. Они синхронизированы, но я не рекомендую их использовать. Свойства — это, пожалуй, одно исключение, но я бы не использовал его в многопоточном контексте.
• Сборники Java 1.2, добавленные в 1998 году, которые в значительной степени заменяют эту коллекцию, не синхронизированы, но могут быть синхронизированы с использованием методов Collections.synchronizedXxx()
• Обновления Java 5.0 concurrency, добавленные в 2004 году, поддерживают блокировки, потокобезопасные коллекции.

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

Простой ответ: ни одна реализация Collection не синхронизируется, потому что synchronized не является свойством класса, он применим только к методам и блокам.

Полагаю, вы хотите знать, какие реализации являются поточно-ориентированными, какие классы из инфраструктуры java collection можно безопасно использовать в многопоточной среде.

Информация всегда включена в javadoc (как здесь: Arraylist — который не является потокобезопасным)

Вы можете получить синхронизированную версию Java Collection с

ArrayList, LinkedList, HashSet, LinkedHashset и TreeSet в интерфейсе коллекции и HashMap, LinkedHashMap и Treemap являются несинхронизированными.

Вектор в интерфейсе коллекции Синхронизированный

Предыдущий пример совершенно неправильный.

Прежде всего, вы не получаете доступ из разных потоков списка, который вы только что синхронизировали, вы не можете доказать, что синхронизация выполняется правильно, вы не можете доказать, что процесс добавления является атомарным. Во-вторых, синхронизированное предложение по самому списку является плохой практикой, вы не знаете, будет ли оптимизатор использовать элемент в списке для синхронизации, что приведет к неожиданному поведению. Кроме того, синхронизация — это доступ к элементам в списке чтения/записи, а не к самому списку. Выньте Collections.synchronized и просмотрите вывод. Попробуйте много раз. Пример:

1. ConcurrentHashMap

Потокобезопасен без синхронизации всей карты. Очень быстрое чтение, когда запись выполняется с блокировкой. Нет блокировки на уровне объекта. Использует множество блокировок.

1. SynchronizedHashMap

Синхронизация на уровне объекта. И чтение, и запись получают блокировку. Блокировка коллекции имеет недостаток производительности. Может вызвать конфликт

Вектор

Хеш-таблица

CopyOnWriteArrayList

CopyOnWriteArraySet

стек

Остальные все не нить безопасны

Все классы коллекций (кроме Vector и Hashtable) в пакете java.util не являются поточно-ориентированными. Только две старые коллекции являются поточно-ориентированными: Vector и Hashtable. ЗАЧЕМ? Вот причина: синхронизация может быть очень дорогой! Вы знаете, Vector и Hashtable — это две коллекции, которые существуют на ранних этапах истории Java, и они с самого начала созданы для поточной защиты (если у вас будет возможность взглянуть на их исходный код, вы увидите, что все их методы синхронизированы!). Однако они быстро показывают низкую производительность в многопоточных программах. Как вы, возможно, знаете, синхронизация требует блокировок, для мониторинга которых всегда требуется время, что снижает производительность. Вот почему новые коллекции (List, Set, Map и т.д.) Вообще не предусматривают управление параллелизмом для обеспечения максимальной производительности в однопоточных приложениях.

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