Почему этот код неэффективен? - PullRequest
0 голосов
/ 15 декабря 2011

Я хочу улучшить следующий код, вычисляя среднее значение:

void calculateMeanStDev8x8Aux(cv::Mat* patch, int sx, int sy, int& mean, float& stdev)
{

    unsigned sum=0;
    unsigned sqsum=0;
    const unsigned char* aux=patch->data + sy*patch->step + sx;
    for (int j=0; j< 8; j++) {
        const unsigned char* p = (const unsigned char*)(j*patch->step + aux ); //Apuntador al inicio de la matrix           

        for (int i=0; i<8; i++) {
            unsigned f = *p++;
            sum += f;
            sqsum += f*f;
        }           
    }       

    mean = sum >> 6;
    int r = (sum*sum) >> 6;
    stdev = sqrtf(sqsum - r);

    if (stdev < .1) {
        stdev=0;
    }
}

Я также улучшил следующий цикл с присущим NEON:

 for (int i=0; i<8; i++) {
            unsigned f = *p++;
            sum += f;
            sqsum += f*f;
        }

Это код, улучшенный для другого цикла:

        int32x4_t vsum= { 0 };
        int32x4_t vsum2= { 0 };

        int32x4_t vsumll = { 0 };
        int32x4_t vsumlh = { 0 };
        int32x4_t vsumll2 = { 0 };
        int32x4_t vsumlh2 = { 0 };

        uint8x8_t  f= vld1_u8(p); // VLD1.8 {d0}, [r0]

        //int 16 bytes /8 elementos
        int16x8_t val =  (int16x8_t)vmovl_u8(f);

        //int 32 /4 elementos *2 
        int32x4_t vall = vmovl_s16(vget_low_s16(val));
        int32x4_t valh = vmovl_s16(vget_high_s16(val));

        // update 4 partial sum of products vectors

        vsumll2 = vmlaq_s32(vsumll2, vall, vall);
        vsumlh2 = vmlaq_s32(vsumlh2, valh, valh);

        // sum 4 partial sum of product vectors
        vsum = vaddq_s32(vall, valh);
        vsum2 = vaddq_s32(vsumll2, vsumlh2);

        // do scalar horizontal sum across final vector

        sum += vgetq_lane_s32(vsum, 0);
        sum += vgetq_lane_s32(vsum, 1);
        sum += vgetq_lane_s32(vsum, 2);
        sum += vgetq_lane_s32(vsum, 3);

        sqsum += vgetq_lane_s32(vsum2, 0);
        sqsum += vgetq_lane_s32(vsum2, 1);
        sqsum += vgetq_lane_s32(vsum2, 2);
        sqsum += vgetq_lane_s32(vsum2, 3);

Но это более или менее на 30 мс медленнее. Кто-нибудь знает почему?

Весь код работает правильно.

Ответы [ 4 ]

3 голосов
/ 15 декабря 2011

Добавить в Лундин. Да, наборы инструкций, такие как ARM, где у вас есть индекс на основе регистра или некоторые из них с непосредственным индексом, могут помочь поощрению компилятора использовать индексирование. Кроме того, хотя ARM, например, может увеличивать свой регистр указателя в инструкции загрузки, в основном * p ++ в одной инструкции.

это всегда бросок с использованием p [i] или p [i ++] vs * p или * p ++, некоторые наборы команд намного более очевидны, какой путь выбрать.

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

inc reg
cmp reg,#7
bne loop_top

Если вы ведете обратный отсчет, вы можете сохранить инструкцию для цикла:

dec reg
bne loop_top

или даже один процессор, который я знаю

decrement_and_jump_if_not_zero  loop_top

Компиляторы обычно знают это, и вам не нужно их поощрять. НО, если вы используете форму p [i], где важен порядок чтения из памяти, компилятор не может или, по крайней мере, не должен произвольно изменять порядок чтения. Так что для этого случая вы хотели бы иметь обратный отсчет кода.

Итак, я попробовал все эти вещи:

unsigned fun1 ( const unsigned char *p, unsigned *x )
{
    unsigned sum;
    unsigned sqsum;
    int i;
    unsigned f;


    sum = 0;
    sqsum = 0;
    for(i=0; i<8; i++)
    {
        f = *p++;
        sum += f;
        sqsum += f*f;
    }
    //to keep the compiler from optimizing
    //stuff out
    x[0]=sum;
    return(sqsum);
}

