До выхода .NET 4.0, если нам нужно было использовать класс Dictionary в многопоточной среде, у нас не было выбора, кроме как реализовать синхронизацию потоков самостоятельно, чтобы сохранить их безопасность.
Многие разработчики, безусловно, реализовывали похожее решение с безопасностью потоков, либо создав совершенно новый тип словаря, безопасного для потоков, либо просто инкапсулируя объект словаря в класс и добавив механизм блокировки ко всем методам, который мы называем «Словарь + Замки».
Но теперь у нас есть ConcurrentDictionary. В описании класса Dictionary Safe на MSDN указано, что если вам нужна реализация с безопасной для потоков, используйте ConcurrentDictionary.
Теперь, когда у нас есть курс по словарю с треком, нам больше не нужно реализовывать его самостоятельно. Здорово, правда?
Происхождение проблемы
На самом деле, я использовал CocurrentDictionary только один раз в тесте, чтобы проверить его отзывчивость. Поскольку тест хорошо показал, я сразу же заменил его на свой класс, провёл тесты, и потом что-то пошло не так.
Так что же пошло не так? Разве ты не говорил, что нитка безопасна?
После дополнительных тестов я нашёл корень проблемы. Но по какой-то причине версия MSDN 4.0 не содержит описания подписи метода GetOrAdd, требующей передачи параметра типа делегата. После просмотра версии 4.5 я наткнулся на следующую заметку:
Если вы вызываете GetOrAdd одновременно в разных потоках, addValueFactory может вызываться несколько раз, но его пара ключ/значение может не добавляться в словарь для каждого вызова.
Вот с чем я столкнулся. Поскольку это не было описано ранее в документации, мне пришлось провести дополнительные тесты, чтобы подтвердить проблему. Конечно, проблема, с которой я сталкиваюсь, связана с моим использованием, обычно я использую тип словаря для кэширования некоторых данных:
Эти данные создаются очень медленно;
Эти данные можно создать только один раз, потому что второе создание вызовет исключение, или несколько созданий могут привести к утечке ресурсов и т.д.;
У меня была проблема со вторым условием. Если обе потоки обнаружат, что какой-либо фрагмент данных не существует, он будет создан один раз, но только один результат будет успешно сохранен. А как насчёт другого?
Если созданный вами процесс выдает исключение, вы можете использовать try: Catch (недостаточно элегантно, но решает проблему). Но что если ресурс создается, а не перерабатывается?
Можно сказать, что объект создан и будет собираться мусором, если он больше не упоминается в нём. Однако подумайте, что произошло бы, если бы произошла описанная ниже ситуация:
Генерируйте код динамически с помощью Emit. Я использовал этот подход в удалённом фреймворке и поместил все реализации в ассемблер, который нельзя было переработать. Если тип создаётся дважды, второй всегда будет существовать, даже если он никогда не использовался.
Создайте тему прямо или косвенно. Например, нам нужно создать компонент, который использует проприетарный поток для обработки асинхронных сообщений и зависит от порядка их получения. При создании компонента создаётся поток. Когда этот экземпляр компонента уничтожается, поток также завершается. Но если мы удаляем ссылку на объект после уничтожения компонента, но поток по какой-то причине не заканчивается и сохраняет ссылку на объект, Тогда, если нить не отключится, объект тоже не будет перерабатываться.
Выполните операцию P/Invoke. Требуйте, чтобы количество времени закрытия для полученной ручки совпадало с количеством открытий.
Безусловно, есть много похожих ситуаций. Например, объект словаря хранит соединение с сервисом на удалённом сервере, которое можно запросить только один раз, и если запросить второй раз, другой сервис решит, что произошла ошибка, и внесёт это в журнал. (В компании, где я работал, за это состояние были предусмотрены юридические санкции.) ）
Так что легко понять, что Dictionary + Locks нельзя срочно заменить на ConcurrentDictionary, даже если в документации указано, что он безопасный для потоков.
Проанализировать проблему
Всё ещё не понимаете?
Действительно, эта проблема может не возникнуть при подходе Словарь + Замки. Поскольку это зависит от конкретной реализации, давайте рассмотрим этот простой пример:
В приведённом выше коде мы удерживаем замок на словаре перед началом запроса значения ключа. Если указанная пара ключ-значение не существует, она будет создана напрямую. В то же время, поскольку у нас уже есть ограничение на этот словарь, мы можем добавлять пары ключ-значение напрямую в словарь. Затем снять словарь и вернуть результат. Если два потока одновременно запрашивают одно и то же значение ключа, первый поток, получивший словарный блокировку, завершит создание объекта, а другой поток ждёт завершения этого создания и получает результат созданного ключа после блокировки словаря.
Это хорошо, правда?
Это совсем не так! Я не думаю, что создание объекта параллельно, где в итоге используется только один, не создаёт описанную мной проблему.
Ситуация и проблема, которые я пытаюсь объяснить, не всегда воспроизводимы: в параллельной среде мы можем просто создать два объекта и затем отбросить один. Итак, как именно сравнивать Dictionary + Locks и ConcurrentDictionary?
Ответ таков: всё зависит от стратегии использования замков и того, как используется словарь.
Игра 1: Создать один и тот же объект параллельно
Во-первых, предположим, что объект может быть создан дважды, а что произойдёт, если два потока создают этот объект одновременно?
Во-вторых, сколько времени мы тратим на похожие творения?
Мы можем просто построить пример, где создание объекта занимает 10 секунд. Когда первый поток создаёт объект через 5 секунд, вторая реализация пытается вызвать метод GetOrAdd для получения объекта, и поскольку объект всё ещё не существует, он также начинает создавать объект.
В таком состоянии 2 процессора работают параллельно в течение 5 секунд, и когда первый поток заканчивается, второй поток всё равно должен продолжать работу 5 секунд, чтобы завершить строительство объекта. Когда второй поток завершает строительство объекта, он обнаруживает, что объект уже существует, и выбирает использовать существующий объект и сбрасывать его напрямую.
Если второй поток просто ждёт, а второй процессор выполняет какую-то другую работу (запускает другие потоки или приложения, экономия энергии), он получит нужный объект через 5 секунд вместо 10.
В таких условиях Словарь + Замки выигрывают небольшую игру.
Игра 2: Посещать разные объекты параллельно
Нет, ситуация, о которой вы сказали, совсем не соответствует действительности!
Ну, приведённый выше пример немного странный, но он описывает проблему, просто такое употребление более радикальное. Итак, представьте, что происходит, если первый поток создаёт объект, а второй поток должен получить доступ к другому объекту key-value, и этот объект уже существует?
В ConcurrentDictionary дизайн без блокировки делает чтение очень быстрым, потому что на чтение нет блокировки. В случае Dictionary + Locks операция чтения будет заблокирована взаимно исключающе, даже если это совершенно другой ключ, что, очевидно, замедляет операцию чтения.
Таким образом, ConcurrentDictionary отменил игру.
Примечание: Здесь я считаю, что вы понимаете несколько понятий, таких как Bucket/Node/Entry в словарном курсе, если нет — рекомендуется прочитать статью Офира Макмала «Глубокое понимание общего словаря», где эти понятия хорошо объясняются.
Третья игра игры: читайте дальше и пишите одиночку
Что произойдёт, если использовать Multiple Readers и Single Writer вместо полной блокировки на словарь в Dictionary + Locks?
Если поток создаёт объект и удерживает блокировку с возможностью обновления до его создания, блокировка обновляется до блокировки записи, после чего операция чтения может выполняться параллельно.
Мы также можем решить задачу, оставив операцию чтения в состоянии постоя на 10 секунд. Но если чтений гораздо больше, чем записей, мы обнаружим, что ConcurrentDictionary всё равно работает быстро, потому что реализует режим чтения без блокировки.
Использование ReaderWriterLockSlim для словарей усугубляет чтение, поэтому обычно рекомендуется использовать Full Lock для словарей вместо ReaderWriterLockSlim.
В таких условиях ConcurrentDictionary выиграл ещё одну игру.
Примечание: я уже рассматривал курсы YieldReaderWriterLock и YieldReaderWriterLockSlim в предыдущих статьях. Используя этот блокировочный режим чтения-записи, скорость значительно улучшилась (теперь эволюционировала в SpinReaderWriterLockSlim) и позволяет выполнять несколько чтений параллельно с минимальным или отсутствующим влиянием. Пока я всё ещё использую этот способ, беззаблокированный ConcurrentDictionary, очевидно, будет быстрее.
Игра 4: Добавить несколько пар ключ-значение
Противостояние ещё не окончено.
Что если у нас есть несколько значений для добавления, и все они не сталкиваются и распределяются в разные бакеты?
Сначала вопрос был любопытным, но я прошёл тест, который не совсем подходил. Я использовал словарь типа <int, int> и фабрика строительства объекта напрямую возвращала отрицательный результат в качестве ключа.
Я ожидал, что ConcurrentDictionary будет самым быстрым, но он оказался самым медленным. Dictionary + Locks, напротив, работает быстрее. Почему так?
Это связано с тем, что ConcurrentDictionary выделяет узлы и помещает их в разные бакеты, оптимизируя для соответствия беззамковому дизайну для операций чтения. Однако при добавлении элементов с ключевым значением процесс создания узла становится дорогостоящим.
Даже в параллельных условиях выделение блокировки узла всё равно занимает больше времени, чем использование полного блокировки.
Итак, Словарь + Замки выигрывают эту игру.
Играя в пятую партию: частота операций чтения выше
Честно говоря, если бы у нас был делегат, способный быстро создавать объекты, нам бы не понадобился словарь. Мы можем напрямую вызвать делегата, чтобы получить объект, верно?
На самом деле, ответ также в том, что всё зависит от конкретной ситуации.
Представьте, что тип ключа — строка, содержащий карты путей для различных страниц веб-сервера, а соответствующее значение — тип объекта, содержащий запись текущих пользователей, заходящих на страницу, и количество всех посещений страницы с момента запуска сервера.
Создание такого объекта происходит почти мгновенно. После этого не нужно создавать новый объект, просто меняйте сохраненные в нём значения. Таким образом, можно позволить создать путь дважды, пока не будет использован только один экземпляр. Однако, поскольку ConcurrentDictionary распределяет ресурсы узлов медленнее, использование Dictionary + Locks приведёт к более быстрому соображению.
Таким образом, этот пример очень особенный: мы также видим, что Dictionary + Locks работает лучше в таком состоянии, занимая меньше времени.
Хотя выделение узлов в ConcurrentDictionary медленнее, я не пытался вставлять туда 100 миллионов элементов данных, чтобы проверить время. Потому что это, конечно, занимает много времени.
Но в большинстве случаев, как только элемент данных создан, его всегда читают. Как меняется содержимое элемента данных — это уже другой вопрос. Так что неважно, сколько миллисекунд занимает создание элемента данных, потому что чтение происходит быстрее (всего на несколько миллисекунд быстрее), но чтение происходит чаще.
Итак, ConcurrentDictionary выиграл игру.
Игра 6: Создавать объекты, которые потребляют разное время
Что происходит, если время создания разных элементов данных меняется?
Создайте несколько элементов данных, которые занимают разное время, и добавляйте их в словарь параллельно. Это самая сильная сторона ConcurrentDictionary.
ConcurrentDictionary использует ряд различных механизмов блокировки для одновременного добавления элементов данных, но логика, такая как выбор блокировки, запрос на изменение размера ведра и т.д., не помогает. Скорость, с которой элементы данных загружаются в ведро, машинно высокая. Что действительно делает ConcurrentDictionary побеждённым — это возможность создавать объекты параллельно.
Однако мы можем сделать то же самое. Если нам всё равно, создаём ли мы объекты параллельно или некоторые из них были отброшены, мы можем добавить блокировку, чтобы определить, существует ли элемент данных, затем снять блокировку, создать элемент данных, нажать на него, чтобы получить блокировку, ещё раз проверить, существует ли элемент данных, а если нет — добавить элемент данных. Код может выглядеть примерно так:
* Обратите внимание, что я использую словарь типа <int, int>.
В простой структуре выше Dictionary + Locks работает почти так же хорошо, как ConcurrentDictionary, при создании и добавлении элементов данных в параллельных условиях. Но есть та же проблема, когда некоторые значения могут генерироваться, но никогда не использоваться.
заключение
Итак, есть ли вывод?
На данный момент ещё есть некоторые:
Все курсы по словарю очень быстрые. Хотя я создал миллионы данных, это всё равно быстро. Обычно мы создаём небольшое количество элементов данных, и между чтениями есть определённые временные интервалы, поэтому мы обычно не замечаем накладных расходов на чтение элементов данных.
Если один и тот же объект невозможно создать дважды, не используйте ConcurrentDictionary.
Если вас действительно волнует производительность, Dictionary + Locks всё ещё может быть хорошим решением. Важным фактором является количество добавленных и удалённых элементов данных. Но если операций чтения много, это медленнее, чем ConcurrentDictionary.
Хотя я не вводил её, на самом деле существует больше свободы для использования схемы Словарь + Замки. Например, вы можете заблокировать один раз, добавить несколько элементов данных, удалить несколько элементов данных или отправить запросы несколько раз и так далее, а затем снять блокировку.
В целом, избегайте использования ReaderWriterLockSlim, если чтений гораздо больше, чем записей. Типы словарей уже гораздо быстрее, чем блокировка чтения в блокировке чтения-записи. Конечно, это также зависит от времени, затраченного на создание объекта в замке.
Поэтому, я считаю, что приведённые примеры немного экстремальны, но они показывают, что использование ConcurrentDictionary не всегда является лучшим решением.
Почувствуйте разницу
Я написал эту статью с намерением найти лучшее решение.
Я уже пытаюсь глубже понять, как работает конкретный курс по словару (теперь мне кажется, что я очень ясен).
Можно утверждать, что Bucket и Node в ConcurrentDictionary очень просты. Я делал что-то похожее, когда пытался создать курс по словаре. Обычный курс Dictionary может показаться проще, но на самом деле он гораздо сложнее.
В ConcurrentDictionary каждый узел является полным классом. В классе Dictionary Node реализуется с использованием типа значения, и все узлы хранятся в огромном массиве, а Bucket используется для индексации массива. Он также используется вместо простой ссылки узла на следующий узел (в конце концов, как узел типа структуры, он не может содержать член узла типа структуры).
При добавлении и удалении словаря класс Dictionary не может просто создать новый узел, он должен проверить, есть ли индекс, отмечающий удалённый узел, и затем использовать его повторно. Или «Count» используется для определения положения нового узла в массиве. Фактически, когда массив заполнен, класс Dictionary заставляет изменить размер.
Для ConcurrentDictionary узел можно рассматривать как новый объект. Удаление узла — это просто удаление его ссылки. Добавление нового узла позволяет просто создать новый экземпляр узла. Изменение размера нужно лишь для предотвращения конфликтов, но это не обязательно.
Итак, если класс Dictionary сознательно использует более сложные алгоритмы для обработки, как ConcurrentDictionary обеспечит его лучшую работу в многопоточной среде?
Правда в том, что размещение всех узлов в одном массиве — самый быстрый способ выделить и прочитать, даже если нам нужен другой массив для отслеживания, где искать эти данные. Похоже, что одинаковое количество бакетов займёт больше памяти, но новые элементы данных не нужно переделывать, не нужны новые синхронизации объектов, и новый сбор мусора не происходит. Потому что всё уже готово.
Однако замена содержимого в узле не является атомарной операцией, что является одним из факторов, делающих его поток небезопасным. Поскольку узлы — это все объекты, изначально создаётся узел, а затем обновляется отдельная ссылка, указывающая на него (здесь атомарная операция). Таким образом, читательный текст может читать содержимое словаря без блокировки, и чтение должно быть одним из старых и новых значений, и нет шанса прочитать неполное значение.
Итак, правда в том, что если блокировка не нужна, то курс Dictionary работает быстрее при чтении, потому что именно блокировка замедляет чтение.
Эта статья переведена из статьи Пауло Земека «Словарь + Блокировка против ConcurrentDictionary» на CodeProject, и некоторые утверждения будут изменяться по причинам понимания.
|
Опубликовано 13.09.2016 13:33:04
|
|
|
Хозяин|
Опубликовано 13.09.2016 13:33:15
|
