Да уж, ругаю всех за деление на F0, а в своем глазу бревна не вижу!
Свежий GCC оптимизирует подобный алгоритм по самые гланды. Он даже умножение заменяет сложениями и сдвигами, на проце с аппаратной математикой двойной точности!!! Видать там очень больное место, которое решили заботливо прикрыть грабельками. Не важно как писать, эта сволочь применяет свой шаблон. Ещё, после затяжных ожесточённых боёв с убегающими в даль указателями - было принято решение передавать в функцию хвост массива. В этом случае потери бойцов минимальны, а весь урон принимает глюкавая функция. В любом случае функция заполняет массив с хвоста.
Eddy_Em - если не сложно, подскажи как культурно приказать GCC не использовать оптимизацию в виде глюкавой записи uint16_t вместо двух char. Последние три строки после цикла.
как культурно приказать GCC не использовать оптимизацию в виде глюкавой записи uint16_t вместо двух char.
В чем глюкавость? Там где невыровненный доступ запрещен совмещенной записи быть не должно, а где разрешен вряд ли что-то можно выиграть дважды сохранив по байту.
Откуда-то два деления придумали, "лишние" обращения, "лишние" ветвления.
Эта операция "/" - называется деление, ежли что. И здесь "%" - тоже деление. А вот это "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) и ни одного лишнего обращения к памяти. Количество тактов считайте сами, вот листинг:
Итого = 8 команд внутри цикла (1-й цикл), почти все 1-тактные (кроме единственной STRB), ни одного ветвления, ни одного деления. И конечно компилятор тут ступил, ибо одна команда в этом цикле явно лишняя, и если бы у него было больше мозгов, он бы её удалил и было бы ещё быстрее. Такты в своём творении сами считайте.
Свежий GCC оптимизирует подобный алгоритм по самые гланды. Он даже умножение заменяет сложениями и сдвигами, на проце с аппаратной математикой двойной точности!!!
Бред какой-то... Это деление должно заменяться умным программистом на одно однотактное умножение. А не на кучу сложений/сдвигов тупым компилятором. Никогда компилятор не будет умнее умного программиста. Даже в этом листинге видно, что даже на максимальной оптимизации компилятор впендюрил как минимум одну лишнюю команду. Непонятно зачем. Это IAR. Может GCC лучше скомпилит - не пробовал.
Последний раз редактировалось jcxz Пт окт 22, 2021 12:23:51, всего редактировалось 2 раз(а).
Это не часто происходит, и вообще непонятно от чего зависит. Появилось с переходом на gcc-arm-none-eabi-10_3, в котором походу слишком сильно закрутили гайки оптимизации.
На ядрах, где невыровненный доступ разрешён (>=Cortex-M3) он скомпилит это в одну STRH, где запрещён - в пару STRB. Может можно аналогично и GCC: через указатель на пакованный тип?
Деление на константу, во многих случаях легко заменяется на умножение. Которое 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
Деление на константу, во многих случаях легко заменяется на умножение. Которое 1-тактное.
Только в тех случаях, когда ядро поддерживает умножение с результатом int64_t.
А в тех ядрах, где такой UMULL нет, имеется аппаратное деление? А если также не имеется, то один фиг - одну UMULL заменяем умножением в столбик на 3-x/4-х командах умножения, и получаем даже ещё бОльший выигрыш в скорости по сравнению с программным делением сдвигами/вычитаниями. Что ваша 2-я ссылка и доказывает.
По Вашей 1-й ссылке попробовал вставить аналог своего цикла: https://godbolt.org/z/9cqovKqnx Один фиг - получаются те же 8 команд внутри цикла как и у IAR. GCC почему-то также тупит на нём. Ведь элементарно CMP можно было бы выкинуть, заменив идущую перед ней MOV, на MOVS.
На M0 все хуже и вызывается относительно тяжелая __udivsi3(), хотя скорость вышеприведенных функций явно повыше и можно их использовать везде, не зависимо от платформы, единственное что размер бинарника может немного вырасти если вызываются и эти функции и обычное деление...
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 бит это далеко не бесплатная операция), мой же - деление с остатком (да, получение частного и остатка это одна функция, а не две). Сравнивать скорость прямо сейчас неудобно, но вечером, если хотите, заморочусь.
Сравнивать скорость прямо сейчас неудобно, но вечером, если хотите, заморочусь.
Как ни сравнивайте, а на любом CPU, который умеет аппаратное умножение, но не умеет деление (или деление намного дольше выполняется), вариант с умножением будет значительно быстрее.
Добавлено after 22 minutes 44 seconds: Непонятно только - нафига и IAR и GCC на Cortex-M4 в вышеприведённых алгоритмах выполняют умножение на 10 с помощью сдвигов/сложений? Ведь если использовать штатную команду умножения, будет и быстрее и короче. Например:
А как умножение uint64_t на 8-битной аврке может быть быстрей? А вообще, надо сравнить скорости выполнения на STM32F0.
_________________ Linux rules! Windows must die. Здравомыслящий человек добровольно будет пользоваться мастдаем лишь в двух случаях: под дулом автомата или под влиянием анального зонда. Я на гитхабе, в ЖЖ
Кстати я заметил прикольную штуку, вне зависимости уровня изврата кода - GCC собирает практически одинаковый бинарный код. При таком раскладе нет смысла извращаться, нужно просто писать код максимально просто.
При том, что именно эта ветка дискуссии была про AVR, естественно. Ну и потому что я синтаксис ассемблера AVR знаю гораздо лучше.
Цитата:
Это одна команда длительностью = 1такт.
Я ведь выложил дизасм листинг: это целая подпрограмма __lshrdi3
Цитата:
Как ни сравнивайте, а на любом CPU, который умеет аппаратное умножение, но не умеет деление (или деление намного дольше выполняется), вариант с умножением будет значительно быстрее.
Числами будет трудно, дешевле использовать логику. Для начала: Существует всего две базовые математические операции(в самой математике) , которые невозможно разложить на более мелкие примитивы. Это сложение и вычитание. Эти операции противоположны по смыслу и действию, хотя и могут заменять друг друга в произвольном порядке. Из сложения с вычитанием получаются все остальные сложные математические операции, вообще буквально все. И точно так-же разложить любую сложную математическую операцию до базовых сложения и вычитания. Однако в некоторых случаях получится слишком чудовищное замещение по своей протяженности. Это те самые моменты, когда матлаб начинает тупить.
Но так или иначе базовых операций всего две. И за прошедшие 80 лет - ничего нового найдено не было.
Умножение очень хорошо выполняется одновременными каскадными сложениями. В первый цикл складываются сразу 16 пар, во второй 8, потом есно 4, и последние 2 числа. В идеале получается 4 цикла сложений, причём они могут работать быстрее тактовой ядра. А в случае использования триггерной логики - от одного до трёх такта ядра. Есно все эти такты полностью проваливаются в конвейер ядра, отчего с некоторого момента стало принято говорить что умножение занимает один такт. Хотя это жуткая неправда и наепалово. Само сложение выполняется то-же быстро, всего два такта. Два - потому как там есть операция обслуживания параллельного переноса. В случае с умножением - перенос добавляет лишний дребезг и немного повышает энергопотребление в триггерную логику. Но всё-же для скорости используют максимальное количество одновременных операций, вместо микрокода как было раньше. + нагрев.
Для деления используется честное вычитание. Не вот это ваше хакерское сложение с отрицательным числом, а настоящее, как учебниках. При этом оно чисто физически не может быть параллельным. На каждом цикле нужно дождаться полного выполнения вычитания. А количество циклов может быть равно количеству разрядов регистра (особо запущенный случай). При этом операция переноса немного подливает масла в огонь - эта сволочь тоже не может работать синхронно на все разряды. Выход и положения всего один - разгон. Для полевых транзисторов разгон - это не просто повышение частоты, это прежде всего повышение мощности. Потому как сам транзистор в состоянии переключаться многократно быстрее, но упирается во входную ёмкость ответной логики и конструкционную ёмкость линий. Всё это нужно прокачать повышенным током, чтоб работало быстрее. Честное вычитание в других местах не применяется, потому как очень накладно по энергопотреблению и времени. Вместо него работает конвертация в отрицательное число и сложение. Это это примерно раз в 30 быстрее получается (если измерять в пикосекундах оба метода).
Отдельная боль - вычитание в числах одинарной и двойной точности. Мало того что приходится двигать два числа в произвольном направлении, так ещё и сама операция происходит в расширенном поле - что существенно добавляет времени. Жирность математики двойных чисел - может превышать по площади всю целочисленную логику ядра. Потому как там есть умножение, которое очень активно расползается в ширину и высоту. И при этом блок математики будет греться только в одном месте - там где выполняется честное вычитание.
Числами будет трудно, дешевле использовать логику.
Чтобы использовать логику нужны какие-то предпосылки. Пока что единственное, что нам известно - что мой код в занимает в 1.6 раз меньше места в ПЗУ. Поскольку никаких кэширований и других оптимизаций на скорость не использовалось, логично предположить, что он будет быстрее выполняться. Но это слишком общие соображения чтобы в выборе алгоритма руководствоваться только ими.
Цитата:
Умножение очень хорошо выполняется одновременными каскадными сложениями. В первый цикл складываются сразу 16 пар, во второй 8, потом есно 4, и последние 2 числа.
Вот только в реальности умножение заменяется на сложения, сдвиги и битовые AND, то есть не чисто арифметические операции, а плюс к ним логические. С делением, насколько я понимаю, принцип примерно тот же: из делимого вычитается делитель, сдвинутый на разное количество битов.
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения
Вход
Регистрация
Правила
FAQ
Поиск
