Jak na pro­jek­ty v ja­zy­ce C

© Damig, 2004 – 2023
Koncept
Listování kapitolami

Profilování a optimalizace programů

Sekce

Profilování

Profiler je program, který umí statisticky analyzovat, ve kterých funkcích a cyklech program tráví nejvíce času. Jen takto vytipované části kódu pak má smysl optimalizovat. Je zbytečné ztrácet čas optimalizováním funkce, která se při běhu programu vyvolá jednou a program v ní stráví pár milisekund.

Profilování se obvykle skládá se dvou kroků. První krok můžeme nazvat měřením. Jde o získávání statistických údajů o běžícím programu. Tyto údaje se obvykle ukládají do nějakého pomocného logovacího souboru. Zaznamenávají se do něj zejména počty vyvolání jednotlivých funkcí, počty iterací v jednotlivých cyklech, počty přístupů do paměti (cache, RAM), případně i počty přístupů na disk nebo k jiným zdrojům (síť, různá zařízení, atd.). Dále se zaznamenává i doba strávená při těchto zaznamenaných činnostech.

Druhý krok profilování lze nazvat profilovací analýza. V tomto kroku získáváme z naměřených údajů různé statistiky. Existují programy s grafickým rozhraním, které umožňují nejenom spočítat, která funkce byla volána nejčastěji, ale dokáží se na naměřená data podívat z různých úhlů a zobrazit výsledky přehledně pomocí tabulek nebo grafů. Pomocí profilovací analýzy se obvykle snažíme vytipovat ta místa programu, v nichž program tráví nejvíce času. Tím, že získáme přehled o tom, jak se jednotlivé funkce podílejí na celkové době běhu programu nebo na přístupu k jiným zdrojům (paměť, síť, atd.), se můžeme lépe rozhodnout která místa a jakým způsobem budeme optimalizovat.

Profilery

Vysvětlili jsme si, že profilování se skládá ze dvou kroků, měření a analýzy. Tomu odpovídá i rozdělení nástrojů pro profilování. Jedna část nástrojů se zaměřuje na sbírání údajů o běhu programu, další programy se pak zaměřují na analýzu a prezentaci naměřených dat.

Generování údajů o běhu programu úzce souvisí s instrumentací programů. Jednoduchou analýzu můžeme provádět sami tím, že do svého kódu doplníme vhodné výpisy, pomocí nichž poté spočítáme, kolikrát program navštívil sledovaná místa v programu. Vhodné je umístit výpisy na začátky a konce všech funkcí a také všech cyklů, protože to jsou místa, kde program typicky tráví nejvíce času. Nevýhodou tohoto přístupu je pracnost a nespolehlivost. Snadno můžeme na některé významné místo zapomenout. Další nevýhodou může být i fakt, že takto doplněná instrumentace činí zdrojový kód méně přehledným.

Další možností je generování dat pro profilovací analýzu automatizovaným způsobem buďto samotným překladačem nebo specializovaným programem. Princip sběru dat zůstává podobný jako při ruční instrumentaci zdrojového kódu. Rozdíl je ale v tom, že nyní zůstává zdrojový kód nedotčený.

GCC a gprof

Principiálně podobný způsob sběru dat jako ruční doplňování kódu o pomocné výpisy nabízejí samotné překladače. Pokud se budeme zabývat programováním v jazycích C a C++ a použijeme překladač GCC, můžeme snadno získávat profilovací data tak, že program přeložíme s přepínačem -p, resp. -pg. Překladač pak přímo do výsledné aplikace doplní kód, který po spuštění programu generuje tzv. graf volání (call graph) a uloží jej do souboru gmon.out. Viz ukázka 1.

Pomocí programu prof, resp. gprof se pak zobrazí výsledky analýzy v čitelné formě. Viz ukázka 2. Význam jed­not­li­vých sloup­ců je ná­sle­du­jí­cí.

  • % time - Procentuálně vyjádřený celkový čas, který program strávil v této funkci.
  • cumulative seconds - Celkový čas v sekundách, které program strávil v této funkci včetně součtu časů strávených ve funkcích volaných z této funkce.
  • self seconds - Čas v sekundách, které program strávil výhradně v této funkci. V tomto údaji nejsou započítány funkce, které jsou z této funkce dále volány.
  • calls - Počet volání této funkce.
  • self ms/call - Průměrný počet milisekund strávených při vykonávání kódu této funkce při jednom zavolání.
  • total ms/call - Průměrný počet milisekund strávených v této funkci při jednom zavolání. Údaj zahrnuje i čas strávený ve funkcích volaných z této funkce.

Tento přístup k profilování má své výhody i nevýhody. Výhodou je, že zdrojový kód programu zůstává nedotčený a vše za nás udělá překladač. Nevýhoda tohoto přístupu se projeví u aplikací, které jsou složeny z více knihoven, kdy některé části aplikace jsou přeloženy s přepínačem pro generování profilovacích informací a některé ne. 

$ gcc -prepinace -pg program.c -o program
$ ./program -parametry
$ gprof ./program
Všimněte si, že program gprof má jako parametr sledovaný binární program. 
     %  cumulative      self              self    total           
  time     seconds   seconds    calls  ms/call  ms/call  name    
  0.00        0.00      0.00      243     0.00     0.00  isBadNumber
  0.00        0.00      0.00       81     0.00     0.00  bToC       
  0.00        0.00      0.00       81     0.00     0.00  bToR       
  0.00        0.00      0.00        9     0.00     0.00  isBlockSolved
  0.00        0.00      0.00        9     0.00     0.00  isColSolved  
  0.00        0.00      0.00        9     0.00     0.00  isRowSolved  
  0.00        0.00      0.00        1     0.00     0.00  _readMatrix  
  0.00        0.00      0.00        1     0.00     0.00  allocMatrix
