Почему это улучшает производительность?

Question

У меня есть два цикла, которые в основном ищут в двух разных массивах (каждый из которых имеет размер около 2-4k на пике) и задают значение в 3-м массиве на основе этих значений. По какой-то странной причине существует разница в два фактора между производительностью этого фрагмента кода, в зависимости от того, в каком порядке я помещаю эти два цикла.

Это первая установка. Он выполняет в ~ 150 миллисекунд на моем компьютере:

public static int[] SchoolMultiplication(int[] a, int[] b, int numberBase) 
{ 
    List<double> times = new List<double>(); 
    TimeTest timeTest = new TimeTest(); 

    int aLen = a.Length; 
    int bLen = b.Length; 

    int[,] resultMatrix = new int[a.Length + b.Length, aLen]; 
    int[] result = new int[a.Length + b.Length]; 

    timeTest.Start(); 

    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
    { 
     for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 

     { 
      resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
     } 
    } 

Теперь, если я ничего не меняется, кроме того, петель, как этот

for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 
{ 
    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
{ 
     resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
    } 
} 

Общее время работы метода падает до ~ 400 миллисекунд , Как простой обмен порядком цикла улучшает производительность почти на 300%? Я полагаю, что это какая-то вещь для кеширования или указателя?

Answer 1

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

---

мульти-одномерный массив выглядит как вам это:

И как это к компьютеру. Оптимальный способ траверсы имеет индексы следующие ниже стрелки:

Итак, когда вы меняете вы массив зацикливания массива проходятся так:

Таким образом, вы получите больше кэша-промахи и более бедной алгоритм исполнительской ,

Answer 2

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

Для простых циклов C++ это также поможет сделать петли назад, чтобы получить некоторую производительность в цикле. Не уверен, как он подходит для .NET.

Answer 3

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

Линейные структуры данных: Локализация часто встречается, потому что код содержит циклы, которые имеют тенденцию ссылаться на массивы или другие структуры данных по индексам. Последовательная локальность, частный случай пространственной локальности, возникает, когда соответствующие элементы данных расположены и доступны линейно. Например, простой обход элементов в одномерном массиве от базового адреса до самого высокого элемента будет использовать последовательную локальность массива в памяти. [2] Более общая равноудаленная локальность возникает, когда линейный обход находится над более длинной областью смежных структур данных, имеющих идентичную структуру и размер, и в дополнение к этому не все структуры находятся в доступе, а только взаимно соответствующие одинаковые элементы структур. Это тот случай, когда матрица представляется в виде последовательной матрицы строк, и требование заключается в доступе к одному столбцу матрицы.

Answer 4

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

Answer 5

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

Fastest way to loop through a 2d array?

Но Shhhh мы не должны заботиться о праве производительности? :)

Answer 6

Я также считаю, что относительные размеры массивов a и b будут иметь значение.

Если длина a.length велика и b.length мала, второй вариант должен быть быстрее. И наоборот, если a.length мала и b.length велика, первый вариант будет быстрее. Проблема заключается в том, чтобы избежать затрат на установку/отключение внутреннего контура.

Кстати, почему у вас

Int Alen = a.length;

Но тогда также вызывается a.Length напрямую? Похоже, вы должны выбрать тот или другой.