Předčasná optimalizace

Školení, která pořádám

Většina programátorů asi někdy slyšela citát Donalda Knutha: „Předčasná optimalizace je kořenem všeho zla.“ Někdo si to ale bohužel vykládá tak, že na výkonnost aplikace nemusí při návrhu a vývoji vůbec brát ohled a že případné výkonnostní problémy vyřeší až na konci podle toho, co mu řekne profiler. Je to nesmysl zhruba stejný, jako kdybychom aplikaci navrhovali a vyvíjeli bez ohledu na bezpečnost a zabezpečili ji až nakonec podle toho, co nám řekne bezpečnostní audit.

Při návrhu a vývoji aplikace musíme především volit správné algoritmy. Pokud existuje algoritmus, který řeší problém v logaritmickém čase, tak bychom neměli použít algoritmus, který ho řeší v lineárním čase, pokud jsou obdobně komplikované a celkově porovnatelné. Jinak se můžeme dostat do situace, kdy nám profiler řekne, že aplikace je příšerně pomalá a že k tomu přispívá tisíc různých míst, které musíme všechny projít a opravit.

Jak vypadá příklad kódu psaného bez ohledu na výkonnost? Třeba takhle:

<?php
$unique = array();
foreach ($strings as $string) {
    if (!in_array($string, $unique)) {
        $unique[] = $string;
    }
}
?>

Kód prochází všechny prvky pole a u každého se kouká, jestli už je v jiném poli. Funkce in_array má lineární časovou složitost, protože prochází jeden prvek zkoumaného pole po druhém. Celková složitost je tedy kvadratická.

Pominu-li existenci funkce array_unique, jak by vypadal kód, který je navržen s ohledem na výkonnost?

<?php
$unique = array();
foreach ($strings as $string) {
    $unique[$string] = true;
}
$unique = array_keys($unique);
?>

Kód má lineární časovou složitost, protože zápis prvku do haštabulky se provede amortizovaně v konstantním čase. Není nijak složitější, dokonce je kratší. Není tedy jediný důvod ho nepoužít.

Další příklad načítá data z databáze:

<?php
$result = mysql_query("SELECT * FROM article");
while ($row = mysql_fetch_assoc($result)) {
    $comments = mysql_result(mysql_query("SELECT COUNT(*) FROM comment WHERE article_id = $row[id]"), 0);
    // ...
}
?>

Kód pokládá lineární počet dotazů do databáze a při velkém počtu článků bude nesnesitelně pomalý. Po dokončení aplikace se to snadno nedozvíme, protože počet článků v databázi bude malý. Správný kód položí dotazů konstantní počet, např. takto:

