Хитрые, необычные алгоритмы и код

[ПростоНуб]

[uquote="Starichok51",url="/forum/viewtopic.php?p=4643649#p4643649"]

искусство программирования возможно только на ассемблере?

да, и еще тысячу раз да![/uquote]
Вы можете привести пример MQTT брокера на ассемблере? А полноценной реализации WiFi и TCP/IP?
Что либо действительно сложное, как тот же ESP IDF, насчитывающий почти полмиллиона строк на C объемом свыше 200 МБ, на ассемблере Вы не напишете и не отладите за адекватное время. То бишь, к тому времени, когда напишете, это никому не будет нужно, так как система команд ESP32 существенно расширится или даже в очередной раз кардинально изменится, как уже произошло при переходе с архитектуры Tensilica на архитектуру RISC-V. Кому нужен код, который эффективно работал на МК, выпуск которых прекращен и неэффективен на имеющихся на рынке МК?

[uquote="Starichok51",url="/forum/viewtopic.php?p=4643649#p4643649"]ни один компилятор с языка высокого уровня с любой оптимизацией не сравнится с программированием на ассемблере.[/uquote]
Теоретически. Я даже не буду рассматривать случай, когда потребуется перенести написанный код с ESP32 на ESP32-C3, то есть с ассемблера Tensilica на RISC-V.
Возьмем более простой вариант. Написали Вы, предположим, за год какой то супер-пупер оптимальный код для ESP32-S2. Например, TCP/IP стек вроде https://github.com/lwip-tcpip/lwip. Тут вдруг вышел ESP32-S3 с поддержкой SIMD инструкций. И если аналогичный код на С, который проигрывал раньше ассемблерному в производительности, просто перекомпилировать, то он может оказаться в разы эффективней Вашего ассемблерного кода. А переписывать такой ассемблерный код с учетом новых SIMD инструкций займет месяцы. А если такого кода накопилось уже много? Да пока Вы его перепишите, появятся новые расширения системы команд и потребует переписывать всё заново!

А ведь у современных МК нередко несколько ядер и без учета этого, ассемблерный код легко может деградировать в производительности, если NUMA для конкретного МК не была учтена изначально.

Практически же, программируя на ассемблере невозможно предугадать особенности развития целевой архитектуры. В этом году вышли ESP32-P4 и С5, в прошлом - H2 и С6, в 2022 - С2, в 2021 - С3 и S3. Будете что ли каждые полгода переписывать все свои наработке на ассемблере под расширяющуюся систему команд, новую логику конвейера, предсказания ветвлений, спекулятивного выполнения, кешей или NUMA? Или все же проще писать на языке высокого уровня, по необходимости компилируя свои наработки под обновленную архитектуру?

[uquote="Starichok51",url="/forum/viewtopic.php?p=4643649#p4643649"]на ассемблере можно делать такие "чудеса", на которые не способен никакой компилятор с языка высокого уровня.[/uquote]
Само собой. Поэтому и Rust, и C поддерживают ассемблерные вставки для тех случаев, когда такие чудеса действительно необходимы. Но программирование только на ассемблере практически умерло, как только МК стали располагать мегабайтами программной и сотнями килобайт оперативной памяти. Остается это лишь принять.
И не стоит меня агитировать за Советскую власть. В свое время я написал тысячи строк кода на ассеблере IBM/370, не меньше - на ассемблере Z80, чуть меньше - на ассемблере i8086, сотни строк кода на ассемблере AVR. Вот только их уже нет с нами и они никому не нужны. Даже Padauk для своих двухцентовых МК не поддерживает разработку на ассемблере, так как система команд изменяется даже от ревизии к ревизии. Разработчики sdcc уже обругались на такие приколы. Стабильную поддержку pdk13 так и не удалось сделать за четыре года.

