Пропустить список противБинарное Дерево поиска

Question

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

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

Answer 1

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

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

---

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

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

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

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

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

---

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

Answer 2

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

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

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

Вопреки тому, что некоторые утверждают выше, у вас могут быть реализации бинарных деревьев поиска (BST), которые хорошо работают в параллельном программировании.Потенциальная проблема с BSTS, ориентированными на параллелизм, заключается в том, что вы не можете легко получить те же гарантии балансировки, что и при использовании красно-черного дерева (RB).(Но "стандартный", т.е.рандомизированные списки пропусков также не дают вам этих гарантий.) Существует компромисс между постоянным поддержанием балансировки и хорошим (и простым в программировании) одновременным доступом, поэтому расслабленный Деревья RB обычно используются, когда требуется хороший параллелизм.Расслабление заключается в том, чтобы не восстанавливать равновесие дерева сразу.Несколько устаревший обзор (1998) смотрите в книге Ханке "Производительность параллельных алгоритмов красно-черного дерева". [ps.gz].

Одним из последних усовершенствований в этой области является так называемый цветовое дерево (в принципе, у вас есть некоторый вес, такой, что черный будет равен 1, а красный - нулю, но вы также допускаете промежуточные значения).И как хроматическое дерево соотносится со списком пропусков?Давайте посмотрим, что делают Браун и др. "Общая техника для неблокирующих деревьев" (2014) должен сказать:

с 128 потоками наш алгоритм превосходит неблокирующий список пропусков Java на 13% до 156%, дерево AVL на основе блокировок Bronson et al.на 63% до 224%, а RBT, использующий программную транзакционную память (STM), в 13-134 раза

ОТРЕДАКТИРУЙТЕ, чтобы добавить:Список пропусков, основанный на блокировке Пью, который был проверен в работе Фрейзера и Харриса (2007). "Параллельное программирование без блокировки" поскольку они приближаются к своей собственной версии без блокировки (на чем убедительно настаивают в главном ответе здесь), они также изменены для хорошей параллельной работы, см.У Пью "Одновременное ведение списков пропусков", хотя и в довольно мягкой форме.Тем не менее, одна более новая статья 2009 года выпуска "Простой оптимистичный алгоритм составления списка пропусков" Херлихи и др., которые предлагают предположительно более простую (чем у Пью) реализацию параллельных списков пропусков на основе блокировок, раскритиковали Пью за то, что он не предоставил достаточно убедительных для них доказательств корректности.Оставляя в стороне это (возможно, слишком педантичное) сомнение, Херлихи и др.покажите, что их более простая реализация списка пропусков на основе блокировок на самом деле не масштабируется так же, как его реализация без блокировок в JDK, но только при высокой конкуренции (50% вставок, 50% удалений и 0% поисков)...который Фрейзер и Харрис вообще не проверяли;Фрейзер и Харрис протестировали только 75% поисковых запросов, 12,5% вставок и 12,5% удалений (в списке пропусков ~ 500 тыс. элементов).Более простая реализация Herlihy et al.также приближается к решению без блокировок из JDK в случае низкой конкуренции, которую они тестировали (70% поисков, 20% вставок, 10% удалений);они фактически превзошли решение без блокировок для этого сценария, когда сделали свой список пропусков достаточно большим, т.е.переход от 200 тысяч к 2 миллионам элементов, так что вероятность конфликта при любой блокировке стала ничтожно малой.Было бы неплохо, если бы Херлихи и др.они преодолели свое замешательство из-за доказательства Пью и тоже протестировали его реализацию, но, увы, они этого не сделали.

РЕДАКТИРОВАТЬ 2:Я нашел (опубликованный в 2015 году) материнский код всех бенчмарков:Грамоли "Больше, чем Ты когда-либо хотел знать о Синхронизации.Synchrobench, измеряющий влияние синхронизации на параллельные алгоритмы":Вот выдержка из изображения, относящегося к этому вопросу.

"Алгоритм.4" является предшественником (более старой версии 2011 года) упомянутой выше работы Brown et al.(Я не знаю, насколько лучше или хуже версия 2014 года)."Algo.26" - это упомянутый выше алгоритм Херлихи;как вы можете видеть, он портится при обновлении, и гораздо хуже на используемых здесь процессорах Intel, чем на процессорах Sun из оригинальной статьи."Algo.28" - это ConcurrentSkipListMap из JDK;это работает не так хорошо, как можно было бы надеяться, по сравнению с другими реализациями списка пропусков на основе CAS.Победителями при высокой конкуренции становятся "Algo.2" алгоритм на основе блокировки (!!), описанный Крейном и др.в "Бинарное дерево поиска, ориентированное на конкуренцию" а "Algo.30" - это "сменяющийся список пропусков" из "Логарифмические структуры данных для многоядерных вычислений"."Алгоритм.29" - это "Нет неблокирующего списка пропусков горячих точек ".Имейте в виду, что Грамоли является соавтором всех трех этих работ с алгоритмами победителей."Algo.27" - это реализация списка пропусков Фрейзера на C ++.