unsigned fun2 ( const unsigned char *p, unsigned *x  )
{
    unsigned sum;
    unsigned sqsum;
    int i;
    unsigned f;


    sum = 0;
    sqsum = 0;
    for(i=8;i--;)
    {
        f = *p++;
        sum += f;
        sqsum += f*f;
    }
    //to keep the compiler from optimizing
    //stuff out
    x[0]=sum;
    return(sqsum);
}

unsigned fun3 ( const unsigned char *p, unsigned *x )
{
    unsigned sum;
    unsigned sqsum;
    int i;

    sum = 0;
    sqsum = 0;
    for(i=0; i<8; i++)
    {
        sum += (unsigned)p[i];
        sqsum += ((unsigned)p[i])*((unsigned)p[i]);
    }
    //to keep the compiler from optimizing
    //stuff out
    x[0]=sum;
    return(sqsum);
}

unsigned fun4 ( const unsigned char *p, unsigned *x )
{
    unsigned sum;
    unsigned sqsum;
    int i;

    sum = 0;
    sqsum = 0;
    for(i=8; i;i--)
    {
        sum += (unsigned)p[i-1];
        sqsum += ((unsigned)p[i-1])*((unsigned)p[i-1]);
    }
    //to keep the compiler from optimizing
    //stuff out
    x[0]=sum;
    return(sqsum);
}

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

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

