Pět optimalizací v .NET (které nepoužijete)

Během vývoje naší interní aplikace v Avastu jsme museli řešit nejeden problém s výkonem. Vždy jsme postupovali tak, že jsme nějakým způsobem změřili výkonnost aplikace a až na základě toho dělali příslušná opatření – a takový přístup bych doporučil vždy – nemá moc cenu odhadovat, co by asi tak mohlo stát za neuspokojivou výkonností, nejlepší je to změřit. Samozřejmě jsou ale vyložené boty, kterých se je třeba vyvarovat vždy. V tomto článku bych rád ukázal pár zajímavých triků pro vyšší výkonnost, které rozhodně nešlo jen tak vykoukat z kódu.

Naše aplikace je ale opravdu hodně zatížená, takže pravděpodobně většinu z těchto triků nikdy nebudete potřebovat. Na druhou stranu, výkonu je dneska sice dost, ale v okamžiku, kdy máte třeba aplikaci v cloudu a účtování podle spotřeby CPU, mohou se výkonností optimalizace vyplatit.

Volba datových typů

Zdálo se nám, že je naše aplikace docela žravá na RAMku, takže jsem na ni pustili memory profiler, který ukázal, že máme alokováno strašně moc stringů, přičemž drtivá většina z nich má velikost 64 znaků. Nebylo divu – v naší aplikace pracujeme se soubory a jako unikátní identifikátor používáme SHA256 hash jeho obsahu. Tento hash máme reprezentovaný vlastní vymazlenou třídou Sha256, která má vnitřně uloženou hodnotu jako string (vždy o velikosti 64 znaků). Rozhodnutí reprezentovat vnitřní stav stringem nemělo žádné opodstatnění – prostě to bylo první, co nás napadlo. Kdybych věděl, že budeme mít v aplikaci obrovské pole Sha256, tak bych o tom začal uvažovat a zamyslel jsem nad tím víc, ale protože jsou Sha256 rozšířené po celé aplikaci…
Takže řešení? Použít místo stringu (vždy o velikosti 64) byte[] (vždy o velikost 32). A poučení pro příště? Pokud je velká pravděpodobnost, že vznikne fakt hodně instancí nějakého typu, vyplatí se přemýšlet o velikosti tohoto objektu.

Nevěřte knihovnám

Už jsem řešil takových problémů s velmi rozšířenými knihovnami, že nevěřím ničemu, ani třídám přímo z .NETu – potenciální zdroje problémů si proklepávám přes ILSpy. I standardní knihovny .NETu implementují jen lidé.
Jednoznačně největším zklamáním pro mě byla implementace metody GetHashCode pro pole. Ale pěkně od začátku.
Při zkoumání obsahu paměti naší aplikace jsme zjistil, že něco smrdí okolo instancí Dictionary<Sha256, T> – viděl jsem, že tam jsou dlouhé lineární seznamy bucketů, což ukazovalo na problém v hashovací funkci (velké množství kolizí). Na tento problém ukazovaly i testy výkonnosti, protože bylo vidět, že se tráví docela dost času při prostém čtení z Dictionary (i v řádu jednotek milisekund!).
Naše třída Sha256 měla metodu GetHashCode() implementovanou tak, že se pouze volalo GetHashCode() na poli bajtů, které reprezentuje vnitřní stav. Ale hledat chybu v samotném .NETu? Nu nakonec se vyplatilo. Zjistil jsem, že u polí se hash počítá jen z posledních 8 prvků pole, což by bylo pravděpodobně ok. Větší problém je to, že to není naimplementované korektně a ve for cyklu indexují místo i pomocí 0. Takže se hash počítá jen z jednoho prvku pole, což u pole bajtů znamená, že v dictionary vznikne max. 256 bucketů. Nakonec jsem zjistil, že nejsem sám, kdo si tohoto problému všiml. Řešení bylo prosté a výkonnostní efekt okamžitý – upravili jsme metodu GetHashCode() třídy Sha256 tak, aby se počítalo se všemi prvky pole. Možná by stálo za zkoumání, jestli by v našem případě (vždy 32 prvků pole) nestačilo iterovat přes menší počet prvků, ale čtení z Dictionaries je nyní prakticky neměřitelné (vzhledem k náročnosti okolního kódu), takže jsme to dál neřešili.

Fakt nevěřte knihovnám

