пятница, июля 30, 2010

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

В посте 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'у за ссылку.


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

14 коммент.:

Kentzo комментирует...

Я так понимаю, что в данном случае можно было ползти из начала, а не из конца?

Анонимный комментирует...

Поскольку пост опубликован в рамках недели борьбы с велосипедизмом, то подразумевается, что Тим Брей придумал что-то, что было описано до него? Или вообще поставил задачу, которая до того была поставлена и решена лучше???

Ползти из начала сложновато, придётся вначале ставить лок на транзакцию: перемещение всех элементов вправо + вставка нового элемента слева + увеличение счётчика. А это как бы длинная транзакция, как я понял условие, не желательно такие лочить...

redbaron комментирует...

Просьба включить в ваш цикл что-нибудь о lock free data structures

Alena комментирует...

Kentzo

Я так понимаю, что в данном случае можно было ползти из начала, а не из конца?

Нет. В самом начале, когда элемент добавлен, а число элементов еще не обновлено, список станет некорректным.

Анонимный

Поскольку пост опубликован в рамках недели борьбы с велосипедизмом, то подразумевается, что Тим Брей придумал что-то, что было описано до него? Или вообще поставил задачу, которая до того была поставлена и решена лучше???

Он решил задачу, на которую не знал ответа. Но после этого не постеснялся спросить в блоге "а может я чего странное придумал и уже такое есть?"

Борьба с велосипедизмом - это чтобы еще раз не придумывать то, что уже придумал Тим Брей.

redbaron

Просьба включить в ваш цикл что-нибудь о lock free data structures

По-моему это будет негуманно. Я лучше когда-нибудь отдельно об этом напишу.

Programmist комментирует...

ИМХО - потенциально опасная структура.
Возможный вариант сбоя:
На шаге 1, когда добавляется последний элемент 40, читающий тред берет количество элементов (4) в свой счетчик цикла.
На следующем шаге читающий тред не успевает прочитать бывший последний элемент (40) до того, как он будет заменен на (30).
Результат: (40) не будет найдено, хотя до момента поиска оно в структуре уже было.

Programmist комментирует...

О. Он оказывается уже описал этот кейс :)
Его решение: ограничение цикла - сам размер странице с пометкой volatile, дабы компилятор не оптимизил.

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

Kentzo комментирует...

Alena
Действительно.
Но можно было бы сначала добавить в конец, потом поменять количество элементов и добавить в начало.

Dimitry Ivanov комментирует...

Если список связанный, то можно добавлять в начало с ценой константы, но, насколько я понимаю (исходя из соображения того как работает binary search) - список все-таки индексированный (тоесть цена доступа по индексу константа)

В таком случае добавление в начало должно привести к сдвигу списка (а тут нам понадобится синхронизация) и мало чем будет отличатся от механизма лок-поиск-сдвиг-вставка-анлок.

Я так понимаю этот алгоритм нужен для того чтобы избавится от долгого лока который нужен для сдвига элементов, и заменить его множеством атомарных операций которые подразумевают что между ними может произойти thread-safe binary search.

Maxime комментирует...

В комментах к оригинальной статье дали ссылку на еще одну интересную статью, про B-heap: http://cacm.acm.org/magazines/2010/7/95061-youre-doing-it-wrong/fulltext

Prokrust комментирует...

Проблема с циклом легко решается маркером в конце списка.

Denis Bazhenov комментирует...

Получается что данная структура основывается на предположении что пишут реже чем читают. Тогда не проще ли было лочить всю страницу или делать копировании страницы с последующей модификацией указателя на страницу (atomic reference)?

id комментирует...

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

pustota1 комментирует...

Хм, а чем это должно быть лучше B-tree, ну скажем с проверкой того
пишут два конкурирующих процесса в одну и ту же ветвь или нет ? Если нет -- без лока, если да -- с локом.

Alena комментирует...

pustota1
Хм, а чем это должно быть лучше B-tree, ну скажем с проверкой того
пишут два конкурирующих процесса в одну и ту же ветвь или нет ? Если нет -- без лока, если да -- с локом.


Он описал другую структуру, попроще. Наверное, ему дерево не нужно было.
Его в комментариях спросили про B-tree, но он не ответил.