[uquote="Starichok51",url="/forum/viewtopic.php?p=4643649#p4643649"]к тому же, рабочий код (хекс) с ассемблера в несколько раз короче аналогичного кода на Си.[/uquote]
Если заархивировать любой текст архиватором, он тоже станет в несколько раз короче. Вот только как Вы его в этом виде читать будете? )))
Ну это не считая того, что на каком бы языке программирования Вы для МК не программировали, заливается в любом случае бинарный код. В том же Linux больше половины firmware в виде бинарников (тот самый "хекс"), написанных на самых разных языках.

Добавлено after 14 minutes 6 seconds:
[uquote="Огонёк",url="/forum/viewtopic.php?p=4643676#p4643676"]А не надо ничего поддерживать. Написал один раз идеальный код, и он потом сам нормально работает, не требуя правок и дополнений.[/uquote]
Код на ассемблере, идеальный для ESP32-S2 может с треском проиграть в производительности не слишком оптимальному коду на Rust или C при переносе его на ESP32-S3. Потому для языков высокого уровня компилятор сам сгенерирует код с поддержкой появившихся в ESP32-S3 SIMD инструкций, а в ассемблере останется ровно то, что было - легаси.
Более того, аналогичные приколы можно получить даже на разных ревизиях одного МК при изменениях в логике NUMA, спекулятивного или out-of-order исполнения команд.
Тот же Espressif клепает новые МК по паре ежегодно. И на каждый за год легко может появится 2-3 ревизии.
Так что в реальной жизни этот самый "идеальный код на ассемблере" необходимо переписывать чуть ли не каждые два месяца, чтобы он оставался "идеальным".

[Огонёк]

под дополнительные задачи в существующем изделии, либо при использовании кода в другом изделии с иными вводными

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

Добавлено after 4 minutes 47 seconds:

Тот же Espressif клепает новые МК по паре ежегодно. И на каждый за год легко может появится 2-3 ревизии.
Так что в реальной жизни этот самый "идеальный код на ассемблере" необходимо переписывать чуть ли не каждые два месяца, чтобы он оставался "идеальным".

Не надо ничего переписывать - надо писать новое. Написал идеальный код для тринадцатой тиньки - он и будет для неё идеальным кодом. Вышла на рынок 328-я мега - для неё нужно писать новый идеальный код.
Ну или воспользоваться универсальным кодом на Си и надеяться, что компилятор не подведёт.

[ПростоНуб]

[uquote="Огонёк",url="/forum/viewtopic.php?p=4643686#p4643686"]Не надо ничего переписывать - надо писать новое.[/uquote]
Ну давайте. За сколько времени Вы напишете на ассемблере аналог TCP/IP стека на C? Вот этого: https://github.com/muvarov/iwip
Там всего лишь 8 мегабайт кода на C из 200 с лишним тысяч строк.
И сколько времени Вы будете его переписывать с ассемблера Tensilica на RISC-V, например, при необходимости перехода с устаревшего ESP32 на ESP32-C?
Боюсь, Esspessif будет клепать новые МК быстрее, чем Вы физически сможете этот код к ним адаптировать. Так что он станет легаси еще до того, как Вы успеете его написать и отладить.

[Огонёк]

Esspessif будет клепать новые МК быстрее, чем Вы физически сможете этот код к ним адаптировать.

А зачем за ними гнаться? Взял себе один камень и работаешь с ним неспеша. Результат будет достигнут. Пусть производитель хоть сколько нового клепает - суета всё это.

[ARV]

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

Вернитесь в русло темы, пожалуйста!

[Adrift]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4643445#p4643445"]

Код: Выделить всё

int median3 (int a, int b, int c) {
  return MAX(MIN(a,b),MIN(c,MAX(a,b)));
}

[/uquote]
У меня на M33 в эффективности этот код проигрывает такому, а ведь это по сути пузырьковая сортировка и есть )

Код: Выделить всё

int median3(int a, int b, int c)
{
	if (a > b) swap(a, b);
	if (b > c) swap(b, c);
	return max(a, b);
}

[ПростоНуб]

[uquote="Огонёк",url="/forum/viewtopic.php?p=4643692#p4643692"]

