Rozpočet na mikrokontroléru a proč se ve smyčce nealokuje
Na počítači se otázka „je to dost rychlé“ obvykle nepokládá. V regulační smyčce, která má milisekundu na všechno, se pokládá pořád — a dá se na ni odpovědět počítáním, ne měřením.
Příklad: procesor 72 MHz, hrubě 4 takty na operaci, perioda smyčky 1 ms a rozumné pravidlo, že algoritmus si smí vzít polovinu rozpočtu. Kolik prvků se stihne setřídit?
| algoritmus | vejde se prvků |
|---|---|
| vkládáním | 132 |
| slučováním | 533 |
Tahle dvě čísla se nepočítají ze vzorce — najdou se tím, že se algoritmus spustí pro každé n a operace se spočítají. Právě proto, že ten vzorec je to, co se ověřuje.
Proč se v regulační smyčce nealokuje
Zdálo by se, že alokace paměti je rychlá, tak co na tom. Problém není rychlost, ale nepředvídatelnost:
- Doba trvání kolísá. Někdy je volný blok hned, jindy se musí hledat, jindy se musí sáhnout do systému. Nejhorší případ je řádově horší než průměr — a je to tentýž argument jako u jitteru v NetLabu.
- Fragmentace. Po hodinách běhu je paměť rozkouskovaná, a alokace, která první den prošla, přestane procházet. Selže tedy až v provozu.
- Uklízeč. V jazyce se správcem paměti navíc kdykoli přijde pauza, kterou nikdo neplánoval.
Proto se v real-time kódu alokuje jen při startu. Všechno, co smyčka potřebuje, se přidělí předem a pak se jen používá. Není to opatrnost — je to jediný způsob, jak může být nejhorší případ známý. A z toho plyne i volba algoritmu: slučování alokuje, tedy do smyčky nepatří, ačkoli je asymptoticky lepší.
Tři pravidla, která z toho vypadnou
- Ve smyčce se nealokuje. Vyrovnávací paměti se přidělí při startu.
- Rekurze má být omezená. Zásobník je na mikrokontroléru pár kilobajtů, a quicksort s nešťastným pivotem jde n úrovní hluboko (kapitola 6). Iterativní varianta nebo pevný strop.
- Nejhorší případ musí být znám. Algoritmus, jehož nejhorší případ je řádově horší než průměr, do smyčky nepatří, i kdyby byl průměrně rychlejší.
Ta tři pravidla jsou přesně to, co říká NetLab v kapitole 8 o síti. Je to tentýž argument: v reálném čase je předvídatelnost víc než rychlost.