Массивы против связанных списков с точки зрения местности

Question

Скажем, у нас есть несортированный массив и связанный список. В худшем случае при поиске элемента для обеих структур данных будет O( n), но мой вопрос:

Будет ли массив по-прежнему работать быстрее из-за использования пространственной локальности в кэше, или же в кэше будет использоваться локальная ветвь, позволяющая связанным спискам работать так же быстро, как любой массив?

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

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

Answer 1

Ваше понимание случая массива в основном верно. Если к массиву осуществляется последовательный доступ, многие процессоры не только извлекают блок, содержащий элемент, но также предварительно выбирают последующие блоки, чтобы минимизировать количество циклов, затрачиваемых на ожидание пропадания кэша. Если вы используете процессор Intel x86, вы можете найти подробности об этом в руководстве по оптимизации Intel x86. Кроме того, если элементы массива достаточно малы, загрузка блока, содержащего элемент, означает, что следующий элемент, вероятно, находится в том же блоке.

К сожалению, для связанных списков картина нагрузок непредсказуема с точки зрения процессора. Он не знает, что при загрузке элемента по адресу X следующий адрес является содержимым (X + 8).

В качестве конкретного примера, последовательность адресов загрузки для последовательного доступа к массиву хороша и предсказуема. Например, 1000, 1016, 1032, 1064 и т. Д.

Для связанного списка это будет выглядеть так: 1000, 3048, 5040, 7888 и т. Д. Очень сложно предсказать следующий адрес.