Esspessif будет клепать новые МК быстрее, чем Вы физически сможете этот код к ним адаптировать.

А зачем за ними гнаться? Взял себе один камень и работаешь с ним неспеша. Результат будет достигнут.[/uquote]
Вот только кому этот результат будет нужен, если он будет достигнут для МК снятого с производства?
Совершенно никому, кроме того, кто этот результат получил )))

Добавлено after 1 minute 47 seconds:
[uquote="ARV",url="/forum/viewtopic.php?p=4643698#p4643698"]Крайне неудачный для этой темы пример TCP-стека![/uquote]
Напишите свой. Если он окажется лучше этого, вот тогда поговорим.

Добавлено after 11 minutes 39 seconds:
[uquote="Adrift",url="/forum/viewtopic.php?p=4643700#p4643700"]У меня на M33 в эффективности этот код проигрывает такому

Код: Выделить всё

int median3(int a, int b, int c)
{
	if (a > b) swap(a, b);
	if (b > c) swap(b, c);
	return max(a, b);
}

[/uquote]
Приведите полностью код на C, чтобы он GCC компилировался и я мог не модифицируя его убедиться в Вашей правоте.

[uquote="Adrift",url="/forum/viewtopic.php?p=4643700#p4643700"]а ведь это по сути пузырьковая сортировка и есть )[/uquote]
Нет. Пузырьковая бы была только если сортировались все пять значений. А так я очень сомневаюсь в сколь-либо заметной разнице в машинном коде после оптимизации компилятором.

[Adrift]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4643704#p4643704"]Приведите полностью код на C, чтобы он GCC компилировался и я мог не модифицируя его убедиться в Вашей правоте.[/uquote]

Код: Выделить всё

template<typename T>
void constexpr swap(T& a, T& b) noexcept
{
	auto tmp = a;
	a = b;
	b = tmp;
}

int median3(int a, int b, int c)
{
	if (a > b) swap(a,b);
	if (b > c) swap(b, c);
	return std::max(a, b);
}

[jcxz]

[uquote="Adrift",url="/forum/viewtopic.php?p=4643700#p4643700"]У меня на M33 в эффективности этот код проигрывает такому, а ведь это по сути пузырьковая сортировка и есть )[/uquote]Листинг в студию! Без листинга это - пустой звон.

[ПростоНуб]

[uquote="ARV",url="/forum/viewtopic.php?p=4643698#p4643698"]отказа от динамического распределения памяти в пользу статического[/uquote]
Хотя бы посмотрели бы в код (iwip/src/core/mem.c и iwip/src/core/memp.c), прежде чем явную дезинформацию тут размещать.

Добавлено after 1 minute 31 second:
[uquote="Adrift",url="/forum/viewtopic.php?p=4643710#p4643710"][uquote="ПростоНуб",url="/forum/viewtopic.php?p=4643704#p4643704"]Приведите полностью код на C, чтобы он GCC компилировался и я мог не модифицируя его убедиться в Вашей правоте.[/uquote]

Код: Выделить всё

template<typename T>

[/uquote]
Я просил полностью код, который я мог бы изучить, запустить и увидеть методику и результат сравнения производительности.

[Adrift]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4643713#p4643713"]Я просил полностью код, который я мог бы изучить, запустить и увидеть методику и результат сравнения производительности.[/uquote]
Я дал функцию, которую просто подставляете в свой код вместо своей. Собственно производительность я даже не сравнивал, просто мой вариант ожидаемо скомпилировался в меньшее количество инструкций, ведь там 3 тернарных операции, вместо четырех, и IT компилятор подставил две, вместо трех. Разница 4-5 инструкций, в зависимости от флагов.

[Starichok51]

Если заархивировать любой текст архиватором, он тоже станет в несколько раз короче. Вот только как Вы его в этом виде читать будете?

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

с каждым годом становится всё меньше и меньше человеков на это способных...

также с каждым годом становится всё меньше и меньше человеков, способных писать качественно и на Си, и пишущих говнокод.

