Почему моя программа работает медленно, когда зацикливается ровно на 8192 элемента?

755

Вот выдержка из рассматриваемой программы. Матрица img[][]имеет размер SIZE × SIZE и инициализируется в:

img[j][i] = 2 * j + i

Затем вы создаете матрицу res[][], и каждое поле здесь считается средним из 9 полей вокруг нее в матрице img. Граница оставлена ​​на 0 для простоты.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Это все, что есть в программе. Для полноты картины вот что предшествует. Код не приходит после. Как видите, это просто инициализация.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

В основном, эта программа работает медленно, когда SIZE кратен 2048, например, время выполнения:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

Компилятор GCC. Из того, что я знаю, это из-за управления памятью, но я не очень много знаю об этом предмете, вот почему я спрашиваю здесь.

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

Я уже знаю о malloc / free, но проблема не в объеме используемой памяти, а в просто времени выполнения, поэтому я не знаю, как это могло бы помочь.

casperOne
источник
67
@bokan это происходит, когда размер кратен критическому шагу кеша.
Лучиан Григоре
5
@ Мистик, это не имеет значения, это та же самая проблема; Код может быть разным, но в основном оба вопроса задаются примерно в одно и то же время (и их названия определенно похожи).
Griwes
33
Вы не должны обрабатывать изображение, используя двухмерный массив, если вы хотите высокую производительность. Рассмотрим все пиксели в необработанном виде и обработайте их как одномерный массив. Сделайте это размытие в два прохода. Сначала добавьте значение окружающих пикселей, используя скользящую сумму в 3 пикселя: slideSum + = src [i + 1] -src [i-1]; Dest [I] = slideSum ;. Затем сделайте то же самое по вертикали и разделите одновременно: dest [i] = (src [i-width] + src [i] + src [i + width]) / 9. www-personal.engin.umd.umich.edu/~jwvm/ece581/18_RankedF.pdf
Bokan
8
Здесь на самом деле происходит две вещи. Это не просто супер-выравнивание.
Мистик
7
(Просто незначительный зазор в вашем ответе. Для первого сегмента кода было бы неплохо, если бы все ваши циклы for имели скобки.)
Тревор Бойд Смит

Ответы:

954

Разница вызвана той же проблемой супер-выравнивания из следующих связанных вопросов:

Но это только потому, что есть еще одна проблема с кодом.

Начиная с оригинального цикла:

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Сначала обратите внимание, что две внутренние петли тривиальны. Их можно развернуть следующим образом:

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Так что остается два внешних цикла, которые нас интересуют.

Теперь мы видим, что проблема в этом вопросе та же: почему порядок циклов влияет на производительность при итерации по двумерному массиву?

Вы перебираете матрицу по столбцам, а не по строкам.


Чтобы решить эту проблему, вы должны поменять местами два цикла.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

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


Core i7 920 @ 3,5 ГГц

Оригинальный код:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Взаимозаменяемые внешние петли:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds
Mysticial
источник
217
Также отмечу, что развертывание внутренних циклов никак не влияет на производительность. Компилятор, вероятно, делает это автоматически. Я развернул их с единственной целью - избавиться от них, чтобы было легче обнаружить проблему с внешними петлями.
Мистик
29
И вы можете ускорить этот код еще в три раза, кэшируя суммы по каждой строке. Но эта и другие оптимизации выходят за рамки первоначального вопроса.
Эрик Постпишил
34
@ClickUpvote На самом деле это проблема аппаратного (кэширования). Это не имеет ничего общего с языком. Если вы попробуете это на любом другом языке, который компилирует или JIT в нативный код, вы, вероятно, увидите те же эффекты.
Мистик
19
@ClickUpvote: Вы, кажется, довольно ошибочны. Эта «вторая петля» была просто мистической, раскручивая внутренние петли вручную. Это то, что ваш компилятор почти наверняка сделает в любом случае, и Mystical сделал это только для того, чтобы сделать проблему с внешними циклами более очевидной. Это ни в коем случае не то, что вы должны заниматься самостоятельно.
Лили Баллард
154
Это прекрасный пример хорошего ответа на SO: ссылки на похожие вопросы, пошаговое объяснение того, как вы к нему подошли, объяснение проблемы, объяснение, как исправить проблему, отличное форматирование и даже пример выполнения кода на твоей машине. Спасибо за ваш вклад.
MattSayar
57

