高速化

概要

高速化には細かいところから大きなアルゴリズム改善まで。

NETライブラリの高速版を実装

逆コンパイラで見ると高速化の余地が大きいと思われます。

FileStream

Byte[]マネージドメモリからWin32APIのWriteFileにfixedしたポインタを渡している。全てをアンマネージドメモリから操作するようにします。

BinaryReader,BinaryWriter

高速版FileStreamはByte[]ではなくByte*なのでそれに対応した高速版BinaryReader,BinaryWriterを実装する。

ILGenerator

Emitで命令を書き込むたびにByte[]の拡張をしているがこれの拡張をなくし、初期化時に最大長を設定しておくことで高速化させます。

staticフィールドへのアクセス

あるstaticフィールドがあるメソッドで最初にアクセスされるとき、そのstaticフィールドの所属するクラスのstaticメンバが初期化されていなければ初期化する処理が入るようなので遅いようです。
staticクラスが定義されていると遅く、そうでなければ早いと聞いたことがありますがそうではないようです。

改善策

メソッドのループ内で複数回アクセスするときはループ前に作業変数に入れておく。

結合

ハッシュ結合

一般に索引よりハッシュ結合のほうが高速
2つの表の内、少ない行数の表を内側内することでハッシュ表のメモリを節約し構築時間を短縮できる。
ハッシュ関数は現在のところ結合キーのデータ型に対応するGetHashCode()メソッドの値の和を使用している。
メモリが確保できない場合索引を使う。

ソートマージジョイン

ハッシュ結合に比べて二つの表をソートする必要があるので二つの結合列に索引が設定してある場合は使えます。

エクステント走査

速い行の走査方法

for(全エクステント走査){

   for(エクステント内の行走査){
       ....
   }

}
複数エクステントを走査するときはイテレータ的な関数を作るよりはエクステントを走査するループの内側にエクステント内の行を走査するループを入れたほうが速い。考えてみれば至極当然。ごく単純な軽いループを内側に入れることでほとんどの処理をその軽いループで済ませることが出来るため。

遅いが汎用的な行の走査方法

