Кто любит RISC в жизни, заходим, не стесняемся.
Ответить

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 10:47:07

Да уж, ругаю всех за деление на F0, а в своем глазу бревна не вижу!

Свежий GCC оптимизирует подобный алгоритм по самые гланды. Он даже умножение заменяет сложениями и сдвигами, на проце с аппаратной математикой двойной точности!!! Видать там очень больное место, которое решили заботливо прикрыть грабельками. Не важно как писать, эта сволочь применяет свой шаблон.
Ещё, после затяжных ожесточённых боёв с убегающими в даль указателями - было принято решение передавать в функцию хвост массива. В этом случае потери бойцов минимальны, а весь урон принимает глюкавая функция. В любом случае функция заполняет массив с хвоста.

Eddy_Em - если не сложно, подскажи как культурно приказать GCC не использовать оптимизацию в виде глюкавой записи uint16_t вместо двух char. Последние три строки после цикла.
Код:
char* nex_char(uint32_t value, char* tail_txt) 
{
    int32_t tmp, jump; jump = 0;
    volatile char* tex; tex = tail_txt;
    *(tex--) = 0;
    do
    {
        tmp = value & 0x0F;
        if (tmp > 9 ) *(tex--) = tmp + 55;
            else *(tex--) = tmp + '0';
        value >>= 4; jump++;
    }while ((value )||(jump & 1));
    *(tex--) = 'x';
    *tex = '0';
    return tex;
};

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 11:54:33

как культурно приказать GCC не использовать оптимизацию в виде глюкавой записи uint16_t вместо двух char.

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

Код:
char* nex_char(uint32_t value, char* tail_txt)
{
   int32_t jump = 0;
   *tail_txt-- = 0;

   do
   {
      int32_t tmp = value & 0x0F;
      if (tmp > 9) tmp += 7;
      *tail_txt-- = tmp + '0';
      value >>= 4;
      jump++;
   } while (value || (jump & 1));
   
   *(volatile char*)tail_txt-- = 'x'; // volatile, если сильно хочется
   *(volatile char*)tail_txt = '0';
   return tail_txt;
}

И наверно все-таки hex_char? :)

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 12:18:22

Откуда-то два деления придумали, "лишние" обращения, "лишние" ветвления.
Эта операция "/" - называется деление, ежли что. И здесь "%" - тоже деление.
А вот это "buf[0]" - лишние обращения к памяти, коих тоже зачем-то вагон.
Это если вы в своём же коде разобраться не можете.
И на кой два раза одно и то же действие делать???

Впрочем, ладно: если уж взяли мой пример для произвольного основания, продемонстрируйте свой вариант, решающий эту задачу не хуже. Естественно, в качестве доказательства принимается количество тактов для среднего и худшего случаев в сравнении с тем, что на вашем компиляторе выдает мой "неоптимальный" код.
Например:
Код:
//Преобразует число x в строку в str с основанием 10.
//Возвращает указатель на завершающий 0-ой символ.
char * utoa10(u32 x, char *str)
{
  #define D ((B35 + 5) / 10)
  u32 i;
  char *s1, *s = str;
  do {
    x = (i = x) * D >> 35;
    *s++ = i - x * 10 + '0';
  } while (x);
  *(s1 = s) = 0;
  while ((uint)--s > (uint)str) {
    i = *s;
    *s = *str;
    *str++ = i;
  }
  return s1;
  #undef D
}

