Anpassade partitionerare för PLINQ och TPL

För att parallellisera en åtgärd på en datakälla är ett av de viktigaste stegen att partitionera källan i flera avsnitt som kan nås samtidigt av flera trådar. PLINQ och TPL (Task Parallel Library) tillhandahåller standardpartitioner som fungerar transparent när du skriver en parallell fråga eller ForEach loop. För mer avancerade scenarier kan du ansluta din egen partitionerare.

Typer av partitionering

Det finns många sätt att partitioneras på en datakälla. I de mest effektiva metoderna samarbetar flera trådar för att bearbeta den ursprungliga källsekvensen, i stället för att fysiskt separera källan i flera underfrågor. För matriser och andra indexerade källor, till exempel IList samlingar där längden är känd i förväg, är intervallpartitionering den enklaste typen av partitionering. Varje tråd tar emot unika start- och slutindex, så att den kan bearbeta källans intervall utan att skriva över eller skrivas över av någon annan tråd. Det enda som krävs för intervallpartitionering är det första arbetet med att skapa intervallen. ingen ytterligare synkronisering krävs efter det. Därför kan det ge bra prestanda så länge arbetsbelastningen delas jämnt. En nackdel med intervallpartitionering är att om en tråd avslutas tidigt kan den inte hjälpa de andra trådarna att slutföra sitt arbete.

För länkade listor eller andra samlingar vars längd inte är känd kan du använda segmentpartitionering. Vid segmentpartitionering förbrukar varje tråd eller uppgift i en parallell loop eller fråga ett visst antal källelement i ett segment, bearbetar dem och kommer sedan tillbaka för att hämta ytterligare element. Partitioneraren ser till att alla element distribueras och att det inte finns några dubbletter. Ett segment kan vara valfri storlek. Partitioneraren som visas i Så här: Implementera dynamiska partitioner skapar till exempel segment som bara innehåller ett element. Så länge segmenten inte är för stora är den här typen av partitionering i sig belastningsutjämning eftersom tilldelningen av element till trådar inte är förutbestämd. Partitioneraren ådrar sig dock synkroniseringskostnaderna varje gång tråden behöver hämta ett annat segment. Mängden synkronisering som uppstår i dessa fall är omvänt proportionell mot storleken på segmenten.

I allmänhet är intervallpartitionering bara snabbare när körningstiden för ombudet är liten till måttlig, och källan har ett stort antal element, och det totala arbetet för varje partition är ungefär likvärdigt. Segmentpartitionering är därför i allmänhet snabbare i de flesta fall. På källor med ett litet antal element eller längre körningstider för ombudet är prestandan för segment- och intervallpartitionering ungefär lika.

TPL-partitionerarna stöder också ett dynamiskt antal partitioner. Det innebär att de kan skapa partitioner direkt, till exempel när loopen ForEach skapar en ny uppgift. Med den här funktionen kan partitioneraren skala tillsammans med själva loopen. Dynamiska partitioner är också belastningsutjämning. När du skapar en anpassad partitionerare måste du ha stöd för dynamisk partitionering för att kunna användas från en ForEach loop.

Konfigurera belastningsutjämningspartitionerare för PLINQ

Med vissa överlagringar av Partitioner.Create metoden kan du skapa en partitionerare för en matris eller IList källa och ange om den ska försöka balansera arbetsbelastningen mellan trådarna. När partitioneraren är konfigurerad för belastningsutjämning används segmentpartitionering och elementen överlämnas till varje partition i små segment när de begärs. Den här metoden hjälper till att säkerställa att alla partitioner har element att bearbeta tills hela loopen eller frågan har slutförts. En ytterligare överlagring kan användas för att tillhandahålla belastningsutjämningspartitionering av valfri IEnumerable källa.

I allmänhet kräver belastningsutjämning att partitionerna begär element relativt ofta från partitioneraren. En partitionerare som utför statisk partitionering kan däremot tilldela elementen till varje partitionerare samtidigt med hjälp av antingen intervall- eller segmentpartitionering. Detta kräver mindre omkostnader än belastningsutjämning, men det kan ta längre tid att köra om en tråd får betydligt mer arbete än de andra. Som standard när den skickas en IList eller en matris använder PLINQ alltid intervallpartitionering utan belastningsutjämning. Om du vill aktivera belastningsutjämning för PLINQ använder du Partitioner.Create metoden, som du ser i följande exempel.