for(エクステント内の行走査){

   ....次の行を走査
   if(行がエクステントをはみ出したら

}
でもソートマージジョインを実現するにはそのイテレータが必要になる。実装は複雑でかなりのコストがかかるため実装の優先順位を下げたほうがいいかな。

API呼び出しにSuppressUnmanagedCodeSecurityAttribute属性

[SuppressUnmanagedCodeSecurity]
[DllImport("kernel32")]
public static extern byte* VirtualAlloc(void* lpAddress,int dwSize,AllocationType flAllocationType,eProtect flProtect);
とする事で呼び出しオーバーヘッドを少し減らせる

並列化

ソート

並列度の高いバイトニックソートというものがある。しかしきわめてオーバヘッドが大きく、キャッシュの局所性を利用することが出来ない。
まだクイックソートを並列化したほうが高速であった。
しかし並列クイックソートには弱点がある。計算量はN*Log2(N)である。65536個のデータをソートすると全要素を最低16回走査する必要がある。
2コアで並列処理できるのはその内15回。
4コアで並列処理できるのはその内14回。
8コアで並列処理できるのはその内13回。
このようにスレッドが増えてもある程度までしか有効に使えない。
とは言ってもデータを範囲に分けて各コアで処理できるためキャッシュが重複せずスーパーリニアリティが働き先の欠点と打ち消しあって事実上リニアにスケールする優れもの。

メモリコピー

大容量のメモリコピーはキャッシュを汚染しない命令、例えばSSE2を利用することで性能向上できる。

集計

マルチスレッディング以外にベクトル命令も使える。大規模であればGPUも使える。

複数の索引更新

同じ行の隣り合った索引を別コアでをアクセスするのでキャッシュコヒーレンシが必要なので意外と性能上がらないかも。

複数表のバキューム

表はそれぞれメモリが独立しているので同期処理は必要ない。

DisposeではなくFinalizerを使う

Finalizerはガベージコレクタにより並列動作する。
Finalizerによる破棄すべきアンマネージドリソース以外の使用中共有リソースは排他処理しておくこと。

シングルスレッド

大きな実行コストを支払ってまで並列化する必要はない。
シングルスレッドでもIntelのプロセッサに有るようなターボモードに期待できる。
これはあるコアしか使われていない場合他のコアを休めて使用しているコアのクロックと電圧を少し上げてシングルスレッド性能を少し上げる機能。

ボトルネック

送受信

実は処理自体はかなり早いのだが大部分はクライアントとの送受信に時間がかかっている。
テストではクライアントの数を増やすことで実行部分をオーバーラップさせることでその時間を隠蔽できる。
GPUはマルチスレッディングによるメモリレイテンシ(今回の送受信時間)隠蔽と同じ手法だね。

stackalloc

小さなサイズの値型を作業変数に入れて処理するときはstackallocで確保したスタック領域を使うことで高速化できます。
C,C++の自動配列変数と異なりサイズは動的に指定できるのが強み。

staticな固定バッファ

static fixedやstatic void*に初期化時に確保した領域を割り当ててて置き、上記のstackallocを使うべきところで使えるなら使う。
再帰的に呼び出され、利用する箇所がプログラムで管理できるならこちらのほうがスタックの解放コストがない。元々stackallocは高速な為それほどメリットがある訳ではない。

GCHandle.Targetのキャスト

TargetはObjectクラスである。
型固有のメソッドを呼び出すとき
C#:(object as 具体的な型).具体的な型の固有のメソッド()
VB:DirectCast(objec,具体的な型).具体的な型の固有のメソッド()
しかしILコードではこのキャストが必要ない。
ILコードをC#風に書くと
object.具体的な型の固有のメソッド()
で実行できてしまうのだ。

ベンチマーク

単体テストで試行錯誤しながら効率的な処理方法、データ構造を見つけている。

仮想メモリ.固定サイズ行.確保:212ms:エクステント数26448
仮想メモリ.固定サイズ行.解放:212ms:エクステント数26448
1000万行を

Rollback処理

TABLE.INSERT処理:5898ms
TABLE.UPDATE処理:14366ms
TABLE.DELETE処理:2219ms
TABLE.Rollback:24811ms

INDEX作業領域をスタック配列にするよう改良

TABLE.INSERT処理:5584ms
TABLE.UPDATE処理:14038ms
TABLE.DELETE処理:2173ms
TABLE.Rollback:24175ms

FIELD作業領域をスタック配列にするよう改良

TABLE.INSERT処理:5496ms
TABLE.UPDATE処理:13618ms
TABLE.DELETE処理:2547ms
TABLE.Rollback:24144ms

索引オフセット計算のオフセットをInt64からInt32へ

TABLE.INSERT処理:5870ms
TABLE.UPDATE処理:14147ms
TABLE.DELETE処理:1826ms
TABLE.Rollback:24634ms

UPDATE,DELETEの開始()にFIELD配列,INDEX配列というString型より低レベルな引数を渡すようにした。UPDATE記録もそれに対応した。

TABLE.INSERT処理:5780ms
TABLE.UPDATE処理:12106ms
TABLE.DELETE処理:1768ms
TABLE.Rollback:21559ms

UPDATEのロールバックのINDEX配列をfixedした

TABLE.INSERT処理:5540ms
TABLE.UPDATE処理:11977ms
TABLE.DELETE処理:1775ms
TABLE.Rollback:21375ms

UPDATE処理で全てのforeachをforにした

TABLE.INSERT処理:5673ms
TABLE.UPDATE処理:10881ms
TABLE.DELETE処理:1688ms
TABLE.Rollback:20452ms

UPDATE処理内部ををDELETE→INSERT処理風に置き換えた

TABLE.INSERT処理:5896ms
TABLE.UPDATE処理:11649ms
TABLE.DELETE処理:1849ms
TABLE.Rollback:17292ms

DELETE処理のforeachをforにした

TABLE.INSERT処理:6099ms
TABLE.UPDATE処理:11426ms
TABLE.DELETE処理:828ms
TABLE.Rollback:17465ms
効果は大きかった。

細かい最適化

TABLE.INSERT処理:5266ms
TABLE.UPDATE処理:10796ms
TABLE.DELETE処理:768ms
TABLE.Rollback:17000ms

追加比較関数をstaticなINSERT関数に渡すようにした

TABLE.INSERT処理:4826ms
TABLE.UPDATE処理:10802ms
TABLE.DELETE処理:752ms
TABLE.Rollback:16883ms

メモリコピーに基本的にInt64を使うようにした。INSERT,UPDATE,DELETEで使うINDEXポインタを必要なデータのみを面罵に格納した構造体を使うようにした。

TABLE.INSERT処理:4760ms
TABLE.UPDATE処理:10568ms
TABLE.DELETE処理:771ms
TABLE.Rollback:16542ms

トランザクション,INSERT,UPDATE,DELETEの仕組みを作り直し

TABLE._INSERT処理:4154ms
TABLE.UPDATE処理:4659ms
TABLE.DELETE処理:817ms
TABLE.Rollback:8413ms

[Amazon商品]

メニュー

高速化

概要