Hodně cachujeme. Víceméně to máme implementované tak, že máme dekorátory, do kterých si necháme injectovat naše jednoduché rozhraní IObjectCache, které má metody Get, Set, Remove – nic složitého. Konkrétní používaná implementace pak používala standardní ASP.NET cache. Cachujeme fakt masivně, takže nebyl problém mít v cache desítky, stovky milióny záznamů (o velikosti desítek GB). No ale když jsem viděl, že čtení z této cache je občas pomalejší než čtení přímo z databáze, musel jsem se podívat této standardní cache na střívka. A zabrečel jsem. Vytvoří se jen pár hashmap (násobky počtu procesorů), do kterých se to snaží všechno nasoukat. Takže následovala implementace vlastní in-memory cache.

Už vůbec nevěřte open-source knihovnám

Používáme databázi Postgres a z .NETu k ní přistupujeme pomocí standardního driveru Npgsql. Performance profiling ale ukázal, že se tráví hrozně moc času při vybírání connection z poolu. Při pohledu na kód přes ILSpy (na originální zdrojáky se nedá koukat) jsem se zhrozil – každé vybrání z libovolného connection poolu znamená lock. Máme docela dost databázových serverů (řekněme >10) a hodně čilý traffic, a když se lockuje na objektu sdíleném všemi (!) pooly…no comment.
Nejelegantnější řešení by bylo upravit přímo knihovnu Npgsql, ale celý projekt je tak strašně zprasený, že jsme to raději vyřešili tak, že jsme connection pooling v Npgsql vypnuli a implementovali si vlastní (pěkně transparentně pomocí dekorátoru, tj. změna na úrovni konfigurace).

ASM FTW!

Je zřejmé, že každá úroveň abstrakce si nějaký výkon vezme, a někdy se tak může vyplatit v kritických částech programu sestoupit o úroveň níže.
V Postgres používáme datový typ hstore (hashmapa), který při čtení dostáváme jako string, který je třeba naparsovat. To jsme dělali elegantně pomocí regulárního výrazu. Základní pravidla pro používání třídy Regex jsou jasná – stačí vytvořit jednu instanci (jedná se o immutable třídu) a nezapomenout specifikovat RegexOptions.Compiled. Ale u nás bylo i takovéto použití příliš pomalé (jak ukázalo měření).
Třída Regex funguje tak, že si vytvoří stavový automat, pomocí kterého pak provádí požadované operace. Sestoupení o úroveň níže tedy znamenalo napsat si automat pro daný regulární výraz ručně. A vyplatilo se!

Takže rada na závěr? Pište čistý kód a až pak měřte, měřte, měřte! A pokud to vypadá, že je problém v nějaké frikulínské knihovně, tak i tuhle eventualitu prověřte.

Příspěvek byl publikován v rubrice Programování a jeho autorem je Augi. Můžete si jeho odkaz uložit mezi své oblíbené záložky nebo ho sdílet s přáteli.

