Будет ли современный процессор (например, i7) следовать указателям и предварительно выбирать их данные, просматривая их список?
Я хочу научиться писать лучший код, который использует кеш процессора. Работа с непрерывной памятью кажется идеальной ситуацией. При этом, мне любопытно, есть ли подобные улучшения, которые могут быть сделаны с несмежной памятью, но с массивом указателей, чтобы следовать, как:
struct Position {
int32_t x,y,z;
}
...
std::vector<Position*> posPointers;
...
updatePosition () {
for (uint32_t i = 0; i < posPointers.size(); i++) {
Position& nextPos = *posPointers[i];
nextPos.x++;
nextPos.y++;
nextPos.z++;
}
}
Это всего лишь грубый макетный код, и для правильного изучения этого давайте просто скажем, что все структуры Position были созданы случайным образом по всей куче.
Могут ли современные, умные процессоры, такие как Intel i7, заглянуть в будущее и понять, что в этом будет необходимость? X_ptrданные очень скоро? Поможет ли следующая строка кода?
... // for loop
Position& nextPos1 = *posPointers[i];
Position& nextPos2 = *posPointers[i+1];
Position& nextPos3 = *posPointers[i+2];
Position& nextPos4 = *posPointers[i+3];
... // Work on data here
Я читал некоторые слайды презентации, которые, казалось, указывали на такой код, который заставил бы процессор предварительно выбирать некоторые данные. Это правда? Я знаю, что есть нестандартные, специфичные для платформы, способы вызова предварительной выборки, такие как __builtin_prefetch, но бросать это повсюду просто кажется уродливой преждевременной оптимизацией. Я ищу способ, которым я могу подсознательно писать эффективный кеш-код.
Решение
Я знаю, что вы не спрашивали (и, вероятно, не нуждаетесь в проповеди о правильном обращении с кешами, но я все равно решил внести свои два цента. Обратите внимание, что все это применимо только в горячей код. Помните, что преждевременная оптимизация — корень всего зла.
Как было отмечено в комментариях, лучший способ — это иметь контейнеры с фактическими данными. Вообще говоря, плоские структуры данных гораздо предпочтительнее «спагетти-указателя», даже если вам приходится дублировать некоторые данные и / или платить цену за изменение размера / перемещение / дефрагментацию ваших структур данных.
И, как вы знаете, плоские структуры данных (например, массив данных) окупаются только в том случае, если вы обращаетесь к ним линейно и последовательно в большинстве случаев.
Но эта стратегия не всегда может быть полезной. Вместо реальных линейных данных вы можете использовать другие стратегии, такие как использование распределителей пулов и итерации по самим пулам, а не по вектору, содержащему указатели. Это, конечно, имеет свои недостатки и может быть немного сложнее.
Я уверен, что вы уже знаете это, но стоит еще раз упомянуть, что одним из наиболее эффективных методов получения максимальной отдачи от вашего кэша является получение меньшего объема данных! В приведенном выше коде, если вы можете сойти с рук int16_t вместо int32_tВы должны определенно сделать это. Вы должны упаковать много bools, а также флаги и перечисления в битовые поля, использование индексов вместо указателей (особенно в 64-битных системах), использование хеш-значений фиксированного размера в ваших структурах данных вместо строк и т. д.
Теперь о вашем главном вопросе: может ли процессор следовать случайным указателям и выводить данные в кеш до того, как они понадобятся. В очень ограниченной степени это происходит. Как вы, наверное, знаете, современные процессоры используют много приемов для увеличения скорости (то есть увеличения скорости удаления инструкций). Такие приемы, как наличие буфера хранилища, выполнение не по порядку, суперскалярные конвейеры, множественные функциональные блоки любого типа, ветвление предсказания и т. д. В большинстве случаев эти трюки просто помогают процессору продолжайте выполнять инструкции, даже если текущие инструкции застопорились или заняли слишком много времени, чтобы закончить. Для загрузок памяти (что медленнее всего делать, если данные не находятся в кеше), это означает, что ЦП должен как можно быстрее получить инструкцию, рассчитать адрес и запросить данные у контроллера памяти. Тем не менее, контроллер памяти может иметь только очень ограниченное количество ожидающих запросов (обычно два в эти дни, но я не уверен.) Это означает, что даже если ЦП делал очень сложные вещи, чтобы заглянуть в другие области памяти (например, элементы вашего posPointers вектор) и определите, что это адреса новых данных, которые понадобятся вашему коду, он не сможет продвинуться далеко вперед, потому что контроллер памяти может иметь только столько ожидающих запросов.
В любом случае, AFAIK, я не думаю, что процессоры на самом деле это делают. Обратите внимание, что это сложный случай, потому что адреса ваших случайно распределенных областей памяти сами по себе находятся в памяти (в отличие от того, чтобы быть в регистре или могут быть вычислены из содержимого регистра). И если бы процессоры это делали, это не было бы В любом случае, это имеет большое значение из-за ограничений интерфейса памяти.
Упомянутая вами техника предварительной выборки мне кажется действительной, и я видел, что она использовалась, но она дает заметный эффект только в том случае, если вашему ЦП нужно что-то делать в ожидании поступления будущих данных. Увеличение трех целых чисел занимает намного меньше времени, чем загрузка 12 байтов из памяти (фактически, загрузка одной строки кэша), и, следовательно, это не будет иметь большого значения для времени выполнения. Но если у вас есть что-то стоящее и более тяжелое для наложения поверх предварительных выборок памяти (например, вычисления сложной функции, которая не требует данных из памяти!), То вы можете получить очень хорошие ускорения. Видите ли, время прохождения вышеуказанного цикла по сути является суммой времени всех пропусков кэша; и вы получаете приращения координат и бухгалтерию цикла бесплатно. Таким образом, вы бы выиграли больше, если бы бесплатные вещи были более ценными!
Другие решения
Современные процессоры имеют аппаратные механизмы предварительной выборки: Аппаратный префиксер Intel. Они выводят шаблоны доступа к памяти и предварительно выбирают области памяти, которые, вероятно, будут доступны в ближайшем будущем.
Однако в случае абсолютно случайной погони за указателем такие приемы не могут помочь. Процессор не знает, что выполняемая программа выполняет отслеживание указателя, поэтому он не может соответственно выполнить предварительную выборку. В таких случаях аппаратные механизмы негативно влияют на производительность, так как они могут предварительно выбирать значения, которые вряд ли будут использоваться.
Лучшее, что вы можете сделать, это попытаться организовать ваши структуры данных в памяти таким образом, чтобы доступ к смежным частям памяти был более вероятным.