Novinky v C# 4 a .NET Frameworku 4.0: Fine-grained paralelizmus

Po krátké prázdninové přestávce se dostáváme zpět k seriálu o nových vlastnostech ve verzích 4.0 .NET Frameworku a C#. Dnes nás čeká nahlédnutí pod pokličku fine-grained paralelnímu zpracování.

S nástupem vícejádrových a víceprocesorových strojů i do běžných kanceláří a na domácí stoly, také vzniká poptávka tyto jednotky efektivně využívat. Ačkoli lze namítnout, že v systému vždy běží dostatek procesů, aby všechny obsadil, ne vždy tyto procesy intenzivně pracují a tak je procesor(y) vytížen jen z části, i když by vaše aplikace mohla pracovat mnohem lépe.

Předchozí verze .NET Frameworku obsahovaly standardní podporu pro práci s vlákny. Dostačující pokud máte jasně definované paralelní cesty a máte tento problém plně pod kontrolou. Pokud však začnete vytvářet vláken o něco více, zbytečně se spotřebovává výkon v plánovači (scheduler). Odpovědí může být ThreadPool. Ikona .NET světa (a nejen .NET) Jeffrey Richter také mimo jiné tvrdí, že vlastní vlákna by měl člověk vytvářet jen velmi sporadicky a vždy používat ThreadPool. Bohužel ani ThreadPool není všelékem (viz. např. minimální možnost kontroly a správy „work items“ zařazených ke zpracování).

Jestliže máte problém, který lze dobře paralelizovat a zkusíte vytvořit vlákna (pro jejich lepší kontrolu) s plným využitím vašeho paralelizovaného algoritmu (typickým příkladem jsou různá procházení grafů apod.) můžete narazit na nepříjemné limity. Jak již bylo zmíněno, bude plánovač systému přetížen. Ztráty způsobené přepínáním kontextu také přestanou být zanedbatelné a nakonec každé vlákno zabere cca 1MB operační paměti, takže při větším než malém množství vyčerpáte dostupnou operační paměť.

Řešení těchto problémů se snaží adresovat nové objekty pro paralelní zpracování v .NET Frameworku 4.0. Tento balík vylepšení můžeme rozdělit na dvě základní kategorie – Parallel LINQ (PLINQ) a Task Parallel Library.

Parallel LINQ

