Что является самым быстрым для цикла в с?

Question

Я пытаюсь написать оптимизированный код для доступа к пикселям изображения, и мне нужно сделать цикл for очень быстрым, не опускаясь до уровня сборки.Более того, индексация выполняется по строкам, чтобы минимизировать потери в кеше.

Вот что у меня есть:

for (indr=0;indr<(height-1)*width;indr+=width) {
        for (indc=0;indc<width;indc++){
            I[indr+indc]= dostuff ;
        }
    }

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

Есть ли более быстрый способ сделать это?

EDIT Хорошо, потому что мой предыдущий пост был немного неясным, я добавляю сюда полный код,Это довольно нечитаемо, но общая идея заключается в том, что я выполняю свертку с простой коробкой, используя целостное изображение.Изображение сначала дополняется нулями ws + 1 слева и снизу и нулями ws справа и сверху.Затем он превращается в цельное изображение Ii.Следующая функция берет целое изображение и извлекает свертку, где результат Ic имеет тот же размер, что и исходное изображение.

void convI(float *Ic,float *Ii,int ws, int width, int height)
{
    int W=width+ws*2+1,indR;
    int H=height+ws*2+1,indC;
    int w=width, indr;
    int h=height, indc;
    int jmpA=W*(ws+1),jmpC=W*ws,jmpB=ws+1,jmpD=ws;

    for (indR=W*(ws+1),indr=0;indr<width*(height-1);indR+=W,indr+=width) {
        for (indC=ws+1,indc=0;indc<width;indC++,indc++){
            //Performs I[indA]+I[indD]-I[indB]-I[indC];
            Ic[indr+indc]=
            Ii[indR-jmpA+indC-jmpB]+
            Ii[indR+jmpC+indC+jmpD]-
            Ii[indR+jmpC+indC-jmpB]-
            Ii[indR-jmpA+indC+jmpD];
        }
    }
}

Так что это часть "dostuff".Петля вялая.

Answer 1

Нет особых причин, по которым другой код мог бы привести к более высокой производительности, чем тот, который вы дали, если у вас все уровни оптимизации включены.

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

Редактировать: После того, как вы показали внутреннюю часть вашего цикла.

Есть немногоНебольшой потенциал размещения выражений ваших вычислений индекса как можно больше вне циклов.Поскольку он смешан с переменными цикла, его, вероятно, нельзя оптимизировать, как следует.(Или просто измените порядок вычислений индексов так, чтобы компилятор мог их видеть и как можно больше вычислять.)

Скорее всего, трудности с производительностью связаны с доступом к вашим векторам.Если вам удастся лучше вычислить ваши индексы, это также может улучшиться, потому что компилятор / система фактически увидит, что вы обращаетесь к своим векторам в обычном порядке.

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

Answer 2

Вы можете развернуть самый внутренний цикл. Вы потеряете читабельность, но кэш процессора и очередь предварительной выборки будут работать лучше. Хотя это всегда так, я не знаю, сколько скорости вы наберете. Вы можете объявить indc и indr как переменные регистра и попытаться избежать пересчета (height-1)*width, вместо этого сохранить его во временной переменной. Вы знаете, умножения съедают много тактов ...

Answer 3

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

В зависимости от того, что на самом деле делает dostuff, вы можете найти некоторую выгоду в кэшировании I[indr+indc] во временном, так что ваш код будет выглядеть примерно так ...

char t = I[indr+indc];
// do stuff
I[indr+indc] = t;

Этот код не будет работать хуже (я полагаю, у вас по крайней мере включены основные оптимизации), но он может работать лучше, если ваш do stuff достаточно причудливый (я могу уточнить, если хотите).

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

Answer 4

Если вы не хотите использовать векторизованные инструкции, например SSE, мало что можно сделать.

Answer 5

Производительность

// DragonLord style:
float *ic_p = I + (width * height) - 1;  // fencepost  
// Start at the end, and work backwards 
// assumes I is 0-based and wraps, is contiguous

for (indr=(height -1) * width; indr>=0; indr-=width ) {
// Sadly cannot test on indr -= width here
// as the 0 pass is needed for the loop
        for (indc=width; indc--; ){
        // Testing on postdecrement
        // allows you to use the 0 value one last time before testing it FTW
            // indr and indc are both 0-based inside the loop for you
            // e.g. indc varies from (width-1) down to 0
            // due to postdecrement before usage
            printf( "I[ %d + %d ] == %f \n", indr, indc, *ic_p );
            // always use pointers in C/C++ for speed, we are not Java
            *ic_p-- = dostuff ;
        }
    }

может быть немного улучшена путем обратного отсчета от высоты до 0, если вам не нужно использовать indr внутри цикла, или предкрементацию вместо постдекрементации indc, если вы можете обойтись с помощью indc на основе 1, вв каком случае indc должен инициализироваться в (ширина +1):

   for (indc=(width+1); --indc; ){

Answer 6

МОЖЕТ быть победа в подъеме height-1 во внешнем цикле до назначения перед циклом. Но тогда я подозреваю, что обычный компилятор в наши дни сделал бы это как стандартную оптимизацию. Может также случиться так, что при наличии другого указателя, установленного на I [indr], а затем индексация, что может быть небольшим выигрышем.

Оба из них потребуют довольно тщательного тестирования, чтобы заметить.