Particionadores personalizados para PLINQ e TPLCustom Partitioners for PLINQ and TPL

Para paralelizar a uma operação em uma fonte de dados, uma das etapas essenciais é particionar a fonte em várias seções que possam ser acessadas simultaneamente por vários threads.To parallelize an operation on a data source, one of the essential steps is to partition the source into multiple sections that can be accessed concurrently by multiple threads. O PLINQ e a TPL (Biblioteca de Paralelismo de Tarefas) fornecem particionadores padrão que funcionam de forma transparente quando você escreve uma consulta paralela ou um loop ForEach.PLINQ and the Task Parallel Library (TPL) provide default partitioners that work transparently when you write a parallel query or ForEach loop. Para cenários mais avançados, você pode conectar seu próprio particionador.For more advanced scenarios, you can plug in your own partitioner.

Tipos de particionamentoKinds of Partitioning

Há muitas maneiras de particionar uma fonte de dados.There are many ways to partition a data source. Nas abordagens mais eficientes, vários threads cooperam para processar a sequência de origem original, em vez de separar fisicamente a origem em várias subsequências.In the most efficient approaches, multiple threads cooperate to process the original source sequence, rather than physically separating the source into multiple subsequences. Para matrizes e outras fontes indexadas como coleções IList em que o tamanho é conhecido com antecedência, o particionamento por intervalos é o tipo mais simples de particionamento.For arrays and other indexed sources such as IList collections where the length is known in advance, range partitioning is the simplest kind of partitioning. Cada thread recebe índices exclusivos de abertura e fechamento, para que possa processar seu intervalo da origem sem substituir ou ser substituído por qualquer outro thread.Every thread receives unique beginning and ending indexes, so that it can process its range of the source without overwriting or being overwritten by any other thread. A única sobrecarga envolvida no particionamento por intervalos é o trabalho inicial de criação de intervalos. Nenhuma sincronização adicional é necessária depois disso.The only overhead involved in range partitioning is the initial work of creating the ranges; no additional synchronization is required after that. Portanto, pode fornecer bom desempenho, desde que a carga de trabalho seja dividida igualmente.Therefore, it can provide good performance as long as the workload is divided evenly. Uma desvantagem do particionamento por intervalos é que se um thread termina cedo, não pode ajudar os outros threads a concluírem seu trabalho.A disadvantage of range partitioning is that if one thread finishes early, it cannot help the other threads finish their work.

Para listas vinculadas ou outras coleções cujo comprimento não é conhecido, você pode usar o particionamento por partes.For linked lists or other collections whose length is not known, you can use chunk partitioning. Na parte de particionamento, cada thread ou tarefa em uma consulta ou um loop paralelo consome alguns elementos de origem em um bloco, processa-os e volta para recuperar elementos adicionais.In chunk partitioning, every thread or task in a parallel loop or query consumes some number of source elements in one chunk, processes them, and then comes back to retrieve additional elements. O particionador garante que todos os elementos sejam distribuídos e que não haja duplicatas.The partitioner ensures that all elements are distributed and that there are no duplicates. Uma parte pode ser de qualquer tamanho.A chunk may be any size. Por exemplo, o particionador que é demonstrado em Como: Implementar partições dinâmicas cria partes que contêm apenas um elemento.For example, the partitioner that is demonstrated in How to: Implement Dynamic Partitions creates chunks that contain just one element. Como as partes não são muito grandes, esse tipo de particionamento é, inerentemente, um balanceamento de carga, pois a atribuição de elementos a threads não é predeterminada.As long as the chunks are not too large, this kind of partitioning is inherently load-balancing because the assignment of elements to threads is not pre-determined. No entanto, o particionador causa sobrecarga de sincronização sempre que o thread precisa obter outro bloco.However, the partitioner does incur the synchronization overhead each time the thread needs to get another chunk. A quantidade de sincronização que ocorre nesses casos é inversamente proporcional ao tamanho das partes.The amount of synchronization incurred in these cases is inversely proportional to the size of the chunks.

