Здравствуйте, smeeld, Вы писали:

S>Что до промахов в кеше из-за раскиданности нод списка, во всех нормальных
S>системах, ноды для списков выделяются из некоторого непрерывного массива,
S>кеша специализированного аллокатора. Так что никакой раскиданности.

Вот мне тоже так думается, но у wathcmaker-а был еще один козырь — зависимость по данным. Компилятор может (хотя и не должен) развернуть цикл обхода массива и (в суперскалярной арх-ре) практически параллельно выполнять операции над группой элементов массива. Отдельные коллеги, (напр. Касперски в одной из своих книг) уверяют, что это дает существенную разницу.

P.S. Кроме того, для связного списка нет никакой гарантии, что последовательные элементы списка располагаются в памяти последовательно, что как бы снижает эффект выделения памяти для узлов списка из одного пула.