Partitioner personalizzati per PLINQ e TPL

  • Articolo

Per parallelizzare un'operazione in un'origine dati, è essenziale partizionare l'origine in più sezioni a cui è possibile accedere contemporaneamente da più thread. PLINQ e Task Parallel Library (TPL) forniscono partitioner predefiniti che funzionano in modo trasparente quando si scrive una query o un ciclo ForEach parallelo. Per scenari più avanzati, è possibile collegare il proprio partitioner.

Tipi di partizionamento

Esistono diversi modi per partizionare un'origine dati. Negli approcci più efficienti, più thread cooperano per elaborare la sequenza di origine originale, invece di separare fisicamente l'origine in più sottosequenze. Per le matrici e le altre origini indicizzate, ad esempio le raccolte IList in cui la lunghezza è nota in anticipo, il partizionamento per intervalli è il tipo più semplice di partizionamento. Ogni thread riceve indici iniziali e finali univoci, in modo che possa elaborare l'intervallo dell'origine senza sovrascrivere un altro thread o esserne sovrascritto. L'unico sovraccarico che si verifica nel partizionamento per intervalli è dovuto all'attività iniziale di creazione degli intervalli, dopo la quale non sono necessarie altre operazioni di sincronizzazione. Può quindi offrire buone prestazioni purché il carico di lavoro sia suddiviso equamente. Uno svantaggio del partizionamento per intervalli è che, se un thread termina prima del previsto, non può supportare il completamento degli altri thread.

Per gli elenchi collegati o altre raccolte la cui lunghezza non è nota, è possibile usare il partizionamento in blocchi. Nel partizionamento in blocchi ogni thread o attività in un ciclo o una query parallela usa un determinato numero di elementi di origine in un blocco, li elabora e quindi torna a recuperare altri elementi. Il partitioner garantisce che tutti gli elementi vengano distribuiti e che non siano presenti duplicati. Un blocco può essere di qualsiasi dimensione. Ad esempio, il partitioner illustrato in Procedura: Implementare partizioni dinamiche crea blocchi che contengono un solo elemento. Purché i blocchi non siano troppo grandi, questo tipo di partizionamento esegue di per sé il bilanciamento del carico perché l'assegnazione di elementi ai thread non è predeterminata. Il partitioner, tuttavia, comporta il sovraccarico di sincronizzazione ogni volta che il thread deve ottenere un altro blocco. La quantità di operazioni di sincronizzazione eseguite in questi casi è inversamente proporzionale alle dimensioni dei blocchi.

Il partizionamento per intervalli è in generale più veloce solo quando il tempo di esecuzione del delegato è da breve a medio, l'origine ha un numero elevato di elementi e il lavoro totale di ogni partizione è quasi equivalente. Il partizionamento in blocchi è quindi in genere più veloce nella maggior parte dei casi. Nelle origini con un numero limitato di elementi o tempi di esecuzione più lunghi per il delegato le prestazioni del partizionamento in blocchi e per intervalli sono più o meno uguali.

I partitioner TPL supportano anche un numero di partizioni dinamico. Ciò significa che possono creare le partizioni immediatamente, ad esempio, quando il ciclo ForEach genera una nuova attività. Questa funzionalità consente al partitioner di essere ridimensionato con il ciclo stesso. I partitioner dinamici eseguono anche implicitamente il bilanciamento del carico. Quando si crea un partitioner personalizzato, è necessario supportare il partizionamento dinamico perché sia utilizzabile da un ciclo ForEach.

Configurazione di partitioner di bilanciamento del carico per PLINQ

Alcuni overload del metodo Partitioner.Create consentono di creare un partitioner per una matrice o un'origine IList e di specificare se deve provare a bilanciare il carico di lavoro tra i thread. Quando il partitioner è configurato per il bilanciamento del carico, viene usato il partizionamento in blocchi e gli elementi vengono passati a ogni partizione in piccoli blocchi quando vengono richiesti. Questo approccio consente di garantire che tutte le partizioni abbiano elementi da elaborare finché l'intero ciclo o query non viene completata. Si può usare un overload aggiuntivo per fornire il partizionamento del bilanciamento del carico di qualsiasi origine IEnumerable.

Per il bilanciamento del carico le partizioni devono in genere richiedere gli elementi al partitioner relativamente spesso. Al contrario, un partitioner che esegue il partizionamento statico può assegnare tutti gli elementi a ogni partitioner contemporaneamente usando il partizionamento per intervalli o in blocchi. Ciò comporta un sovraccarico minore rispetto al bilanciamento del carico, ma l'esecuzione potrebbe richiedere più tempo se un thread termina con molte più attività rispetto agli altri. Per impostazione predefinita, quando viene passato un elemento IList o una matrice, PLINQ usa sempre il partizionamento per intervalli senza bilanciamento del carico. Per abilitare il bilanciamento del carico per PLINQ, usare il metodo Partitioner.Create, come illustrato nell'esempio seguente.

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