Em geral, a partição de intervalo só é mais rápida quando o tempo de execução do representante é pequeno a médio e a origem tem um grande número de elementos e o trabalho total de cada partição é aproximadamente equivalente.In general, range partitioning is only faster when the execution time of the delegate is small to moderate, and the source has a large number of elements, and the total work of each partition is roughly equivalent. Portanto, o particionamento de bloco geralmente é mais rápido na maioria dos casos.Chunk partitioning is therefore generally faster in most cases. Em origens com um pequeno número de elementos ou tempos de execução maiores para o representante, o desempenho de bloco e particionamento por intervalos é mais ou menos igual.On sources with a small number of elements or longer execution times for the delegate, then the performance of chunk and range partitioning is about equal.

Os particionadores de TPL também dão suporte a um número dinâmico de partições.The TPL partitioners also support a dynamic number of partitions. Isso significa que podem criar partições imediatamente, por exemplo, quando o loop ForEach gera uma nova tarefa.This means they can create partitions on-the-fly, for example, when the ForEach loop spawns a new task. Esse recurso permite que o particionador seja dimensionado junto com o próprio loop.This feature enables the partitioner to scale together with the loop itself. Os particionadores dinâmicos também realizam, inerentemente, o balanceamento de carga.Dynamic partitioners are also inherently load-balancing. Ao criar um particionador personalizado, você deve dar suporte ao particionamento dinâmico para ser consumível de um loop ForEach.When you create a custom partitioner, you must support dynamic partitioning to be consumable from a ForEach loop.

Configuração de particionadores de balanceamento de carga para PLINQConfiguring Load Balancing Partitioners for PLINQ

Algumas sobrecargas do método Partitioner.Create permitem que você crie um particionador para uma matriz ou origem IList e especifique se deve tentar equilibrar a carga de trabalho entre os threads.Some overloads of the Partitioner.Create method let you create a partitioner for an array or IList source and specify whether it should attempt to balance the workload among the threads. Quando o particionador está configurado para balanceamento de carga, o particionamento por partes é usado, e os elementos são enviados para cada partição em pequenas partes conforme são solicitados.When the partitioner is configured to load-balance, chunk partitioning is used, and the elements are handed off to each partition in small chunks as they are requested. Essa abordagem ajuda a garantir que todas as partições tenham elementos para processar até que a consulta ou o loop inteiro seja concluído.This approach helps ensure that all partitions have elements to process until the entire loop or query is completed. Uma sobrecarga adicional pode ser usada para fornecer particionamento de balanceamento de carga de qualquer origem de IEnumerable.An additional overload can be used to provide load-balancing partitioning of any IEnumerable source.

Em geral, o balanceamento de carga requer que as partições solicitem elementos relativamente com frequência do particionador.In general, load balancing requires the partitions to request elements relatively frequently from the partitioner. Por outro lado, um particionador que faz o particionamento estático pode atribuir os elementos a cada particionador de uma só vez usando o particionamento por intervalos ou bloco.By contrast, a partitioner that does static partitioning can assign the elements to each partitioner all at once by using either range or chunk partitioning. Isso requer menos sobrecarga de balanceamento de carga, mas pode levar mais tempo para ser executado se um thread acaba com significativamente mais trabalho do que os outros.This requires less overhead than load balancing, but it might take longer to execute if one thread ends up with significantly more work than the others. Por padrão, quando recebe uma IList ou uma matriz, o PLINQ sempre usa o particionamento por intervalos sem balanceamento de carga.By default when it is passed an IList or an array, PLINQ always uses range partitioning without load balancing. Para habilitar o balanceamento de carga para o PLINQ, use o método Partitioner.Create, conforme mostrado no exemplo a seguir.To enable load balancing for PLINQ, use the Partitioner.Create method, as shown in the following example.

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

A melhor maneira de determinar se é preciso usar o balanceamento de carga em qualquer cenário específico é testar e medir o tempo necessário para concluir operações em cargas representativas e configurações de computador.The best way to determine whether to use load balancing in any given scenario is to experiment and measure how long it takes operations to complete under representative loads and computer configurations. Por exemplo, o particionamento estático pode fornecer um aumento de velocidade significativo em um computador com vários núcleos que tenha apenas alguns núcleos, mas pode resultar em lentidão em computadores que têm relativamente muitos núcleos.For example, static partitioning might provide significant speedup on a multi-core computer that has only a few cores, but it might result in slowdowns on computers that have relatively many cores.

A tabela a seguir lista as sobrecargas disponíveis do método Create.The following table lists the available overloads of the Create method. Essas particionadores não estão limitados ao uso somente com PLINQ ou Task.These partitioners are not limited to use only with PLINQ or Task. Também podem ser usados com qualquer constructo paralelo personalizado.They can also be used with any custom parallel construct.

