Пропустить список против бинарного дерева поиска
Недавно я наткнулся на структуру данных, известную как список пропусков. Похоже, что он очень похож на бинарное дерево поиска.
Зачем вам когда-либо использовать список пропуска через дерево двоичного поиска?
7 ответов
Списки пропуска более поддаются одновременному доступу / изменению. Херб Саттер написал статью о структуре данных в параллельных средах. У него есть более глубокая информация.
Наиболее часто используемая реализация двоичного дерева поиска - красно-черное дерево. Одновременные проблемы возникают, когда дерево модифицируется, и оно часто нуждается в восстановлении баланса. Операция перебалансировки может повлиять на большие части дерева, что потребует блокировки мьютекса во многих узлах дерева. Вставка узла в список пропуска гораздо более локализована, только узлы, непосредственно связанные с уязвимым узлом, должны быть заблокированы.
Обновление от комментариев Джона Харропса
Я прочитал последнюю статью Фрейзера и Харриса " Параллельное программирование без блокировок". Действительно хороший материал, если вы заинтересованы в структурах данных без блокировки. Статья посвящена транзакционной памяти и теоретическим операциям MCAS с несколькими словами, сравниванием и заменой. Оба из них симулируются в программном обеспечении, поскольку никакое оборудование еще не поддерживает их. Я весьма впечатлен тем, что им вообще удалось создать MCAS в программном обеспечении.
Я не нашел, что транзакционная память особенно привлекательна, так как требует сборщика мусора. Кроме того, программная транзакционная память страдает от проблем с производительностью. Тем не менее, я был бы очень взволнован, если аппаратная транзакционная память когда-либо станет обычной. В конце концов, это все еще исследование и не будет полезным для производственного кода еще около десяти лет.
В разделе 8.2 они сравнивают производительность нескольких параллельных реализаций дерева. Я подведу итоги своих выводов. Это стоит того, чтобы скачать pdf, поскольку он содержит несколько очень информативных графиков на страницах 50, 53 и 54.
- Списки пропуска блокировки безумно быстрые. Они невероятно хорошо масштабируются с количеством одновременных обращений. Это то, что делает списки пропусков особенными, другие структуры данных, основанные на блокировках, имеют тенденцию к каркасу под давлением.
- Списки пропусков без блокировок всегда быстрее, чем списки пропусков с блокировкой, но только в очень редких случаях.
- Списки пропущенных транзакций последовательно в 2-3 раза медленнее, чем версии с блокировкой и без блокировки.
- блокировка красно-черных деревьев каркает при одновременном доступе. Их производительность линейно снижается с каждым новым параллельным пользователем. Из двух известных реализаций красно-черного дерева блокировок у одного по существу есть глобальная блокировка во время перебалансировки дерева. Другой использует причудливое (и сложное) повышение блокировок, но все же значительно не справляется с глобальной версией блокировки.
- красно-черные деревья без блокировок не существуют (больше не верно, см. Обновление).
- Транзакционные красно-черные деревья сравнимы с транзакционными пропускаемыми списками. Это было очень удивительно и очень многообещающе. Транзакционная память, хотя и медленнее, если ее легче писать. Это может быть так же просто, как быстрый поиск и замена на не параллельной версии.
Обновить
Вот статья о деревьях без блокировки: Красно-черные деревья без блокировки с использованием CAS.
Я не изучал это глубоко, но на первый взгляд это кажется твердым.
Во-первых, вы не можете честно сравнить рандомизированную структуру данных с той, которая дает вам гарантии наихудшего случая.
Список пропусков эквивалентен случайно сбалансированному дереву двоичного поиска (RBST), что более подробно объясняется в статье Дина и Джонса "Изучение двойственности между списками пропусков и деревьями двоичного поиска".
С другой стороны, вы можете также иметь детерминированные списки пропусков, которые гарантируют худшую производительность, ср. Munro et al.
Вопреки тому, что некоторые утверждают выше, у вас могут быть реализации двоичных деревьев поиска (BST), которые хорошо работают в параллельном программировании. Потенциальная проблема с BST, ориентированными на параллелизм, заключается в том, что вы не можете легко получить те же гарантии с балансировкой, что и из красно-черного (RB) дерева. (Но "стандартные", то есть случайные, пропускающие списки также не дают вам этих гарантий.) Существует компромисс между поддержанием баланса в любое время и хорошим (и простым в программировании) параллельным доступом, поэтому обычно используются расслабленные деревья RB когда хороший параллелизм желателен. Релаксация состоит в том, чтобы не перебалансировать дерево сразу. Несколько устаревший (1998 г.) опрос см. В статье "Эффективность параллельных алгоритмов красно-черного дерева" Ханке [ps.gz].
Одним из последних улучшений в них является так называемое хроматическое дерево (в основном у вас есть некоторый вес, такой, что черный будет равен 1, а красный будет равен нулю, но вы также допускаете значения между ними). И как цветное дерево обходится без списка пропусков? Давайте посмотрим, что Браун и соавт. "Общая техника неблокирующих деревьев" (2014) должна сказать:
с 128 потоками наш алгоритм превосходит неблокирующий пропускаемый список Java на 13% до 156%, основанное на блокировках дерево AVL Bronson et al. на 63% до 224%, а RBT, использующий программную транзакционную память (STM), от 13 до 134 раз
РЕДАКТИРОВАТЬ, чтобы добавить: Список пропусков, основанный на блокировке Пью, который был сравнен с Fraser and Harris (2007) "Параллельное программирование без блокировки" как близкий к их собственной версии без блокировки (точка, на которой настойчиво настаивал верхний ответ здесь), также настроен для хорошей параллельной работы, ср. "Одновременное ведение пропускаемых списков" Пью, хотя и довольно мягко. Тем не менее, одна более новая статья /2009 "Простой оптимистический алгоритм пропускаемых списков" Херлихи и др., Которая предлагает предположительно более простую (чем Пью) реализацию одновременных списков пропусков на основе блокировок, критиковала Пью за то, что он не предоставил доказательства правильности, достаточно убедительного для них. Оставляя в стороне этот (возможно, слишком педантичный) вопрос, Herlihy et al. показать, что их более простая реализация на основе блокировок списка пропусков фактически не масштабируется так же, как их реализация без блокировок в JDK, но только для высокой конкуренции (50% вставок, 50% удалений и 0% поисков)... которые Fraser и Харрис не проверял вообще; Фрейзер и Харрис протестировали только 75% поисков, 12,5% вставок и 12,5% удалений (в списке пропуска с элементами ~500K). Более простая реализация Herlihy et al. также приближается к решению без блокировок от JDK в случае низкой конкуренции, которую они протестировали (70% просмотров, 20% вставок, 10% удалений); они фактически опередили решение без блокировок для этого сценария, когда сделали свой список пропусков достаточно большим, то есть с 200K до 2M элементов, так что вероятность конфликта при любой блокировке стала незначительной. Было бы неплохо, если бы Herlihy и соавт. пережил их зависание от доказательства Пью и проверил его реализацию, но, увы, они этого не сделали.
РЕДАКТИРОВАТЬ 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" - это "Список пропущенных неблокируемых горячих точек". Имейте в виду, что Gramoli является соавтором всех трех работ с алгоритмом победителя. "Algo.27" - реализация C++ списка пропусков Fraser.
Грамоли пришел к выводу, что гораздо проще испортить реализацию параллельного дерева на основе CAS, чем аналогичный список пропусков. И на основании цифр трудно не согласиться. Его объяснение этому факту таково:
Сложность создания дерева без блокировки связана с трудностью атомного изменения нескольких ссылок. Списки пропусков состоят из башен, связанных друг с другом посредством указателей-преемников, в которых каждый узел указывает на узел, находящийся непосредственно под ним. Их часто считают похожими на деревья, потому что каждый узел имеет преемника в башне преемника и под ним, однако основное отличие состоит в том, что нисходящий указатель, как правило, является неизменным, что упрощает атомарную модификацию узла. Это различие, вероятно, является причиной того, что пропуски списков превосходят деревья в условиях сильной конкуренции, как показано на рисунке [выше].
Преодоление этой трудности было ключевой проблемой в недавней работе Брауна и др. У них есть целая отдельная (2013 г.) статья "Прагматические примитивы для неблокирующих структур данных", посвященная созданию составных "примитивов" LL/SC, которые они называют LLX/SCX, которые сами реализованы с использованием CAS (на уровне машины). Браун и соавт. использовал этот строительный блок LLX / SCX в их параллельной реализации дерева 2014 года (но не в 2011 году).
Я думаю, что, возможно, также стоит кратко изложить здесь фундаментальные идеи списка пропусков "без горячей точки"/con-friendly (CF). Он добавляет основную идею из расслабленных деревьев RB (и аналогичных структур данных): башни больше не создаются сразу после вставки, а откладываются до тех пор, пока не будет меньше конфликтов. И наоборот, удаление высокой башни может создать много споров; это наблюдалось еще в 1990 году, когда Пью опубликовал список пропущенных списков, и именно поэтому Пью ввел изменение указателя при удалении (тикбайт, который страница Википедии в списках пропусков до сих пор не упоминает, увы). Список пропусков CF делает этот шаг еще дальше и задерживает удаление верхних уровней высокой башни. Оба вида отложенных операций в списках пропуска CF выполняются отдельным потоком, подобным сборщику мусора (на основе CAS), который его авторы называют "адаптирующимся потоком".
Код Synchrobench (включая все протестированные алгоритмы) доступен по адресу: https://github.com/gramoli/synchrobench. Последний Браун и соавт. реализация (не указанная выше) доступна по адресу http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java Есть ли у кого-нибудь более 32-ядерный компьютер? J/K Моя точка зрения заключается в том, что вы можете запустить их сами.
Кроме того, помимо данных ответов (простота реализации в сочетании с сопоставимой производительностью сбалансированного дерева). Я обнаружил, что реализация упорядоченного обхода (вперед и назад) намного проще, потому что список пропусков фактически имеет связанный список внутри своей реализации.
На практике я обнаружил, что производительность B-дерева в моих проектах оказалась лучше, чем в списках пропусков. Пропускать списки кажется проще для понимания, но реализовать B-дерево не так сложно.
Одно известное мне преимущество состоит в том, что некоторые умные люди разработали, как реализовать параллельный список пропусков без блокировки, который использует только атомарные операции. Например, Java 6 содержит класс ConcurrentSkipListMap, и вы можете прочитать исходный код, если вы сошли с ума.
Но не так уж сложно написать параллельный вариант B-дерева - я видел, что это сделал кто-то другой - если вы упреждающе разбиваете и объединяете узлы "на всякий случай", когда идете по дереву, тогда вам не придется беспокоиться о взаимоблокировках и только когда-либо нужно удерживать блокировку на двух уровнях дерева одновременно. Затраты на синхронизацию будут немного выше, но B-дерево, вероятно, быстрее.
Из статьи Википедии, которую вы цитировали:
Θ(n) операции, которые вынуждают нас посещать каждый узел в порядке возрастания (например, распечатывать весь список), дают возможность выполнить скрытую дерандомизацию структуры уровней пропускающего списка оптимальным способом, приведение списка пропусков к O(log n) времени поиска. [...] Список пропусков, над которым мы недавно не выполняли [любые такие] операции Θ(n), не обеспечивает такие же абсолютные гарантии производительности в худшем случае, как более традиционные структуры данных сбалансированного дерева, потому что это всегда возможно (хотя и с очень низкой вероятностью), что бросание монет, использованное для построения списка пропусков, приведет к плохо сбалансированной структуре
РЕДАКТИРОВАТЬ: так что это компромисс: Пропуск списки используют меньше памяти с риском, что они могут выродиться в несбалансированное дерево.
Пропуск списков реализован с использованием списков.
Существуют решения без блокировок для одно- и двусвязных списков, но не существует решений без блокировок, которые напрямую используют только CAS для любой структуры данных O(logn).
Однако вы можете использовать списки на основе CAS для создания списков пропуска.
(Обратите внимание, что MCAS, созданный с использованием CAS, допускает произвольные структуры данных, и доказательство концепции красно-черного дерева было создано с использованием MCAS).
Так что, как ни странно, они оказываются очень полезными:-)
Пропуск списков имеет преимущество снятия блокировки. Но время прогона зависит от того, как определяется уровень нового узла. Обычно это делается с помощью Random(). В словаре из 56000 слов список пропусков занимал больше времени, чем простое дерево, а дерево занимало больше времени, чем хеш-таблица. Первые два не могут соответствовать времени выполнения хеш-таблицы. Кроме того, массив хеш-таблицы также может быть одновременно очищен от блокировки.
Список пропусков и аналогичные упорядоченные списки используются, когда требуется местность ссылки. Например: поиск рейсов рядом и до даты в приложении.
Запоминающее дерево бинарного поиска в памяти отлично подходит и используется чаще.
Пропустить список против Splay Tree Vs Hash Table Runtime для словаря найти оп