Ответ 1
Я считаю, что вы смотрите на эффекты локальности ссылки в иерархии памяти компьютера.
Обычно компьютерная память разделяется на разные типы, которые имеют разные характеристики производительности (это часто называют иерархией ). Самая быстрая память находится в регистрах процессора, которые могут (как правило) получать и считывать за один такт. Однако, как правило, только несколько таких регистров (обычно не более 1 КБ). С другой стороны, основная память компьютера огромна (скажем, 8 ГБ), но гораздо медленнее для доступа. Для повышения производительности компьютер обычно физически сконструирован таким образом, чтобы несколько уровней кэшей между процессором и основной памятью. Эти кэши работают медленнее, чем регистры, но намного быстрее, чем основная память, поэтому, если вы делаете доступ к памяти, который выглядит что-то в кеше, он, как правило, намного быстрее, чем если вы должны перейти в основную память (обычно между 5-25x Быстрее). При обращении к памяти процессор сначала проверяет кеш памяти для этого значения, прежде чем вернуться в основную память, чтобы прочитать значение. Если вы последовательно получаете доступ к значениям в кеше, вы получите гораздо лучшую производительность, чем если бы вы пропустили память, случайный доступ к значениям.
Большинство программ написаны таким образом, что если в память считывается один байт в памяти, программа позже считывает несколько разных значений из этой области памяти. Следовательно, эти кэши обычно создаются так, что когда вы читаете одно значение из памяти, блок памяти (обычно где-то между 1 КБ и 1 МБ) значений вокруг этого единственного значения также втягивается в кеш. Таким образом, если ваша программа считывает близлежащие значения, они уже находятся в кеше, и вам не нужно переходить в основную память.
Теперь, одна последняя деталь - в C/С++, массивы хранятся в строчном порядке, что означает, что все значения в одной строке матрицы хранятся рядом друг с другом. Таким образом, в памяти массив выглядит как первая строка, затем вторая строка, затем третья строка и т.д.
Учитывая это, давайте посмотрим на ваш код. Первая версия выглядит так:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
Теперь посмотрим на эту самую внутреннюю строку кода. На каждой итерации значение k изменяется с увеличением. Это означает, что при запуске самого внутреннего цикла каждая итерация цикла, вероятно, будет иметь недостаток в кеше при загрузке значения b[k][j]
. Причина этого в том, что, поскольку матрица хранится в строчном порядке, каждый раз, когда вы увеличиваете k, вы пропускаете целую строку матрицы и много прыгаете в память, возможно, далеко за значения, которые вы кэшировали, Тем не менее, у вас нет промаха при поиске c[i][j]
(так как i
и j
совпадают), и вы, вероятно, не пропустите a[i][k]
, потому что значения находятся в строчном порядке, и если значение a[i][k]
кэшируется из предыдущей итерации, значение a[i][k]
, читаемое на этой итерации, происходит из соседней ячейки памяти. Следовательно, на каждой итерации самого внутреннего цикла вы, вероятно, будете пропускать один кеш.
Но рассмотрим эту вторую версию:
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
for (int j = 0; j < n; j++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
Теперь, поскольку вы увеличиваете j
на каждой итерации, подумайте о том, сколько промахов в кеше вы, скорее всего, найдете в самом внутреннем заявлении. Поскольку значения находятся в строчном порядке, значение c[i][j]
, скорее всего, будет в кэше, потому что значение c[i][j]
из предыдущей итерации, скорее всего, кэшируется и готово к чтению. Аналогично, b[k][j]
, вероятно, кэшируется, и поскольку i
и k
не изменяются, скорее всего, кешируются a[i][k]
. Это означает, что на каждой итерации внутреннего цикла вы, вероятно, не будете пропускать кеш.
В целом, это означает, что вторая версия кода вряд ли имеет пропуски кэша на каждой итерации цикла, в то время как первая версия почти наверняка будет. Следовательно, второй цикл, вероятно, будет быстрее первого, как вы видели.
Интересно, что многие компиляторы начинают иметь поддержку прототипа для обнаружения того, что вторая версия кода быстрее первой. Некоторые попытаются автоматически переписать код, чтобы максимизировать parallelism. Если у вас есть копия Purple Dragon Book, в главе 11 обсуждается, как работают эти компиляторы.
Кроме того, вы можете оптимизировать производительность этого цикла еще больше, используя более сложные циклы. Например, метод, называемый blocking, может использоваться для значительного повышения производительности путем разделения массива на субрегионы, которые могут храниться в кеше дольше, затем используя несколько операций над этими блоками, чтобы вычислить общий результат.
Надеюсь, это поможет!