<?php
$result = mysql_query("
    SELECT article.*, COUNT(comment.id) AS comments
    FROM article
    LEFT JOIN comment ON article.id = comment.article_id
    GROUP BY article.id
");
while ($row = mysql_fetch_assoc($result)) {
    $comments = $row["comments"];
    // ...
}
?>

Kód je tentokrát o něco složitější, čímž se dostáváme k tomu, proč je důležité aplikaci už navrhovat s ohledem na výkonnost. Pokud si uvědomíme, kde chceme používat jaké algoritmy, tak můžeme zvolit abstrakci, která kód učiní rychlejší a elegantnější zároveň. V tomto případě třeba NotORM. Pokud to neuděláme na začátku, tak nejspíš skončíme s aplikací prolezlou neefektivním kódem, s kterým už těžko něco uděláme, aniž bychom aplikaci celou přepsali. Je to podobné jako si na začátku zvolit vhodný šablonovací systém, abychom později nemuseli hledat, kde jsme zapomněli napsat htmlspecialchars.

Při vývoji aplikace se tedy řiďte tímto pravidlem: Můžu použít algoritmus, který má lepší asymptotickou složitost a není přitom dramaticky komplikovanější? Měl bych ho použít. Zlepší zamýšlená změna pouze čas provedení jedné operace a ne to, kolik se jich provádí? Jde o předčasnou optimalizaci, nechte to na konec, pokud vám to poradí profiler. V každém případě se ale snažte mít aplikaci co nejpochopitelnější, často použitím vhodné abstrakce.

Přijďte si o tomto tématu popovídat na školení Výkonnost webových aplikací.

Jakub Vrána, Dobře míněné rady, 11.12.2013, diskuse: 11 (nové: 0)

Diskuse

Ondřej Mirtes:

Dbaní na časovou složitost algoritmů by se programátorům mělo do hlavy vtloukat víc, spousta jich o ní nemá ani tušení.

Líbí se mi třeba přístup autorů Redisu, kteří v dokumentaci u každé funkce uvádějí její složitost, např.: http://redis.io/commands/del Tohle by mělo být součástí dokumentace každého programovacího jazyka, abychom to nemuseli odhadovat či (nepřesně) měřit.

11.12.2013 00:11:24

O:

Pak zjistime, ze i select count() je prilis pomaly a zacneme si ukladat pocet komentaru primo do tabulky article, nasledne tedy mame opet jen select * from article.

11.12.2013 00:56:25

Jakub Vrána :

To je pěkná ukázka změny, kterou bychom měli provést až na základě toho, co nám odhalí profiler. Možná s výjimkou případu, kdy máme po ruce nějakou pěknou abstrakci, v tomto případě materializované pohledy.

11.12.2013 20:33:16

v6ak :

Optimalizace je vždy ekonomická otázka:

Obvykle se lepší asymptotická složitost vyplatí, pokud nejde o rozdíly mezi O(1) a O(log(n)) apod., ale o nějaký ten stupeň polynomu nebo O(log(n)) vs. O(n). Může to být podstatné i kvůli DDoSu, protože jako útočník bych se soustředil právě na špatně optimalizovanou stránku, aby např. lehla DB.

Ale není to pravidlo. Například můžu mít neoptimální stránku v administraci, ke které se bude přistupovat jednou za rok. Tam může být i rozdíl mezi O(1) a O(n^3) v některých případech bezvýznamný a útočník tudy DDoS asi neudělá. Samozřejmě, nebudu dělat velkou složitost schválně, ale pokud by to bylo výrazně víc práce, možná by se to nevyplatilo.

Navíc, pokud bych kvůli tomu například muset vytvořit nový index, který se jinde nepoužije, bylo by to i plýtvání výpočetními zdroji. Byť asymptoticky OK. (Vím, toto zavání předčasnou optimalizací :) )

12.12.2013 23:14:14

Jakub Vrána :

Důležité je hlavně to, aby se nad výkonností programátoři zamýšleli. Často se totiž setkávám s tím, že tam fláknou první algoritmus, který je napadne, aniž by zvážili jakékoliv alternativy. Obhajují si to tím, že by to byla předčasná optimalizace. Přitom efektivnější algoritmus by mohl být dokonce jednodušší (viz příklad v článku).

Co se stránky v administraci týče, tak já se kloním k tomu, aby byla optimalizovaná i ta, protože pomalá aplikace je uživatelsky strašně nepříjemná. Když se třeba nějaký report nahraje obratem, tak se na něj budu chodit koukat a třeba z toho vyvodím nějaké důsledky. Když se bude nahrávat dlouho, tak tam chodit nebudu a třeba tím přijdu o důležité informace. Jednoduchý report se dá poslat i e-mailem, ale může mít třeba nějaké filtry a řazení, takže s ním potřebuji pracovat interaktivně.

Samozřejmě je potřeba zvážit, jestli za to dodatečná práce stojí (třeba zpomalení všech uživatelů aktualizací indexu při každé změně proto, aby se zrychlilo načtení stránky v administraci).

13.12.2013 17:29:40

v6ak :

"je potřeba zvážit, jestli za to dodatečná práce stojí"

O tom jsem přesně psal. Na _některých_ místech se to prostě vyplatit nemusí.

