Як писати оптимізований код у системах з обмеженою пам’яттю

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Привіт, я Петро Каращенко, Firmware Engineering Manager у R&D центрі SQUAD. Я координую роботу Embedded-команди, яка займається розробкою широкої лінійки систем безпеки розумного дому та IoT-пристроїв.

Embedded-системи — це завжди системи із обмеженими ресурсами. Тому виникає питання: яким чином написати код, щоб перетворити цю тендітну систему у надійний продукт, що буде приносити радість від користування.

Ця стаття буде корисна Embedded SW девелоперам, SW девелоперам, SW technical лідам, SW архітекторам, які працюють з hardware-напрямом та системами з обмеженою пам’яттю.

Що означає оптимізований код

При розробці Embedded-системи, ми мусимо себе запитати: що ми намагаємося досягти? Як має працювати наш продукт? Чим ми можемо пожертвувати заради досягнення мети? Такі питання ставляться ще на етапі проєктування продукту і визначають його подальший розвиток. Тільки так ми можемо зрозуміти, яким чином і що нам потрібно оптимізовувати.

В класичному розумінні — ми хочемо досягти максимальної продуктивності, при цьому оптимізувавши ресурси і бюджет. Зробити продукт, який буде ефективним та конкурентним, як у вартісному сенсі, так і в продуктивності своєї роботи.

В Embedded-системах (і не лише в них), ми тяжіємо до оптимального балансу між «часом» і «розміром». Під часом мається на увазі швидкодія — швидкість виконання програми. А під розміром — наскільки маленькою може бути програма та який мінімальний набір ресурсів вона може використовувати. Адже, на противагу «високорівневим» програмам, тобто тим, які виконуються на персональних комп’ютерах або в «хмарі», в нас є певні обмеження в ресурсах, які ми не можемо подолати, просто зробивши «апгрейд».

Час, або ж швидкодія, переважає лише в так званих «hard real-time» системах — тих, що мають обмежений час реакції на зовнішні події. Наприклад, автоматизація роботи вітрових електростанцій, виробничих ліній або медичного обладнання, чи автоматичне керування квадрокоптером. В інших системах ми можемо пожертвувати часом виконання, щоб отримати менший розмір та зменшене споживання пам’яті нашої програмою. Ощадливе використання ресурсів дає змогу зробити пристрій більш дешевим і, як наслідок, доступнішим більшому сегменту користувачів.

Тож як ми можемо зменшити розмір програми та споживаної пам’яті?

  • Рівні оптимізації компілятора.
  • FPU (Floating-point Unit): коли доцільно використовувати, а коли ні.
  • Сегменти пам’яті, процес лінкування та збору кінцевого виконавчого модулю (GNU Linker garbage collector).
  • GNU LTO (link time optimization): оптимізація програми на етапі лінкування.
  • Зменшення розміру логувальних стрічок без втрати читабельності.

Рівні оптимізації

Почнемо із компілятора. Вибираємо рівні оптимізації:

-O0 — No optimization (default option)

-O, -O1 — Reduce code size and execution time

-Og — Optimize debugging experience with better code quality than -O0

-O2 — Faster performance, but do not involve a space vs speed tradeoff

-O3 — Faster performance, but might result in an increased code size

-Ofast — The fastest performance

-Os — Optimize for size

Що отримуємо?

-O0 — 491 Kb

-O1 — 348,3 Kb (29,1% improvement)

-O2 — 358 Kb (27,1% improvement)

-Os — 322,5 Kb (34,3% improvement)

Floating-point Unit

Чим далі ми рухаємось у розробці новітніх технологій, тим частіше виникають потреби в обрахунках із числами з плаваючою комою — так званими floating point-ами. Все більше новітніх мікроконтролерів мають вбудований floating point unit (FPU), що суттєво пришвидшує цей процес. Без FPU використовується набір бібліотек, які емулюють розрахунки з плаваючою комою через цілочисельну математику і різного штибу ряди наближення. І тут виникає цікаве питання: чи завжди нам варто використовувати вбудований FPU? На перший погляд, відповідь може здатись очевидною.

FPU забезпечує енергоефективність, тому дуже важливо ввімкнути його для пристроїв, що працюють від батареї. Інший випадок — у системі працює DSP або інші алгоритми, які використовують обчислення з плаваючою комою.

FPU не користується регістрами загального призначення — тими, які нам у процесорі доступні завжди. Тільки своїм окремим набором FPU-регістрів. Тому, якщо ми хочемо використовувати FPU при обчисленнях з основного потоку, а також з переривання або з кількох потоків, то всі ці регістри нам потрібно зберігати при перемиканні контексту.

