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

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


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