15 сентября 2010 г.

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

Стыдно признаться, но я никогда еще в своей практике не использовал LinkedList. Не находилось оказии -- всегда оказывалось, что ArrayList либо в принципе подходит лучше, либо алгоритм можно так перестроить, что будет подходить лучше, либо в принципе он хуже, но на потребных размерах выигрывает. Последовательный доступ, большие накладные расходы памяти на хранение указателей в узлах, недружественность к кэшу и векторным инструкциям -- на мой взгляд, этого достаточно, чтобы 10 раз подумать, прежде чем его использовать. Тем не менее, никуда не деться -- вставка в случайное место для ArrayList дороже, чем для Linked уже начиная где-то с 500-1000 элементов (ну еще есть многопоточные приложения, где недружественность к кэшу становится преимуществом -- меньше конкуренция разных вычислительных ядер за строки кэша).

Не далее как вчера я обдумывал эту мысль, и пришел к выводу, что если бы мне нужен был быстрый список без (быстрого) случайного доступа но со всеми остальными плюшками, я бы попробовал сделать что-то вроде смеси array и linked -- узлы с массивами по нескольку элементов, так, чтобы узел вместе со всей служебной информацией влезал, скажем, в cache line. Получаем сразу и меньшие накладные расходы памяти -- одна пара указателей не на один, а сразу на несколько элементов. И лучшую локальность данных, и поле применимости для векторых инструкций. Все плюшки, кроме быстрого случайного доступа.

А сегодня обнаруживаю, что идею украли прямо из головы. И даже обозвать уже успели, и в википедии записали. Называется развернутый связный список (unrolled linked list). Неплохая статья на MSDN по этой структуре данных. Автор провел небольшое исследование производительности, и нашел, что развернутый список обходится (последовательно) примерно в 2.5 раза медленнее массива (обычный связный -- в 12 раз медленнее). На мой взгляд -- вполне разумный компромисс.

Еще вчера же, когда я дочитывал про B-trees, мне так же пришло в голову, что обычные бинарные диревья в нынешних условиях многоуровневых кэшей и векторных инструкций тоже очень не в тему. Всякие TreeMap разумнее было бы делать на базе B-trees, нежели на основе красно-черных бинарных деревьев. Ведь в конце-концов B-trees и были придуманы для ситуаций, когда операция сравнения элементов гораздо (на порядки) дешевле операции загрузки очередной страницы дерева. Некогда имелась в виду загрузка с диска/ленты, но нынче в роли "медленного хранилища" вполне подходит основная оперативная память. При разнице в скоростях доступа к кэшу и оперативке в несколько порядков -- куда уж медленнее. Вместо того, чтобы делать одно сравнение, и переходить к следующему узлу -- с высокой вероятностью кэш-промаха -- было бы оптимальнее сделать десяток-другой сравнений сразу.

8 комментариев:

  1. Вот. Мы (точнее, Сергей Куксенко, конечно) в своё время сделали т.н. "fat TreeMap", в котором в узлах как раз были массивы. Эту же идею хотели применить в листах, но руки не дошли.

    Открытый вопрос, кстати, что лучше: зафолдить LinkedList, чтобы доступ был более cache-friendly, или же разбить ArrayList на куски, чтобы апдейт был быстрее. ;)

    ОтветитьУдалить
  2. >"fat TreeMap", в котором в узлах как раз были массивы

    Если не секрет -- почему в продакшн не пошло? Или там какие-то неявные недостатки появляются?

    >Открытый вопрос, кстати, что лучше: зафолдить LinkedList, чтобы доступ был более cache-friendly, или же разбить ArrayList на куски, чтобы апдейт был быстрее

    Мне кажется, лучше зафолдить LinkedList. Просто потому, что ArrayList на порядок чаще используется, и ухудшение его производительности в самых простых операциях, типа get(int) -- а оно же все-таки будет -- может очень многих неприятно удивить. А с LinkedList хуже уже и не будет :)

    ОтветитьУдалить
  3. Этот комментарий был удален автором.

    ОтветитьУдалить
  4. >>"fat TreeMap", в котором в узлах как раз были массивы

    >Если не секрет -- почему в продакшн не пошло? Или там какие-то неявные недостатки появляются?

    -XX:+AggressiveOpts

    ;)

    ОтветитьУдалить
  5. Я правильно понял -- в режиме AggressiveOpts JIT перепишет java.util.TreeMap так, что там будет flat map? Я думал, JIT только код оптимизирует, а получается, он и структуры данных может менять "под себя"?

    ОтветитьУдалить
  6. Правильно думаете. Всё проще: с AggressiveOpts автоматически bootclasspath'нется alt-rt.jar, в котором лежит в т.ч. и чистая Java-реализация fat TreeMap.

    ОтветитьУдалить
  7. Хм. А есть где-нибудь полное описание, какие еще классы "оптимизированы" в alt-rt.jar?

    ОтветитьУдалить