[ПростоНуб]

[uquote="Adrift",url="/forum/viewtopic.php?p=4643717#p4643717"][uquote="ПростоНуб",url="/forum/viewtopic.php?p=4643713#p4643713"]Я просил полностью код, который я мог бы изучить, запустить и увидеть методику и результат сравнения производительности.[/uquote]
Собственно производительность я даже не сравнивал[/uquote]
То есть, это только гипотеза?

[uquote="Adrift",url="/forum/viewtopic.php?p=4643717#p4643717"]просто мой вариант ожидаемо скомпилировался в меньшее количество инструкций[/uquote]
А с чего Вы взяли, что меньшее количество инструкций - это лучше?
К тому же моя попытка скомпилировать Ваш код привела к тому, что мой код занял 8 инструкций:

Код: Выделить всё

median3:
.LFB41:
	.cfi_startproc
	endbr64
	vmovd	%edi, %xmm2
	vmovd	%esi, %xmm0
	vpmaxsd	%xmm2, %xmm0, %xmm1
	vmovd	%edx, %xmm3
	vpminsd	%xmm2, %xmm0, %xmm0
	vpminsd	%xmm3, %xmm1, %xmm1
	vpmaxsd	%xmm0, %xmm1, %xmm0
	vmovd	%xmm0, %eax
	ret

А Ваш 9:

Код: Выделить всё

adrift_median3:
.LFB42:
	.cfi_startproc
	endbr64
	cmpl	%esi, %edi
	movl	%esi, %eax
	cmovle	%edi, %esi
	cmovle	%eax, %edi
	cmpl	%edx, %edi
	movl	%esi, %eax
	cmovg	%edx, %edi
	cmpl	%esi, %edi
	cmovge	%edi, %eax
	ret
	.cfi_endproc

[Adrift]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4643761#p4643761"]То есть, это только гипотеза?
А с чего Вы взяли, что меньшее количество инструкций - это лучше?[/uquote]
Потому что я видел эти инструкции и запускаю не на M7 )

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

Так у вас и не Cortex-M33. У меня для O3 листинги такие:

Спойлер

Код: Выделить всё

cmp r0, r5 
bgt.n 0x20001030
cmp r5, r0 
mov r1, r5 
it lt 
movlt r1, r0 
mov r5, r0 
mov r0, r1 
cmp r3, r0 
it ge 
movge r3, r0 
cmp r3, r5 
it lt 
movlt r3, r5
           
   vs

cmp r1, r0 
itte le 
movle r12, r1 
movle r1, r0 
movgt r12, r0 
cmp r2, r1 
it ge 
movge r2, r1 
cmp r2, r12 
it lt 
movlt r2, r12 

Выполняется мой вариант тоже быстрее, цикл на 1000 итераций может выдавать 14К vs 13К тактов, а может 17К vs 15К, смотря откуда и какие abc подсовывать.

[ПростоНуб]

[uquote="Starichok51",url="/forum/viewtopic.php?p=4643741#p4643741"]

Если заархивировать любой текст архиватором, он тоже станет в несколько раз короче. Вот только как Вы его в этом виде читать будете?

ты думаешь, что я МК записываю заархивированную программу, а МК её разархивирует и потом исполняет?[/uquote]
Я не думаю, а утверждаю:

на каком бы языке программирования Вы для МК не программировали, заливается в любом случае бинарный код

Рекомендую внимательней читать сообщения, на которые Вы отвечаете.

[uquote="Starichok51",url="/forum/viewtopic.php?p=4643741#p4643741"]ну да, сегодня на мощных МК программы на десятки и тем более на сотни килобайт никто на ассемблере не будет.[/uquote]
Вот и я о том же.