SobrecargaOverload Usa o balanceamento de cargaUses load balancing
Create<TSource>(IEnumerable<TSource>) SempreAlways
Create<TSource>(TSource[], Boolean) Quando o argumento Boolean é especificado como trueWhen the Boolean argument is specified as true
Create<TSource>(IList<TSource>, Boolean) Quando o argumento Boolean é especificado como trueWhen the Boolean argument is specified as true
Create(Int32, Int32) NuncaNever
Create(Int32, Int32, Int32) NuncaNever
Create(Int64, Int64) NuncaNever
Create(Int64, Int64, Int64) NuncaNever

Configurando particionadores de intervalo estático para Parallel.ForEachConfiguring Static Range Partitioners for Parallel.ForEach

Em um loop For, o corpo do loop é fornecido para o método como um representante.In a For loop, the body of the loop is provided to the method as a delegate. O custo de invocar esse representante é quase o mesmo que o de uma chamada de método virtual.The cost of invoking that delegate is about the same as a virtual method call. Em alguns cenários, o corpo de um loop paralelo pode ser pequeno o suficiente para que o custo da invocação do representante em cada iteração do loop se torne significativo.In some scenarios, the body of a parallel loop might be small enough that the cost of the delegate invocation on each loop iteration becomes significant. Nessas situações, você pode usar uma das sobrecargas Create para criar um IEnumerable<T> de partições de intervalo sobre os elementos de origem.In such situations, you can use one of the Create overloads to create an IEnumerable<T> of range partitions over the source elements. Em seguida, você pode passar essa coleção de intervalos para um método ForEach cujo corpo consiste em um loop for regular.Then, you can pass this collection of ranges to a ForEach method whose body consists of a regular for loop. A vantagem dessa abordagem é que o custo de invocação do representante é incorrido apenas uma vez por intervalo, em vez de uma vez por elemento.The benefit of this approach is that the delegate invocation cost is incurred only once per range, rather than once per element. O exemplo a seguir demonstra o padrão básico.The following example demonstrates the basic pattern.

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

Cada thread no loop recebe seu próprio Tuple<T1,T2>, que contém os valores de índice inicial e final no subintervalo especificado.Every thread in the loop receives its own Tuple<T1,T2> that contains the starting and ending index values in the specified sub-range. O loop interno for usa os valores fromInclusive e toExclusive para executar um loop sobre a matriz ou o IList diretamente.The inner for loop uses the fromInclusive and toExclusive values to loop over the array or the IList directly.

Uma das sobrecargas Create permite especificar o tamanho de partições e o número delas.One of the Create overloads lets you specify the size of the partitions, and the number of partitions. Essa sobrecarga pode ser usada em cenários em que o trabalho por elemento é tão baixo que até mesmo uma chamada de método virtual por elemento tem impacto significativo sobre o desempenho.This overload can be used in scenarios where the work per element is so low that even one virtual method call per element has a noticeable impact on performance.

Particionadores PersonalizadosCustom Partitioners

Em alguns cenários, talvez seja útil ou até mesmo necessário implementar seu próprio particionador.In some scenarios, it might be worthwhile or even required to implement your own partitioner. Por exemplo, você pode ter uma classe de coleção personalizada que pode particionar de forma mais eficiente do que os particionadores padrão, com base em seu conhecimento sobre a estrutura interna da classe.For example, you might have a custom collection class that you can partition more efficiently than the default partitioners can, based on your knowledge of the internal structure of the class. Ou, talvez, você queira criar partições de intervalo de tamanhos variados com base em seu conhecimento de quanto tempo levará para processar elementos em locais diferentes na coleção de origem.Or, you may want to create range partitions of varying sizes based on your knowledge of how long it will take to process elements at different locations in the source collection.

Para criar um particionador personalizado básico, derive uma classe de System.Collections.Concurrent.Partitioner<TSource> e substitua os métodos virtuais, conforme descrito na tabela a seguir.To create a basic custom partitioner, derive a class from System.Collections.Concurrent.Partitioner<TSource> and override the virtual methods, as described in the following table.

