Na svém kurzu Výkonnost a rozšiřitelnost aplikací, který školím v Gopasu, mám jedno poměrně pěkné demo, na kterém je vidět, proč se vyplatí použít StringBuilder místo klasického sčítání stringů.
Je to vlastně taková matematická úloha – kolik paměti naalokuje následující kód?
var str = string.Empty;
for (int i = 0; i < 100000; i++)
str += (char)(i % 26 + 65);
return str;
Nevinná smyčka, která stotisíckrát do jedné stringové proměnné přidá na konec jeden znak.
Tak co? Už to máte? Výsledek je neuvěřitelných 10GB! Datový typ string je totiž immutable, což znamená, že jakmile jej jednou vytvoříme, nedá se změnit. Cokoliv se stringem uděláte, vykoná jen to, že se vytvoří nový řetězec a obsah se zkopíruje (a případně mírně upraví).
Třeba takové str.Replace nemění původní proměnnou str, ale vrátí nám nový upravený řetězec. A stejně tak přičtení znaku na konec – vytvoří se nový řetězec a probíhá kopírování.
No dobře dobře, tak tedy se vytváří nový řetězec. Ale 10GB?? No tak počítejte se mnou – po prvním kroku cyklu je délka řetězce 1, po posledním je jeho délka 100 000 (v každém průchodu přidáme jeden znak). Průměrná délka řetězce je tedy něco jako 50 000 znaků. Protože string podporuje Unicode, ukládá se v paměti tak, že zabere 2 bajty na 1 znak. Průměrná velikost řetězce je tedy 100 000 bajtů.
No a protože v každém kroku cyklu původní řetězec změníme a vytvoříme nový (o 1 delší), tak celkem vytvoříme 100 000 nových řetězců. A jelikož průměrná délka je 100 000 bajtů, pak to celkem sežere, ať už chceme nebo ne, 10 000 000 000 bajtů paměti, což je slíbených 10GB. No dobře, podvádím, necelých 10GB, ale na tom až tak nezáleží.
“Ale no tak pane Herceg, netahejte nás za noc. Pustil jsem to, sledoval task manager a bralo to nějakých 40MB a celou dobu.” No samozřejmě, Garbage Collector vás nenechá naalokovat 10GB paměti, pokud ji skutečně nepotřebujete, a během toho cyklu se bude opakovaně spouštět. Stringy, ke kterým přičítáme, totiž v průběhu zahazujeme – nedržíme si je v žádné proměnné, proto se dají bezpečně uklidit. GC sleduje alokace a v okamžiku, kdy překročíte nějakou hranici (třeba každých 16MB, to záleží na platformě) provede garbage collection.
Pamatujte, že alokace paměti je v .NETu velmi rychlá, je to jedno přičtení k ukazateli, který určuje místo, kde končí obsazená paměť. Dealokace nepoužívaných objektů je ale velmi složitý proces, při kterém se pozastaví na chvilku všechna vlákna v aplikaci. Ideální je tedy snažit se psát tak, abyste GC nedali příležitost se spustit – prostě neakolujte pořád novou a novou paměť a nespustí se. Ne vždy to jde, je třeba zvolit zorumný kompromis. Ale naalokovat během pár sekund 10GB paměti je extrém.
Otázkou je, jak to opravit. No snadno, použijeme StringBuilder. Ten funguje trochu jinak – naalokuje si paměť předem a do ní můžeme metodami Append přidávat řetězce. V okamžiku, kdy paměť nestačí, naalokuje si dvakrát větší prostor a řetězec překopíruje (ve skutečnosti nemá jeden buffer, ale má jich víc a mají omezenou velikost, aby se nealokovaly zbytečně velké kusy paměti). No ale takhle nějak příbližně tato třída funguje.
Dejme tomu, že na začátku si udělá prostor 16 bajtů, když nestačí tak ho zvětší dvakrát. Nějaké bloky a maximální velikost, na to pro jednoduchost kašleme, spočítáme, kolik paměti by takový StringBuilder potřeboval.
Na začátku má 16 bajtů, po osmi přidaných znacích nestačí, tak naalokuje 32 bajtů, zase nestačí, tak 64 atd. Hledáme tedy nejnižší mocninu dvojky, která je větší než 200 000 bajtů, protože to je délka finálního řetězce. Touto délkou je 262 144 bajtů. Když sečteme tuhle a všechny menší mocniny dvojky, podle známého vzorečku 20 + 21 + 2n = 2n+1 – 1 zjistíme, že jsme nenaalokovali víc než dvojnásobek této hodnoty, totiž cca 512 kB. Docela rozdíl oproti 10GB, ne? Ano, zase podvádím, na konci se musí ještě zavolat ToString a výsledek nakopírovat do nového stringu, takže je to ještě o 200kB víc, ale čert to vem.
Můžete si říct, že GC to sebere, tak co mě to zajímá (i když takové lidi bych střílel). Ale dá se spočítat i časová náročnost obou řešení, vyjde to prakticky stejně. Kolik paměti naalokujeme, tolik musíme popsat, přitom zrovna tady nic nepřepisujeme, každý bajt zapíšeme nejvýše jednou. Popsat půl mega a deset giga paměti je taky rozdíl.
Na mém počítači řešení pomocí sčítání stringů trvá asi 15s, StringBuilder, který jsem nechal konstruovat 100x delší řetězec (tedy 10 000 000 znaků), aby výsledek byl vůbec měřitelný, zabral 34ms. Pokud navíc StringBuilderu v konstruktoru řeknete koncovou velikost řetězce, aby nemusel zvětšovat vnitřní buffery, zabere to jen asi 29ms (opět stavíme 100x delší řetězec, aby vyšlo něco jiného než 0).
A jak vypadá kód?
var sb = new StringBuilder(10000000);
for (int i = 0; i < 10000000; i++)
sb.Append((char)(i % 26 + 65));
Pozor, neznamená to, že StringBuilder máte používat i kdůli dvěma sečtením řetězců, on má také nějakou režii, takže u malých počtů a krátkých řetězců se to nevyplatí. Pokud ale sčítání provádíte opakovaně (desítky a více), pak už se StringBuilder rozhodně vyplatí a nebojte se ho použít. Najdete jej v namespace System.Text.