Следующие тесты были выполнены с компилятором Visual C ++, так как он используется при установке по умолчанию Qt Creator (я думаю, без флага оптимизации). При использовании GCC нет большой разницы между версией Mystical и моим «оптимизированным» кодом. Итак, вывод заключается в том, что оптимизация компилятора заботится о микрооптимизации лучше, чем люди (наконец-то я). Я оставляю остаток моего ответа для справки.


Неэффективно обрабатывать изображения таким образом. Лучше использовать одномерные массивы. Обработка всех пикселей выполняется за один цикл. Произвольный доступ к точкам может быть выполнен с использованием:

pointer + (x + y*width)*(sizeOfOnePixel)

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

Я сделал несколько тестов, и я думаю, что стоит поделиться. Каждый результат - в среднем пять тестов.

Оригинальный код от пользователя1615209:

8193: 4392 ms
8192: 9570 ms

Мистическая версия:

8193: 2393 ms
8192: 2190 ms

Два прохода с использованием одномерного массива: первый проход для горизонтальных сумм, второй для вертикальной суммы и среднего. Двухпроходная адресация с тремя указателями и только такими приращениями:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

Два прохода с использованием одномерного массива и адресации следующим образом:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

Горизонтальные кеширующие за один проход суммы всего на одну строку впереди, поэтому они остаются в кеше:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Вывод:

  • Нет пользы от использования нескольких указателей и просто приращений (я думал, что это было бы быстрее)
  • Кэшировать горизонтальные суммы лучше, чем вычислять их несколько раз.
  • Два прохода не в три раза быстрее, только в два раза.
  • Можно достичь в 3,6 раза быстрее, используя как один проход, так и кэшируя промежуточный результат

Я уверен, что можно сделать намного лучше.

ПРИМЕЧАНИЕ. Обратите внимание, что я написал этот ответ для решения общих проблем с производительностью, а не проблемы с кешем, описанной в превосходном ответе Mystical. В начале это был просто псевдокод. Меня попросили сделать тесты в комментариях ... Вот полностью переработанная версия с тестами.

bokan
источник
9
«Я думаю, что это по крайней мере в 3 раза быстрее» - хотите подкрепить это утверждение некоторыми показателями или цитатами?
Адам Розенфилд
8
@AdamRosenfield "Я думаю" = предположение! = "Это" = претензия. У меня нет метрики для этого, и я хотел бы увидеть тест. Но мой требует 7 приращений, 2 sub, 2 add и один div на пиксель. Каждый цикл использует меньше локальных переменных, чем регистр в CPU. Другие требуют 7 приращений, 6 приращений, 1 деление и от 10 до 20 муль для адресации в зависимости от оптимизации компилятора. Также каждая инструкция в цикле требует результата предыдущей инструкции, что исключает преимущества суперскалярной архитектуры Pentiums. Так должно быть быстрее.
Бокан
3
Ответ на оригинальный вопрос - все об эффектах памяти и кэша. Причина того, что код OP является настолько медленным, заключается в том, что его шаблон доступа к памяти идет по столбцам, а не по строкам, что имеет очень плохую привязку к кэш-памяти. Это особенно плохо в 8192, потому что тогда последовательные строки заканчивают тем, что используют те же самые строки кэша в кэше с прямым отображением или кэше с низкой ассоциативностью, таким образом, частота ошибок кэша еще выше. Чередование циклов обеспечивает огромный прирост производительности благодаря значительному увеличению локальности кэша.
Адам Розенфилд
1
Молодцы, это впечатляющие цифры. Как вы обнаружили, все дело в производительности памяти - использование нескольких указателей с приращениями не принесло никакой пользы.
Адам Розенфилд
2
@AdamRosenfield Я был очень обеспокоен этим утром, потому что я не мог воспроизвести тесты. Похоже, что повышение производительности происходит только с компилятором Visual C ++. Используя gcc, есть только небольшая разница.
Бокан