Оптимизация алгоритма на С, вопрос к знатокам компиляторов Опции

[singlskv]

Есть два варианта функции вычисления CRC:

Код

unsigned char code[8]={0x01,0xd0,0x5e,0x3c,0x0d,0x00,0x00,0x84};

unsigned char crc8_1(unsigned char *buff,unsigned char num)
{
    unsigned char i=0,j,tmp,data,crc=0;
    for (i=0;i<num;i++) {
        data=*buff++;
        for (j=0;j<8;j++) {
            tmp=1&(data^crc);
            crc>>=1;
            data>>=1;
            if (tmp!=0) crc^=0x8c;
        }
    }
    return crc;
}

unsigned char crc8_2(unsigned char *buff,unsigned char num)
{
    unsigned char i=num,j,tmp,data,crc=0;
    for (;i>0;i--) {
        data=*buff++;
        for (j=8;j>0;j--) {
            tmp=1&(data^crc);
            crc>>=1;
            data>>=1;
            if (tmp!=0) crc^=0x8c;
        }
    }
    return crc;
}

int main(int argc, char* argv[])
{
    unsigned char crc_;
    crc_=crc8_1(code,7);
    crc_=crc8_2(code,7);
    return 0;
}

Как видно из рисунка, это собственно один и тот же алгоритм.
Но, при компиляции под WinAVR(gcc), при любом уровне оптимизации, второй
вариант работает на 10-15% быстрее.
Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

[defunct]

Вы уверены что у вас считается именно CRC?
Попробуйте такой код:

Код

/**********************************************************
*   Функция РАСЧЕТА CRC8 (по полиному X8 + X5 + X2 + 1)  
* Оптимизация по объему требуемой памяти и по скорости
* ---> packet - массив данных                            
* ---> size - количество байт в пакете                  
* <--- результат расчитанной CRC8                        
**********************************************************/
U8 rtm_crc8(U8 *packet, U8 size)
{
#define h_byte (1)
#define l_byte (0)
typedef union _DummyUnion
{
  U16 word;
  U8  bytes[sizeof(U16)];
} DummyUnion;

  DummyUnion tempDivisor;
  DummyUnion tempData;
  U8 i;

  if (size < 2)
    return crc8_ERROR;

  tempData.bytes[h_byte] = *packet++;
  size -= 1;
  do
  {
    tempData.bytes[l_byte] = *packet++;
    tempDivisor.word = 0x9280;  // полином X8 + X5 + X2 + 1

    i = 0x80;
    do
    {
      if (i & tempData.bytes[h_byte])
      {
        tempData.word ^= tempDivisor.word;
      }
      tempDivisor.word >>=1;
      i >>= 1;
    } while (i);

    tempData.bytes[h_byte] = tempData.bytes[l_byte];
    size -= 1;
  } while (size);
  return tempData.bytes[h_byte];
}

[KRS]

конечно 2 вариант быстрее!
дело в организации цикла!
он скомпилируется по другому примерно так:

Код

  mov r16, 8
loop:
  .....
  .....
  dec r16
  brne loop

а 1 вариант подразумевает лишнюю команду сравнения

Код

  mov r16, 0
loop:
  .....
  .....
  inc r16
  cpi r16, 8
  brcs loop

а вообще для полной потимизации я пишу такие циклы так

Код

j=8;
do {
  ....
  ....
}while(--j);

[vet]

Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

IAR.

[Old1]

Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

IAR.

К сожалению нет времени проверять... Вы уверены, что IAR эти функции скомпилирует одинаково оптимально? Вопрос задаю потому, что сами ИАРовцы рекомендуют (AN AVR035) для оптимизации кода по возможности использовать вычитающие циклические счетчики и предварительный декремент.

[singlskv]

Вы уверены что у вас считается именно CRC?

Да уверен.
Это CRC для 1-wire по полиному X8+X5+X4+1.

конечно 2 вариант быстрее!
дело в организации цикла!

Ну в этом и вопрос, умеет ли какой-нибудь компилятор разбираться
с такой ситуацией.

Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

IAR.

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

К сожалению нет времени проверять... Вы уверены, что IAR эти функции скомпилирует одинаково оптимально? Вопрос задаю потому, что сами ИАРовцы рекомендуют (AN AVR035) для оптимизации кода по возможности использовать вычитающие циклические счетчики и предварительный декремент.

Собственно, если кто проверит, сообщите результат.

[vet]