// 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))

Det bästa sättet att avgöra om belastningsutjämning ska användas i ett visst scenario är att experimentera och mäta hur lång tid det tar att utföra åtgärder under representativa belastningar och datorkonfigurationer. Statisk partitionering kan till exempel ge betydande hastighet på en dator med flera kärnor som bara har några kärnor, men det kan leda till långsammare prestanda på datorer som har relativt många kärnor.

I följande tabell visas de tillgängliga överlagringarna av Create metoden. Dessa partitionerare är inte begränsade till att endast användas med PLINQ eller Task. De kan också användas med alla anpassade parallella konstruktioner.

Överbelastning	Använder belastningsutjämning
Create<TSource>(IEnumerable<TSource>)	Alltid
Create<TSource>(TSource[], Boolean)	När det booleska argumentet anges som sant
Create<TSource>(IList<TSource>, Boolean)	När det booleska argumentet anges som sant
Create(Int32, Int32)	Aldrig
Create(Int32, Int32, Int32)	Aldrig
Create(Int64, Int64)	Aldrig
Create(Int64, Int64, Int64)	Aldrig

Konfigurera partitioner för statiskt intervall för Parallel.ForEach

I en For loop tillhandahålls loopens brödtext till metoden som ombud. Kostnaden för att anropa ombudet är ungefär samma som ett virtuellt metodanrop. I vissa scenarier kan brödtexten i en parallell loop vara tillräckligt liten för att kostnaden för delegatanropet för varje loop-iteration blir betydande. I sådana situationer kan du använda en av överlagringarna Create för att skapa en IEnumerable<T> uppsättning intervallpartitioner över källelementen. Sedan kan du skicka den här samlingen med intervall till en ForEach metod vars brödtext består av en vanlig for loop. Fördelen med den här metoden är att kostnaden för ombudsanrop endast uppstår en gång per intervall i stället för en gång per element. I följande exempel visas det grundläggande mönstret.

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

Varje tråd i loopen tar emot sina egna Tuple<T1,T2> som innehåller start- och slutindexvärdena i det angivna underintervallet. Den inre for loopen fromInclusive använder värdena och toExclusive för att loopa över matrisen eller IList direkt.

Med en av Create överlagringarna kan du ange storleken på partitionerna och antalet partitioner. Den här överlagringen kan användas i scenarier där arbetet per element är så lågt att även ett virtuellt metodanrop per element har en märkbar inverkan på prestandan.

Anpassade partitionerare

I vissa scenarier kan det vara värt eller till och med nödvändigt att implementera din egen partitionerare. Du kan till exempel ha en anpassad samlingsklass som du kan partitionera mer effektivt än standardpartitionerarna kan, baserat på dina kunskaper om klassens interna struktur. Eller så kanske du vill skapa intervallpartitioner av olika storlekar baserat på dina kunskaper om hur lång tid det tar att bearbeta element på olika platser i källsamlingen.

Om du vill skapa en grundläggande anpassad partitionerare härleder du en klass från System.Collections.Concurrent.Partitioner<TSource> och åsidosätter de virtuella metoderna enligt beskrivningen i följande tabell.

Metod	beskrivning
GetPartitions	Den här metoden anropas en gång av huvudtråden och returnerar en IList(IEnumerator(TSource)). Varje arbetstråd i loopen eller frågan kan anropa GetEnumerator i listan för att hämta en IEnumerator<T> över en distinkt partition.
SupportsDynamicPartitions	Returnera true om du implementerar GetDynamicPartitions, annars . false
GetDynamicPartitions	Om SupportsDynamicPartitions är truekan den här metoden anropas i stället för GetPartitions.

Om resultatet måste vara sorterbart eller om du behöver indexerad åtkomst till elementen, härleds sedan från System.Collections.Concurrent.OrderablePartitioner<TSource> och åsidosätter dess virtuella metoder enligt beskrivningen i följande tabell.