GetPartitions Esse método é chamado uma vez pelo thread principal e retorna um IList(IEnumerator(TSource)).This method is called once by the main thread and returns an IList(IEnumerator(TSource)). Cada thread de trabalho na consulta ou no loop pode chamar GetEnumerator na lista para recuperar um IEnumerator<T> por uma partição distinta.Each worker thread in the loop or query can call GetEnumerator on the list to retrieve a IEnumerator<T> over a distinct partition.
SupportsDynamicPartitions Retorne true se você implementar GetDynamicPartitions; caso contrário, false.Return true if you implement GetDynamicPartitions, otherwise, false.
GetDynamicPartitions Se SupportsDynamicPartitions for true, esse método poderá ser opcionalmente chamado, em vez de GetPartitions.If SupportsDynamicPartitions is true, this method can optionally be called instead of GetPartitions.

Se os resultados precisarem ser classificáveis ou exigirem acesso indexado aos elementos, derive de System.Collections.Concurrent.OrderablePartitioner<TSource> e substitua seus métodos virtuais, conforme descrito na tabela a seguir.If the results must be sortable or you require indexed access into the elements, then derive from System.Collections.Concurrent.OrderablePartitioner<TSource> and override its virtual methods as described in the following table.

GetPartitions Esse método é chamado uma vez pelo thread principal e retorna um IList(IEnumerator(TSource)).This method is called once by the main thread and returns an IList(IEnumerator(TSource)). Cada thread de trabalho na consulta ou no loop pode chamar GetEnumerator na lista para recuperar um IEnumerator<T> por uma partição distinta.Each worker thread in the loop or query can call GetEnumerator on the list to retrieve a IEnumerator<T> over a distinct partition.
SupportsDynamicPartitions Retorne true se você implementar GetDynamicPartitions; caso contrário, false.Return true if you implement GetDynamicPartitions; otherwise, false.
GetDynamicPartitions Normalmente, isso apenas chama GetOrderableDynamicPartitions.Typically, this just calls GetOrderableDynamicPartitions.
GetOrderableDynamicPartitions Se SupportsDynamicPartitions for true, esse método poderá ser opcionalmente chamado, em vez de GetPartitions.If SupportsDynamicPartitions is true, this method can optionally be called instead of GetPartitions.

A tabela a seguir fornece detalhes adicionais sobre como os três tipos de particionadores de balanceamento de carga implementam a classe OrderablePartitioner<TSource>.The following table provides additional details about how the three kinds of load-balancing partitioners implement the OrderablePartitioner<TSource> class.

Método/propriedadeMethod/Property IList/matriz sem balanceamento de cargaIList / Array without Load Balancing IList/matriz com balanceamento de cargaIList / Array with Load Balancing IEnumerableIEnumerable
GetOrderablePartitions Usa o particionamento por intervalosUses range partitioning Usa o particionamento por partes otimizado para Listas para o partitionCount especificadoUses chunk partitioning optimized for Lists for the partitionCount specified Usa o particionamento por partes por meio da criação de um número estático de partições.Uses chunk partitioning by creating a static number of partitions.
OrderablePartitioner<TSource>.GetOrderableDynamicPartitions Gera uma exceção sem suporteThrows not-supported exception Usa o particionamento por partes otimizado para Listas e partições dinâmicasUses chunk partitioning optimized for Lists and dynamic partitions Usa o particionamento por partes por meio da criação de um número dinâmico de partições.Uses chunk partitioning by creating a dynamic number of partitions.
KeysOrderedInEachPartition Retorna trueReturns true Retorna trueReturns true Retorna trueReturns true
KeysOrderedAcrossPartitions Retorna trueReturns true Retorna falseReturns false Retorna falseReturns false
KeysNormalized Retorna trueReturns true Retorna trueReturns true Retorna trueReturns true
SupportsDynamicPartitions Retorna falseReturns false Retorna trueReturns true Retorna trueReturns true

Partições dinâmicasDynamic Partitions

Se desejar que o particionador seja usado em um método ForEach, você deverá ser capaz de retornar um número dinâmico de partições.If you intend the partitioner to be used in a ForEach method, you must be able to return a dynamic number of partitions. Isso significa que o particionador pode fornecer um enumerador para uma nova partição sob demanda a qualquer momento durante a execução do loop.This means that the partitioner can supply an enumerator for a new partition on-demand at any time during loop execution. Basicamente, sempre que o loop adicionar uma nova tarefa paralela, solicitará uma nova partição para a tarefa.Basically, whenever the loop adds a new parallel task, it requests a new partition for that task. Se for preciso que os dados sejam ordenáveis, derive System.Collections.Concurrent.OrderablePartitioner<TSource> para que seja atribuído um índice exclusivo a cada item em cada partição.If you require the data to be orderable, then derive from System.Collections.Concurrent.OrderablePartitioner<TSource> so that each item in each partition is assigned a unique index.