[uquote="Starichok51",url="/forum/viewtopic.php?p=4643741#p4643741"]а вот когда для АТтини13, у которой памяти сущие крохи, берутся писать на Си из-за полного незнания ассемблера...[/uquote]
Я даже для ATMega328 на ассемблере выписывал весь обмен по SPI с LCD. Так как без этого сделать игрушку вроде Арканоида не удавалось. Слишком низкий получался FPS получался.
Но сейчас времена другие. ESP32-C3 можно купить в розницу у китайцев меньше, чем за 200 рублей с доставкой https://aliexpress.ru/item/100500624107 ... 7692069730
А туже же ATTINY13A дешевле, чем за 160 рублей с доставкой я недавно не нашел. Даже STM32F103C6T6 на плате получается дешевле, чем просто DIP8!
Почему? Да потому, что спроса нет. Выпускается мелкими сериями для устаревшего оборудования. Потому и дорого.
Теперь вместо Atmel на рынке дешевых МК лидирует Padauk. Вот, даже в Чип и Дип берите по 11 рублей за шутуку в розницу: https://www.chipdip.ru/product0/8010768955
Ну ладно, это OTP (хотя за 11 рублей не очень то жалко). С флешем заметно дороже, уже по 28 рублей https://www.chipdip.ru/product0/8015935028
И есть ли смысл после этого что-то делать с ATTiny?

[uquote="Starichok51",url="/forum/viewtopic.php?p=4643741#p4643741"]также с каждым годом становится всё меньше и меньше человеков, способных писать качественно и на Си, и пишущих говнокод.[/uquote]
Есть такое. Уж не знаю, ЕГЭ в этом виновато или еще что-то, но нанимать адекватных программистов с каждым годом становится всё сложнее. И это относится далеко не только к C.
Например, буквально вчера сеньор пришел ко мне с SQL запросом, который слишком долго выполнялся. Просто обновить статистики у таблиц он не догадался (

[smacorp]

к тому времени, когда напишете, это никому не будет нужно, так как система команд ESP32 существенно расширится или даже в очередной раз кардинально изменится, как уже произошло при переходе с архитектуры Tensilica на архитектуру RISC-V. Кому нужен код, который эффективно работал на МК, выпуск которых прекращен и неэффективен на имеющихся на рынке МК?

ПростоНуб, а это ещё вопрос нужно ли так часто менять линейки МК и процессоров. Да, до определённого момента прогресс был налицо, а какое-то время назад начали гнаться в первую очередь за финансовым успехом и насильно заставлять людей покупать новые камни. Я вот до сих пор сижу на i7-2600K и мне его хватает даже для Solidworks. Но нет, для Windows 11 я должен полностью сменить весь компьютер только потому, что так захотел "поганый Майкрософт".

Не было бы этой далеко не всем нужной гонки железа, глядишь больше программистов думали бы об оптимальности кода, а не о том, как слепить его побыстрее и попроще.

[Огонёк]

Теперь вместо Atmel на рынке дешевых МК лидирует Padauk.

Ну и накой оно нужно, если

Даже Padauk для своих двухцентовых МК не поддерживает разработку на ассемблере, так как система команд изменяется даже от ревизии к ревизии.

?
Бардак, однако.

[ПростоНуб]

[uquote="smacorp",url="/forum/viewtopic.php?p=4643815#p4643815"]

Кому нужен код, который эффективно работал на МК, выпуск которых прекращен и неэффективен на имеющихся на рынке МК?

ПростоНуб, а это ещё вопрос нужно ли так часто менять линейки МК и процессоров.[/uquote]
Так в итоге решаем этот вопрос не мы. Я вот выше уже написал, что ATTiny просто в DIP8 сейчас стоит дороже, чем STM32F103C6T6 на плате с питанием. А вместо ATtiny теперь Чип и Дип торгует Padauk по 11 рублей за штуку.
Тут уж хочешь или не хочешь, а будешь менять линейки МК.
А что касается Espressif, то линейка ESP32 вроде как одна, но внутри нее даже системы команд разные, не говоря уже о двухядерных вариантах с NUMA. Тут уж опять, хочешь или не хочешь, но на ассемблере писать становиться самоубийственно. Особенно с учетом того, что весь ESP IDF на C и напрямую мимо него лазить к железу в среде FreeRTOS может вылезти боком.

Получается, лично для себя и за свой счет- естественно твори, что хочешь. Но если хочешь хотя бы коммитить в мэйнстрим и развивать инфраструктуру, то об ассемблере приходится забыть и разрабатывать для современных МК,

Добавлено after 2 minutes 33 seconds:
[uquote="Огонёк",url="/forum/viewtopic.php?p=4643820#p4643820"]

Теперь вместо Atmel на рынке дешевых МК лидирует Padauk.

Ну и накой оно нужно, если

Даже Padauk для своих двухцентовых МК не поддерживает разработку на ассемблере, так как система команд изменяется даже от ревизии к ревизии.

?[/uquote]
Кто запрещает писать на C?
Ну да, родной компилятор у них убогий, а sdcc на месяц-другой отстает от новых ревизий. Но уж при цене МК 11 рублей вполне можно позволить держать у себя запас, позволяющий безбедно пережить эти месяц-другой.

[Огонёк]

Кто запрещает писать на C?

Никто. Просто хочется иметь дело с нормальным производителем, способным сохранять систему команд в рамках разных ревизий одной модели. А то и в рамках целой линейки устройств. А вот эта вот ветренность в головах разработчиков - она не к добру. Стильно, модно, молодёжно - возможно. Но я консервативен.

[ПростоНуб]

[uquote="Adrift",url="/forum/viewtopic.php?p=4643791#p4643791"][uquote="ПростоНуб",url="/forum/viewtopic.php?p=4643761#p4643761"]То есть, это только гипотеза?
А с чего Вы взяли, что меньшее количество инструкций - это лучше?[/uquote]
Потому что я видел эти инструкции и запускаю не на M7 )[/uquote]
А у M33 что ли отменили конвейер?

