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

Стыдно признаться, но я никогда еще в своей практике не использовал 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 и были придуманы для ситуаций, когда операция сравнения элементов гораздо (на порядки) дешевле операции загрузки очередной страницы дерева. Некогда имелась в виду загрузка с диска/ленты, но нынче в роли "медленного хранилища" вполне подходит основная оперативная память. При разнице в скоростях доступа к кэшу и оперативке в несколько порядков -- куда уж медленнее. Вместо того, чтобы делать одно сравнение, и переходить к следующему узлу -- с высокой вероятностью кэш-промаха -- было бы оптимальнее сделать десяток-другой сравнений сразу.