LINQ přináší některé myšlenky z funkcionálně smýšlejících jazyků (Haskell nebo např. F#) a aplikuje je v imperativním světě. LINQ se také snaží unifikovat různé přístupy ke kolekcím, XML dokumentům, databázím, … Pokud již LINQ používáte a zkoušíte, kam až lze zajít, určitě jste si všimli, že velká část „příkazů“ neříká jak výsledek spočítat, ale jak chcete, aby výsledek vypadal – tj. neprogramujete imperativně, ale funkcionálně (částečně). Díky této abstrakci se přímo nabízí myšlenka zpracovat některé dotazy ve více vláknech na více procesorech. Taková „where“ podmínka na poli o milionech prvků se na 4 procesorech (nebo jádrech) provede jistě rychleji než na jednom a přitom její paralelizace je vskutku triviální.

A přesně tuto cestu prošlapává PLINQ. Dotazy, které lze paralelizovat jsou samozřejmě pouze ty, které se provádí lokálně, tj. provider je nedeleguje na jiný program jako je tomu kupříkladu v LINQ to Entities nebo LINQ to SQL, kde je dotaz vyhodnocen v RDBMS (a kde je pravděpodobně i mnohem efektivněji paralelizován).

Podívejme se na jednoduchý příklad:

int[] numbers = new[] { 1, 2, 3, 4, 10, 20, 30, 40 };
int[] evenNumbers = numbers.Where(n => n % 2 == 0).ToArray();
int[] evenNumbers2 = numbers.AsParallel().Where(n => n % 2 == 0).ToArray();

Druhý řádek získá z pole čísel pouze čísla sudá. Pokud je pole velké, bude průchod trvat velmi dlouho a zatížena bude pouze jedna výpočetní jednotka, neboť Where metoda je vlastně sekvenční průchod a testování podmínky. Naproti tomu třetí řádek, přidává volání AsParallel, jinak je shodný. Volání této metody přepne provádění z IEnumerable na (zjednodušeně řečeno) „paralelní IEnumerable“. Výsledek je pak získán mnohem rychleji. A nejen to, PLINQ za programátory řeší i otázku kolik vláken použít (a znovu použít) – podle počtu procesorů a jader. Pokud máte víceprocesorový/vícejádrový stroj, vygenerujte si obrovské pole a zkuste si uvedený příklad. Zrychlení se bude téměř blížit počtu procesorů/jader.

Možná vás napadá, proč musím jako vývojář, přidávat AsParallel, když framework by toto mohl udělat automaticky. Inu není to tak jednoduché. Jednou z klíčových problematických částí jsou tzv. side-effects (vedlejší efekty) a shared-state (sdílená část paměti). Bližší popis je mimo rozsah tohoto článku a tak odkážu zájemce na zdroje z vašeho oblíbeného vyhledávače.

Kromě paralelizace linqových extension metod vás mohlo napadnout, že když je např. „where“ jen sekvenčním průchodem, jde vlastně o ekvivalent for smyčky a tedy i tuto by mohlo být jednoduché paralelizovat. Pokud se odstíníme od problémů jako zmiňovaný shared-state nebo side-effects (čímž provedeme velké zjednodušení), je tomu skutečně tak. A ani zde .NET Framework nezahálí.

Pro smyčky, které jsou obecně horkým kandidátem na paralelizaci, nabízí třída Parallel několik statických metod – For, ForEach, Invoke.

Nejprve jednoduchý příklad:

for (int i = 0; i < numbers.Length; i++)
{
	numbers[i] = numbers[i] * numbers[i];
}

Parallel.For(0, numbers.Length, i =>
	{
		numbers[i] = numbers[i] * numbers[i];
	});

Letmým pohledem zjistíte, že přepis je otrocký. Jednoduše tak můžete zrychlit často prováděné dlouhé smyčky a víceméně zadarmo. Jen je třeba dávat pozor, jestli váš výpočet může ve více vláknech bezpečně běžet (viz výše), což nemusí být vždy triviální, a případně, je-li to možné, jej upravit.

Metodu ForEach, asi není třeba dlouze představovat. Stejně jako for i foreach smyčku můžete jednoduše spustit ve více vláknech. Obě metody mají množství variací a možností jak chování ještě jemněji nastavit.

Poslední metoda Invoke slouží ke spuštění několika procedur, samozřejmě paralelně. Nápadně se tedy podobá použití ThreadPoolu, avšak nabízí dodatečné možnosti v podobě objektu ParallelOptions pro ovlivnění chování.

Task Parallel Library

Použití PLINQu a především třídy Parallel již dává poměrně bohaté avšak stále jednoduše uchopitelné nástroje, jak program zrychlit. Každý, kdo má vícevláknové programování rád (jako např. já), ale cítí, že je zde ještě prostor pro vylepšování. Tento velký prostor částečně zaceluje Task Parallel Library.

Task

Jak jsem zmínil v začátku, máte-li algoritmus vhodný k paralelizaci a to k hodně velké, narazíte s klasickými vlákny na mnoho problémů. Thread je prostě kanón na vrabce. To co potřebujete, je třída Task, která představuje základní stavební kámen pro tzv. fine-grained paralelizmus. Neorientujeme se nyní již na vlákna, ale na úkoly – ty mohou běžet na jednom nebo více procesorech/jádrech. My pouze říkáme, co je možné spustit nezávisle na sobě a volitelně očekáváme výsledek.

Pojďme se podívat na příklad použití. Původně jsem chtěl demonstrovat využití na klasickém případu traverzování stromu, nakonec však zkusíme něco jiného. Zkusíme udělat sumu prvků v poli a umíme udělat sumu jen pro jedno a dvouprvková pole (ano, je to jen ukázka).

static int SumItems(int[] items)
{
	Contract.Requires(items.Length > 0);

	switch (items.Length)
	{
		case 1:
			return items[0];
		case 2:
			return items[0] + items[1];
		default:
			int[] half1 = items.TakeWhile((_, i) => i < items.Length / 2).ToArray();
			int[] half2 = items.SkipWhile((_, i) => i < items.Length / 2).ToArray();
			Task<int> t1 = Task.Factory.StartNew(() => SumItems(half1));
			Task<int> t2 = Task.Factory.StartNew(() => SumItems(half2));
			return t1.Result + t2.Result;
	}
}

Metoda pro více než dvouprvkové pole toto rozdělí na dvě poloviny a z těchto půlek se pokusí opět rekurzí spočítat výsledek. Výpočet v obou polovinách je možné provádět paralelně a také se tak děje. Pokud algoritmus zkusíte napsat čistě pomocí vláken, při jisté velikosti (a tedy počtu vláken) vám aplikace přestane fungovat – dojde paměť. U ThreadPoolu je problematické čekání na dokončení a zjištění výsledku. Všechny tyto „neduhy“ vyřeší použití právě třídy Task. Pomocí ní vytvoříte jednotlivé úkoly (StartNew), které následně framework distribuuje na jednotlivé procesory/jádra a můžete nejen kontrolovat stav, ale i jednoduše získat výsledek. A pokud se na výsledek dotážete dříve, než je připraven, program se zastaví a počká na něj.

Instanci třídy Task můžete vytvořit přímo pomocí konstruktoru a poté výpočet spustit nebo můžete využít factory metod, jako v mém případě. Pro pohodlné využití nabízí třída několik metod a vlastností, jejichž absence u objektů Thread a ThreadPool způsobovala zbytečně mnoho práce okolo.

Task.Cancel a Task.CancelAndWait

Metody slouží ke zrušení úlohy. Vhodné například když víte, že další výpočty již nepotřebujete a můžete okamžitě skončit. Pokud úloha ještě nebyla spuštěna, bude jednoduše odstraněna z fronty.

Task.ContinueWith

Pokud jste někdy slyšeli o tzv. continuation passing style, vězte, že přesně tato metoda vám umožní toto provést. Metoda bere jako parametr metodu, která se spustí, jakmile je provádění této úlohy dokončeno. Můžete tak napsat:

Task.Factory.StartNew(() => SumItems(Enumerable.Range(1, 99999).ToArray()))
	.ContinueWith(t => Console.WriteLine(t.Result));

Což přibližně odpovídá (na výsledek t.Result se automaticky „počká“):

Task<int> t = Task.Factory.StartNew(() => SumItems(Enumerable.Range(1, 99999).ToArray()));
Console.WriteLine(t.Result);

Task.CreationOptions

Každá úloha může být vytvořena s několika různými vlastnostmi, které ovlivňují její výsledný běh. Slouží k tomu výčtový typ TaskCreationOptions.

• DetachedFromParent: určuje, že vazba parent-child je v tomto případě přetržena a nově vytvářená úloha nemá předka.
• LongRunning: dává signál pro plánovač úloh, že tato úloha se bude provádět déle a thread, který ji bude provádět, bude déle obsazený.
• PreferFairness: instruuje plánovač na provádění stylem „dříve vytvořená úloha, bude dříve spuštěna“.
• RespectParentCancellation: určuje, že zrušení (Cancel) předka úlohy, zruší i potomky.

Task.Exception

Umožňuje přečíst neošetřenou výjimku, pokud se při provádění úlohy vyskytla. Výjimky samozřejmě nejsou propagovány do hlavního vlákna aplikace, takže pokud je možné, že bude výjimka vyhozena, je vhodné před další prací s úlohou resp. výsledkem ověřit, jestli byl výpočet úspěšně dokončen či nikoli.

Task.IsCanceled, Task.IsCancellationRequested, Task.IsCompleted, Task.IsFaulted

Tyto IsXXX vlastnosti umožňují zjistit, jaký je aktuální stav úlohy – zdali byla zrušena, bylo požádáno o zrušení (ale ještě nedošlo ke zrušení), byla dokončena či byla násilně ukončena kvůli neošetřené výjimce.

Task.Parent

Určuje nadřazenou úlohu.

Task.Result

Výsledek úlohy, pokud se jedná o Task<TResult>. Pokud potřebujete z úlohy vrátit více výsledků, je třeba je zabalit do objektu s několika vlastnostmi a vrátit tento objekt, případně použít objekt Tuple (viz předchozí díly seriálu).

Task.Start

Spustí úlohu, tj. je zařazena do fronty pro zpracování.

Task.Status

Udává aktuální (detailní) status úlohy. Property může nabývat hodnot z výčtu TaskStatus.

Task. Wait

Vyčká na dokončení úlohy s volbou čekat pouze definovaný timeout. A umožňuje případně využít objekt CancellationToken ke sledování „co se dějě“.

Třída Task event. Task.Factory ještě obsahuje několik statických metod, které se většinou zaměřují na práci s více úlohami najednou WaitAll, WaitAny, ContinueWhenAll, ContinueWhenAny, FromAsync apod. Jejich použití je velmi přímočaré.

Pokud máte rádi seriózní práci nebo i jen hraní s vícevláknovými aplikacemi a algoritmy, musí vaše srdce nad těmito změnami zaplesat. Doufejme, že výzva pro vývojáře v podobě efektivního využívání výpočetních jednotek s těmito nástroji nezůstane bez odpovědi.