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

[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% быстрее.
Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

[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

[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]

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

Лучший компилятор это человек.
на 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]

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

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

[zltigo]

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

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

и 'ломается' на больших кусках кода :-(

в общем виде (таблицой из 256 значений как в даташите "1-wire" все равно быстрее).

Быстрее :-) сопроцессор поставить....

Код

//---------------------------------------------------------------------------
// Verilog module containing a synthesizable CRC8 function
//   - Polynomial: (8 5 4 0)
//   - Data width: 8
//   - CRC width : 8
//   - Mirror
//---------------------------------------------------------------------------
module CRC8_8540;

  function [7:0] nextCRC;

    input [7:0] Data;
    input [7:0] CRC;

    reg [7:0] D;
    reg [7:0] C;
    reg [7:0] xCRC;


      begin

    D = Data;
    C = CRC;

    // Mirror DATA and final CRC
    xCRC[7] = D[1]^D[3]^D[4]^D[7]^C[7]^C[4]^C[3]^C[1];
    xCRC[6] = D[0]^D[2]^D[3]^D[6]^C[6]^C[3]^C[2]^C[0];
    xCRC[5] = D[1]^D[2]^D[5]^C[5]^C[2]^C[1];
    xCRC[4] = D[0]^D[1]^D[4]^C[4]^C[1]^C[0];
    xCRC[3] = D[0]^D[1]^D[4]^D[7]^C[7]^C[4]^C[1]^C[0];
    xCRC[2] = D[0]^D[1]^D[4]^D[6]^D[7]^C[7]^C[6]^C[4]^C[1]^C[0];
    xCRC[1] = D[0]^D[3]^D[5]^D[6]^C[6]^C[5]^C[3]^C[0];
    xCRC[0] = D[2]^D[4]^D[5]^C[5]^C[4]^C[2];

    nextCRC = xCRC;

      end

  endfunction

endmodule

Извините :-( Настроение сегодня такое :-).
А верилоговский код рабочий под Dallas - вдруг кому пригодится. Использую я его, поскольку полином хорош для любых небольших пакетов.