Vlastní dělicí metody pro PLINQ a TPL

  • Článek

Pokud chcete paralelizovat operaci ve zdroji dat, jedním z základních kroků je rozdělení zdroje do několika oddílů, ke kterým může přistupovat souběžně více vláken. PLINQ a knihovna TPL (Task Parallel Library) poskytují výchozí dělicí moduly, které transparentně fungují při psaní paralelního dotazu nebo ForEach smyčky. Pro pokročilejší scénáře můžete připojit vlastního dělitele.

Druhy dělení

Existuje mnoho způsobů, jak rozdělit zdroj dat. V nejúčinnějších přístupech spolupracuje více vláken na zpracování původní zdrojové sekvence namísto fyzického oddělení zdroje do několika dílčích sekvencí. Pro pole a další indexované zdroje, jako IList jsou kolekce, kde je délka známa předem, je dělení rozsahu nejjednodušší druh dělení. Každé vlákno obdrží jedinečné počáteční a koncové indexy, aby bylo možné zpracovat jeho rozsah zdroje bez přepsání nebo přepsání jiným vláknem. Jedinou režií spojenou s dělením rozsahu je počáteční práce vytváření rozsahů; Po této operaci není nutná žádná další synchronizace. Proto může poskytovat dobrý výkon, pokud je úloha rovnoměrně rozdělena. Nevýhodou dělení rozsahu je, že pokud se jedno vlákno dokončí brzy, nemůže pomoct ostatním vláknům dokončit svou práci.

U propojených seznamů nebo jiných kolekcí, jejichž délka není známá, můžete použít dělení bloků dat. Při dělení bloků dat využívá každé vlákno nebo úkol v paralelní smyčce nebo dotazu určitý počet zdrojových prvků v jednom bloku, zpracuje je a pak se vrátí k načtení dalších prvků. Rozdělovač zajišťuje distribuci všech prvků a že neexistují žádné duplicity. Blok dat může mít libovolnou velikost. Například partitioner, který je ukázaný v postupu: Implementace dynamických oddílů vytváří bloky dat, které obsahují pouze jeden prvek. Pokud nejsou bloky dat příliš velké, je tento druh dělení ze své podstaty vyrovnávání zatížení, protože přiřazení prvků do vláken není předem určeno. Při každém načtení dalšího bloku vlákna ale dochází k režii synchronizace. Množství synchronizace vzniklé v těchto případech je inverzní úměrné velikosti bloků dat.

Obecně platí, že dělení rozsahu je rychlejší pouze v případě, že doba provádění delegáta je malá až střední a zdroj má velký počet prvků a celková práce každého oddílu je přibližně ekvivalentní. Dělení bloků dat je proto ve většině případů obecně rychlejší. U zdrojů s malým počtem prvků nebo delší dobou provádění delegáta je výkon bloků dat a dělení rozsahu přibližně stejný.

Oddíly TPL podporují také dynamický počet oddílů. To znamená, že můžou vytvářet oddíly za běhu, například když smyčka ForEach vytvoří novou úlohu. Tato funkce umožňuje děliteli škálovat společně se samotnou smyčkou. Dynamické dělicí nástroje jsou také ze své podstaty vyrovnávání zatížení. Při vytváření vlastního partitioneru musíte podporovat dynamické dělení, aby bylo možné ho použít ze smyčky ForEach .

Konfigurace oddílů vyrovnávání zatížení pro PLINQ

Některá přetížení Partitioner.Create metody umožňují vytvořit partitioner pro pole nebo IList zdroj a určit, zda se má pokoušet vyrovnávat zatížení mezi vlákny. Když je partitioner nakonfigurovaný na vyrovnávání zatížení, použije se dělení bloků dat a prvky se předají do každého oddílu v malých blocích, jak jsou požadovány. Tento přístup pomáhá zajistit, aby všechny oddíly měly elementy ke zpracování, dokud se nedokončila celá smyčka nebo dotaz. Další přetížení lze použít k zajištění dělení na vyrovnávání zatížení libovolného IEnumerable zdroje.

