Списки с одновременным доступом Тима Брея

В посте Concurrent List Update With Shuffling Тим описывает задачу, которую решил когда-то давно.

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

Тиму надо было работать со списком в многопоточном приложении, количество локов должно быть минимально. Для поиска он использовал бинарный поиск, который умеет работать с дубликатами, в данном случае это важно.

Как была организована работа со страницей. Записывает он все это так: сначала указано количество элементов, их четыре. Дальше перечислены сами элементы:

4: 10, 20, 30, 40

Теперь мы добавляем туда число 15, которое должно разместиться между 10 и 20. Допустим, что у нас есть еще свободное место на странице, а число 4 означает только число элементов, которые используются в данный момент.

Начинаем процесс вмешивания (shuffling-in) нового злемента

4: 10, 20, 30, 40, 40

Теперь увеличиваем счетчик

5: 10, 20, 30, 40, 40

Перемещаем элемент...

5: 10, 20, 30, 30, 40

5: 10, 20, 20, 30, 40

И в конце ставим элемент на его законное место.

5: 10, 15, 20, 30, 40

Удаление происходит аналогично.

Итого: можно искать по списку в то время, когда в него кто-то пишет. Но если пишут несколько потоков, то приходится список лочить.

Основной минус всего этого - если мы начали искать число 15 из приведенного примера, в то время как оно ползет до своего места, то мы его не найдем.

Тим Брей спрашивает, не придумал ли он чего странное, но в комментариях пока ничего эдакого не нашли.

Спасибо Maniac'у за ссылку.


(Пост опубликован в рамках недели борьбы с велосипедизмом)

Развернутые списки

Развернутый список, отличается от обычного тем, что в его узле содержится несколько элементов, а не один, как в обычном.
И такое простое решение обеспечивает очень интересные преимущества перед обычным списком. Во-первых, экономится память. Приятно, но это не главное. Главное, что в кэш теперь попадает не один элемент, а сразу пачка, и это сказывается на производительности самым положительным образом. Количество элементов в узле развернутого списка удобно выбирать таким, чтобы они как раз укладывались в кэш-линию.

Развернутые списки - это простой пример структуры данных, которая знает о существовании кэша и умеет это использовать.

Есть примеры и посложнее, например деревья Ван Эмде Боаса (они же vEB деревья).
Вообще с этими деревьями интересно получилось. По привычке я пошла в Википедию и долго тупила в картинку, пытаясь понять что же там изображено. Я всегда думала, что они выглядят вот так (картинка из слайдов Descent into Cache-Oblivion [.pdf]):

После чего нашла упоминания того, что это ненастоящие деревья Ван Эмде Боаса. Поскольку картинка из Википедии мне ничем не помогла, я попыталась найти труд самого Ван Эмде Боаса. Он называется Design and Implementation of an Efficient Priority Queue и его предлагают покупать за деньги. Короче, если вы знаете ссылку на хорошее описание, киньте ее, пожалуйста.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Ссылки по теме:
Cache-oblivious data structures
Несколько ссылок на материалы про кэш
Unrolled linked lists

Красно-черные деревья

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

Пример использования из реальной жизни: std::map'ы обычно реализуют через красно-черные деревья.

Картинка из Википедии, которую обычно приводят в качестве примера красно-черного дерева, мне не нравится.



Эта картинка дает неверное впечатление. Дерево, изображенное на ней, сбалансировано. И разноцветные вершины расположены рядами. И создается ощущение, что оно всегда так. Вот картинка получше (из статьи Advanced Haskell Data Structures: Red-Black Trees):


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



Если хочется расширить и углубить свое знание красно-черных деревьяв - вот вам хорошая лекция по красно-черным деревьям. На английском.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Фильтр Блума

Фильтр Блума - это структура данных, придуманная Бёртоном Блумом в 1970 году, которая позволяет быстро проверять принадлежность элемента множеству, при этом не затратная по памяти.

Фильтр Блума представляет собой битовый массив, в которой с помощью нескольких хэш-функций отображается каждый элемент. Картинка из Википедии.

Фильтр Блума может сработать ложно. То есть элемента во множестве нет, а он говорит, что есть. И чем больше элементов в множестве, тем выше вероятность ложного срабатывания. Однако, если вы знаете, что основной массы элементов в вашем множестве нет, то этот фильтр очень удобен. Вы сначала прогоняете их все через фильтр. А потом проверяете еще раз каким-нибудь иным более точным образом.
Ложные срабатывания - не единственная проблема фильтра Блума. Еще из него нельзя удалять элементы. Есть различные расширения фильтра Блума, которые все-таки позволяют это делать, но, понятное дело, не бесплатно.

Пример использования из Википедии:
Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.

(Пост опубликован в рамках недели борьбы с велосипедизмом)