Скомпилировал в IAR 4.11A два цикла for с инкрементом от 0 до 8 и декрементом от 8 до 0, макс.оптимизация по скорости. Код одинаков.

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 void main() {
main:
//    4 char i;

//    5   for (i=0;i<8;i++) {
        LDI    R16, 8
//    6     asm("nop");
??main_0:
        nop
//    7   }
        DEC    R16
        BRNE    ??main_0

//    8   for (i=8;i;i--) {
        LDI    R16, 8
//    9     asm("nop");
??main_1:
        nop
//   10   }
        DEC    R16
        BRNE    ??main_1

//   11 }
        RET

Выкладываю листинг компиляции вышеприведённого исходника:

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 unsigned char crc8_1(unsigned char *buff,unsigned char num)
crc8_1:
//    4 {
//    5     unsigned char i=0,j,tmp,data,crc=0;
        LDI    R21, 0
//    6     for (i=0;i<num;i++) {
        LDI    R20, 0
        RJMP    ??crc8_1_0
//    7         data=*buff++;
??crc8_1_1:
        MOVW    R31:R30, R17:R16
        LD    R23, Z+
        MOVW    R17:R16, R31:R30
//    8         for (j=0;j<8;j++) {
        LDI    R19, 8
//    9             tmp=1&(data^crc);
??crc8_1_2:
        MOV    R0, R23
        BST    R0, 0
        CLR    R0
        BLD    R0, 0
        MOV    R22, R21
        ANDI    R22, 0x01
        EOR    R22, R0
        ANDI    R22, 0x01
//   10             crc>>=1;
        LSR    R21
//   11             data>>=1;
        LSR    R23
//   12             if (tmp!=0) crc^=0x8c;
        TST    R22
        BREQ    ??crc8_1_3
        LDI    R22, 140
        EOR    R21, R22
//   13         }
??crc8_1_3:
        DEC    R19
        BRNE    ??crc8_1_2
//   14     }
        INC    R20
??crc8_1_0:
        CP    R20, R18
        BRCS    ??crc8_1_1
//   15     return crc;
        MOV    R16, R21
        RET
//   16 }
//   17

        RSEG CODE:CODE:NOROOT(1)
//   18 unsigned char crc8_2(unsigned char *buff,unsigned char num)
crc8_2:
//   19 {
//   20     unsigned char i=num,j,tmp,data,crc=0;
        MOV    R19, R18
        LDI    R20, 0
        RJMP    ??crc8_2_0
//   21     for (;i>0;i--) {
//   22         data=*buff++;
??crc8_2_1:
        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30
//   23         for (j=8;j>0;j--) {
        LDI    R18, 8
//   24             tmp=1&(data^crc);
??crc8_2_2:
        MOV    R23, R22
        ANDI    R23, 0x01
        MOV    R21, R20
        ANDI    R21, 0x01
        EOR    R21, R23
        ANDI    R21, 0x01
//   25             crc>>=1;
        LSR    R20
//   26             data>>=1;
        LSR    R22
//   27             if (tmp!=0) crc^=0x8c;
        TST    R21
        BREQ    ??crc8_2_3
        LDI    R21, 140
        EOR    R20, R21
//   28         }
??crc8_2_3:
        DEC    R18
        BRNE    ??crc8_2_2
//   29     }
        DEC    R19
??crc8_2_0:
        TST    R19
        BRNE    ??crc8_2_1
//   30     return crc;
        MOV    R16, R20
        RET
//   31 }
//   32

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

Сообщение отредактировал vet - Aug 24 2006, 10:37

[µµC]

Да уверен.
Это CRC для 1-wire по полиному X8+X5+X4+1.

Код

U8 CRC8_1 (U8 val, U8 crc)
{
  U8 tmp;
  U8 i = 8;
  do {
    tmp = (val ^ crc) & 0x01;
    crc >>= 1;
    val >>= 1;
    if (tmp != 0) crc ^= 0x8c;
  } while (--i);
  return crc;
}

U8 CRC8_2(U8 data, U8 crc)
{
  U8 i = data ^ crc;
  crc = 0;
  if (i & 0x01) crc ^= 0x5e;
  if (i & 0x02) crc ^= 0xbc;
  if (i & 0x04) crc ^= 0x61;
  if (i & 0x08) crc ^= 0xc2;
  if (i & 0x10) crc ^= 0x9d;
  if (i & 0x20) crc ^= 0x23;
  if (i & 0x40) crc ^= 0x46;
  if (i & 0x80) crc ^= 0x8c;
  return crc;
}

CRC8_1 это твой вариант для одного байта. CRC8_2 имеет тот же полином, но работает значительно быстрее.

Сообщение отредактировал µµC - Aug 24 2006, 12:43

[Old1]

Скомпилировал в IAR 4.11A два цикла for с инкрементом от 0 до 8 и декрементом от 8 до 0, макс.оптимизация по скорости. Код одинаков.
...

Но если поставить оптимизацию по объему кода, то появляется тот эффект о котором писал автор, функция с циклом с декрементом выполняется быстрее. (Я обычно использую оптимизацию по объему, и когда спрашивал упустил, что автора интересует максимальная скорость.)

[µµC]

Но если поставить оптимизацию по объему кода, то появляется тот эффект о котором писал автор, функция с циклом с декрементом выполняется быстрее.

Человек явно ищет идеальный компилятор, а их, как известно, в природе не бывает. От программиста требуется хорошо знать какой будет код в какой ситуации, "чувствовать селезенкой", "заставлять" компилятор быть эффективным. Например:

Код

U8 CRC8_1 (U8 val, U8 crc)
{
  U8 tmp;
  U8 i = 8;
  do {
    tmp = (val ^ crc) & 0x01;
    crc >>= 1;
    val >>= 1;
    if (tmp != 0) crc ^= 0x8c;
  } while (--i);
  return crc;
}

U8 CRC8_1 (U8 val, U8 crc)
{
  U8 tmp;
  U8 i = 8;
  do {
    tmp = (val ^ crc);
    crc >>= 1;
    val >>= 1;
    if (tmp & 0x01) crc ^= 0x8c;
  } while (--i);
  return crc;
}

154 цикла к 122. А, казалось бы, от перемены мест ...

[singlskv]

Скомпилировал в IAR 4.11A два цикла for с инкрементом от 0 до 8 и декрементом от 8 до 0, макс.оптимизация по скорости. Код одинаков.

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 void main() {
main:
//    4 char i;

//    5   for (i=0;i<8;i++) {
        LDI    R16, 8
   ..............................................................

Вы попробуйте два вложенных цикла, как в моем примере,
да и еще что нибудь кроме nop вставте в середину.

Выкладываю листинг компиляции вышеприведённого исходника:

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 unsigned char crc8_1(unsigned char *buff,unsigned char num)
crc8_1:
//    4 {
//    5     unsigned char i=0,j,tmp,data,crc=0;
        LDI    R21, 0
//    6     for (i=0;i<num;i++) {
        LDI    R20, 0
        RJMP    ??crc8_1_0
//    7         data=*buff++;
??crc8_1_1:
        MOVW    R31:R30, R17:R16
        LD    R23, Z+
        MOVW    R17:R16, R31:R30
//    8         for (j=0;j<8;j++) {
        LDI    R19, 8
//    9             tmp=1&(data^crc);
??crc8_1_2:
        MOV    R0, R23
        BST    R0, 0
        CLR    R0
        BLD    R0, 0
        MOV    R22, R21
        ANDI    R22, 0x01
        EOR    R22, R0
        ANDI    R22, 0x01
//   10             crc>>=1;
        LSR    R21
//   11             data>>=1;
        LSR    R23
//   12             if (tmp!=0) crc^=0x8c;
        TST    R22
        BREQ    ??crc8_1_3
        LDI    R22, 140
        EOR    R21, R22
//   13         }
??crc8_1_3:
        DEC    R19
        BRNE    ??crc8_1_2
//   14     }
        INC    R20
??crc8_1_0:
        CP    R20, R18
        BRCS    ??crc8_1_1
//   15     return crc;
        MOV    R16, R21
        RET
//   16 }
//   17

        RSEG CODE:CODE:NOROOT(1)
//   18 unsigned char crc8_2(unsigned char *buff,unsigned char num)
crc8_2:
//   19 {
//   20     unsigned char i=num,j,tmp,data,crc=0;
        MOV    R19, R18
        LDI    R20, 0
        RJMP    ??crc8_2_0
//   21     for (;i>0;i--) {
//   22         data=*buff++;
??crc8_2_1:
        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30
//   23         for (j=8;j>0;j--) {
        LDI    R18, 8
//   24             tmp=1&(data^crc);
??crc8_2_2:
        MOV    R23, R22
        ANDI    R23, 0x01
        MOV    R21, R20
        ANDI    R21, 0x01
        EOR    R21, R23
        ANDI    R21, 0x01
//   25             crc>>=1;
        LSR    R20
//   26             data>>=1;
        LSR    R22
//   27             if (tmp!=0) crc^=0x8c;
        TST    R21
        BREQ    ??crc8_2_3
        LDI    R21, 140
        EOR    R20, R21
//   28         }
??crc8_2_3:
        DEC    R18
        BRNE    ??crc8_2_2
//   29     }
        DEC    R19
??crc8_2_0:
        TST    R19
        BRNE    ??crc8_2_1
//   30     return crc;
        MOV    R16, R20
        RET
//   31 }
//   32

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

Просимулировал Ваш код в AVR Studio.
Итого: (для семи байт)
crc8_1 986 тактов
crc8_2 774 такта
разница слегка удивила, это уже 25%.

очень повеселил этот код:

Код

        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30

и так 7 раз подряд

[singlskv]

Да уверен.
Это CRC для 1-wire по полиному X8+X5+X4+1.

Код

U8 CRC8_1 (U8 val, U8 crc)
{
  U8 tmp;
  U8 i = 8;
  do {
    tmp = (val ^ crc) & 0x01;
    crc >>= 1;
    val >>= 1;
    if (tmp != 0) crc ^= 0x8c;
  } while (--i);
  return crc;
}

U8 CRC8_2(U8 data, U8 crc)
{
  U8 i = data ^ crc;
  crc = 0;
  if (i & 0x01) crc ^= 0x5e;
  if (i & 0x02) crc ^= 0xbc;
  if (i & 0x04) crc ^= 0x61;
  if (i & 0x08) crc ^= 0xc2;
  if (i & 0x10) crc ^= 0x9d;
  if (i & 0x20) crc ^= 0x23;
  if (i & 0x40) crc ^= 0x46;
  if (i & 0x80) crc ^= 0x8c;
  return crc;
}

CRC8_1 это твой вариант для одного байта. CRC8_2 имеет тот же полином, но работает значительно быстрее.

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

[µµC]

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

Код

#define U8 unsigned char

U8 code[8] = {0x01, 0xd0, 0x5e, 0x3c, 0x0d, 0x00, 0x00, 0x84};

U8 crc8_1(U8 *buff, U8 num)
{
  U8 i, tmp, val, crc = 0;
  
  do {
    val = *buff++;
    i = 8;
    do {
      tmp = (val ^ crc);
      crc >>= 1;
      val >>= 1;
      if (tmp & 0x01) crc ^= 0x8c;
    } while (--i);      
  } while (--num);
  return crc;
}

U8 crc8_2(U8 *buff, U8 num)
{
  U8 val, crc = 0;
  
  do {
    val = *buff++;
    val ^= crc;
    crc = 0;
    if(val & 0x01) crc ^= 0x5e;
    if(val & 0x02) crc ^= 0xbc;
    if(val & 0x04) crc ^= 0x61;
    if(val & 0x08) crc ^= 0xc2;
    if(val & 0x10) crc ^= 0x9d;
    if(val & 0x20) crc ^= 0x23;
    if(val & 0x40) crc ^= 0x46;
    if(val & 0x80) crc ^= 0x8c;    
  } while (--num);
  return crc;
}

volatile U8 result[4];

void main(void)
{
   while (1) {
    result[0] = crc8_1(code, 7); //649
    result[1] = crc8_2(code, 7); //265
    result[2] = crc8_1(code, 7);
    result[3] = crc8_2(code, 7);
   }
}

IAR, opt = max speed, остальные опции выкл.

649 циклов к 265.

[singlskv]

Человек явно ищет идеальный компилятор, а их, как известно, в природе не бывает.

Лучший компилятор это человек.
на ASM у меня получилось 530 тактов:

Код

crc8:    ;Input: X - buffer; r17 - number of bytes    
    ;Output: r16 = CRC

    ldi    r16,0    ;CRC
    ldi    r20,0x8c
crc8_1:
    ld    r18,X+
    ldi    r19,8
crc8_2:
    lsr    r16
    brbc    0,crc8_3
    eor    r16,r20
crc8_3:
    sbrc    r18,0
    eor    r16,r20
    lsr    r18
crc8_4:
    dec    r19
    brne    crc8_2
    dec    r17
    brne    crc8_1

    ret

НО, надо отдать должное WinAVR(gcc)

ИТОГО:

Код

                    CRC8_1    CRC8_2
WinAVR(-o1)        620           556
WinAVR(-o2)        620           556
WinAVR(-o3)        606           544

IAR                986           774

ASM                       530

У WinAVR(-o3) удалось украсть всего 14 тактов, то есть по 2 такта на основной цикл.
Приятно удививший результат

А с IAR просто какая-то лабудень, возможно Вы vet там чего-то не то указали при
оптимизации?

[µµC]

Лучший компилятор это человек.

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