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

[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 там чего-то не то указали при
оптимизации?

[_Bill]

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

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

Вся проблема в том, что компилятор использует определенные соглашения по передаче параметров и использованию регистров. Ваша функция под соглашения, принятые, например, в IAR, не попадает. Для стыковки с Си-шными функциями ее потребуется изменить с принятыми в компиляторе соглашениями. А это приведет к увеличению и размера кода, и увеличением времени его выполнения.

Сообщение отредактировал _Bill - Aug 25 2006, 11:33

[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 там чего-то не то указали при
оптимизации?

Вся проблема в том, что компилятор использует определенные соглашения по передаче параметров и использованию регистров. Ваша функция под соглашения, принятые, например, в IAR, не попадает. Для стыковки с Си-шными функциями ее потребуется изменить с принятыми в компиляторе соглашениями. А это приведет к увеличению и размера кода, и увеличением времени его выполнения.

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

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

Вся проблема в том, что компилятор использует определенные соглашения по передаче параметров и использованию регистров. Ваша функция под соглашения, принятые, например, в IAR, не попадает. Для стыковки с Си-шными функциями ее потребуется изменить с принятыми в компиляторе соглашениями. А это приведет к увеличению и размера кода, и увеличением времени его выполнения.

такты я считал по возможности честно, т.е. не учитывая такты потраченные на передачу
параметров.
А мой ASM код можно легко переписать под нужные регистры.
Да и разница в тактах что-то великовата, что бы ее объяснять только передачей
параметров.

Сообщение отредактировал singlskv - Aug 25 2006, 11:39

[_Bill]

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

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

[singlskv]

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

В свое время я написал небольшой опус на эту тему. К сожалению, он и сейчас далек от завершения.

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

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

Вот код для IAR (если я ничего не напутал):

Код

crc8iar:            ;Input: r17:r16 buffer; r18 - number of bytes    
                    ;Output: r16 = CRC

        movw    r31:r30,r17:r16
        ldi        r16,0            ;CRC
        ldi        r19,0x8c
crc8iar_1:
        ld        r20,Z+
        ldi        r21,8
crc8iar_2:
        lsr        r16
        brbc    0,crc8iar_3
        eor        r16,r19
crc8iar_3:
        sbrc    r20,0
        eor        r16,r19
        lsr        r20
crc8iar_4:
        dec        r21
        brne    crc8iar_2
        dec        r18
        brne    crc8iar_1

        ret

Добавилась всего одна инструкция:

Код

        movw    r31:r30,r17:r16

[_Bill]

Вот код для IAR (если я ничего не напутал):

Код

crc8iar:;Input: r17:r16 buffer; r18 - number of bytes    
        ;Output: r16 = CRC

        movw    r31:r30,r17:r16
        ldi        r16,0;CRC
        ldi        r19,0x8c
crc8iar_1:
        ld        r20,Z+
        ldi        r21,8
crc8iar_2:
        lsr        r16
        brbc    0,crc8iar_3
        eor        r16,r19
crc8iar_3:
        sbrc    r20,0
        eor        r16,r19
        lsr        r20
crc8iar_4:
        dec        r21
        brne    crc8iar_2
        dec        r18
        brne    crc8iar_1

        ret

Добавилась всего одна инструкция:

Код

        movw    r31:r30,r17:r16

Вроде все правильно. Только я думаю, что если Вы переведете ваш код на Си, то компилятор сделает код, аналогичный вашему. Лично я добавил бы еще одну переменную - указатель:

Код

#define BIT_0   (1<<0)
unsigned char crc8iar(char *buffer, char nbytes)
    {
    char   *bp = buffer;
    char   crc = 0, tmp, x8C = 0x8C;
    char   i;

    do    {
         tmp = *bp++;
         i     = 8;
         do   {
            if ((crc >>= 1) & BIT_0)
                crc ^= x8C;
            if (tmp & BIT_0)
                crc ^= x8C;
            tmp >>= 1;
            }
        while (--i);
        }
    while (--nbytes);
    return crc;
    }

Вроде так, если я нигде не ошибся.

Сообщение отредактировал _Bill - Aug 25 2006, 13:22

[_Bill]

Вот код для IAR (если я ничего не напутал):

Код

crc8iar:;Input: r17:r16 buffer; r18 - number of bytes    
    ;Output: r16 = CRC

        movw    r31:r30,r17:r16
        ldi        r16,0;CRC
        ldi        r19,0x8c
crc8iar_1:
        ld        r20,Z+
        ldi        r21,8
crc8iar_2:
        lsr        r16
        brbc    0,crc8iar_3
        eor        r16,r19
crc8iar_3:
        sbrc    r20,0
        eor        r16,r19
        lsr        r20
crc8iar_4:
        dec        r21
        brne    crc8iar_2
        dec        r18
        brne    crc8iar_1

        ret

Добавилась всего одна инструкция:

Код

        movw    r31:r30,r17:r16

Вот результат трансляции. Можете сравнить.

Код

     70          #define BIT_0   (1<<0)

   \                                 In segment CODE, align 2, keep-with-next
     71          unsigned char crc8iar(char *buffer, char nbytes)
   \                     crc8iar:
     72              {
     73              char   *bp = buffer;
   \   00000000   01F8               MOVW    R31:R30, R17:R16
     74              char   crc = 0, tmp, x8C = 0x8C;
   \   00000002   E000               LDI     R16, 0
     75              char   i;
     76          
     77              do    {
     78                   tmp = *bp++;
   \                     ??crc8iar_0:
   \   00000004   9141               LD      R20, Z+
     79                   i     = 8;
   \   00000006   E018               LDI     R17, 8
     80                   do   {
     81                      if ((crc >>= 1) & BIT_0)
   \                     ??crc8iar_1:
   \   00000008   9506               LSR     R16
   \   0000000A   FB00               BST     R16, 0
   \   0000000C   F416               BRTC    ??crc8iar_2
     82                          crc ^= x8C;
   \   0000000E   E83C               LDI     R19, 140
   \   00000010   2703               EOR     R16, R19
     83                      if (tmp & BIT_0)
   \                     ??crc8iar_2:
   \   00000012   FB40               BST     R20, 0
   \   00000014   F416               BRTC    ??crc8iar_3
     84                          crc ^= x8C;
   \   00000016   E83C               LDI     R19, 140
   \   00000018   2703               EOR     R16, R19
     85                      tmp >>= 1;
   \                     ??crc8iar_3:
   \   0000001A   9546               LSR     R20
     86                      }
     87                  while (--i);
   \   0000001C   951A               DEC     R17
   \   0000001E   F7A1               BRNE    ??crc8iar_1
     88                  }
     89              while (--nbytes);
   \   00000020   952A               DEC     R18
   \   00000022   F781               BRNE    ??crc8iar_0
     90              return crc;
   \   00000024   9508               RET
     91              }

[singlskv]

Вот результат трансляции. Можете сравнить.

Код

     70          #define BIT_0   (1<<0)

   \                                 In segment CODE, align 2, keep-with-next
     71          unsigned char crc8iar(char *buffer, char nbytes)
   \                     crc8iar:
     72              {
     73              char   *bp = buffer;
   \   00000000   01F8               MOVW    R31:R30, R17:R16
     74              char   crc = 0, tmp, x8C = 0x8C;
   \   00000002   E000               LDI     R16, 0
     75              char   i;
     76          
     77              do    {
     78                   tmp = *bp++;
   \                     ??crc8iar_0:
   \   00000004   9141               LD      R20, Z+
     79                   i     = 8;
   \   00000006   E018               LDI     R17, 8
     80                   do   {
     81                      if ((crc >>= 1) & BIT_0)
   \                     ??crc8iar_1:
   \   00000008   9506               LSR     R16
   \   0000000A   FB00               BST     R16, 0
   \   0000000C   F416               BRTC    ??crc8iar_2
     82                          crc ^= x8C;
   \   0000000E   E83C               LDI     R19, 140
   \   00000010   2703               EOR     R16, R19
     83                      if (tmp & BIT_0)
   \                     ??crc8iar_2:
   \   00000012   FB40               BST     R20, 0
   \   00000014   F416               BRTC    ??crc8iar_3
     84                          crc ^= x8C;
   \   00000016   E83C               LDI     R19, 140
   \   00000018   2703               EOR     R16, R19
     85                      tmp >>= 1;
   \                     ??crc8iar_3:
   \   0000001A   9546               LSR     R20
     86                      }
     87                  while (--i);
   \   0000001C   951A               DEC     R17
   \   0000001E   F7A1               BRNE    ??crc8iar_1
     88                  }
     89              while (--nbytes);
   \   00000020   952A               DEC     R18
   \   00000022   F781               BRNE    ??crc8iar_0
     90              return crc;
   \   00000024   9508               RET
     91              }

696 тактов однако ???

Код

   \   0000000E   E83C               LDI     R19, 140
   \   00000010   2703               EOR     R16, R19
     83                      if (tmp & BIT_0)
   \                     ??crc8iar_2:
   \   00000012   FB40               BST     R20, 0
   \   00000014   F416               BRTC    ??crc8iar_3
     84                          crc ^= x8C;
   \   00000016   E83C               LDI     R19, 140

А не слишком ли мы часто загружаем константу 140 (0x8c).