PLINQ および TPL 用のカスタム パーティショナーCustom Partitioners for PLINQ and TPL

データ ソース上で操作を並列化する場合の必須の手順の 1 つは、ソースを複数のスレッドによって同時にアクセスできる複数のセクションにパーティション分割することです。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. PLINQ およびタスク並列ライブラリ (TPL: Task Parallel Library) には、並列クエリまたは ForEach ループを記述するときに透過的に機能する既定のパーティショナーが用意されています。PLINQ and the Task Parallel Library (TPL) provide default partitioners that work transparently when you write a parallel query or ForEach loop. より高度なシナリオでは、独自のパーティショナーをプラグインできます。For more advanced scenarios, you can plug in your own partitioner.

パーティション分割の種類Kinds of Partitioning

データ ソースは、さまざまな方法でパーティション分割できます。There are many ways to partition a data source. 最も効率的な方法は、ソースを複数のサブシーケンスに物理的に分離するのではなく、複数のスレッドが協調して元のソース シーケンスを処理するというものです。In the most efficient approaches, multiple threads cooperate to process the original source sequence, rather than physically separating the source into multiple subsequences. 配列や、長さが事前にわかっている IList コレクションなどの他のインデックス付きソースの場合は、"範囲パーティション分割" が最も簡単なパーティション分割です。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. 各スレッドは、一意の開始インデックスおよび終了インデックスを受け取ります。そのため、他のスレッドで上書きしたり、上書きされたりすることなく、ソースの範囲を処理できます。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. 範囲パーティション分割に必要なオーバーヘッドは、最初に行われる範囲を作成する作業のみです。その後は、追加の同期は不要です。The only overhead involved in range partitioning is the initial work of creating the ranges; no additional synchronization is required after that. したがって、ワークロードが均等に分割されている限り、優れたパフォーマンスを実現できます。Therefore, it can provide good performance as long as the workload is divided evenly. 範囲パーティション分割の欠点は、あるスレッドが早く終了した場合、他のスレッドが作業を終了するのを支援できないことです。A disadvantage of range partitioning is that if one thread finishes early, it cannot help the other threads finish their work.

リンク リストまたは長さがわからない他のコレクションの場合は、"チャンク パーティション分割" を使用できます。For linked lists or other collections whose length is not known, you can use chunk partitioning. チャンク パーティション分割では、並列ループまたは並列クエリ内のすべてのスレッドまたはタスクが、1 つのチャンク内のソース要素をいくつか使用し、それらのソース要素を処理し、その後追加の要素を取得します。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. パーティショナーは、すべての要素が配布され、重複する要素が存在しないことを保証します。The partitioner ensures that all elements are distributed and that there are no duplicates. チャンクは任意のサイズにすることができます。A chunk may be any size. たとえば、「方法:動的パーティションを実装する」で示されているパーティショナーは、1 つの要素のみを含むチャンクを作成します。For example, the partitioner that is demonstrated in How to: Implement Dynamic Partitions creates chunks that contain just one element. チャンクが大きすぎない限り、この種類のパーティション分割は、本質的に負荷分散を実行します。これは、スレッドへの要素の割り当てが事前に決定されないからです。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. ただし、スレッドが別のチャンクを取得する必要があるたびに、パーティショナーが同期のオーバーヘッドを発生させます。However, the partitioner does incur the synchronization overhead each time the thread needs to get another chunk. これらのケースで発生する同期の量は、チャンクのサイズに反比例します。The amount of synchronization incurred in these cases is inversely proportional to the size of the chunks.

一般に、範囲パーティション分割の方が高速なのは、デリゲートの実行時間が短時間から中程度までの長さであり、ソースに多数の要素があり、かつ各パーティションの総作業量がほぼ等価である場合のみです。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. したがってチャンク パーティション分割の方が、ほとんどのケースで高速です。Chunk partitioning is therefore generally faster in most cases. 要素が少ないか、またはデリゲートの実行時間が長いソースでは、チャンク パーティション分割と範囲パーティション分割のパフォーマンスがほぼ等しくなります。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.

TPL パーティショナーは、動的な数のパーティションもサポートします。The TPL partitioners also support a dynamic number of partitions. つまり、たとえば ForEach ループが新しいタスクを作成するときに、パーティションをその場で作成できます。This means they can create partitions on-the-fly, for example, when the ForEach loop spawns a new task. この機能により、パーティショナーをループ自体と共に拡大縮小できます。This feature enables the partitioner to scale together with the loop itself. 動的パーティショナーも本質的に負荷分散を実行します。Dynamic partitioners are also inherently load-balancing. カスタム パーティショナーを作成するときは、ForEach ループから使用できるようにするために、動的パーティション分割をサポートする必要があります。When you create a custom partitioner, you must support dynamic partitioning to be consumable from a ForEach loop.

