Во-первых, вы не можете честно сравнить рандомизированную структуру данных с той, которая дает вам гарантии наихудшего случая.
Список пропусков эквивалентен случайно сбалансированному бинарному дереву поиска (RBST), что более подробно объясняется в статье Дина и Джонса «Изучение двойственности между списками пропусков и деревьями двоичного поиска» .
С другой стороны, вы можете также иметь детерминированные списки пропусков, которые гарантируют худшую производительность, ср. Манро и др.
Вопреки тому, что некоторые утверждают выше, у вас могут быть реализации двоичных деревьев поиска (BST), которые хорошо работают в параллельном программировании. Потенциальная проблема с BST, ориентированными на параллелизм, заключается в том, что вы не можете легко получить те же гарантии с балансировкой, что и из красно-черного (RB) дерева. (Но «стандартные», то есть рандомизированные, пропускающие списки также не дают вам этих гарантий.) Существует компромисс между поддержанием баланса в любое время и хорошим (и простым в программировании) параллельным доступом, поэтому relaxed Деревья RB обычно используются, когда требуется хороший параллелизм. Релаксация состоит в том, чтобы не перебалансировать дерево сразу. Несколько устаревший (1998 г.) обзор см. В статье Ханка «Производительность параллельных алгоритмов красно-черного дерева» [ps.gz] .
Одним из недавних улучшений является так называемое хроматическое дерево (в основном у вас есть некоторый вес, такой, что черный будет равен 1, а красный будет равен нулю, но вы также допускаете значения между ними) , И как цветное дерево обходится без списка пропусков? Давайте посмотрим, что Браун и соавт. «Общая техника для неблокирующих деревьев» (2014) должны сказать:
с 128 потоками наш алгоритм превосходит неблокирующий пропускаемый список Java
от 13% до 156%, основанное на блокировке дерево AVL Bronson et al. от 63% до 224%, а RBT, использующий программную транзакционную память (STM), от 13 до 134 раз
РЕДАКТИРОВАТЬ, чтобы добавить: Список пропусков, основанный на блокировке Пью, который был оценен в Fraser and Harris (2007) «Параллельное программирование без блокировки» как близкий к их собственной версии без блокировки (точная точка зрения) настаивал на верхнем ответе здесь), также настроен для хорошей параллельной работы, ср. Pugh's "Одновременное ведение списков пропусков" , хотя и довольно мягко. Тем не менее, одна более новая статья 2009 года «Простой оптимистический алгоритм списка пропусков» , выполненная Herlihy et al., В которой предлагается предположительно более простая (чем у Пью) реализация одновременных списков пропусков на основе блокировок, критиковала Пью за отсутствие доказательство правильности достаточно убедительно для них. Оставляя в стороне этот (возможно, слишком педантичный) вопрос, Herlihy et al. показать, что их более простая реализация на основе блокировок списка пропусков фактически не масштабируется так же, как их реализация без блокировок в JDK, но только для высокой конкуренции (50% вставок, 50% удалений и 0% поисков) ... которые Fraser и Харрис не проверял вообще; Фрейзер и Харрис протестировали только 75% поисков, 12,5% вставок и 12,5% удалений (в пропущенном списке с элементами ~ 500K). Более простая реализация Herlihy et al. также приближается к решению без блокировок от JDK в случае низкой конкуренции, которую они протестировали (70% поисков, 20% вставок, 10% удалений); они фактически опередили решение без блокировок для этого сценария, когда сделали свой список пропусков достаточно большим, то есть с 200K до 2M элементов, так что вероятность конфликта при любой блокировке стала незначительной. Было бы неплохо, если бы Herlihy et al. пережил их зависание из-за доказательства Пью и проверил его реализацию, но, увы, они этого не сделали.
РЕДАКТИРОВАТЬ 2: Я нашел (опубликованный в 2015 году) исходный код для всех тестов: от Gramoli «Больше, чем вы когда-либо хотели знать о синхронизации. Synchrobench, Измерение влияния синхронизации на параллельные алгоритмы» : Вот отрывочное изображение, относящееся к этому вопросу.
«Algo.4» является предшественником (более старая, версия 2011 года) Брауна и др., Упомянутых выше. (Я не знаю, насколько лучше или хуже версия 2014 года). «Алго.26» - это упомянутое выше Херлихи; как вы можете видеть, он загружается при обновлениях, и гораздо хуже для процессоров Intel, используемых здесь, чем для процессоров Sun из оригинальной статьи. «Algo.28» - это ConcurrentSkipListMap из JDK; это не так хорошо, как можно было бы надеяться, по сравнению с другими реализациями списка пропуска на основе CAS. Победители в условиях высокой конкуренции - это алгоритм «Algo.2» (!!), описанный Crain et al. в «Дружественное для конкуренции дерево двоичного поиска» и «Algo.30» - это «вращающийся пропускающий список» из «Логарифмические структуры данных для
многоядерный "." Algo.29 "- это " Отсутствует неблокируемая горячая точка
list ". Имейте в виду, что Gramoli является соавтором всех трех из этих статей с алгоритмом победителя." Algo.27 "- реализация C ++ списка пропуска Фрейзера на C ++.
Вывод Gramoli заключается в том, что гораздо проще испортить реализацию параллельного дерева на основе CAS, чем аналогичный список пропусков. И на основании цифр трудно не согласиться. Его объяснение этому факту таково:
Сложность создания дерева без блокировки проистекает из
сложность модификации нескольких ссылок атомарно. Пропустить списки
состоят из башен, связанных друг с другом через указатели преемника и
в котором каждый узел указывает на узел непосредственно под ним. Они есть
часто считается похожим на деревья, потому что каждый узел имеет преемника
однако в башне-преемнике и под ней основное различие заключается в
что нисходящий указатель, как правило, является неизменным, следовательно, упрощается
атомная модификация узла. Это различие, вероятно,
причина, по которой пропущенные списки превосходят деревья в условиях сильной конкуренции
как показано на рисунке [выше].
Преодоление этой трудности было ключевой проблемой в недавней работе Брауна и соавторов.
У них есть отдельная (2013) статья "Прагматические примитивы для неблокирующих структур данных"
на построении составных «примитивов» LL / SC, которые они называют LLX / SCX, которые сами реализуются с использованием (на уровне машины) CAS. Браун и соавт. использовал этот строительный блок LLX / SCX в их параллельной реализации дерева 2014 года (но не в 2011 году).
Я думаю, что, возможно, здесь также стоит обобщить основные идеи.
из списка пропускаемых списков "без горячих точек" (CF). Он добавляет основную идею из расслабленных деревьев RB (и аналогичных структур данных): башни больше не создаются сразу после вставки, а откладываются до тех пор, пока не будет меньше конфликтов. И наоборот, удаление высокой башни может создать много споров;
это наблюдалось еще в 1990 году, когда Пью публиковал список пропущенных списков, именно поэтому Пью ввел инверсию указателей при удалении (лакомый кусочек, который страница Википедии в списках пропуска до сих пор не упоминает, увы). Список пропусков CF делает этот шаг еще дальше и задерживает удаление верхних уровней высокой башни. Оба вида отложенных операций в списках пропуска CF выполняются отдельным (подобным CAS) отдельным потоком, подобным сборщику мусора, который его авторы называют «адаптирующимся потоком».
Код Synchrobench (включая все протестированные алгоритмы) доступен по адресу: https://github.com/gramoli/synchrobench.
Последний Браун и соавт. реализация (не включенная в вышеприведенное) доступна по адресу http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java У кого-нибудь есть машина с ядром 32+? J / K Моя точка зрения заключается в том, что вы можете запустить их сами.