Para obter mais informações e um exemplo, confira Como: Implementar partições dinâmicas.For more information, and an example, see How to: Implement Dynamic Partitions.

Contrato para particionadoresContract for Partitioners

Ao implementar um particionador personalizado, siga estas diretrizes para garantir a interação correta com PLINQ e ForEach na TPL:When you implement a custom partitioner, follow these guidelines to help ensure correct interaction with PLINQ and ForEach in the TPL:

  • Se GetPartitions for chamado com um argumento de zero ou menos para partitionsCount, gere ArgumentOutOfRangeException.If GetPartitions is called with an argument of zero or less for partitionsCount, throw ArgumentOutOfRangeException. Embora o PLINQ e o TPL nunca passem um partitionCount igual a 0, mesmo assim, recomendamos que você proteja contra a possibilidade.Although PLINQ and TPL will never pass in a partitionCount equal to 0, we nevertheless recommend that you guard against the possibility.

  • GetPartitions e GetOrderablePartitions devem retornar sempre partitionsCount partições.GetPartitions and GetOrderablePartitions should always return partitionsCount number of partitions. Se o particionador ficar sem dados e não puder criar tantas partições quantas foram solicitadas, o método deverá retornar um enumerador vazio para cada uma das partições restantes.If the partitioner runs out of data and cannot create as many partitions as requested, then the method should return an empty enumerator for each of the remaining partitions. Caso contrário, o PLINQ e o TPL gerarão um InvalidOperationException.Otherwise, both PLINQ and TPL will throw an InvalidOperationException.

  • GetPartitions, GetOrderablePartitions, GetDynamicPartitions e GetOrderableDynamicPartitions nunca devem retornar null (Nothing no Visual Basic).GetPartitions, GetOrderablePartitions, GetDynamicPartitions, and GetOrderableDynamicPartitions should never return null (Nothing in Visual Basic). Se isso ocorrer, PLINQ/TPL gerará um InvalidOperationException.If they do, PLINQ / TPL will throw an InvalidOperationException.

  • Os métodos que retornam partições devem retornar sempre partições que podem enumerar total e exclusivamente a fonte de dados.Methods that return partitions should always return partitions that can fully and uniquely enumerate the data source. Não deve haver nenhuma duplicação na fonte de dados nem itens ignorados, a menos que isso seja especificamente necessário para o design do particionador.There should be no duplication in the data source or skipped items unless specifically required by the design of the partitioner. Se essa regra não for seguida, a ordem de saída poderá ser embaralhada.If this rule is not followed, then the output order may be scrambled.

  • Os seguintes getters boolianos devem sempre retornar com precisão os seguintes valores para que a ordem de saída não seja embaralhada:The following Boolean getters must always accurately return the following values so that the output order is not scrambled:

    • KeysOrderedInEachPartition: Cada partição retorna elementos com índices de chave crescentes.KeysOrderedInEachPartition: Each partition returns elements with increasing key indices.

    • KeysOrderedAcrossPartitions: Para todas as partições retornadas, os índices de chave na partição i são maiores que os índices de chave na partição i-1.KeysOrderedAcrossPartitions: For all partitions that are returned, the key indices in partition i are higher than the key indices in partition i-1.

    • KeysNormalized: Todos os índices de chave aumentam de forma monotônica sem lacunas, começando com zero.KeysNormalized: All key indices are monotonically increasing without gaps, starting from zero.

  • Todos os índices devem ser exclusivos.All indices must be unique. Não pode haver índices duplicados.There may not be duplicate indices. Se essa regra não for seguida, a ordem de saída poderá ser embaralhada.If this rule is not followed, then the output order may be scrambled.

  • Todos os índices devem ser não negativos.All indices must be nonnegative. Se essa regra não for seguida, PLINQ/TPL poderão gerar exceções.If this rule is not followed, then PLINQ/TPL may throw exceptions.

Consulte tambémSee also