"třeba zpomalení všech uživatelů aktualizací indexu při každé změně proto, aby se zrychlilo načtení stránky v administraci"
Toto může být svým způsobem taky předčasná optimalizace :)

14.12.2013 18:24:13

jozko:

Pekny clanok. Ked uz sa v clanku spomenul sablonovaci system, musim sa opytat... Mne sa paci ako sablonovaci system pouzit rovno PHP, vyhodu v tom vidim, ze je to rychlejsie(alebo netreba cache) a netreba sa ucit ziadny sablonovaci system.

Toto je moje riesenie a chcem sa opytat na spatnu vazbu od diskuterov:
1. controller nahadze veci do view
2. pri zavolani metody view->render sa na vsetky premenne objektu view zavola funkcia htmlspecialchars
3. pri zavolani metody view->render sa taktiez vytvori objekt literal, ktory obsahuje znova vsetky premenne, ale tentoraz nie su vobec osetrene
4. v sablone vypisujete premenne $this->premenna a uz su osetrene a ked chcete neosetrenu premennu, tak vypisujete $this->literal->premenna

Chcem to pouzit do vacsieho projektu a chcem sa opytat, ci tom vidite nejaku vaznu medzeru. Dakujem

14.12.2013 22:31:31

v6ak :

"ze je to rychlejsie(alebo netreba cache)"

To bych považoval za dobrý příklad předčasné optimalizace. Strojový čas je levnější než čas programátora a typicky se to nevyplatí, pokud ta aplikace nebude mít brutální množství uživatelů. A i pokud bude, je obvykle stejně výhodnější si napsat nějaký kompilátor jako je třeba Latte, který zkompiluje šablonu do PHP. (To je možná ta cache, o které píšeš, nejsem si ale úplně jist.) Zabere to něco málo diskového prostoru a jednorázově něco málo času při kompilaci, ale ani při velké fantazii mě nenapadá příklad, kdy by to bylo dražší.

"netreba sa ucit ziadny sablonovaci system"

Naučit se šablonovací systém je investice. Pro základní použití je to navíc celkem malá investice, která se brzy vrátí. Navíc v některých šablonovacích systémech (např. Latte a Twirl) lze používat kód toho obecného programovacího jazyka (PHP v Latte, příp. Scala v Twirl), takže se není potřeba bát, že by najednou byl šablonovací systém malý a člověk si s tím nevěděl rady. Je to určitě varovné znamení, zvlášť pokud se to stává často, ale pořád lepší než používat čistý jazyk na šablon všude, zvlášť v případě PHP.

To oescapování proměnných může vést ke zmatku, když se k tomu dostane člověk, který to nezná. Pokud z názvu proměnné nevyplývá jinak, nečekám, že je obsah jakkoli escapován (pro HTML, URL, Javascript, CSS, SQL, ...), a tedy že echo $name vypíše hodnotu $name bez escapování. Vím, to lze použít i jako argument proti šablonovacímu systému, ale ten aspoň člověku nedává falešný pocit, že ví, co to znamená.

Chce to nejen escapovat, ale escapovat správně (viz http://php.vrana.cz/context-aware-html-escaping.php ) a ani to někdy nestačí, když člověk napíše něco jako <a href="<?php echo htmlspecialchars($link);?>">WWW</a> a do $link se dostane javascript://%0d%0aalert(%22XSS%22). Některým těžko viditelným problémům se věnuje například http://php.vrana.cz/reseni-alert-1-to-win.php (doporučuju každopádně).

15.12.2013 09:35:24

mastodon't:

Já v prvním nástřelu volím kód nejprostší, s nejméně úskalími, klidně i delší, dobře komentovaný, hlavně jednoduchý na přečtení a blbuvzdorný. Pokud zafunguje a vím, že to není nejlepší řešení, mám špatné svědomí a pomyslný červík v mé hlavě mi nenechá tenhle hřích zapomenout a vrtá tak dlouho, dokud to nepřepíšu.

19.12.2013 23:56:43