На картинці нижче показано, як виглядає стек при ввімкненому та вимкненому FPU. Бачимо, що приріст при використанні пам’яті значний. Тому, якщо ми вмикаємо FPU і використовуємо його з різних контекстів та потоків, ми одразу маємо бути готові до того, що час перемикання між ними зросте, а також буде витрачатися більше пам’яті. Ми одразу маємо збільшити стек у всіх своїх задачах, незалежно від того використовуються в них обчислення з плаваючою комою чи ні. До того ж, сам context switch буде працювати повільніше. Деякі операційні системи мають можливість відслідковувати (вибирати) чи використовується FPU задачею чи ні. І, як наслідок, зберігати або ж відновлювати FPU-регістри — тільки якщо в перемиканні контексту беруть участь відповідні задачі.

ARM Cortex-M Exception stack frame

Ще один нюанс. Треба дуже уважно перевіряти чи ваш FPU підтримує розрахунки з double precision — обчислення з подвійною точністю. Більшість слабких мікроконтролерів підтримують тільки single precision (float) розрахунки, і якщо ви використаєте double, то згенеруються додатковий набір інструкцій, який буде емулювати обчислення з подвійною точністю.

На мою думку, треба позбавлятися від обчислень з плаваючою комою у системах, які потребують швидкодії.

Memory segments

Linker Garbage Collector

З чого складаються наші об’єктні файли та кінцевий виконавчий модуль? Із так званих memory-сегментів, тобто тих областей куди потрапляє:

  • скомпільований код (секція .text)
  • певні дані, ініціалізовані змінні (секція .data)
  • неініціалізовані змінні (секція .bss)

Тож коли компілятор компілює код (розглянемо C-код), на виході ми отримуємо набір об’єктних файлів, кожен з яких має відповідний набір секцій. Він може мати якісь додаткові секції, але ці три, що зазначені вище, обов’язково.

Потім, коли ми переходимо до етапу лінкування кінцевої програми, лінкувальник з’єднує ці сегменти, а memory layout файл вказує, де на пристрої вони будуть знаходитись. На етапі executable object module, вони ще не мають жорсткої прив’язки до пам’яті. Там є лише адресні інструкції, за допомогою яких лінкувальник, взявши memory layout файл, і будує кінцевий образ. Таким чином, ми знаємо, на які безпосередні адреси він має завантажуватись.

Структура об’єктного і виконавчого файлу та процес формування виконавчого файлу з об’єктних файлів

Компілятор працює таким чином, що всі функції, які є в цьому C-файлі, будуть потрапляти в єдину секцію .text, яка є в об’єктному файлі. Такий же механізм спрацьовує і для ініціалізованих та неініціалізованих змінних. Тож на етапі лінкування, лінкувальник завжди використовує секції: він не може викинути або замінити частину секції. В кінцевий виконавчий файл потрапляє завжди ціла секція. Це означає, що якщо в нашому файлі 10 функцій, а з них ми використовуємо лише одну — в наш кінцевий виконавий файл все одно потрапить секція з 10 функціями. Що є дуже неефективно з точку зору розміру кінцевої програми.

Як з цим боротися? Нам компілятор надає певний набір можливостей, зокрема -ffunction-sections і -fdata-sections, які вказують йому створити набагато більше секцій, а ніж три початкових. Кожна функція поміщається в окрему секцію, яка буде мати назву: .text.function_name. Таким чином для 10 функцій, ми отримаємо 10 секцій. Для 10 змінних — 10 секцій. Відповідно на етапі лінкування, лінкувальник буде брати тільки ті функції й дані, які реально використовуються.

На додачу, сам лінкувальник має бути готовим прибрати ті функції, що не використовуются. Це робиться за допомогую опції —gc-sections, тобто garbage collection sections: проходження по всім секціям до яких не має жодних звернень і видалення їх з кінцевого файла. Щоб це спрацювало, обов’язково треба задати entry point (-e / —entry) — точку з якої починається виконання програми. Якщо ви її не задасте і включите опцію —gc-sections, лікувальник просто викине всі секції, які у вас є і ви отримаєте виконавчий модуль розміром 0. Якщо ж ви вкажете entry point, лінкувальник побудує все дерево викликів у вашому коді і, відповідно, зможе позбутися тих частин коду і тих змінних, які туди не потрапили.

Що отримуємо?

-O0 — 491 Kb

-Os — 322,5 Kb (34,3% improvement)

-Os + GС — 281,3 Kb (42,7% improvement)

Whole program optimization

Link Time Optimization (оптимізація на етапі лінкування)

GCC компілятор складається із Front-end, Middle-end та Back-end. Де Front-end — це вхідна мова, якою ви компілюєте. Middle-end — це частина, яка генерує з цього коду псевдо-інструкції. І Back-end — це вже безпосередньо архітектура, яка відповідно цим псевдо-інструкціям, ставить вже реальний набір інструкцій, які використовуются вашою архітектурою.

