固定サイズバッファによる高速化効果
2009.11.27 金 06:19:57
以前にC#での固定サイズバッファの記述について触れ、そこで｢高速化にも使える｣と書いたことがありますが、実際にどれほどの効果が得られるのかを試すことにしました。
ポインタを使用することにより通常のC#プログラミングからは少し斜め上の知識が必要となる点、また泣いても笑ってもコンパイル時に固定されたサイズとなる点など、独特の扱い方が必要となるテクニックですが、それに見合う効果が得られるでしょうか。
なお公式ドキュメントで固定サイズバッファの目的が｢ネイティブとの相互運用を可能とするもの｣となっているように、元々は高速化のための機能というわけではありません。
低レベルな話も一部含んでいますが、CPUアーキテクチャとしてはIA-32であることを想定しています。
はじめに、構造体のnew
直接は関係ない事項ですが、構造体について注意事項です。
C#においては、構造体もクラスもインスタンス作成には基本的にnewを使います。
ここで、特にC/C++出身者からは勘違いされやすいようなのですが、C#において値型である構造体はnewをした際にヒープではなくスタックに確保されます。
構造体インスタンスがヒープに配置されるのは、クラスメンバとして(配列など)使用されたときとなります。
テストプログラム
80バイトのデータを持つ構造体を、(1)固定サイズバッファによるものと、(2)通常の配列によるものの2通り定義します。(80バイトっていうのは深い意味はありません)
これに対し、A.初期化(領域割り当て)と、B.値の変更をそれぞれ100万回行ったときの時間を比べてみました。
unsafe struct FixedBuffer
{
public fixed int Buffer[20];
public FixedBuffer(int init)
{
//Bufferははじめから確保された領域なのですぐに操作できる
SetValue(init);
}
public void SetValue(int val)
{
fixed(int *p = Buffer)
for(int i = 0; i < 20; i++)
p[i] = val;
}}
struct DynamicBuffer
{
public int[] Buffer;
public DynamicBuffer(int init)
{
Buffer = new int[20];
SetValue(init);
}
public void SetValue(int val)
{
for(int i = 0; i < 20; i++)
Buffer[i] = val;
}
}
static void Main()
{
int num = 1000000;
Stopwatch sw = new Stopwatch();
Console.WriteLine("A. allocate");
sw.Reset();
sw.Start();
FixedBuffer[] fixbuf = new FixedBuffer[num];
for(int i = 0; i < num; i++)
fixbuf[i] = new FixedBuffer(i);
sw.Stop();
Console.WriteLine("{0:f3}ms", 1000f * sw.ElapsedTicks / Stopwatch.Frequency);
sw.Reset();
sw.Start();
DynamicBuffer[] dynbuf = new DynamicBuffer[num];
for(int i = 0; i < num; i++)
dynbuf[i] = new DynamicBuffer(i);
sw.Stop();
Console.WriteLine("{0:f3}ms", 1000f * sw.ElapsedTicks / Stopwatch.Frequency);
Console.WriteLine("B. alter");
sw.Reset();
sw.Start();
for(int i = 0; i < num; i++)
fixbuf[i].SetValue(i * 2);
sw.Stop();
Console.WriteLine("{0:f3}ms", 1000f * sw.ElapsedTicks / Stopwatch.Frequency);
sw.Reset();
sw.Start();
for(int i = 0; i < num; i++)
dynbuf[i].SetValue(i * 2);
sw.Stop();
Console.WriteLine("{0:f3}ms", 1000f * sw.ElapsedTicks / Stopwatch.Frequency);
}
動作結果:
A. allocate
185.598ms
769.134ms
B. alter
68.849ms
72.421ms
領域確保+初期化においては、固定サイズバッファを使用するとnew操作がまるごと省けるため、圧倒的に高速化しています。
一方で値の変更については有意差は無いと言えそうです。
領域さえ確保できていれば、メモリアクセスの速度については変わりません。
純粋に領域確保の時間を比べると、固定サイズバッファでは115msほど、通常の配列を使用した構造体では700msほどであり、このケースでは6倍程度高速化していると言えそうです。
そうは言っても、メモリを80MB、100万回に分けて確保したわけですが、それでも700ms程度(1回あたり0.7μ秒)と、意外にもヒープからの確保は速いんだな、と。
｢効果的｣かどうか
テストした結果、｢領域確保の高速化｣を図ることはできることが確認できました(何せ実質は領域をどこかから確保したわけではないですから)。
実際のプログラムの中で、この効果がどれほど得られるでしょうか。
(長いので｢結論｣まですっ飛ばしてもＯＫです)
- インスタンスのサイズが 16 バイト未満である。
というものがあります。
条件は絶対的なものではありませんが、『これらの条件を 1 つ以上満たしていない場合は、構造体ではなく、参照型を作成します。このガイドラインに従わない場合、パフォーマンスが低下する可能性があります。』とあります。
なお｢16バイト未満｣と言えば文意としては｢15バイト以下｣ですが、こちらの記事で調べたとおり、内部のメンバ変数サイズの合計が8バイトより大きい場合、全体サイズは16バイトに切り上げられます。この条件は実質、構造体にするなら8バイト以下に、という意味となります。
この文では、｢パフォーマンス低下｣の要因として、構造体を使っていると、何かと値を丸ごとコピーすることが生じる、といった点を考慮しているものと思われます。
つまり、
int val = 100;
int val2 = val;
このコードでは、val2はvalとは別領域ながら同じ値をとる、すなわちバイトごとの完全なコピー(いわゆるハードコピー)が行われていることになります。
これは上記サンプルのFixedBuffer型においても同じで、代入を行った際にはバッファの内容は80バイト丸ごとコピーされます。
int数値のコピーであればCPUレジスタの範囲で行えますが、サイズが大きくなると、内部的にはループでコピーすることとなり、コストが大きくなってきます。
このために、ガイドラインでは｢16バイト以上の構造体ではパフォーマンス低下の恐れがある｣と言っているものと思われます。
一方、上記サンプルのDynamicBuffer型は、内部には配列への参照を保持しているだけで、そのサイズ(メモリ占有量)を調べると4バイトとなります(ポインタ型のサイズと等しいわけです)。
ガイドラインの通り、サイズは非常に小さく構造体同士の代入も高速に行えますが、代入を行った場合、メンバである配列の実体は同一のものとなります。
つまりDynamicBuffer型の変数aを作成し、bに代入すると、aやbそれぞれでの変更が相互に反映されることになります。
もしこれを避けたい事情があり、手動でハードコピーしようとした、結局newによるヒープからの確保が生じることになり、上で実験した分の時間的コストがかかることになります。
○結論
長くなりましたが、結論としては、固定サイズバッファによる｢領域確保の高速化｣による効果が実用上得られる場面というのは、
- 値の新規作成が極めて多く発生する場合
- 値のハードコピーが極めて多く発生する場合
に限定されます。
ルービックキューブや8パズル・15パズルをA*アルゴリズムなどで解こうとすれば、このテクニックをパフォーマンスに生かすことができるでしょう。
全体で数割程度の高速化は期待できるかも知れません。
ついでに、時としてハードコピーする必要はなく参照コピーで済ませたい時があります。
典型的な例として、構造体変数をメソッドに渡す際にはコピーが生じますが、これは一般的に｢必要な｣ハードコピーではありません。
このときは、refによる値型の参照渡し(≒4バイト値のコピー)を用いることで解決できます。
C++においても参照渡しはポインタ渡しより好まれる方法(らしい)です。
FixedBuffer構造体に、丸ごと加算するメソッドを追加するとします。
public FixedBuffer Add(FixedBuffer val)
{
FixedBuffer result = this;
int *p1 = result.Buffer;
int *p2 = val.Buffer;
for(int i = 0; i < 20; i++)
p1[i] += p2[i];
return result;
}
こうするとvalは80バイト丸ごとコピーされます。
このため、このメソッドでFixedBuffer型の値コピーは、(1)呼び出し時の引数、(2)変数resultへの代入、(3)returnによる返し と、3回行われることになります。
しかし引数valからは値を読み取るだけなので、わざわざ別領域にコピーして渡すこともありません。
コピーのコストを考えると、refによる参照渡しをした方が良さそうです。
public FixedBuffer Add(ref FixedBuffer val)
{
FixedBuffer result = this;
int *p1 = result.Buffer;
fixed(int *p2 = val.Buffer)
for(int i = 0; i < 20; i++)
p1[i] += p2[i];
return result;
}
こうすれば、このメソッドでのFixedBuffer型の値コピーは1回減り、全体として2割程度は高速化します。
ちなみにDynamicBuffer型に同様のメソッドを追加した場合、内部の配列丸ごとのハードコピーは1度行われるだけですみますが、メモリ確保のコストが大きく、パフォーマンスはだいぶ劣ります。
※固定サイズバッファでは、値の操作のためにいちいちポインタを取得する必要がありますが(fixedブロック)、そのときの記述についてはこちらの記事を参考にしてください。
(追記)
この例の場合は値渡しのままハードコピーを2回に抑えるようにできることに気づきました。
valにthisを足し込んでvalを返せば良いじゃないか…
そちらの方がrefを使うよりスマートで安全だ…
ちなみにC++では演算子をオーバーロードする際には、同じくパフォーマンス上の理由で参照渡しをすることがほぼ常識(らしい)ですが、C#では演算子関数に参照渡しを行うことはできません。
この違いの理由はC++の仕組みと上記の｢ガイドライン｣から導き出すことができますが、長いので割愛します。
理由があるにせよ、不便だとは思いますけど。
以上、 非常にネチネチとしたC#での高速化テクニックの話でした。
結局どんな言語でどんなプログラムを書こうとしても、突き詰めていくと低いレイヤでの思考能力が求められます。
高専教育は5年という長い時間を生かして、そういう能力を身につけられるよう工夫して欲しいものです。
ちなみに今回の話は、私が今年度の第20回高専プロコン競技部門に出場した際に用い、劇的な効果を確認できたテクニックです(決勝までギリギリ勝ち上がれず敗退しましたが…)。
今後しばらくは、このブログでプロコンに使ったテクについても放出していくと思います。