Собственно - преобразование в строку - это 1-й цикл. Как видно в нём: 1) ни одного деления; 2) ни одного ветвления; 3) и ни одного лишнего обращения к памяти.
Количество тактов считайте сами, вот листинг:
Код:
char * utoa10(u32 x, char *str)                               
{                                                             
        _Z6utoa10mPc: (+1)                                   
 0xB470             PUSH     {R4-R6}                         
 0x460C             MOV      R4,R1                           
  #define D ((B35 + 5) / 10)                                 
  u32 i;                                                     
  char *s1, *s = str;                                         
                    REQUIRE ?Subroutine0                     
                    ;; // Fall through to label ?Subroutine0 
       ?Subroutine0: (+1)                                 
0x4625             MOV      R5,R4                         
0x.... 0x....      LDR.W    R6,??DataTable4  ;; 0xcccccccd
       ??Subroutine0_0: (+1)                             
0x4602             MOV      R2,R0                         
0xFBA6 0x0102      UMULL    R0,R1,R6,R2                   
0x08C8             LSRS     R0,R1,#+3                     
0xEB00 0x0380      ADD      R3,R0,R0, LSL #+2             
0xEBA2 0x0143      SUB      R1,R2,R3, LSL #+1             
0x3130             ADDS     R1,R1,#+48                   
0x2800             CMP      R0,#+0                       
0xF805 0x1B01      STRB     R1,[R5], #+1                 
0xD1F2             BNE.N    ??Subroutine0_0               
0x4628             MOV      R0,R5                         
0x2100             MOVS     R1,#+0                       
0x7001             STRB     R1,[R0, #+0]                 
0xE004             B.N      ??Subroutine0_1               
       ??Subroutine0_2: (+1)                             
0x7829             LDRB     R1,[R5, #+0]                 
0x7822             LDRB     R2,[R4, #+0]                 
0x702A             STRB     R2,[R5, #+0]                 
0xF804 0x1B01      STRB     R1,[R4], #+1                 
       ??Subroutine0_1: (+1)                             
0x1E6D             SUBS     R5,R5,#+1                     
0x42AC             CMP      R4,R5                         
0xD3F7             BCC.N    ??Subroutine0_2               
0xBC70             POP      {R4-R6}                       
0x4770             BX       LR               ;; return   

Итого = 8 команд внутри цикла (1-й цикл), почти все 1-тактные (кроме единственной STRB), ни одного ветвления, ни одного деления.
И конечно компилятор тут ступил, ибо одна команда в этом цикле явно лишняя, и если бы у него было больше мозгов, он бы её удалил и было бы ещё быстрее.
Такты в своём творении сами считайте.

Добавлено after 2 minutes 48 seconds:
Свежий GCC оптимизирует подобный алгоритм по самые гланды. Он даже умножение заменяет сложениями и сдвигами, на проце с аппаратной математикой двойной точности!!!
Бред какой-то... Это деление должно заменяться умным программистом на одно однотактное умножение. А не на кучу сложений/сдвигов тупым компилятором. Никогда компилятор не будет умнее умного программиста. Даже в этом листинге видно, что даже на максимальной оптимизации компилятор впендюрил как минимум одну лишнюю команду. Непонятно зачем. Это IAR. Может GCC лучше скомпилит - не пробовал.
Последний раз редактировалось jcxz Пт окт 22, 2021 12:23:51, всего редактировалось 2 раз(а).

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 12:20:31

jcxz, чему равно B35?

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 12:20:57

Работает, теперь выглядит красиво.
В чем глюкавость?

Это не часто происходит, и вообще непонятно от чего зависит. Появилось с переходом на gcc-arm-none-eabi-10_3, в котором походу слишком сильно закрутили гайки оптимизации.

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 12:22:31

jcxz, чему равно B35?
Я же привёл исходник. И листинг.

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 12:24:01

Исходник привел и там в макро используется неизвестная константа B35...

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 12:46:32

jcxz, блин, у меня такой же косяк был! Исправился (для STM32F0, где нет деления):
У Вас там тоже деление.
Деление на константу, во многих случаях легко заменяется на умножение. Которое 1-тактное.

Добавлено after 2 minutes 5 seconds:
Исходник привел и там в макро используется неизвестная константа B35...
А, да, сорри:
Код:
#define B0  0x00000001ul
...
#define B31 0x80000000ul
#define B32 (1ull << 32)
#define B33 (1ull << 33)
#define B34 (1ull << 34)
#define B35 (1ull << 35)
...

Ну и по листингу можно посмотреть во что скомпилилось ((B35 + 5) / 10). (отображается в комменте)

Добавлено after 9 minutes 48 seconds:
Eddy_Em - если не сложно, подскажи как культурно приказать GCC не использовать оптимизацию в виде глюкавой записи uint16_t вместо двух char.
Не знаю как GCC, но IAR-у легко:
Код:
typedef __packed u16 u16p8;
typedef __packed s16 s16p8;
typedef __packed u32 u32p8;
typedef __packed s32 s32p8;
typedef __packed u64 u64p8;
typedef __packed s64 s64p8;
typedef __packed u32 u32p16;
typedef __packed s32 s32p16;
typedef __packed u64 u64p16;
typedef __packed s64 s64p16;
typedef __packed u64 u64p32;
typedef __packed s64 s64p32;

u16p8 *ptr = ...;
*ptr = ...;

На ядрах, где невыровненный доступ разрешён (>=Cortex-M3) он скомпилит это в одну STRH, где запрещён - в пару STRB.
Может можно аналогично и GCC: через указатель на пакованный тип?

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 14:10:42

Деление на константу, во многих случаях легко заменяется на умножение. Которое 1-тактное.

Только в тех случаях, когда ядро поддерживает умножение с результатом int64_t.
char* u32_char (uint32_t value, char* tail_txt) cortex-m7 https://godbolt.org/z/GGdGb77hM
char* u32_char (uint32_t value, char* tail_txt) atmega32 https://godbolt.org/z/dYWvhhMds

AVI-crak писал(а):И наверно все-таки hex_char?

Ну вот, а я уже привык писать nex...

Добавлено after 1 hour 6 minutes 31 second:
Бред какой-то... Это деление должно заменяться умным программистом на одно однотактное умножение.

Сам видел, не знаю как оно получилось, наверное как-то само.
Но вот этого
Код:
#define D ((B35 + 5) / 10)
- я не могу понять.

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 14:30:33

Но вот этого
Код:
#define D ((B35 + 5) / 10)
- я не могу понять.

Фактически D равна 0.1, принцип тот же что и для чисел с фиксированной точкой(35 бит под дробную часть).

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 14:35:16

Деление на константу, во многих случаях легко заменяется на умножение. Которое 1-тактное.

Только в тех случаях, когда ядро поддерживает умножение с результатом int64_t.
А в тех ядрах, где такой UMULL нет, имеется аппаратное деление?
А если также не имеется, то один фиг - одну UMULL заменяем умножением в столбик на 3-x/4-х командах умножения, и получаем даже ещё бОльший выигрыш в скорости по сравнению с программным делением сдвигами/вычитаниями. Что ваша 2-я ссылка и доказывает.

char* u32_char (uint32_t value, char* tail_txt) cortex-m7 https://godbolt.org/z/GGdGb77hM
По Вашей 1-й ссылке попробовал вставить аналог своего цикла: https://godbolt.org/z/9cqovKqnx
Один фиг - получаются те же 8 команд внутри цикла как и у IAR. GCC почему-то также тупит на нём. :(
Ведь элементарно CMP можно было бы выкинуть, заменив идущую перед ней MOV, на MOVS. :dont_know:

Добавлено after 3 minutes 2 seconds:
Но вот этого
Код:
#define D ((B35 + 5) / 10)
- я не могу понять.
Замена деления умножением, посредством переноса десятичной точки из позиции 0 в позицию 35.

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 16:17:35

В общем на кортексах где есть аппаратное деление и длинное умножение gcc генерит код эквивалентный выполнению таких функций:
Код:
uint32_t divu10(uint32_t val)   { return val * (((1ULL << 35) + 5) / 10) >> 35; }
uint32_t divu100(uint32_t val)  { return val * (((1ULL << 38) + 5) / 100 + 1) >> 38; }
uint32_t divu1000(uint32_t val) { return val * (((1ULL << 41) + 5) / 1000 + 1) >> 41; }
uint32_t divu1M(uint32_t val)   { return val * (((1ULL << 51) + 5) / 1000000 + 1) >> 51; }

uint32_t remu10(uint32_t val) { return val - divu10(val) * 10; }

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

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 17:41:47

Например:

Отлично! Проверяем. С вашего позволения я изменил ваш пример чтобы avr-gcc на него не ругался. Ну там всякие uint->unsigned int, u32->uint32_t.
Код:
#include <avr/io.h>

#define B35 (1ULL<<35)

char * utoa10(uint32_t x, char *str){
  #define D ((B35 + 5) / 10)
  uint32_t i;
  char *s1, *s = str;
  do {
    x = (i = x) * D >> 35;
    *s++ = i - x * 10 + '0';
  } while (x);
  *(s1 = s) = 0;
  while ((unsigned int)--s > (unsigned int)str) {
    i = *s;
    *s = *str;
    *str++ = i;
  }
  return s1;
  #undef D
}

int main(){
  char buf[20];
  volatile char *res;
  res = utoa10(0x12345678, buf);
}

$ avr-gcc main.c -mmcu=atmega8 -Os
$ avr-size a.out
text data bss dec hex filename
432 0 0 432 1b0 a.out

Код:
#include <avr/io.h>

char* u32toa(uint32_t val, char *buf){
  buf+=10;
  buf[1] = 0;
  do{
    buf[0] = val % 10;
    val /= 10;
    if(buf[0] < 10)buf[0] += '0'; else buf[0] = buf[0] - 0x0A + 'A';
    buf--;
  }while(val);
  return buf;
}

int main(){
  char buf[20];
  volatile char *res;
  res = u32toa(0x87654321, buf);
}

Код:
$ avr-gcc main.c -mmcu=atmega8 -Os
$ avr-size a.out
   text    data     bss     dec     hex filename
    264       0       0     264     108 a.out

Разница по объему в полтора раза.
Из того, что с ходу бросилось в глаза при анализе дизасма: ваш вариант активно использует умножение и сдвиги (а сдвиг на 35 бит это далеко не бесплатная операция), мой же - деление с остатком (да, получение частного и остатка это одна функция, а не две). Сравнивать скорость прямо сейчас неудобно, но вечером, если хотите, заморочусь.
Вложения
disasm.txt
(11.87 KiB) Скачиваний: 87
main.c
(705 байт) Скачиваний: 94

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 18:15:28

Например:

Отлично! Проверяем. С вашего позволения я изменил ваш пример чтобы avr-gcc на него не ругался.
Не понял - а при чём тут AVR если тема про ARM? Мой пример был для него.

Добавлено after 1 minute 33 seconds:
(а сдвиг на 35 бит это далеко не бесплатная операция)
Это одна команда длительностью = 1такт.

Добавлено after 4 minutes 26 seconds:
Сравнивать скорость прямо сейчас неудобно, но вечером, если хотите, заморочусь.
Как ни сравнивайте, а на любом CPU, который умеет аппаратное умножение, но не умеет деление (или деление намного дольше выполняется), вариант с умножением будет значительно быстрее.

Добавлено after 22 minutes 44 seconds:
Непонятно только - нафига и IAR и GCC на Cortex-M4 в вышеприведённых алгоритмах выполняют умножение на 10 с помощью сдвигов/сложений?
Ведь если использовать штатную команду умножения, будет и быстрее и короче. Например:
Код:
               PUSH     {R4}
               LDR.W    R12,=0CCCCCCCDh
               MOVS     R4,#10
ppp_02:        UMULL    R2,R3,R12,R0
               LSRS     R3,R3,#+3
               MLS      R2,R3,R4,R0
               ADDS     R2,#'0'
               MOVS     R0,R3
               STRB     R2,[R1], #+1
               BNE.N    ppp_02
               STRB     R0,[R1]
               POP      {R4}
               BX       LR

Только 6 команд в теле цикла.

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 18:24:48

А как умножение uint64_t на 8-битной аврке может быть быстрей?
А вообще, надо сравнить скорости выполнения на STM32F0.

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 18:52:45

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

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 19:22:16

Не понял - а при чём тут AVR если тема про ARM?
При том, что именно эта ветка дискуссии была про AVR, естественно. Ну и потому что я синтаксис ассемблера AVR знаю гораздо лучше.
Это одна команда длительностью = 1такт.
Я ведь выложил дизасм листинг: это целая подпрограмма __lshrdi3
Как ни сравнивайте, а на любом CPU, который умеет аппаратное умножение, но не умеет деление (или деление намного дольше выполняется), вариант с умножением будет значительно быстрее.
Такое высказывания требует подтверждения числами.

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 21:59:05

Такое высказывания требует подтверждения числами.

Числами будет трудно, дешевле использовать логику.
Для начала:
Существует всего две базовые математические операции(в самой математике) , которые невозможно разложить на более мелкие примитивы. Это сложение и вычитание. Эти операции противоположны по смыслу и действию, хотя и могут заменять друг друга в произвольном порядке.
Из сложения с вычитанием получаются все остальные сложные математические операции, вообще буквально все. И точно так-же разложить любую сложную математическую операцию до базовых сложения и вычитания. Однако в некоторых случаях получится слишком чудовищное замещение по своей протяженности. Это те самые моменты, когда матлаб начинает тупить.

Но так или иначе базовых операций всего две. И за прошедшие 80 лет - ничего нового найдено не было.

Умножение очень хорошо выполняется одновременными каскадными сложениями. В первый цикл складываются сразу 16 пар, во второй 8, потом есно 4, и последние 2 числа. В идеале получается 4 цикла сложений, причём они могут работать быстрее тактовой ядра. А в случае использования триггерной логики - от одного до трёх такта ядра. Есно все эти такты полностью проваливаются в конвейер ядра, отчего с некоторого момента стало принято говорить что умножение занимает один такт. Хотя это жуткая неправда и наепалово.
Само сложение выполняется то-же быстро, всего два такта. Два - потому как там есть операция обслуживания параллельного переноса. В случае с умножением - перенос добавляет лишний дребезг и немного повышает энергопотребление в триггерную логику. Но всё-же для скорости используют максимальное количество одновременных операций, вместо микрокода как было раньше. + нагрев.

Для деления используется честное вычитание. Не вот это ваше хакерское сложение с отрицательным числом, а настоящее, как учебниках. При этом оно чисто физически не может быть параллельным. На каждом цикле нужно дождаться полного выполнения вычитания. А количество циклов может быть равно количеству разрядов регистра (особо запущенный случай). При этом операция переноса немного подливает масла в огонь - эта сволочь тоже не может работать синхронно на все разряды. Выход и положения всего один - разгон.
Для полевых транзисторов разгон - это не просто повышение частоты, это прежде всего повышение мощности. Потому как сам транзистор в состоянии переключаться многократно быстрее, но упирается во входную ёмкость ответной логики и конструкционную ёмкость линий. Всё это нужно прокачать повышенным током, чтоб работало быстрее.
Честное вычитание в других местах не применяется, потому как очень накладно по энергопотреблению и времени. Вместо него работает конвертация в отрицательное число и сложение. Это это примерно раз в 30 быстрее получается (если измерять в пикосекундах оба метода).

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

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 23:34:57

Числами будет трудно, дешевле использовать логику.

Чтобы использовать логику нужны какие-то предпосылки. Пока что единственное, что нам известно - что мой код в занимает в 1.6 раз меньше места в ПЗУ. Поскольку никаких кэширований и других оптимизаций на скорость не использовалось, логично предположить, что он будет быстрее выполняться.
Но это слишком общие соображения чтобы в выборе алгоритма руководствоваться только ими.
Умножение очень хорошо выполняется одновременными каскадными сложениями. В первый цикл складываются сразу 16 пар, во второй 8, потом есно 4, и последние 2 числа.

Вот только в реальности умножение заменяется на сложения, сдвиги и битовые AND, то есть не чисто арифметические операции, а плюс к ним логические. С делением, насколько я понимаю, принцип примерно тот же: из делимого вычитается делитель, сдвинутый на разное количество битов.

Re: Лучше не использовать типы char в stm32?

Пт окт 22, 2021 23:58:09

Чтобы использовать логику нужны какие-то предпосылки. Пока что единственное, что нам известно - что мой код в занимает в 1.6 раз меньше места в ПЗУ.

Логика очень простая - новые технологии экономят флеш, и значительно повышают быстродействие.
Ответить