Як влаштований компілятор

Отже на етапі Middle-end, коли компілюється код, генерується GIMPLE — внутрішня репрезентація коду, який вже протрансльований з вашого C-файлу. Оптимізація компіляції проводиться саме на цьому проміжному етапі, коли вказуєти -Os, -Ofast або будь-яку іншу опцію. Тобто оптимізується вже не кінцевий assembler, а саме GIMPLE репрезентація. І потім вже генеруються кінцеві інструкції під вашу архітектуру.

Процес перетворення програмних файлів в кінцеву програму (виконавчий модуль)

Для компілятора GCC є можливість увімкнути прапорець -flto. Що це нам дає? Коли компілятор компілює код, він, крім тих секцій, що ми розглянули, додатково вставляє секцію, яка містить в собі GIMPLE репрезентацію (і всі проміжні результати GCC Middle end). Тоді, вже на етапі лінкування, лінкувальник може ще раз викликати GCC Middle-end, зібрати всі GIMPLE репрезентації з усіх об’єктних файлів, і ще раз зробити оптимізацію кінцевого коду вже в одному величезному файлі. І вже після цього відтрансльований юніт генерує для нього фінальний асемблерний код. Це дає достатньо хороший результат. Адже ми оптимізуємо програму як одне ціле.

Що робити з пре-компільованими, не оптимізованими бібліотеками? У версії компіляторів, які використовують та підтримують Link Time Optimization, можна додати прапорець -fuse-linker-plugin. Тобто вказати, що компілятор має вибрати той набір бібліотек, які також мають секцію з GIMPLE репрезентацією. Таким чином GIMPLE репрезентація бібліотек об’єднається з кодом вашої програми, і відбудеться оптимізація всього тіла програми, включаючи бібліотечні функції. Ми використовуємо це при розробці власних пристроїв та отримуємо суттєвий приріст оптимізації.

Що отримуємо?

-O0 — 491 Kb

-Os + GC — 281,3 Kb (42,7% improvement)

-Os + GC + LTO — 257 Kb (47,7% improvement)

Зменшення розміру логувальних стрічок

Кожна система обов’язково мусить містити елементи логування. Вони використовуються в місцях, де немає доступу або немає засобів для налагодження, проте log-повідомлення все одно можуть допомогти локалізувати проблеми.

Зазвичай, якщо наша програма росте, кількість модулів та, відповідно, функціональність нашого пристрою збільшується — зростає і кількість log-повідомлень. Кожна така стрічка збільшує розмір кінцевого виконавчого модуля, а відповідно й використання пам’яті. Як ми можемо це оптимізувати? Давайте подивимось на одну із технік нижче.

Як зазвичай виглядають логи?

Чи є в нас місце для оптимізації?

«Кодування» стрічок логування

Крок 1. Створіть header file з усіма log-повідомленнями.

Крок 2. Використайте aliases для стрічок у всьому коді

Крок 3. Створіть словник відповідностей у JSON-форматі

Крок 4. Створіть скрипти для генерації альтернативних header-ів із закодованими стрічками на базі словника JSON

Крок 5. Створіть набір скриптів, щоб відтворити оригінальні log-повідомлення за допомогою словника JSON

Готово. Наші стрічки починають займати менше місця ніж оригінальні. А за рахунок скриптів, які проводять зворотній декодінг, ми можемо зберегти читабельність наших log-повідомлень при цьому не збільшуючи розмір програми.

Є ще один приємний бонус з точки зору безпеки. Якщо зловмисник випадково (або не випадково) отримає доступ до вашого пристрою і зможе побачити ці логи — йому буде вкрай важко щось там зрозуміти, на відміну від вас.

Кінцевий результат оптимізації

-O0 — 491 Kb

-Os + GC + LTO — 257 Kb (47,7% improvement)

-Os + GC + LTO + Enc Logs — 252,7 Kb (48,5% improvement)

Висновок

Підсумовуючи — ми розглянули, як можна використовувати архітектуру, компілятори та, власне, написання коду для оптимізації роботи пристроїв та систем з обмеженою пам’яттю. Сподіваюсь, мій досвід та практичні поради стануть у пригоді всім, хто працює з подібними системами. Запрошую всіх охочих ділитись власними досвідом та думками у коментарях. Дякую за увагу. Все буде Україна!

👍ПодобаєтьсяСподобалось20
До обраногоВ обраному8
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Взагалі-то викидають STL та exceptions.
А стосовно теорії оптимізації для швидкості ось класика www.agner.org/...​timize/optimizing_cpp.pdf

1а. Видел я в одном проекте сплошные заказы логов в виде


LOG_INFO("%s %s=%d; %s=%d", "subfoo", "buka", buka, "zuka", zuka);