[uquote="Adrift",url="/forum/viewtopic.php?p=4643791#p4643791"]Так у вас и не Cortex-M33. У меня для O3 листинги такие:[/uquote]
И так не складывается.
Запускаю arm-none-eabi-gcc -O3 -mtune=cortex-m33 -S -o median-c.s ./median.c
Вижу:

Код: Выделить всё

median3:
	cmp	r1, r0
	movge	r3, r1
	movlt	r3, r0
	cmp	r3, r2
	movge	r3, r2
	cmp	r1, r0
	movlt	r0, r1
	cmp	r3, r0
	movge	r0, r3
	bx	lr

против

Код: Выделить всё

adrift_median3:
	cmp	r0, r1
	bgt	.L81
	mov	r3, r1
	mov	r1, r0
	mov	r0, r3
.L81:
	cmp	r0, r2
	movge	r0, r2
	cmp	r0, r1
	movlt	r0, r1
	bx	lr

Вы всё же дайте полностью свой код, причем не воруя у меня median5, а сделав нахождение медианы полностью пузырьковой сортировкой. Вот тогда и сравним.

Добавлено after 11 minutes 52 seconds:
[uquote="Огонёк",url="/forum/viewtopic.php?p=4643843#p4643843"]

Кто запрещает писать на C?

Просто хочется иметь дело с нормальным производителем, способным сохранять систему команд в рамках разных ревизий одной модели.[/uquote]
Такое сейчас редко не встречается. Почти каждый производитель МК/CPU постоянно расширяет возможности своего продукта.
Не забывайте, с чего мы начали. С возможности написать идеально оптимизированную программу на ассемблере. На новых ревизиях Padauk она, естественно работать будет, так совместимость снизу вверх поддерживается. А вот по эффективности она сразу начнет проигрывать скомпилированному C коду, так как компилятор будет поддерживать новые расширения.
Собственно говоря, тоже самое мы видим и на десктопах. Когда перекомпилировав код с использованием новых инструкций процессора (обычно SIMD), получаем существенный прирост производительности.
Баги тема отдельная. У всех они случаются. Читаем ERRATA и учитываем.