Il modo migliore per stabilire se è opportuno usare il bilanciamento del carico in qualsiasi scenario specificato consiste nello sperimentare e misurare il tempo necessario per il completamento delle operazioni con carichi e configurazioni di computer rappresentativi. Il partizionamento statico, ad esempio, potrebbe offrire un considerevole aumento di velocità in un computer con solo pochi core, ma potrebbe comportare rallentamenti nei computer con un numero relativamente elevato di core.

Nella tabella seguente sono elencati gli overload disponibili del metodo Create. Questi partitioner non sono limitati all'uso con PLINQ o Task. Possono essere usati anche con qualsiasi costrutto parallelo personalizzato.

Overload Usa il bilanciamento del carico
Create<TSource>(IEnumerable<TSource>) Sempre
Create<TSource>(TSource[], Boolean) Quando l'argomento booleano viene specificato come true
Create<TSource>(IList<TSource>, Boolean) Quando l'argomento booleano viene specificato come true
Create(Int32, Int32) Mai
Create(Int32, Int32, Int32) Mai
Create(Int64, Int64) Mai
Create(Int64, Int64, Int64) Mai

Configurazione di partitioner per intervalli statici per Parallel.ForEach

In un ciclo For il corpo del ciclo viene fornito al metodo come delegato. Il costo della chiamata a tale delegato è più o meno lo stesso di una chiamata a un metodo virtuale. In alcuni scenari il corpo di un ciclo parallelo potrebbe essere tanto piccolo che il costo della chiamata al delegato a ogni iterazione del ciclo diventa considerevole. In tali situazioni, è possibile usare uno degli overload Create per creare un'interfaccia IEnumerable<T> di partizioni a intervalli sugli elementi di origine. È quindi possibile passare questa raccolta di intervalli a un metodo ForEach il cui corpo è costituito da un normale ciclo for. Il vantaggio di questo approccio è che il costo della chiamata al delegato viene applicato una sola volta per intervallo, invece che una volta per elemento. L'esempio seguente illustra il modello di base.

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

Ogni thread nel ciclo riceve la propria classe Tuple<T1,T2> che contiene i valori degli indici iniziali e finali dell'intervallo secondario specificato. Il ciclo for interno usa i valori fromInclusive e toExclusive per eseguire il ciclo direttamente sulla matrice o sull'interfaccia IList.

Uno degli overload Create consente di specificare le dimensioni delle partizioni e il numero di partizioni. Questo overload può essere usato negli scenari in cui il lavoro per ogni elemento è così ridotto che anche una sola chiamata a un metodo virtuale per ogni elemento ha un impatto notevole sulle prestazioni.

Partitioner personalizzati

In alcuni scenari, potrebbe essere utile o anche necessario implementare un partitioner personalizzato. Si potrebbe, ad esempio, avere una classe di raccolte personalizzata che è possibile partizionare in modo più efficiente di quanto possono fare i partitioner predefiniti, in base alla propria conoscenza della struttura interna della classe. In altri casi, può rivelarsi utile creare partizioni a intervalli di dimensioni variabili a seconda del tempo necessario per elaborare gli elementi in posizioni diverse della raccolta di origine.

Per creare un partitioner personalizzato di base, derivare una classe da System.Collections.Concurrent.Partitioner<TSource> ed eseguire l'override dei metodi virtuali, come illustrato nella tabella seguente.

metodo Descrizione
GetPartitions Questo metodo viene chiamato una volta dal thread principale e restituisce un'interfaccia IList(IEnumerator(TSource)). Ogni thread di lavoro nel ciclo o nella query può chiamare GetEnumerator sull'elenco per recuperare un'interfaccia IEnumerator<T> su una partizione distinta.
SupportsDynamicPartitions Restituisce true se si implementa GetDynamicPartitions. In caso contrario, false.
GetDynamicPartitions Se SupportsDynamicPartitions è true, si può chiamare questo metodo invece di GetPartitions.

Se i risultati devono essere ordinabili o è necessario l'accesso indicizzato agli elementi, derivare da System.Collections.Concurrent.OrderablePartitioner<TSource> ed eseguire l'override dei metodi virtuali, come illustrato nella tabella seguente.