13 komentářů u „Pět optimalizací v .NET (které nepoužijete)

  1. Ahoj Augi,
    pěkný článek. Jen se zeptám k regulárním výrazům – zkoušel jsi i volbu “Regex.CompileToAssembly”?
    Pokud máš množinu regulárních výrazů, které používáš v aplikaci stále dokola, tak tohle je podle mě dostačující, resp. nikdy jsem nenarazil na to, že by nějaká další mikrooptimalizace regulárních výrazů měla pro aplikaci význam.

  2. Díky René!
    Ohledně těch regulárních výrazů – když jsem na to tehdy koukal (a teď jsem na to hodil oko znova), tak mi přišlo, že o kód generovaný RegexOptions.Compiled i Regex.CompileToAssembly se stará tatáž třída, z které jsou poděděné další třídy, které jen dělají jinou obálku, takže rozdíl v performance bude prakticky nulový.

    Nicméně teď jsem přidal do našeho benchmarku použití Regex.CompileToAssembly a vidím, že na našich datech má vždy o cca 5 % lepší výkonnost než RegexOptions.Compiled. Nicméně je to stále cca 5x pomalejší než ručně napsaný automat (60 řádek kódu).

    Ještě je tu možnost, že je ten náš regulár napsaný neefektivně, ale vytunil nám ho místní Perlový guru, tak snad ne 🙂

  3. Perlový guru by ho měl vytunit dobře, protože regulární výrazy v C# IMO nejvíc (IMO) odpovídají syntaxi RV v Perlu.:)
    Regex.CompileToAssembly je rychlejší, protože jde de facto o volbu

    (RegexOptions.Compiled. – počáteční režie na kompilaci výrazu, která je umořena v době kompilace assembly).

  4. Jj, ale jsou tam drobné nuance. Proto na některých místech (kvůli kompatibilitě) používáme přímo PCRE.

  5. Když jsem potřeboval třídu pro hash, tak jsem místo reference na pole, přímo do třídy přidal několik long fieldů, abych neztrácel paměť referencí a hlavičkou pole. Nevím jak v C#, ale Javě to může představovat extra režii až 24 bajtů na jednu instanci (předpokládám, že to bude podobně) a to bylo hodně, když šlo o MD5, který je dlouhý jenom 16B.

    Nicméně, když pracuješ s SHA256 nebo podobnými a chceš jeho hash code, tak stačí z něj vzít libovolné 4 bajty a výsledek je nejlepší jaký může být. Ideální hash (a SHA je jedním z nich) by měl mít naprosto uniformní distribuci – hash nějaké hodnoty by měl vypadat jako náhodné číslo a každá část hashe (např. první 4 bajty) by měla být nezávislá na všech ostatních segmentech. Žádná kombinace všech 32 bajtů nemůže poskytnout víc informací než první čtyři.

  6. Máš pravdu – uložit hashe do longů apod. je paměťově výhodnější. U nás za rozhodnutím použít pole bajtů stálo ještě to, že nějaké low-level knihovny, do kterých ty hashe hlavně cpeme, požadují pole bajtů. Tím jsme omezili počet prováděných konverzí.

    Ohledně toho SHA256 máš také pravdu, já jsem to do článku napsal hodně nepřesně (upravím to v něm). Jádro problému je v tom, že oni chtějí počítat hash přes posledních 8 prvků pole, ale ve for cyklu mají chybu a místo proměnné i tam mají 0 – takže se hash počítá jen z jednoho bajtu a v dictionary pak vznikne max. 256 bucketů.

  7. Pingback: Zajímavé novinky ze světa IT z 50. týdne 2013 | Igorovo

  8. Ty regulární výrazy jsou celkem zajímavé. To, co považujeme za regulární výrazy, se tak někdy jmenuje jen z historických důvodů. Ve skutečnosti mají ale vyšší sílu. Matchování Perlovských “regulárních” výrazů je, tuším, NP-úplný problém, některé “regulární” výrazy jsou snad i turingovsky kompletní. V praxi se mi v Javě podařilo u celkem jednoduchého výrazu dosáhnout nejspíš exponenciální složitosti.

    Vyšší možnosti regulárních výrazů jsou vykoupeny nižšími možnostmi automatických optimalizací. S klasickým regulárním výrazem by šlo udělat klasické automatické optimalizace (minimální konečný automat) a následně by se dala optimalizovat jeho realizace – ten základ nám totiž dostatečně popisuje teorie a je to celkem jednoduché.

    Navíc se regulární výrazy nepoužívají jen na zjištění, zda slovo patří do jazyka (se skutečně regulárním výrazem je to v O(n)), ale i na parseování textu, kde si už s O(n) nejsem úplně jistý. To může při některých jednodušších implementacích zdržovat vždy – i u metody vracející pouze booleovskou hodnotu, zda match uspěl.

  9. K tem pametovym narokum. Pokud je hodne instanci “maleho” typu, tak je dobre si to predtim proste spocitat. Tohle se tyka i napriklad hodne vnorenych instanci Dictionary ve kterych je ulozeno malo polozek, protoze rezie samotne implementace Dictionary bude vyssi nez tech polozek. Staci si pro tuto situaci napsat vlastni primitivnejsi implementaci IDictionary. Knihovny jsou vzdy kompromis pro obvykle situace, v extremnich situacich se ukaze ze ne vse se hodi univerzalne vsude.

    Ohledne GetHashCode(), neni od veci si precist Richtera 🙂

    Open source knihovny (a multithreading), naprosty souhlas.

  10. Vím,
    že ten dotaz bude možná trošku mimo, ale proč jako jednoznačný identifikátor nepoužíváte GUID?

  11. Pro jednoznačnou identifikaci používáme SHA256, protože se jedná o aplikaci, která pracuje se soubory, a SHA256 obsahu souboru se v našem oboru používá jako jednoznačný identifikátor souboru. Díky tomu můžeme používat SHA256 coby “přirozený klíč”.

Napsat komentář

Vaše emailová adresa nebude zveřejněna.