PLINQ 用の負荷分散パーティショナーの構成Configuring Load Balancing Partitioners for PLINQ

Partitioner.Create メソッドの一部のオーバーロードを使用すると、配列または IList ソース用のパーティショナーを作成し、スレッド間でワークロードの分散を試みるかどうかを指定できます。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. 負荷分散を実行するようにパーティショナーを構成した場合、チャンク パーティション分割が使用され、要素は要求時に小さいチャンクで各パーティションに渡されます。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. この方法は、ループまたはクエリの全体が完了するまで、すべてのパーティションに処理する要素があることを保証するのに役立ちます。This approach helps ensure that all partitions have elements to process until the entire loop or query is completed. 追加のオーバーロードを使用すると、任意の IEnumerable ソースを負荷分散パーティション分割できます。An additional overload can be used to provide load-balancing partitioning of any IEnumerable source.

一般に、負荷分散では、パーティションで比較的頻繁にパーティショナーに要素を要求する必要があります。In general, load balancing requires the partitions to request elements relatively frequently from the partitioner. これに対し、静的パーティション分割を実行するパーティショナーでは、範囲パーティション分割またはチャンク パーティション分割を使用して、各パーティショナーに要素を一度に割り当てることができます。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. この方法では、負荷分散よりもオーバーヘッドが少なくて済みますが、あるスレッドが他のスレッドよりもはるかに多くの作業を行う場合は、実行時間が長くなることがあります。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. 既定では、IList または配列が渡された場合、PLINQ は常に負荷分散なしの範囲パーティション分割を使用します。By default when it is passed an IList or an array, PLINQ always uses range partitioning without load balancing. PLINQ で負荷分散を有効にするには、次の例に示すように、Partitioner.Create メソッドを使用します。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))

特定のシナリオで負荷分散を使用するかどうかを判断する最適な方法は、典型的な負荷およびコンピューター構成の下で操作が完了するまでにどのくらいの時間がかかるかを実験し、計測することです。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. たとえば、静的パーティション分割は、少数のコアしか持たないマルチコア コンピューターでは速度が飛躍的に向上することがありますが、比較的多くのコアを持つコンピューターでは速度が低下することがあります。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.

次の表に、Create メソッドで使用できるオーバーロードを示します。The following table lists the available overloads of the Create method. これらのパーティショナーは、PLINQ または Task での使用に限定されるわけではありません。These partitioners are not limited to use only with PLINQ or Task. これらのパーティショナーは、任意のカスタム parallel コンストラクトでも使用できます。They can also be used with any custom parallel construct.

オーバーロードOverload 負荷分散を使用するUses load balancing
Create<TSource>(IEnumerable<TSource>) AlwaysAlways
Create<TSource>(TSource[], Boolean) ブール型の引数を true と指定した場合When the Boolean argument is specified as true
Create<TSource>(IList<TSource>, Boolean) ブール型の引数を true と指定した場合When the Boolean argument is specified as true
Create(Int32, Int32) NeverNever
Create(Int32, Int32, Int32) NeverNever
Create(Int64, Int64) NeverNever
Create(Int64, Int64, Int64) NeverNever

Parallel.ForEach 用の静的範囲パーティショナーの構成Configuring Static Range Partitioners for Parallel.ForEach

For ループでは、ループの本体がデリゲートとしてメソッドに提供されます。In a For loop, the body of the loop is provided to the method as a delegate. このデリゲートを呼び出すコストは、仮想メソッドの呼び出しとほぼ同じです。The cost of invoking that delegate is about the same as a virtual method call. シナリオによっては、並列ループの本体が小さく、各ループ反復でデリゲートを呼び出すコストが膨大になることがあります。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. そのような状況では、いずれかの Create オーバーロードを使用して、ソース要素に対する範囲パーティション分割の IEnumerable<T> を作成できます。In such situations, you can use one of the Create overloads to create an IEnumerable<T> of range partitions over the source elements. その後、この範囲のコレクションを、本体が通常の for ループで構成される ForEach メソッドに渡すことができます。Then, you can pass this collection of ranges to a ForEach method whose body consists of a regular for loop. この方法の利点は、デリゲートを呼び出すコストが、要素ごとに 1 回ではなく、範囲ごとに 1 回しか発生しないことです。The benefit of this approach is that the delegate invocation cost is incurred only once per range, rather than once per element. 基本的なパターンを次の例に示します。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

ループ内のすべてのスレッドは、指定されたサブ範囲の開始インデックス値と終了インデックス値を含む独自の Tuple<T1,T2> を受け取ります。Every thread in the loop receives its own Tuple<T1,T2> that contains the starting and ending index values in the specified sub-range. 内側の for ループでは、fromInclusive 値および toExclusive 値を使用して、配列または IList を直接ループ処理します。The inner for loop uses the fromInclusive and toExclusive values to loop over the array or the IList directly.