metodo Descrizione
GetPartitions Questo metodo viene chiamato una volta dal thread principale e restituisce un'interfaccia IList(IEnumerator(TSource)). Ogni thread di lavoro nel ciclo o nella query può chiamare GetEnumerator sull'elenco per recuperare un'interfaccia IEnumerator<T> su una partizione distinta.
SupportsDynamicPartitions Restituisce true se si implementa GetDynamicPartitions. In caso contrario, false.
GetDynamicPartitions In genere, si limita a chiamare GetOrderableDynamicPartitions.
GetOrderableDynamicPartitions Se SupportsDynamicPartitions è true, si può chiamare questo metodo invece di GetPartitions.

La tabella seguente fornisce altri dettagli su come i tre tipi di partitioner di bilanciamento del carico implementano la classe OrderablePartitioner<TSource>.

Metodo/proprietà IList/Matrice senza bilanciamento del carico IList/Matrice con bilanciamento del carico IEnumerable
GetOrderablePartitions Usa il partizionamento per intervalli Usa il partizionamento in blocchi ottimizzato per gli elenchi del partitionCount specificato Usa il partizionamento in blocchi creando un numero statico di partizioni.
OrderablePartitioner<TSource>.GetOrderableDynamicPartitions Genera un'eccezione non supportata Usa il partizionamento in blocchi ottimizzato per gli elenchi e le partizioni dinamiche Usa il partizionamento in blocchi creando un numero dinamico di partizioni.
KeysOrderedInEachPartition Restituisce true. Restituisce true. Restituisce true.
KeysOrderedAcrossPartitions Restituisce true. Restituisce false. Restituisce false.
KeysNormalized Restituisce true. Restituisce true. Restituisce true.
SupportsDynamicPartitions Restituisce false. Restituisce true. Restituisce true.

Partizioni dinamiche

Se si prevede che il partitioner venga usato in un metodo ForEach, è necessario poter restituire un numero dinamico di partizioni. Questo significa che il partitioner può fornire un enumeratore per una nuova partizione on demand in qualsiasi momento durante l'esecuzione del ciclo. In sostanza, quando il ciclo aggiunge una nuova attività parallela, richiede una nuova partizione per tale attività. Se è necessario che i dati siano ordinabili, derivare da System.Collections.Concurrent.OrderablePartitioner<TSource> in modo che a ogni elemento in ogni partizione venga assegnato un indice univoco.

Per altre informazioni e per un esempio, vedere Procedura: Implementare partizioni dinamiche.

Contratto per i partitioner

Quando si implementa un partitioner personalizzato, seguire queste linee guida per assicurare la corretta interazione con PLINQ e ForEach in TPL:

  • Se GetPartitions viene chiamato con un argomento pari a zero o meno per partitionsCount, generare ArgumentOutOfRangeException. Anche se PLINQ e TPL non passeranno mai un partitionCount uguale a 0, è tuttavia consigliabile proteggersi da questa possibilità.

  • GetPartitions e GetOrderablePartitions devono restituire sempre un numero di partizioni pari a partitionsCount. Se il partitioner non ha dati sufficienti e non può creare tutte le partizioni richieste, il metodo deve restituire un enumeratore vuoto per ogni partizione rimanente. In caso contrario, sia PLINQ che TPL genereranno un'eccezione InvalidOperationException.

  • GetPartitions, GetOrderablePartitions, GetDynamicPartitions e GetOrderableDynamicPartitions non devono mai restituire null (Nothing in Visual Basic), altrimenti PLINQ/TPL genererà un'eccezione InvalidOperationException.

  • I metodi che restituiscono partizioni devono sempre restituire partizioni che possano enumerare l'origine dati in modo completo e univoco. Non devono essere presenti duplicazioni nell'origine dati o elementi ignorati se non specificamente richiesto dalla progettazione del partitioner. Se questa regola non viene seguita, l'ordine dell'output potrebbe non risultare corretto.

  • I getter booleani seguenti devono sempre restituire in modo accurato i valori seguenti in modo che l'ordine dell'output sia corretto:

    • KeysOrderedInEachPartition: ogni partizione restituisce elementi con indici di chiave crescenti.

    • KeysOrderedAcrossPartitions: per tutte le partizioni restituite, gli indici di chiave della partizione i hanno un valore superiore rispetto a quelli nella partizione i-1.

    • KeysNormalized: tutti gli indici di chiave sono a incremento progressivo costante senza gap, a partire da zero.

  • Tutti gli indici devono essere univoci. Non possono essere presenti indici duplicati. Se questa regola non viene seguita, l'ordine dell'output potrebbe non risultare corretto.

  • Tutti gli indici devono essere non negativi. Se questa regola non viene rispettata, PLINQ/TPL può generare eccezioni.

Vedi anche