Vyrovnávání zatížení obecně vyžaduje, aby oddíly vyžadovaly prvky relativně často od partitioneru. Naproti tomu rozdělovač, který dělá statické dělení, může přiřadit prvky každému oddílu najednou pomocí rozsahu nebo dělení bloků dat. To vyžaduje menší režii než vyrovnávání zatížení, ale spuštění jednoho vlákna může trvat déle, pokud jedno vlákno skončí výrazně více práce než ostatní. Ve výchozím nastavení při předání IList nebo pole plINQ vždy používá dělení rozsahu bez vyrovnávání zatížení. Pokud chcete povolit vyrovnávání zatížení pro PLINQ, použijte metodu Partitioner.Create , jak je znázorněno v následujícím příkladu.

// Static partitioning requires indexable source. Load balancing
// can use any IEnumerable.
var nums = Enumerable.Range(0, 100000000).ToArray();

// Create a load-balancing partitioner. Or specify false for static partitioning.
Partitioner<int> customPartitioner = Partitioner.Create(nums, true);

// The partitioner is the query's data source.
var q = from x in customPartitioner.AsParallel()
        select x * Math.PI;

q.ForAll((x) =>
{
    ProcessData(x);
});

' Static number of partitions requires indexable source.
Dim nums = Enumerable.Range(0, 100000000).ToArray()

' Create a load-balancing partitioner. Or specify false For  Shared partitioning.
Dim customPartitioner = Partitioner.Create(nums, True)

' The partitioner is the query's data source.
Dim q = From x In customPartitioner.AsParallel()
        Select x * Math.PI

q.ForAll(Sub(x) ProcessData(x))

Nejlepší způsob, jak určit, jestli použít vyrovnávání zatížení v jakémkoli daném scénáři, je experimentovat a měřit, jak dlouho trvá dokončení operací v rámci reprezentativních zatížení a konfigurací počítače. Statické dělení může například výrazně zrychlit na počítači s více jádry, který má pouze několik jader, ale může způsobit zpomalení na počítačích s relativně velkým počtem jader.

Následující tabulka uvádí dostupné přetížení Create metody. Tyto dělicí nástroje nejsou omezeny pouze na použití s PLINQ nebo Task. Lze je také použít s libovolným vlastním paralelním konstruktorem.

Přetížení Používá vyrovnávání zatížení.
Create<TSource>(IEnumerable<TSource>) Always
Create<TSource>(TSource[], Boolean) Pokud je logický argument zadán jako true
Create<TSource>(IList<TSource>, Boolean) Pokud je logický argument zadán jako true
Create(Int32, Int32) Nikdy
Create(Int32, Int32, Int32) Nikdy
Create(Int64, Int64) Nikdy
Create(Int64, Int64, Int64) Nikdy

Konfigurace oddílů statického rozsahu pro Parallel.ForEach

For Ve smyčce je tělo smyčky poskytováno metodě jako delegát. Náklady na vyvolání delegáta jsou přibližně stejné jako volání virtuální metody. V některých scénářích může být tělo paralelní smyčky dostatečně malé, aby náklady na vyvolání delegáta na každé iteraci smyčky byly významné. V takových situacích můžete pomocí jednoho z Create přetížení vytvořit IEnumerable<T> oddíly rozsahu nad zdrojovými prvky. Tuto kolekci oblastí ForEach pak můžete předat metodě, jejíž tělo se skládá z pravidelné for smyčky. Výhodou tohoto přístupu je, že náklady na vyvolání delegáta se účtují pouze jednou za rozsah, nikoli jednou za prvek. Následující příklad ukazuje základní vzor.

using System;
using System.Collections.Concurrent;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {

        // Source must be array or IList.
        var source = Enumerable.Range(0, 100000).ToArray();

        // Partition the entire source array.
        var rangePartitioner = Partitioner.Create(0, source.Length);

        double[] results = new double[source.Length];

        // Loop over the partitions in parallel.
        Parallel.ForEach(rangePartitioner, (range, loopState) =>
        {
            // Loop over each range element without a delegate invocation.
            for (int i = range.Item1; i < range.Item2; i++)
            {
                results[i] = source[i] * Math.PI;
            }
        });

        Console.WriteLine("Operation complete. Print results? y/n");
        char input = Console.ReadKey().KeyChar;
        if (input == 'y' || input == 'Y')
        {
            foreach(double d in results)
            {
                Console.Write("{0} ", d);
            }
        }
    }
}