Create オーバーロードのいずれかを使用すると、パーティションのサイズと、パーティションの数を指定できます。One of the Create overloads lets you specify the size of the partitions, and the number of partitions. このオーバーロードは、要素ごとの作業がきわめて少なく、要素ごとに 1 回の仮想メソッド呼び出しでもパフォーマンスに大きな影響が及ぶシナリオで使用できます。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.

カスタム パーティショナーCustom Partitioners

シナリオによっては、独自のパーティショナーを実装するのが適切か、または必須である場合があります。In some scenarios, it might be worthwhile or even required to implement your own partitioner. たとえば、クラスの内部構造に関する知識に基づいて、カスタム コレクション クラスを既定のパーティショナーよりも効率的にパーティション分割できる場合があります。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. または、ソース コレクションの異なる場所にある要素を処理するのにかかる時間についての知識に基づいて、可変サイズの範囲パーティションを作成する必要がある場合があります。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.

基本的なカスタム パーティショナーを作成するには、System.Collections.Concurrent.Partitioner<TSource> からクラスを派生させ、次の表に示すように仮想メソッドをオーバーライドします。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 このメソッドは、メイン スレッドによって 1 回呼び出され、IList(IEnumerator(TSource)) を返します。This method is called once by the main thread and returns an IList(IEnumerator(TSource)). ループまたはクエリ内の各ワーカー スレッドでは、リスト上で GetEnumerator を呼び出して、個別のパーティションに対する IEnumerator<T> を取得できます。Each worker thread in the loop or query can call GetEnumerator on the list to retrieve a IEnumerator<T> over a distinct partition.
SupportsDynamicPartitions true を実装した場合は GetDynamicPartitions を返し、それ以外の場合は false を返します。Return true if you implement GetDynamicPartitions, otherwise, false.
GetDynamicPartitions SupportsDynamicPartitionstrue の場合、このメソッドを必要に応じて GetPartitions の代わりに呼び出すことができます。If SupportsDynamicPartitions is true, this method can optionally be called instead of GetPartitions.

結果が並べ替え可能である必要がある場合、または要素へのインデックス付きアクセスが必要な場合、System.Collections.Concurrent.OrderablePartitioner<TSource> から派生させて、次の表に示すように仮想メソッドをオーバーライドします。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 このメソッドは、メイン スレッドによって 1 回呼び出され、IList(IEnumerator(TSource)) を返します。This method is called once by the main thread and returns an IList(IEnumerator(TSource)). ループまたはクエリ内の各ワーカー スレッドでは、リスト上で GetEnumerator を呼び出して、個別のパーティションに対する IEnumerator<T> を取得できます。Each worker thread in the loop or query can call GetEnumerator on the list to retrieve a IEnumerator<T> over a distinct partition.
SupportsDynamicPartitions GetDynamicPartitions を実装した場合は true を返し、それ以外の場合は false を返します。Return true if you implement GetDynamicPartitions; otherwise, false.
GetDynamicPartitions 通常は GetOrderableDynamicPartitions を単純に呼び出します。Typically, this just calls GetOrderableDynamicPartitions.
GetOrderableDynamicPartitions SupportsDynamicPartitionstrue の場合、このメソッドを必要に応じて GetPartitions の代わりに呼び出すことができます。If SupportsDynamicPartitions is true, this method can optionally be called instead of GetPartitions.

次の表に、3 種類の負荷分散パーティショナーで OrderablePartitioner<TSource> クラスを実装する方法の詳細を示します。The following table provides additional details about how the three kinds of load-balancing partitioners implement the OrderablePartitioner<TSource> class.

メソッド/プロパティMethod/Property 負荷分散なしの IList/配列IList / Array without Load Balancing 負荷分散ありの IList/配列IList / Array with Load Balancing IEnumerableIEnumerable
GetOrderablePartitions 範囲パーティション分割を使用Uses range partitioning 指定された partitionCount のリストに最適化されたチャンク パーティション分割を使用Uses chunk partitioning optimized for Lists for the partitionCount specified 静的な数のパーティションを作成することにより、チャンク パーティション分割を使用Uses chunk partitioning by creating a static number of partitions.
OrderablePartitioner<TSource>.GetOrderableDynamicPartitions サポートしていない機能にアクセスしたときの例外をスローThrows not-supported exception リストおよび動的なパーティションに最適化されたチャンク パーティション分割を使用Uses chunk partitioning optimized for Lists and dynamic partitions 動的な数のパーティションを作成することにより、チャンク パーティション分割を使用Uses chunk partitioning by creating a dynamic number of partitions.
KeysOrderedInEachPartition true を返します。Returns true true を返します。Returns true true を返します。Returns true
KeysOrderedAcrossPartitions true を返します。Returns true false を返します。Returns false false を返します。Returns false
KeysNormalized true を返します。Returns true true を返します。Returns true true を返します。Returns true
SupportsDynamicPartitions false を返します。Returns false true を返します。Returns true true を返します。Returns true