Výsledná tabulka programu gprof. Z tabulky je vidět, že řešená úloha byla velice krátká, protože časové údaje jsou v podstatě nulové i u nejčastěji volané funkce isBadNumber. Pokud byla měřena typická úloha, program zřejmě nemá cenu optimalizovat.

Callgrind a KCacheGrind

Posledním přístupem, který si zde ukážeme je použití programů valgrind a KCacheGrind. Oba programy fungují pouze v operačním systému Linux. Program valgrind používá pro profilovací analýzu modul callgrind. Jeho přístup k získávání profilovacích informací je odlišný od předchozích přístupů. Valgrind funguje jako interpret programu, který sleduje, co program dělá. Praktické použití viz ukázka 3.

Zaznamenávaná data se standardně ukládají do souboru callgrind.out.pid, kde pid je číslo procesu. Tímto způsobem lze generovat profilovací údaje pro různé kombinace spouštěcích parametrů a vzájemně je porovnávat. Výsledný soubor lze prohlédnout a analyzovat programem KCacheGrind, viz obrázek 1.

Základní údaje, které KCacheGrind zobrazuje v pohledu Flat profile jsou tyto:

  • Incl. (including cost) - Celková cena výpočtu dané funkce, která zahrnuje i cenu všech funkcí, které jsou z této funkce volány. Lze přepnout mezi zobrazením absolutní hodnoty nebo procentuálního vyjádření vzhledem k celkové době výpočtu programu. Funkce main bude mít například vždy cenu zhruba 100%. Nejsem schopen říci v jakých jednotkách je vyjádřena cena výpočtu v absolutní hodnotě, ale pro nalezení nejvíce vytížených částí programu to není důležité.
  • Self (self cost) - Vlastní cena výpočtu dané funkce, která nezahrnuje cenu všech funkcí, které jsou z této funkce volány.
  • Called - Počet volání dané funkce.
  • Function - Jméno sledované funkce.
  • Place - Umístění sledované funkce ve zdrojovém souboru, modulu nebo knihovně.

Pomocí dalších pohledů lze zobrazit různé další zajímavé informace. Na obrázku je například zobrazen graf volání a mapa volaných funkcí, které zobrazují cenu výpočtu názorněji než tabulka.

Vedlejším efektem získávání profilovacích údajů simulačním způsobem je určité zpomalení vykonávaného programu (cca 5x, profilovací kód generovaný překladačem sice také zpomaluje, ale zřejmě výrazně méně), ale poskytuje to zajímavější informace než výše zmiňované přístupy. Výhodou callgrindu na druhou stranu je, že lze analyzovat prakticky hotové programy, včetně modulů a knihoven třetích stran, na jejichž překlad nemáme nejmenší vliv. 

$ valgrind --tool=callgrind ./program -parametry
Volání programu valgrind s modulem callgrind.
Program KCacheGrind se zobrazeným výsledkem profilovací analýzy provedené modulem callgrind.

Tipy pro optimalizaci programů

Neoptimalizujte nepodstatné

Ideální je vůbec neoptimalizovat. Dnešní překladače umí optimalizovat velice dobře samy. Když už se rozhodnete do optimalizace pustit, měli byste to mít dobře zdůvodněno. Předčasná optimalizace může způsobit více škody než užitku. Když začnete optimalizovat už v průběhu vytváření programu, když ještě nemáte ujasněno, jak bude program nakonec vypadat, může se vzápětí ukázat, že jde o zbytečné úsilí. Navíc přílišné optimalizace na úrovni zdrojového kódu dost často zatemňují podstatu řešeného problému. Zvláště nepříjemné to může být při práci v týmu.

Věnujte větší pozornost analýze řešeného problému

Analýza problému může být užitečnější než optimalizace. Výsledky optimalizace řešení s kvadratickou časovou složitostí budou i po velkém úsilí většinou horší než neoptimalizované řešení se složitostí lineární. Znalosti matematiky a teorie jsou v důsledku lepší než znalosti nejrůznějších exotických konstrukcí programovacího jazyka.

Zvažte použití statických inline funkcí

Norma jazyka ISO C99 zavádí možnost použití statických inline funkcí. Použití klíčových slov static inline před hlavičkou funkce (bližší informace viz dokumentace GCC) nemá žádný vliv na výsledné chování programu, ale překladač potom může takto označené funkce přeložit bez kódu pro volání funkcí. Výsledek je pak podobný, jako když se použije makro, ale s výhodou větší přehlednosti zdrojového kódu. 

static inline
int bToC(int b, int i, int order)
{
  return order * (b%order) + (i%order);
}
Ukázka static inline funkce. Musí jít o lokální, neveřejnou funkci modulu. Překladač do místa jejího volání přímo vkládá její kód.

Tímto způsobem nelze ošetřit všechny funkce. Hodí se to pro velmi jednoduché funkce. Když potom při překladu zapneme optimalizace, dojde ke zrychlení programu, protože se ušetří kód nutný pro zavolání funkce (alokace paměti na zásobníku, skok). Pokud jde o funkci, která je volána opravdu často, může být úspora významná. Nezapomínejte ovšem na předchozí rady.

Označení funkce jako inline je pro překladač jenom doporučení. Překladač se pokusí vytvořit efektivnější kód, až když zapneme generování optimalizovaného kódu pomocí přepínače. I když jsou optimalizace zapnuté, může překladač vyhodnotit, že funkci nelze přeložit efektivněji.

Listování kapitolami

Obsah