очевидно, росло из вот таких подходов.
При этом целевая область как-то не была похожа на экономную по ресурсам (бинарник 250MB я нечасто видел, надо заметить...)

1б. Вариант таких компактифицированных логов явно напомнил OS/360:)
Приходит тебе нечто в виде

IEA0123A X=46 M=0 P=16

и лезешь в книжку типа Ц51.804.006 Д29, чтобы понять, что же случилось:)

2. Часто оказывается, что при -Os программа и работает быстрее:) чем вроде бы быстро должно было быть при всяких -Ofast. Ибо чтение из памяти.

3. Для GCC и Clang смешно сравнивать с -O0, это некорректно, потому что они создают там 100500 лишних операций на каждую строку кода. Хотя бы -Og. Можно ещё комплект readable_asm по образцу Linux.

Думав що тут буде щось цікаве про алгоритми та нестандартні підходи для вирішення певних задач, а тут перелік опцій компілятора та невеличкий рефакторінг логування.
Оце і все??
До чого тут клікабельний заголовок про написання оптимізованого коду??
Чи може я там щось не дочитав і існують такі флаги які з квадратичної складності роблять лінійну?
А як послухати тих ембедерів так там ціла магія недосяжна фуллстек макакам....

Дякую за відгук!
Стаття орієнтована на достатньо широке коло читачів так кожен з наведених підходів можна з достаньою кількістю зусиль застосувати на практиці. Нею я ніяк не хотів образити фуллстек розробників.
Нажаль опцій які аналізують алгоритми та зменшують їх складність зараз немає. Такі задачі є більше математичного характеру і однаково застосовні як для embedded, так і для web, cloud чи розробці для PC.

Пишу софт на go для embedded систем (buildroot linux). Мова деколи може рішати багато проблем)

Розкид інструментів в світі embedded систем дуже широкий і справді багато чого вирішує. Але моя особита думка, що якщо система підтримує Linux, то це вже не зовсім система з обмеженою пам’яттю :)

Ну як... На платі 32мб рама та 16мб флешки...
Не в все що підтримує linux можливо заткнути все що захочеш...

Як писати оптимізований код у системах з обмеженою пам’яттю

Ответ: тщательно )

ви можете викласти увесь код для того щоб результати можно було валідувати? «кодування» стрічок виглядає не реалістично (макроси будуть підставлені під час препроцессингу, тому код майже ідентичний, різниця тільки в тому що у вас там додаковий словник з’явиться), мабуть справа у вашому компілляторі або коді

до того ж в багатьох компілляторах э опція(приклад з GCC):
-fmerge-constants
Attempt to merge identical constants (string constants and floating-point constants) across compilation units.

This option is the default for optimized compilation if the assembler and linker support it. Use -fno-merge-constants to inhibit this behavior.

Enabled at levels -O1, -O2, -O3, -Os.

Я можу запевнити, що приклад з кодуванням застосовується в одному з реальних проектів над яким ми працюємо. Не певен чи можу викласти увесь код зараз, але спробую уточнити і якщо це не суперечитиме політикам конфіденційності, то обов’язково поділюсь.
«-fmerge-constants» не дасть Вам очікуваного результату, тому що буде усувати тільки дубльовані значення. Для прикладу стрічки «Custom string» і «Custom string 1» не будуть піддаватись вищевказаній оптимізації хоча і рівень співпадіння в них востатньо високий, але під оптимізацію підпадають тільки випадки коли повні співпадіння є лише в закінченні (тому що стрічки мають закінчуватись нульовим символом). Приклад який компілятор зможе добре заоптимізувати це «Custom string» і «1 Custom string» так як компілятор залишить тільки «1 Custom string» і підставить посилання на 2й елемент у всі місця де використовується «Custom string».

ок ви можете пояснити чому зменьшуеться розмір коду у вашому випадку? за рахунок чого?

Так, звичайно.
Всі стрічки які є в програмі компілятор розміщує в секції .rodata яка зазвичай є частино .text сегменту. Зменшення розміру досягається за рахунок зменшення розміру самих стрічок. Так для прикладу стрічка «Custom string» може бути поставлена у відповідність стрічці «а» (через словник). Таким чином в кінцевий виконавчий файл потріпляє на 12 (при даному прикладі) бай менше. А таких стрічок може бути достатньо багато. Після такої підстановки пристій починає друкувати нікому не зрозумілі логи типу «a», «b», «aa:10» і тому подібне, але у Вас є словник, тому пропустивши цей вивід через python скрипт у вас на комп’ютері і підставивши правильний словник ви можете зробити зворотнє перетворення в читабельну людиною інформацію.

а то ви розкодовуете не під час виводу, а під час аналізу логу, ну тоді зрозуміло

цікаво почитати. дякую

Підписатись на коментарі