Горизонтальный и вертикальный просмотр массива

Question

Рассмотрим два почти идентичных кода:

Первый

for (int k=0;k<1000;k++)
{
    for (int i=0;i<600;i++)
    {
         for (int j=0;j<600;j++)
         {
              tab[i][j] = i *j;
         }
    }
 }

Второй

for (int k=0;k<1000;k++)
{
    for (int i=0;i<600;i++)
    {
         for (int j=0;j<600;j++)
         {
              tab[j][i] = i *j;
         }
    }
 }

Во втором вместо вкладки [i] [j] у нас есть вкладка [j] [i].
Первый код намного быстрее.

Вопрос
Почему первый код намного быстрее?

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

Answer 1

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

Answer 2

Это из-за локальности кэша. Строка кэша процессора может содержать несколько элементов массива одновременно, но только с адресов смежных областей.

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

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

Answer 3

Да, ваша теория верна.

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

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