Unrolled linked list на Java

Всем привет.

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

В этот раз мне на глаза попались статью по cache oblivious алгоритмы, то есть такие алгоритмы, которые изначально более оптимизированы для работы с подсистемой кэширования современных процессоров.

Одним из представителей этой группы является Unrolled linked list.

Что же это такое?

Чтобы понять, что же это такое и с чем его едят, предлагаю вспомнить наиболее популярные реализации списков: ArrayList (с некоторым упрощением будем говорить о массивах вместо непосредственно списка) и LinkedList.

Рассмотрим их основные достоинства и недостатки:

ArrayList:

Достоинства

• Компактность — массив является наиболее (по крайней мере одной из) компактной структур данных для представления списков;
• Скорость вставки в конец незаполненного массива — операция очень быстрая, факт!;
• Скорость взятия элемента по индексу — также очень высока, количество cache miss можно оценить в N/B, где B — размер строки кэша, а N — количество элементов массива, что можно считать эталонным для такого рода структуры.

Недостатки

• Вставка в середину — не очень удобная операция для массива, приходится сдвигать правую часть, что даже с arraycopy всё же не бесплатно;
• Протяжённость области памяти — для хранения больших массивов требуется большой непрерывный участок памяти. И хотя многие сборщики мусора эффективно борются с фрагментацией памяти, вероятность OutOfMemmory особенно для больших списков является существенной.

LinkedList:

Достоинства

• Относительно более простая и быстрая операция вставки в середину;
• Нет проблем при работе с сильно фрагментированой памятью.

Недостатки

• Существенно больший объём необходимой памяти для хранения данных того же размера (до 4-х раз);
• При итерации по списку количество cache miss в худшем случае может быть равно количеству нод списка. Даже в лучшем случае, когда все ноды находятся в пямяти друг за другом, за счёт большего размера ноды количество cache miss будет в несколько раз больше такового для ArrayList.

Так вот UnrolledLinkedList пытается объединить достоинства двух списков и при этом не унаследовать их недостатки.
Рассмотрим устройство этого списка более подробно.

Попросту говоря, UnrolledLinkedList — связный(двусвязный) список массивов длины n. То есть каждая нода содержит в себе не одно значение, а массив значений. При этом массив является достаточно маленьким, чтобы опреции вставки и удаления были очень быстрыми и фрагментация памяти меньше влияла на возможность создания ноды, но достаточно большие, чтобы полностью помещаться в строку кэша, для сокращения количества cache miss. Дополнительно каждая нода хранит в себе количество добаленных в неё элементов. Графически этот список можно представить следующим образом:

Рассмотрим оперции для этого списка:

Вставка в ноду:
В случае наличия свободных ячеек, новый элемент просто добавляется в конец массива. Если массив уже полон, то мы создаём новую ноду за текущей и переносим в неё правую половину массива, создавая тем самым место для вставки новых значений. Новый элемент в таком случае будет вставлен в конец новой ноды. То же можно применить к вставке в середину массива.

Графически эту операцию можно представить следующим образом:

Удаление из ноды:
Операция досточно простая, мы просто удаляем нужный элемент из массива и делаем сдвиг остальных элементов, если это необходимо. Но есть одно но, в случае если количество элементов в массиве уменьшается до n/2, то из соседних ячеек переносятся n/2 элементов. Если после этого какая-то из ячеек оказалась пустой — она удаляется. Эта опреция нужна для редуцирования расхода памяти при постепенной очистке больших списков.

Поиск ноды по индексу:
Как и связном списке поиск начинается с головы иди хвоста, откуда ближе, отличие в том, что итерироваться по массивам нет нужды — необходимо просто суммировать значения полей содержащие количество элементов в ноде. Таким образом поиск нужной ноды происходит существенно быстрее, чем в LinkedList, хотя асимптотика тут попрежнему O(N).

Изначально мне показалось, что половина пустых ячеек в каждой ноде — это слишком расточительно. Однако как показали небольшие экперименты, в среднем уровень заполнения ячеек находится на уровне 70%, и даже с 50% заполнением расход памяти должен быть существенно меньше, чем у связного списка. Более того список позволяет настраивать себя под различные нужды. Я пытался поиграть с коэффициентом заполнения массива, но существенной выгоды не извлёк, поэтому оставил всё как есть.

Говоря про количество cache miss, то при итерации по таком списку его можно оценить как (N/n+1)(n/B), где N — длина списка, n — длина массива ноды, B — длина строки кэша. Такая оценка достаточно близка к оценке для ArrayList.

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

Исходники выложены на github.
Из себя они представляют достаточно сырой код, так что просьба не сильно пинать ногами за качество. Однако в любом случае буду признателен любой критике.

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

Спасибо за внимание.

Источники:
blogs.msdn.com/b/devdev/archive/2005/08/22/454887.aspx
en.wikipedia.org/wiki/Unrolled_linked_list

Автор: Falland