Я пытаюсь оптимизировать этот код C, используя 4-х стороннее развертывание цикла

Question

То, что я пытаюсь сделать, это взять этот код C и оптимизировать его, используя технику, называемую развертывание цикла, но в этом случае я хочу использовать развертывание с четырьмя путями. Теперь я понимаю технику и понимаю концепцию, я просто не знаю, как применить ее к этому коду. Должен ли я добавить некоторые дополнительные переменные? Должен ли я иметь некоторый код после каждого цикла или только в конце всех циклов? Этот код представляет собой блочный код 8x8, предназначенный для взятия пикселей и поворота их на 90 градусов против часовой стрелки. Любая помощь будет принята с благодарностью. Спасибо.

/* 
 * rotate8 - rotate with 8x8 blocking
 */

char rotate8_descr[] = "rotate8: rotate with 8x8 blocking";

void rotate8(int dim, pixel *src, pixel *dst) 
{

int i, j, ii, jj;

for(ii = 0; ii < dim; ii += 8)
       for(jj = 0; jj < dim; jj += 8)
              for (i = ii; i < ii + 8; i++)   
                  for (j = jj; j < jj + 8; j++)
                      dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}

Answer 1

Вы можете заменить внутренний цикл на 8 явных строк кода

          dst[RIDX(dim-1-jj, i, dim)] = src[RIDX(i, jj, dim)];
          dst[RIDX(dim-1-(jj+1), i, dim)] = src[RIDX(i, (jj+1), dim)];
          ...
          dst[RIDX(dim-1-(jj+7), i, dim)] = src[RIDX(i, (jj+7), dim)];

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

Теперь вы можете повторить, что для 8 значений следующего цикла у вас будет 8 x 8 строк кода и т. Д.

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

Answer 2

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

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

Вот моя самая быстрая версия с отступом, чтобы показать, чем она отличается от вашей версии. Макрос RIDX предполагается таким, как определено.

#define RIDX(x,y,d) (x+(y)*(d))
typedef unsigned char pixel;
void rotate8(int dim, pixel *src, pixel *dst)
{
    int i, j, ii, jj;
        for(jj = 0; jj < dim; jj += 8)
    for(ii = 0; ii < dim; ii += 8)
              for (i = ii; i < ii + 8; i++)
                  for (j = jj; j < jj + 8; j++)
                      dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}

... извлеченный урок: Всегда в профиле: -)

Answer 3

gcc -funrull-loops

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

Этот пример кода у вас выглядит как идеальный кандидат на автоматическое развертывание цикла.

Некоторые другие полезные флаги:

-O3                          // turns on a lot of optimizations (almost all)
-ftree-vectorize -msse2      // vectorizes automatically some loops

Answer 4

http://www.relisoft.com/book/lang/pointer/2ptrarr.html

Если ваш компилятор не может оптимизировать удобочитаемую, поддерживаемую версию алгоритма, и вам нужно работать как человеческий компилятор - купите новый компилятор! Никто больше не может позволить себе человеческие компиляторы. Так что помилуйте себя и своих коллег-программистов, которым придется взглянуть на ваш код.