Блог

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

Есть две причины, по которым непрерывная память более удобна для кэша, чем несмежная память:

1. Если данные хранятся последовательно, то данные, скорее всего, будут храниться в меньшем количестве строк кэша (которые на большинстве платформ представляют собой блоки размером 64 байта). В этом случае выше вероятность того, что все данные поместятся в кэш, и новые строки кэша будут загружаться реже. Если данные хранятся не последовательно и разбросаны по множеству случайных ячеек памяти, то возможно, что только небольшая часть каждой строки кэша будет содержать важные данные, а остальная часть строки кэша будет содержать неважные данные. В этом случае для кэширования всех важных данных потребуется больше строк кэша, и если кэш недостаточно велик для хранения всех этих строк кэша, эффективность кэша снизится.

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

Вы правы в том, что даже если массив хранится непрерывно в виртуальном адресном пространстве, это не обязательно означает, что массив также непрерывно находится в физическом адресном пространстве.

Однако это не имеет отношения к моим заявлениям, сделанным в # 1 моего ответа), потому что строка кэша не может перекрывать границу страницы памяти. Содержимое одной страницы памяти всегда является непрерывным, как в виртуальном адресном пространстве, так и в физическом адресном пространстве.

Но вы правы, что это может иметь отношение к моим заявлениям, сделанным в # 2 моего ответа. Предполагая, что размер страницы памяти составляет 4096 байт (что является стандартным для платформы x64) и размер строки кэша 64 байта, тогда на страницу памяти приходится 64 строки кэша. Это означает, что каждая 64-^я строка кэша может находиться на границе «скачка» в физическом адресном пространстве. В результате каждая 64-^я строка кэша может быть неправильно предсказана аппаратной предварительной выборкой кэша. Кроме того, предварительная выборка кэша может быть не в состоянии сразу адаптироваться к этой новой ситуации, поэтому она может не выполнить предварительную выборку нескольких строк кэша, прежде чем она сможет надежно предсказать следующие строки кэша снова и предварительно загрузить их вовремя. Однако, как программисту приложений, вам не нужно беспокоиться об этом. Операционная система несет ответственность за организацию сопоставления пространства виртуальной памяти с пространством физической памяти таким образом, чтобы не было слишком много «переходов», которые могли бы оказать негативное влияние на производительность. Если вы хотите узнать больше по этой теме, вы можете прочитать эту исследовательскую работу: Анализ предварительной выборки оборудования по границам виртуальной страницы

Как правило, массивы лучше, чем связанные списки, с точки зрения эффективности кэша, потому что они всегда непрерывны (в виртуальном адресном пространстве).