четверг, июля 29, 2010

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

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

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

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

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

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

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

13 коммент.:

Сергей комментирует...

откуда берется макрос dcbt? (не нашел ее описание в инете)
современные компиляторы разве не пользуются префетч?

в с++0x не включили named функции?

заранее большое спасибо за ответ

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

А развёрнутые списки используют "как есть"? Мне казалось, все предпочитают держать вектор векторов, а не список векторов.

23Skidoo комментирует...

Отправил статью на адрес в профайле.

Сергей комментирует...

указатель на указатель вряд ли позволит держать все данные рядом (плохая локализация кеша) да и указатели почти не подвержены оптимизации автоматом компилятора

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

Занимался я cache-oblivious алгоритмами для себя в этом семестре, поэтому могу кое-чего рассказать. :)

С деревьями вана Эмде Боаса история такая: изначально его деревья служили для того, чтобы при некоторых ограничениях на ключ иметь возможность делать O(log log n) лукап и (могу врать) Succ, Pred. Фишка деревьев была в том, что все множество билось на куски по sqrt(n) элементов, и они распихивались по O(sqrt(n)) узлам.

Потом появилась cache-oblivious модель вычислений, в которой сложность алгоритма -- это количество memory-transfers между уровнями памяти (ну в CO есть еще пару предположений, но не суть). Чтобы более-менее неплохо укладывать деревья в памяти, умные ребята обратились к идеям ван Эмде Боаса. И то, что показано на рисунке, -- это van Emde Boas _layout_, а не tree (а. к. а. способ укладки).

Для сбалансированного бинарного дерева с n элементами vEB-layout определяется так:
1) Если n == 1, то vEB-layout такого дерева -- просто сам элемент.
1) Иначе разобъем дерево по уровню высоты h / 2; тогда в верхней части (пусть это часть #0) получим O(sqrt(n)) элементов, а снизу получим O(sqrt(n)) висящих деревьев (пронумеруем их слева направо). Заметим, что в каждом поддереве тоже O(sqrt(n)) элементов.
Теперь выложим исходное дерево в памяти следующим образом: сначала в vEB-layout-е выложим верхнюю часть (#0), а затем все остальные также в vEB-layout-е (т. о. vEB-layout -- рекурсивно определяемое понятие).

Если повтыкать теперь на текст выше и на картинку -- станет ясно. :)

Зачем это нужно: пусть у нас есть сбалансированное бинарное дерево поиска, выложенное в памяти в inorder-обходе. Известно, что поиск ключа требует O(log n) операций сравнения. Хочется понять, сколько обращений в память потребует поиск элемента. Вот утверждается, что в плохом случае это потребует O(log (n/B)) пересылок памяти (B -- размер блока данных, передаваемых между уровнями памяти; грубо говоря, размер кеш-строки).

По некоторым причинам, это плохо. :) Например, известно, что можно обойтись O(log_B(n)) пересылками памяти (что, если подумать, в разы лучше). Как этого достичь? Выложим дерево в vEB-layout-е!
Далее доказательство идет примерно так: так как vEB-layout определяется рекурсивно, то можно выбрать, как говорят, такой уровень детализации, что все дерево будет разбито на кусочки-треугольнички из O(B) элементов, которые в памяти лежат одним куском и, соответственно, подгружаются за O(1) операцию. Соответственно, любой путь от корня до вершины разбивается на кусочки длины O(log B) внутри которых не происходит I/O-операций. Соответственно, на весь lookup потребуется не более O(log n / log B) = O(log_B(n)) I/O.

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

Почитать и посмотреть картинки по CO можно, например, тут: link.

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

Впрочем, все, что я написал, есть по ссылке на одноименный пост в MSDN. :)

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

Отличное описание vEB-tree есть в лекциях MIT:
http://courses.csail.mit.edu/6.851/spring07/scribe/lec12.pdf

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

@aamonster: извините, но как вы будете удалять из вектора за время O(1)?

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

aamonster

А развёрнутые списки используют "как есть"? Мне казалось, все предпочитают держать вектор векторов, а не список векторов.

Какой-либо статистики у меня по этому поводу нет.
Список векторов хорош тем, что позволяет объединить плюсы списков и векторов.

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

2 ilyaraz: как правило, я буду удалять из одного из векторов "второго уровня" за время O(m), m - длина вектора. И с вероятностью 1/m - удалять из вектора-оглавления длиной ~n/m (n - число элементов). Итого получаем O(m)+1/m*O(n/m) = O(m)+O(n/m^2).
Для развёрнутого списка будет просто O(m). А теперь можно прикинуть, при каком соотношении между m и n это будет одно и то же.
Эстеты могут сделать три уровня вложенности (хе-хе, ext2 не напоминает? ;-))

2 Alena:
Это понятно. Но когда количество элементов списка более-менее предсказуемо (скажем, не больше количества пикселов изображения) - эти преимущества особой роли не играют.

Впрочем, я не о преимуществах. Просто с тем, что люди используют для таких нужд массив массивов, я сталкивался. А со списком массивов - кажется, нет. Вот и спрашиваю - оно реально используется?

Кстати, если они реально используются - то почему нет в boost? (стандартное хранилище велосипедов).

P.S. А за саму тему - спасибо... О велосипедах надо знать. Я, к примеру, только недавно открыл для себя пирамиду.

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

23Skidoo, Sandello, ilyaraz спасибо, стало понятнее.

aamonster
Вот и спрашиваю - оно реально используется?

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

Кстати, если они реально используются - то почему нет в boost?

Это я не знаю :-)

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

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

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

Andrey
если не изменяет память, представленную структуру Кормен называет heap (что в русском переводе - пирамида)

Не, heap - это совершенно другая структура данных