動的パーティションDynamic Partitions

パーティショナーを ForEach メソッドで使用する場合、動的な数のパーティションを返すことができる必要があります。If you intend the partitioner to be used in a ForEach method, you must be able to return a dynamic number of partitions. これは、パーティショナーがループの実行中の任意の時点で、新しいパーティションの列挙子をオンデマンドで供給できることを意味します。This means that the partitioner can supply an enumerator for a new partition on-demand at any time during loop execution. 基本的に、ループで新しい並列タスクを追加するたびに、そのタスク用の新しいパーティションが要求されます。Basically, whenever the loop adds a new parallel task, it requests a new partition for that task. データが順序付け可能である必要がある場合は、System.Collections.Concurrent.OrderablePartitioner<TSource> から派生させて、各パーティション内の各項目に一意のインデックスが割り当てられるようにします。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.

詳細および使用例については、「方法:動的パーティションを実装する」を参照してください。For more information, and an example, see How to: Implement Dynamic Partitions.

パーティショナーのコントラクトContract for Partitioners

カスタム パーティショナーを実装するときは、次のガイドラインに従って、PLINQ および TPL 内の ForEach との適切な相互作用を保証します。When you implement a custom partitioner, follow these guidelines to help ensure correct interaction with PLINQ and ForEach in the TPL:

  • GetPartitionspartitionsCount に 0 以下の引数を指定して呼び出された場合は、ArgumentOutOfRangeException をスローします。If GetPartitions is called with an argument of zero or less for partitionsCount, throw ArgumentOutOfRangeException. PLINQ および TPL が 0 と等しい partitionCount を渡すことはありませんが、このような場合に備えることをお勧めします。Although PLINQ and TPL will never pass in a partitionCount equal to 0, we nevertheless recommend that you guard against the possibility.

  • GetPartitions および GetOrderablePartitions では、常に partitionsCount 個のパーティションを返す必要があります。GetPartitions and GetOrderablePartitions should always return partitionsCount number of partitions. パーティショナーがデータを使い果たし、要求された数のパーティションを作成できない場合、このメソッドでは残りのパーティションのそれぞれについて、空の列挙子を返す必要があります。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. それ以外の場合、PLINQ と TPL はいずれも InvalidOperationException をスローします。Otherwise, both PLINQ and TPL will throw an InvalidOperationException.

  • GetPartitionsGetOrderablePartitionsGetDynamicPartitionsGetOrderableDynamicPartitions では、null (Visual Basic では Nothing) を返さないようにします。GetPartitions, GetOrderablePartitions, GetDynamicPartitions, and GetOrderableDynamicPartitions should never return null (Nothing in Visual Basic). 返した場合、PLINQ または TPL は InvalidOperationException をスローします。If they do, PLINQ / TPL will throw an InvalidOperationException.

  • パーティションを返すメソッドでは、データ ソースを完全かつ一意に列挙できるパーティションを常に返す必要があります。Methods that return partitions should always return partitions that can fully and uniquely enumerate the data source. パーティショナーの設計により特別に必要な場合を除いて、データ ソース内の項目が重複したり、スキップされたりすることがないようにします。There should be no duplication in the data source or skipped items unless specifically required by the design of the partitioner. この規則に従わないと、出力順序が乱れる場合があります。If this rule is not followed, then the output order may be scrambled.

  • 次のブール型の getter では、常に以下の値を正確に返して、出力順序が乱れないようにする必要があります。The following Boolean getters must always accurately return the following values so that the output order is not scrambled:

    • KeysOrderedInEachPartition:各パーティションは、昇順のキー インデックスを持つ要素を返します。KeysOrderedInEachPartition: Each partition returns elements with increasing key indices.

    • KeysOrderedAcrossPartitions:返されるすべてのパーティションについて、パーティション i のキー インデックスは、パーティション 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:すべてのキー インデックスは、0 から始まりギャップなしで単調に増加します。KeysNormalized: All key indices are monotonically increasing without gaps, starting from zero.

  • どのインデックスも一意である必要があります。All indices must be unique. インデックスを重複させることはできません。There may not be duplicate indices. この規則に従わないと、出力順序が乱れる場合があります。If this rule is not followed, then the output order may be scrambled.

  • どのインデックスも負数以外である必要があります。All indices must be nonnegative. この規則に従わないと、PLINQ または TPL が例外をスローする場合があります。If this rule is not followed, then PLINQ/TPL may throw exceptions.

関連項目See also