Metod	beskrivning
GetPartitions	Den här metoden anropas en gång av huvudtråden och returnerar en IList(IEnumerator(TSource)). Varje arbetstråd i loopen eller frågan kan anropa GetEnumerator i listan för att hämta en IEnumerator<T> över en distinkt partition.
SupportsDynamicPartitions	Returnera true om du implementerar GetDynamicPartitions, annars falskt.
GetDynamicPartitions	Vanligtvis anropar GetOrderableDynamicPartitionsdetta bara .
GetOrderableDynamicPartitions	Om SupportsDynamicPartitions är truekan den här metoden anropas i stället för GetPartitions.

Följande tabell innehåller ytterligare information om hur de tre typerna av belastningsutjämningspartitioner implementerar OrderablePartitioner<TSource> klassen.

Metod/egenskap	IList/Matris utan belastningsutjämning	IList/Matris med belastningsutjämning	Ienumerable
GetOrderablePartitions	Använder intervallpartitionering	Använder segmentpartitionering optimerad för listor för det angivna partitionskontot	Använder segmentpartitionering genom att skapa ett statiskt antal partitioner.
OrderablePartitioner<TSource>.GetOrderableDynamicPartitions	Genererar undantag som inte stöds	Använder segmentpartitionering optimerad för listor och dynamiska partitioner	Använder segmentpartitionering genom att skapa ett dynamiskt antal partitioner.
KeysOrderedInEachPartition	Returnerar true	Returnerar true	Returnerar true
KeysOrderedAcrossPartitions	Returnerar true	Returnerar false	Returnerar false
KeysNormalized	Returnerar true	Returnerar true	Returnerar true
SupportsDynamicPartitions	Returnerar false	Returnerar true	Returnerar true

Dynamiska partitioner

Om du tänker att partitioneraren ska användas i en ForEach metod måste du kunna returnera ett dynamiskt antal partitioner. Det innebär att partitioneraren kan ange en uppräknare för en ny partition på begäran när som helst under loopkörningen. När loopen lägger till en ny parallell uppgift begär den i princip en ny partition för den uppgiften. Om du kräver att data ska vara ordnade kan du härleda från System.Collections.Concurrent.OrderablePartitioner<TSource> så att varje objekt i varje partition tilldelas ett unikt index.

Mer information och ett exempel finns i Så här implementerar du dynamiska partitioner.

Kontrakt för partitionerare

När du implementerar en anpassad partitionerare följer du dessa riktlinjer för att säkerställa korrekt interaktion med PLINQ och ForEach I TPL:

• Om GetPartitions anropas med argumentet noll eller mindre för partitionsCountgenererar du ArgumentOutOfRangeException. Även om PLINQ och TPL aldrig kommer att passera i en partitionCount lika med 0, rekommenderar vi ändå att du skyddar mot möjligheten.

• GetPartitions och GetOrderablePartitions bör alltid returnera partitionsCount antalet partitioner. Om partitioneraren får slut på data och inte kan skapa så många partitioner som begärts bör metoden returnera en tom uppräknare för var och en av de återstående partitionerna. I annat fall genererar både PLINQ och TPL en InvalidOperationException.

• GetPartitions, GetOrderablePartitions, GetDynamicPartitionsoch GetOrderableDynamicPartitions bör aldrig returnera null (Nothing i Visual Basic). Om de gör det genererar PLINQ/TPL en InvalidOperationException.

• Metoder som returnerar partitioner bör alltid returnera partitioner som helt och unikt kan räkna upp datakällan. Det bör inte finnas någon duplicering i datakällan eller överhoppade objekt om inte specifikt krävs av partitionerarens design. Om den här regeln inte följs kan utdataordningen förvrängas.

• Följande booleska getters måste alltid returnera följande värden korrekt så att utdataordningen inte förvrängs:

  • KeysOrderedInEachPartition: Varje partition returnerar element med ökande nyckelindex.

  • KeysOrderedAcrossPartitions: För alla partitioner som returneras är nyckelindexen i partition i högre än nyckelindexen i partition i-1.

  • KeysNormalized: Alla nyckelindex ökar monotont utan luckor, från noll.

• Alla index måste vara unika. Det kanske inte finns duplicerade index. Om den här regeln inte följs kan utdataordningen förvrängas.

• Alla index måste vara icke-negativa. Om den här regeln inte följs kan PLINQ/TPL utlösa undantag.

Se även

• Parallell programmering
• Anvisningar: Implementera dynamiska partitioner
• Anvisningar: Implementera en partitionerare för statisk partitionering