Будет ли современный процессор (например, i7) следовать указателям и выполнять предварительную выборку их данных при переборе их списка?

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

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

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

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

Я уверен, что вы это уже знаете, но стоит еще раз упомянуть, что одним из наиболее эффективных методов получения максимальной отдачи от кэша является использование меньшего объема данных! В приведенном выше коде, если вы можете обойтись int16_t вместо int32_t, вы обязательно должны это сделать. Вы должны упаковать свои многочисленные bool, флаги и перечисления в битовые поля, использовать индексы вместо указателей (особенно в 64-битных системах), использовать хеш-значения фиксированного размера в ваших структурах данных вместо строк и т. д.

Теперь о вашем главном вопросе: может ли процессор следовать случайным указателям и помещать данные в кеш до того, как они потребуются. В очень ограниченной степени это действительно происходит. Как, вероятно, вы знаете, современные процессоры используют множество приемов для увеличения скорости (т. е. увеличения скорости удаления инструкций). Такие приемы, как наличие буфера сохранения, неупорядоченное выполнение, суперскалярные конвейеры, множественные функциональные блоки всех видов, ветвления. предсказание и т. д. В большинстве случаев все эти приемы просто помогают процессору продолжать выполнение инструкций, даже если текущие инструкции зависли или слишком долго выполняются. Для загрузки памяти (что является самым медленным, если данные не находятся в кеше) это означает, что ЦП должен как можно быстрее добраться до инструкции, вычислить адрес и запросить данные из контроллера памяти. Однако у контроллера памяти может быть только очень ограниченное количество необработанных запросов (обычно два в наши дни, но я не уверен). элементы вашего вектора posPointers) и сделать вывод, что это адреса новых данных, которые потребуются вашему коду, он не может продвинуться далеко вперед, потому что контроллер памяти может иметь только определенное количество ожидающих запросов.

В любом случае, AFAIK, я не думаю, что процессоры действительно делают это. Обратите внимание, что это сложный случай, потому что адреса ваших случайно распределенных ячеек памяти сами находятся в памяти (в отличие от того, чтобы быть в регистре или вычисляться из содержимого регистра). И если бы ЦП сделали это, это не было бы в любом случае имеют такой большой эффект из-за ограничений интерфейса памяти.

Упомянутый вами метод предварительной выборки кажется мне действительным, и я видел, как он используется, но он дает заметный эффект только в том случае, если ваш процессор должен что-то делать, ожидая поступления будущих данных. Увеличение трех целых чисел занимает намного меньше времени, чем загрузка 12 байтов из памяти (на самом деле загрузка одной строки кэша), и поэтому это не будет иметь большого значения для времени выполнения. Но если бы у вас было что-то стоящее и более тяжелое для наложения поверх предварительной выборки памяти (например, вычисление сложной функции, которая не требует данных из памяти!), то вы могли бы получить очень хорошие ускорения. Видите ли, время прохождения вышеуказанного цикла, по сути, является суммой времени всех промахов кеша; и вы получаете приращения координат и бухгалтерский учет цикла бесплатно. Таким образом, вы бы выиграли больше, если бы бесплатные вещи были более ценными!

Современные процессоры имеют аппаратные механизмы предварительной выборки: Предварительная загрузка оборудования Intel. Они выводят шаблоны пошагового доступа к памяти и выполняют предварительную выборку областей памяти, к которым, вероятно, будет осуществлен доступ в ближайшем будущем.

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

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