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

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

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

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

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

Ответы

Ответ 1

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

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

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

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