Imports System.Threading.Tasks
Imports System.Collections.Concurrent

Module PartitionDemo

    Sub Main()
        ' Source must be array or IList.
        Dim source = Enumerable.Range(0, 100000).ToArray()

        ' Partition the entire source array. 
        ' Let the partitioner size the ranges.
        Dim rangePartitioner = Partitioner.Create(0, source.Length)

        Dim results(source.Length - 1) As Double

        ' Loop over the partitions in parallel. The Sub is invoked
        ' once per partition.
        Parallel.ForEach(rangePartitioner, Sub(range, loopState)

                                               ' Loop over each range element without a delegate invocation.
                                               For i As Integer = range.Item1 To range.Item2 - 1
                                                   results(i) = source(i) * Math.PI
                                               Next
                                           End Sub)
        Console.WriteLine("Operation complete. Print results? y/n")
        Dim input As Char = Console.ReadKey().KeyChar
        If input = "y"c Or input = "Y"c Then
            For Each d As Double In results
                Console.Write("{0} ", d)
            Next
        End If

    End Sub
End Module

Každé vlákno ve smyčce obdrží vlastní Tuple<T1,T2> , které obsahuje počáteční a koncové hodnoty indexu v zadaném podsadě. Vnitřní for smyčka používá fromInclusive a toExclusive hodnoty ke smyčce přes matici IList nebo přímo.

Jedno z Create přetížení umožňuje určit velikost oddílů a počet oddílů. Toto přetížení lze použít ve scénářích, kdy je práce na prvek tak nízká, že dokonce i jedno volání virtuální metody na prvek má výrazný dopad na výkon.

Vlastní dělitele

V některých scénářích může být vhodné nebo dokonce vyžadovat implementaci vlastního partitioneru. Můžete mít například vlastní třídu kolekce, kterou můžete efektivněji rozdělit, než mohou výchozí dělicí nástroje na základě vašich znalostí o interní struktuře třídy. Nebo můžete chtít vytvořit oddíly rozsahu různých velikostí na základě znalostí o tom, jak dlouho bude trvat zpracování prvků v různých umístěních ve zdrojové kolekci.

Chcete-li vytvořit základní vlastní dělicí nástroj, odvodit třídu z System.Collections.Concurrent.Partitioner<TSource> virtuálních metod a přepsat ji, jak je popsáno v následující tabulce.

metoda Popis
GetPartitions Tato metoda je volána jednou hlavním vláknem a vrátí IList(IEnumerator(TSource)). Každé pracovní vlákno ve smyčce nebo dotazu může volat GetEnumerator seznam, který načte IEnumerator<T> přes odlišný oddíl.
SupportsDynamicPartitions Vrátí true , pokud implementujete GetDynamicPartitions, jinak , false.
GetDynamicPartitions Pokud SupportsDynamicPartitions je true, tato metoda může být volitelně volána místo GetPartitions.

Pokud musí být výsledky seřazené nebo vyžadujete indexovaný přístup k prvkům, odvozujte z System.Collections.Concurrent.OrderablePartitioner<TSource> jeho virtuálních metod a přepište je, jak je popsáno v následující tabulce.

metoda Popis
GetPartitions Tato metoda je volána jednou hlavním vláknem a vrátí .IList(IEnumerator(TSource)) Každé pracovní vlákno ve smyčce nebo dotazu může volat GetEnumerator seznam, který načte IEnumerator<T> přes odlišný oddíl.
SupportsDynamicPartitions Vrátí hodnotu true , pokud implementujete GetDynamicPartitions, jinak nepravda.
GetDynamicPartitions Obvykle to jen volá GetOrderableDynamicPartitions.
GetOrderableDynamicPartitions Pokud SupportsDynamicPartitions je true, tato metoda může být volitelně volána místo GetPartitions.