00000000 <fun1>:
   0:   e92d05f0    push    {r4, r5, r6, r7, r8, sl}
   4:   e5d06001    ldrb    r6, [r0, #1]
   8:   e00a0696    mul sl, r6, r6
   c:   e4d07001    ldrb    r7, [r0], #1
  10:   e02aa797    mla sl, r7, r7, sl
  14:   e5d05001    ldrb    r5, [r0, #1]
  18:   e02aa595    mla sl, r5, r5, sl
  1c:   e5d04002    ldrb    r4, [r0, #2]
  20:   e02aa494    mla sl, r4, r4, sl
  24:   e5d0c003    ldrb    ip, [r0, #3]
  28:   e02aac9c    mla sl, ip, ip, sl
  2c:   e5d02004    ldrb    r2, [r0, #4]
  30:   e02aa292    mla sl, r2, r2, sl
  34:   e5d03005    ldrb    r3, [r0, #5]
  38:   e02aa393    mla sl, r3, r3, sl
  3c:   e0876006    add r6, r7, r6
  40:   e0865005    add r5, r6, r5
  44:   e0854004    add r4, r5, r4
  48:   e5d00006    ldrb    r0, [r0, #6]
  4c:   e084c00c    add ip, r4, ip
  50:   e08c2002    add r2, ip, r2
  54:   e082c003    add ip, r2, r3
  58:   e023a090    mla r3, r0, r0, sl
  5c:   e080200c    add r2, r0, ip
  60:   e5812000    str r2, [r1]
  64:   e1a00003    mov r0, r3
  68:   e8bd05f0    pop {r4, r5, r6, r7, r8, sl}
  6c:   e12fff1e    bx  lr

индекс для нагрузок и тонкого смешивания регистров был единственным отличием функций от gcc, все операции были одинаковыми в одном и том же порядке.

LLVM / лязг:

00000000 <fun1>:
   0:   e92d41f0    push    {r4, r5, r6, r7, r8, lr}
   4:   e5d0e000    ldrb    lr, [r0]
   8:   e5d0c001    ldrb    ip, [r0, #1]
   c:   e5d03002    ldrb    r3, [r0, #2]
  10:   e5d08003    ldrb    r8, [r0, #3]
  14:   e5d04004    ldrb    r4, [r0, #4]
  18:   e5d05005    ldrb    r5, [r0, #5]
  1c:   e5d06006    ldrb    r6, [r0, #6]
  20:   e5d07007    ldrb    r7, [r0, #7]
  24:   e08c200e    add r2, ip, lr
  28:   e0832002    add r2, r3, r2
  2c:   e0882002    add r2, r8, r2
  30:   e0842002    add r2, r4, r2
  34:   e0852002    add r2, r5, r2
  38:   e0862002    add r2, r6, r2
  3c:   e0870002    add r0, r7, r2
  40:   e5810000    str r0, [r1]
  44:   e0010e9e    mul r1, lr, lr
  48:   e0201c9c    mla r0, ip, ip, r1
  4c:   e0210393    mla r1, r3, r3, r0
  50:   e0201898    mla r0, r8, r8, r1
  54:   e0210494    mla r1, r4, r4, r0
  58:   e0201595    mla r0, r5, r5, r1
  5c:   e0210696    mla r1, r6, r6, r0
  60:   e0201797    mla r0, r7, r7, r1
  64:   e8bd41f0    pop {r4, r5, r6, r7, r8, lr}
  68:   e1a0f00e    mov pc, lr

намного проще для чтения и отслеживания, возможно, думая о кеше и получая чтение всего за один раз. По крайней мере, в одном случае показания считывались не по порядку.

00000144 <fun4>:
 144:   e92d40f0    push    {r4, r5, r6, r7, lr}
 148:   e5d0c007    ldrb    ip, [r0, #7]
 14c:   e5d03006    ldrb    r3, [r0, #6]
 150:   e5d02005    ldrb    r2, [r0, #5]
 154:   e5d05004    ldrb    r5, [r0, #4]
 158:   e5d0e000    ldrb    lr, [r0]
 15c:   e5d04001    ldrb    r4, [r0, #1]
 160:   e5d06002    ldrb    r6, [r0, #2]
 164:   e5d00003    ldrb    r0, [r0, #3]

Да, для усреднения некоторых значений из ОЗУ порядок не является проблемой, двигаясь дальше.

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

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

  a4:   e4d35001    ldrb    r5, [r3], #1

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

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

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

const unsigned char* p = (const unsigned char*)(j*patch->step + aux );

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

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

1 голос
/ 15 декабря 2011

Поскольку ваши данные считываются группами по 8 байт, в зависимости от аппаратной шины и выравнивания самого массива, вы, вероятно, можете получить некоторые выгоды, читая внутренний цикл через одно длинное длинное чтение, а затем либо разделение чисел вручную на отдельные значения или использование встроенных функций ARM для параллельного добавления некоторого встроенного ассемблера с помощью инструкции add8 (добавление 4 чисел одновременно в 1 регистр) или внесение изменений и использование add16, чтобы разрешить значения для переполнения в 16-битное пространство. Существует также команда умножения и накопления с двойной подписью, благодаря которой ваш первый цикл накопления практически безупречно поддерживается с помощью ARM. Кроме того, если поступающие данные могут быть преобразованы в 16-битные значения, это также может ускорить это.

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

1 голос
/ 15 декабря 2011

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

Некоторые комментарии относительно эффективности и подозрительных типов переменных:

unsigned f = *p++; Вам, вероятно, будет лучше, если вы получите доступ к p через индексирование массива, а затем используете p [i] для доступа к данным. Это сильно зависит от компилятора, оптимизации кэш-памяти и т. Д. (Некоторые гуру ARM могут дать мне лучший совет в этом вопросе).

Кстати, весь const char в int выглядит крайне подозрительно. Я так понимаю, эти символы должны рассматриваться как 8-битные целые числа без знака? Стандартный C uint8_t, вероятно, является лучшим типом для этого, char имеет различные неопределенные проблемы подписи, которых вы хотите избежать.

Кроме того, почему вы делаете дикое смешивание unsigned и int? Вы запрашиваете неявные ошибки целочисленной балансировки.

stdev < .1. Просто незначительная вещь: измените это на .1f, или вы заставите неявное повышение вашего числа с плавающей запятой удвоиться, так как .1 - двойной литерал.

0 голосов
/ 16 декабря 2011

Спасибо Лундину, Двелчу и Мишелю. Я сделал следующее улучшение, и оно кажется лучшим для моего кода. Я пытаюсь уменьшить количество циклов, улучшающих доступ к кешу, поскольку доступ к кешу осуществляется только один раз.

int step=patch->step;
 for (int j=0; j< 8; j++) {
        p = (uint8_t*)(j*step + aux ); /

        i=8;
        do {                
            f=p[i];
            sum += f;
            sqsum += f*f;

        } while(--i);

}
...