Profilování a optimalizace programů

[  Profilování  |  Profilery  |  GCC a gprof  |  Callgrind a KCachegrind  |  Tipy pro optimalizaci  ]

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. Pomocí programu prof, resp. gprof se pak zobrazí výsledky analýzy v čitelné formě.

$ 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. Jedna ze zobrazených tabulek pak může vypadat takto:

  %   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ýznam jednotlivých sloupců je následují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.

Callgrind a KCachegrind

Posledním přístupem, který si zde ukážeme je použití programů Callgrind a KCachegrind. Callgrind je modul programu valgrind. 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á.

$ valgrind --tool=callgrind ./program -parametry

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 například programem KCachegrind.

KCachegrind

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.

Tipy pro optimalizaci programů

Neoptimalizujte dokud to není nutné

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);
}

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.

Pro účely zkoumání programu pomocí profileru může být užitečné, když program přeložíme zároveň s přepínačem pro optimalizaci a pro generování ladících informací. Například program KCachegrind potom dokáže zobrazovat části zdrojového kódu včetně hodnocení ceny jednotlivých řádků programu.


Autor: David Martinek. Poslední modifikace: 9. October 2011. Pokud v tomto dokumentu narazíte na chybu, dejte mi prosím vědět.