[TechDays 2010] PLINQ のデモについて
今回は、パラレルLINQに関して説明します。PLINQに関しては、用意していたデモの半分もお見せしていませんでした。この意味でのフォローアップを兼ねています。
最初は、手続とLINQ、PLINQでどのように記述方法が違うのかという点です。コードを以下に示します。
//手続
int[] arr = Enumerable.Range(100000000, 100000).ToArray();
bool[] results = new bool[arr.Length];
for (int i = 0; i < arr.Length; i++)
{ results[i] = Utils.IsPrime(arr[i]); }
});
//LINQ
bool[] results = arr
.Select(x => Utils.IsPrime(x))
.ToArray();
//PLINQ
bool[] results = arr.AsParallel()
.Select(x => Utils.IsPrime(x))
.ToArray();
上記のコードで理解できると思いますが「AsParallel」という拡張メソッドを記述することでパラレルLINQとなります。当然のことながら、手続とLINQは一つのスレッド内で実行され、PLINQでは同時実行ランタイムを使って複数のスレッドでタスクとして動作します。複数のタスクで動作しているかどうかをVisual Studio 2010で確認するには、[デバッグ]-[ウインドウ]から[並列スタック]か[並列タスク]を利用することで調べることができます。
PLINQを使う場合に気を付けていただきたいのは、パフォーマンスに関する点です。特にターゲットCPUを「Any」にしてリリースモードでパフォーマンスを計測して欲しい点です。この理由は、64ビットOSの場合に32ビットアプリはWoW64でエミュレートされた状態でCLRが動作するからです。従って、CLRが持つスレッドプールのスケジューラが高速に動作するモードでテストすることで意味のあるパフォーマンス計測ができるようになります。
次にPLINQの基本的な動作を確認するためのコードを以下に示します。
//PLINQ の基本(出力順序)
int[] src = Enumerable.Range(0, 100).ToArray();
var query = src.AsParallel()
.Select(x => x + 2);
foreach (var x in query)
{
outwindow.OutputMessage(x.ToString());
}
このコードで確認していただきたいのは、出力順序の問題です。PLINQが内部的に行う動作とは、以下のようなものです。
- 入力の集合をスレッド毎に分割する(パーティション化)。
- 分割したスレッド毎にタスク(上記ではラムダ式)を処理し、結果を出力バッファに出力する。
- スレッド毎の出力バッファの内容を一つの配列にマージ。
入力された集合をタスク単位に分割して、並列に処理した結果をマージしますので、出力順序はバラバラになるのがPLINQとしての普通の動作になるわけです。これを昇順にするには、「.AsParallel() .AsOrdered() 」 のように「AsOrdered」拡張メソッドを使用する必要があります。これ以外にも、以下のような拡張メソッドがあります。
- Where：条件でフィルタリングします。
- Sum：合計を算出します。
このような拡張メソッドは、LINQでもお馴染みだと思います。LINQと同じとはいいませんが、ほぼ同等の拡張メソッドがParallelEnumerableクラスで定義されています。
続いて、PLINQのを結果を使ってパラレルに別の処理を呼び出すコードを以下に示します。
//結果に対してアクションを呼び出す
int[] src = Enumerable.Range(0, 100).ToArray();
var query = src.AsParallel().AsOrdered()
.Select(x => x + 2);
query.ForAll( x =>
outwindow.OutputMessage(x.ToString()) );
このれいのポイントは、「ForAll」拡張メソッドになります。ご存知のようにLINQは遅延実行が行われます。ということは、ForAllを呼び出すときにPLINQがタスクとしてクエリーを実行し、さらにForAllがタスクとして並列実行されることになります。よって上記のコードでは、表示される順番はバラバラになることを意味します。
続いて複数の配列をマージする例を以下に示します。
//2つの配列を並列処理
int[] src = Enumerable.Range(0, 100).ToArray();
int[] src2 = Enumerable.Range(200, 100).ToArray();
var query = src.AsParallel().AsOrdered()
.Zip(src2.AsParallel().AsOrdered(),
(element1, element2) =>
element1 + element2);
query.ForAll( x =>
outwindow.OutputMessage(x.ToString()) );
このれいは、「for () { for() { }}」のようなネストしたループを処理するものです。このようなネストしたループを処理する場合に、「Zip」拡張メソッドを使用します。これ以外にも様々な使い方が考えられますが、ここでは割愛させていただきます。
・並列アルゴリズムに関連する課題
今度は、PLINQの問題ではなく並列アルゴリズムを利用する場合に発生するであろう課題を扱います。TechDaysの会場で見られた方は記憶にあるかも知れませんが、フラッシュで眩しいスライドになります(まあ、少し難しめということです)。
最初に取り扱うのがGCと組み合わさった場合の例です。以下にコードを示します。
//LINQ
Enumerable.Range(0, 10000000)
.Select(x => new { Value = x })
.Max(x => x.Value)
//PLINQ
ParallelEnumerable.Range(0, 10000000)
.Select(x => new { Value = x })
.Max(x => x.Value);
このコードで注目して欲しいのは、Select拡張メソッドのラムダ式「x => new { Value = 4 } 」です。並列実行される中で1千万回のnewが行われています。これだけのオブジェクトの生成が繰り返されると、当然のこととしてGCが動作するわけです。このサンプルをanyでリリースモードで実行します。CPUの性能に依存しますが、手続のLINQの方が早くなるケースもあります。続いてアプリケーション構成ファイルに以下の記述を行います。
<runtime>
<gcServer enabled="true"/>
</runtime>
これで使用するGCが、ワークステーション用からサーバー用に切り替わります。これでanyでリリースモードで実行すると私のPCの場合は、計測時間がPLINQの方が早くなります。このことから理解できるのは、並列実行中にオブジェクトの生成を繰り返すアルゴリズムであればGCのプロファイルを切り替えるというチューニングが必要だということです。特にパフォーマンスに直結する事前のテストであれば、可能な限り本番環境でGCを含めたチューニングが必要だということを表しているのです。
続いてラムダ式の中でローカル変数(共有メモリ)を使用したコードを以下に示します。
//ローカル変数
int[] count = new int[4];
//手続
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 10000000; j++)
{ count[i] = count[i] + 3; }
}
//PLINQ
int[] count = new int[4];
ParallelEnumerable.Range(0, 4).ForAll(i =>
{
for (int j = 0; j < 10000000; j++)
{ count[i] = count[i] + 3; }
});
このコードは配列であるcountに3を加えるループを1千万回繰り返すだけです。実行してみるとわかりますが、PLINQの方が明らかに遅くなります。なぜ遅いのかといえば、ローカル変数に対するロック待ちが発生しているからですします。手続の場合はシングルスレッドで動作しますから、ローカル変数に対してロック待ちは発生しません。が、PLINQはタスクが複数のスレッドで動作するためにメモリ上に確保されているローカル変数のアクセスに対してロック待ちが発生するのです。この問題を解決する一つのテクニックとして、以下にコードを示します。
//手続
int[] count = new int[4];
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 10000000; j++)
{ count[i] = count[i] + 3; }
}
//PLINQ(メモリオフセット)
const int PADDING = 16;
int[] count = new int[5 * PADDING];
ParallelEnumerable.Range(0, 4).ForAll(i =>
{
int offsetId = (i + 1) * PADDING;
for (int j = 0; j < 10000000; j++)
{ count[offsetId] = count[offsetId] + 3; }
});
この例では配列の作成方法と使用方法に特徴があります。手続パターンは同じですが、PLINQでは以下のようなことを行っています。
- new int[5 * PADDING]として、PADDING定数を加味した配列の大きさを確保している。
- offsetId = (i + 1) * PADDINGとして、添え字にPADDINGを加味した位置を計算している。
実行してみれば明らかになりますが、PLINQの方が早くなります。先ほどの説明と合わせれば、メモリのロック待ちが解消されたということになります。上記のテクニックを理解するには、CPUのキャッシュメモリを理解する必要があります。大体ですが現在のCPUは、キャッシュメモリとして「L0」「L1」「L2」を持っています。この中でL0キャッシュの大きさは、64Kが一般的になっています。L1やL2は大きなキャッシュを持っているケースもありますが、L0(レベル0)は少量でしかないのです。これで勘感の良い方は気が付かれたことでしょう。そうです、キャッシュの無効化を防止するためのテクニックなのです。さらにCPUがメモリをロックする範囲もパディングすることによって回避することを行っているのです。ここから理解できるのは、以下のような課題です。
- ローカル変数(共有メモリ)を書き換えるとロック待ちが発生する。
- ロック待ちを回避するには、ロックフリーな仕組みを利用する必要がある。
- 限定的なテクニックとしてCPU依存の方法がある(キャッシュのパディング)。
.NET Framework 4では、このような用途のためにロックフリーコレクションを用意しています。ここで説明した課題は、PLINQの課題ではなく並列プログラムを記述する上のものです。つまり、並列化するということは、並列動作に耐えうるアルゴリズムを考える必要があるということになります。
それからTechDaysの会場でいただいた質問に、「メモリが大量に必要になるますよね」というものがありました。この答えは、「その通りです」というものです。ここで並列化する前提条件を思い出していただきたいのですが、以下のようなことが考えられると思います。
- 複数コアを持っている(サーバーであれば8や16は当たり前)。
- コア当たり1G以上のメモリを搭載している。
- ともかく時間を短縮したい。
つまりシングルコアの時代と異なって、大量のコアと大量のリソースを使って早くしたいというのが並列化の前提になります。少ないリソースで如何に早くするかという世界とは、真逆の発想だということになります。したがって、リソースが不足するのであればリソースを追加(コストは安いですよね)して、そのリソースを使い切るように並列化するというのが目標になっていくのではないかと、私は考えています。
それからもう一つ皆さんに考えていただきたいのは、マルチコアが一般化していますからプログラムを使用するお客様から早くならないのという疑問にどのように答えていくのかということです。現在はデュアルコアが一般的ですが、クアッドコアが一般的になるPCもそう遠くない年に実現することでしょう。このようなPC環境が一般化したときに、素直にパフォーマンスが向上すれば嬉しいですよね。ですから、並列プログラミングに取り組んでいくのも良いのではないかと私は考えています。