Následující tabulka obsahuje další podrobnosti o tom, jak tři druhy rozdělovačů vyrovnávání zatížení implementují OrderablePartitioner<TSource> třídu.

Metoda/vlastnost IList / Pole bez vyrovnávání zatížení IList / Array s vyrovnáváním zatížení Ienumerable
GetOrderablePartitions Používá dělení rozsahu. Používá dělení bloků dat optimalizované pro seznamy pro zadaný počet oddílů. Používá dělení bloků dat vytvořením statického počtu oddílů.
OrderablePartitioner<TSource>.GetOrderableDynamicPartitions Vyvolá výjimku, která není podporována. Používá dělení bloků dat optimalizované pro seznamy a dynamické oddíly. Používá dělení bloků dat vytvořením dynamického počtu oddílů.
KeysOrderedInEachPartition Vrátí true Vrátí true Vrátí true
KeysOrderedAcrossPartitions Vrátí true Vrátí false Vrátí false
KeysNormalized Vrátí true Vrátí true Vrátí true
SupportsDynamicPartitions Vrátí false Vrátí true Vrátí true

Dynamické oddíly

Pokud máte v úmyslu použít partitioner v ForEach metodě, musíte být schopni vrátit dynamický počet oddílů. To znamená, že partitioner může kdykoli během provádění smyčky poskytnout výčet nového oddílu na vyžádání. V podstatě, kdykoli smyčka přidá novou paralelní úlohu, požádá o nový oddíl pro daný úkol. Pokud potřebujete, aby byla data uspořádaná, odvozujte je z System.Collections.Concurrent.OrderablePartitioner<TSource> toho, aby každá položka v každém oddílu byla přiřazena jedinečnému indexu.

Další informace a příklad najdete v tématu Postupy: Implementace dynamických oddílů.

Kontrakt pro dělitele

Při implementaci vlastního partitioneru postupujte podle těchto pokynů, abyste zajistili správnou interakci s PLINQ a ForEach v TPL:

  • Je-li GetPartitions volána s argumentem nula nebo menší pro partitionsCount, vyvolání ArgumentOutOfRangeException. I když PLINQ a TPL nikdy nepřejdou rovnou partitionCount 0, přesto doporučujeme, abyste se hlídali proti možnosti.

  • GetPartitions a GetOrderablePartitions měl by vždy vracet partitionsCount počet oddílů. Pokud partitioner vyčerpá data a nemůže vytvořit tolik oddílů, kolik požadujete, pak by metoda měla vrátit prázdný výčet pro každý z zbývajících oddílů. V opačném případě plINQ i TPL vyvolá výjimku InvalidOperationException.

  • GetPartitions, GetOrderablePartitions, GetDynamicPartitionsa GetOrderableDynamicPartitions nikdy by se neměly vracet null (Nothing v jazyce Visual Basic). Pokud ano, PLINQ / TPL vyvolá .InvalidOperationException

  • Metody vracející oddíly by vždy měly vracet oddíly, které mohou plně a jedinečně vytvořit výčet zdroje dat. Ve zdroji dat by se nemělo duplikovat ani přeskakovat položky, pokud to návrh oddílu výslovně nevyžaduje. Pokud toto pravidlo není dodrženo, může se výstupní pořadí zakódovat.

  • Následující logické gettery musí vždy přesně vracet následující hodnoty, aby výstupní pořadí nebylo zakódováno:

    • KeysOrderedInEachPartition: Každý oddíl vrací prvky se zvýšením klíčových indexů.

    • KeysOrderedAcrossPartitions: Pro všechny vrácené oddíly jsou klíčové indexy v oddílu i vyšší než klíčové indexy v oddílu i-1.

    • KeysNormalized: Všechny klíčové indexy se monotonicky zvětšují bez mezer, počínaje nulou.

  • Všechny indexy musí být jedinečné. Nemusí existovat duplicitní indexy. Pokud toto pravidlo není dodrženo, může se výstupní pořadí zakódovat.

  • Všechny indexy musí být nenegativní. Pokud toto pravidlo není dodrženo, může plINQ/TPL vyvolat výjimky.

Viz také