Вывод Грамоли заключается в том, что гораздо проще испортить параллельную реализацию дерева на основе CAS, чем испортить аналогичный список пропусков.И, судя по цифрам, с этим трудно не согласиться.Его объяснение этого факта таково:

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

Преодоление этой трудности было ключевой задачей в недавней работе Brown et al.У них есть целая отдельная статья (2013). "Прагматичные примитивы для неблокирующих структур данных" при создании составных "примитивов" с несколькими записями LL / SC, которые они называют LLX / SCX, сами реализованы с использованием (машинного уровня) CAS.Браун и др.использовали этот строительный блок LLX / SCX в своей параллельной реализации дерева 2014 (но не в 2011).

Я думаю, что это возможно, также, стоит кратко основные идеи в "нет горячих точек" / список пропусков, учитывающий конкуренцию (CF).Он добавляет важную идею из расслабленных деревьев RB (и аналогичных структур данных с высокой степенью конкретности).:башни больше не возводятся сразу после установки, а откладываются до тех пор, пока не уменьшатся разногласия.И наоборот, удаление высокой башни может вызвать множество споров;это было замечено еще в 1990 году в параллельной статье Пью о списках пропусков, именно поэтому Пью ввел отмену указателя при удалении (лакомый кусочек, о котором страница Википедии о списках пропусков, увы, по сей день не упоминается).Список пропусков CF делает этот шаг еще дальше и задерживает удаление верхних уровней высокой башни.Оба вида отложенных операций в списках пропусков CF выполняются отдельным потоком, похожим на сборщик мусора (на основе CAS), который его авторы называют "адаптирующим потоком".

Код Synchrobench (включая все протестированные алгоритмы) доступен по адресу: https://github.com/gramoli/synchrobench.Последнее исследование Brown et al.реализация (не включенная в вышеприведенное) доступна по адресу http://www.cs.toronto.edu /~tabrown/chromatic/ConcurrentChromaticTreeMap.java У кого-нибудь есть в наличии 32-ядерная машина?J / K Я хочу сказать, что вы можете запустить их сами.

Answer 3

Кроме того, помимо данных ответов (простота реализации в сочетании с сопоставимой производительностью сбалансированного дерева). Я считаю, что реализация обхода по порядку (вперед и назад) намного проще, потому что у пропускающего списка фактически есть связанный список внутри его реализации.

Answer 4

На практике я обнаружил, что производительность B-дерева в моих проектах оказалась лучше, чем в списках пропусков. Пропуск списков кажется проще для понимания, но реализовать B-дерево не так , как сложно.

Одно известное мне преимущество состоит в том, что некоторые умные люди разработали, как реализовать параллельный список пропусков без блокировки, который использует только атомарные операции. Например, Java 6 содержит класс ConcurrentSkipListMap, и вы можете прочитать исходный код, если вы сошли с ума.

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

Answer 5

Из статьи Википедии , которую вы цитировали:

  

& # 920; (n) операции, которые вынуждают нас посещать каждый узел в порядке возрастания (например, распечатывать весь список), дают возможность выполнить закулисную дерандомизацию структуры уровней пропуска. список оптимальным образом, приводя список пропуска к O (log n) времени поиска. [...]   Пропустить список, по которому у нас нет   [любые такие] (n) недавно выполненные операции, не   обеспечить такой же абсолютный наихудший случай   производительность гарантирует как больше   традиционные сбалансированные данные дерева   структуры , потому что это всегда   возможно (хотя с очень низким   вероятность) что использовались монеты   построить список пропуска будет производить   плохо сбалансированная структура

РЕДАКТИРОВАТЬ: так что это компромисс: Пропуск списков использует меньше памяти с риском того, что они могут выродиться в несбалансированное дерево.

Answer 6

Пропуск списков реализован с использованием списков.

Решения без блокировок существуют для одно- и двусвязных списков, но не существует решений без блокировок, которые напрямую использовали бы только CAS для любой структуры данных O (logn).

Однако вы можете использовать списки на основе CAS для создания списков пропуска.

(Обратите внимание, что MCAS, созданный с использованием CAS, допускает произвольные структуры данных, а доказательство концепции красно-черного дерева было создано с использованием MCAS).

Как ни странно, они оказываются очень полезными: -)

Answer 7

Пропускные списки имеют преимущество снятия блокировки. Но время прогона зависит от того, как определяется уровень нового узла. Обычно это делается с помощью Random (). В словаре из 56000 слов список пропусков занимал больше времени, чем простое дерево, а дерево занимало больше времени, чем хеш-таблица. Первые два не могут соответствовать времени выполнения хеш-таблицы. Кроме того, массив хеш-таблицы также может быть одновременно очищен от блокировки.

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

Простое дерево бинарного поиска в памяти отлично подходит и используется чаще.

Пропустить список против Splay Tree и Hash Table Время выполнения по словарю найти оп