Proč se vyplatí použít StringBuilder

Tomáš Herceg       17.08.2010       C#, VB.NET       13720 zobrazení

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.

 

hodnocení článku

2 bodů / 2 hlasů       Hodnotit mohou jen registrované uživatelé.

 

Nový příspěvek

 

Diskuse: Proč se vyplatí použít StringBuilder

Zdravim, chtel bych se zeptat.

Da se pouzit i StringBuilder kdyz nevime presny pocet pruchodu ?

A tim padem nemuzeme pouzit FOR, ale While ?

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Samozřejmě. Četl jste ten článek? StringBuilder si nejdřív naalokuje pár bajtů a když mu to nestačí, naalokuje nové pole. Takhle to může dělat jakkoliv dlouho (dokud nedojde paměť) a nemusí vědět, kdy už bude konec.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Aha, díky, trochu mě mate

 
var sb = new StringBuilder(10000000);

nahlásit spamnahlásit spam 0 odpovědětodpovědět

No ten parametr tam dát můžete a nemusíte. Když ho tam dáte, bude to o trochu rychlejší (i když rozdíl není tak velký), protože potřebná paměť se naalokuje hned. Pokud ho tam nedáte, začne se s nějakou výchozí velikostí (16 bajtů nebo něco podobně malého) a jakmile místo dojde, naalokuje se výdy 2x větší buffer.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Toto je velmi zajimavé a hlavně prakticky použitelné. Ještě odbočím. Dá se "nějaký uklízeč" pustit i chtěně ? Něco ve smyslu, mám na tomto místě v programu čas a tak uklidím ?

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Zajisté, ona metoda je GC.Collect.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Diskuse: Proč se vyplatí použít StringBuilder

Existuje nějaká možnost, jak mít Muttable String podobně jako ve StringBuilderu, ale s podporou IndexOf, IndexOfAny atp? StringBuilder podporuje pouze Replace.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Můžete použít:

// Máte stringbuilder sb s textem.
// Můžete použít:
sb.ToString().IndexOf(vastext);
// apod.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

ToString ten řetězec ale kopíruje (z obsahu StringBuilderu vytvoří nový) a je to tím pádem pomalé.

nahlásit spamnahlásit spam 1 / 1 odpovědětodpovědět
                       
Nadpis:
Antispam: Komu se občas házejí perly?
Příspěvek bude publikován pod identitou   anonym.

Nyní zakládáte pod článkem nové diskusní vlákno.
Pokud chcete reagovat na jiný příspěvek, klikněte na tlačítko "Odpovědět" u některého diskusního příspěvku.

Nyní odpovídáte na příspěvek pod článkem. Nebo chcete raději založit nové vlákno?

 

  • Administrátoři si vyhrazují právo komentáře upravovat či mazat bez udání důvodu.
    Mazány budou zejména komentáře obsahující vulgarity nebo porušující pravidla publikování.
  • Pokud nejste zaregistrováni, Vaše IP adresa bude zveřejněna. Pokud s tímto nesouhlasíte, příspěvek neodesílejte.

přihlásit pomocí externího účtu

přihlásit pomocí jména a hesla

Uživatel:
Heslo:

zapomenuté heslo

 

založit nový uživatelský účet

zaregistrujte se

 
zavřít

Nahlásit spam

Opravdu chcete tento příspěvek nahlásit pro porušování pravidel fóra?

Nahlásit Zrušit

Chyba

zavřít

feedback