Пропустить список против бинарного дерева поиска

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

Зачем вам когда-либо использовать список пропуска через дерево бинарного поиска?

Списки пропуска более поддаются одновременному доступу / изменению. Херб Саттер написал статью о структуре данных в параллельных средах. У него есть более глубокая информация.

Наиболее часто используемая реализация двоичного дерева поиска - красно-черное дерево . Одновременные проблемы возникают, когда дерево модифицируется, и оно часто нуждается в восстановлении баланса. Операция перебалансировки может повлиять на большие части дерева, что потребует блокировки мьютекса во многих узлах дерева. Вставка узла в список пропуска гораздо более локализована, только узлы, непосредственно связанные с уязвимым узлом, должны быть заблокированы.

Обновление от комментариев Джона Харропса

Я прочитал последнюю статью Фрейзера и Харриса « Параллельное программирование без блокировок» . Действительно хороший материал, если вы заинтересованы в структурах данных без блокировки. Статья посвящена транзакционной памяти и теоретическим операциям MCAS с несколькими словами, сравниванием и заменой. Оба они смоделированы в программном обеспечении, поскольку никакое оборудование еще не поддерживает их. Я весьма впечатлен тем, что им вообще удалось создать MCAS в программном обеспечении.

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

В разделе 8.2 они сравнивают производительность нескольких параллельных реализаций дерева. Я подведу итоги. Это стоит того, чтобы скачать pdf, поскольку он содержит несколько очень информативных графиков на страницах 50, 53 и 54.

• Списки пропуска блокировки безумно быстрые. Они невероятно хорошо масштабируются с количеством одновременных обращений. Это то, что делает списки пропусков особенными, другие структуры данных, основанные на блокировках, как правило, ломаются под давлением.
• Списки пропусков без блокировок всегда быстрее, чем списки пропусков с блокировкой, но лишь в незначительной степени.
• Списки пропущенных транзакций последовательно в 2-3 раза медленнее, чем версии с блокировкой и без блокировки.
• блокировка красно-черных деревьев каркает при одновременном доступе. Их производительность линейно снижается с каждым новым пользователем одновременно. Из двух известных реализаций красно-черного дерева блокировок у одного по существу есть глобальная блокировка во время перебалансировки дерева. Другой использует причудливое (и сложное) повышение блокировки, но все еще не значительно справляется с глобальной версией блокировки.
• красно-черные деревья без блокировок не существуют (больше не верно, см. Обновление).
• Транзакционные красно-черные деревья сравнимы с транзакционными пропущенными списками. Это было очень удивительно и очень многообещающе. Транзакционная память, хотя и медленнее, если ее легче писать. Это может быть так же просто, как быстрый поиск и замена на не параллельной версии.

Обновление
Вот статья о деревьях без блокировки : Красно-черные деревья без блокировки с использованием CAS .
Я не изучал это глубоко, но на первый взгляд это кажется твердым.

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

Список пропусков эквивалентен случайно сбалансированному дереву двоичного поиска (RBST), что более подробно объясняется в статье Дина и Джонса «Изучение двойственности между списками пропусков и деревьями двоичного поиска» .

С другой стороны, вы также можете иметь детерминированные списки пропусков, которые гарантируют худшую производительность, ср. Мунро и соавт.

Вопреки тому, что некоторые утверждают выше, у вас могут быть реализации двоичных деревьев поиска (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» - «вращающийся список пропусков» из «Логарифмические структуры данных для многоядерных систем» . ", Имейте в виду, что 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 против Hash Table Runtime для словаря find op