85000バイト問題はいまだ健在
ガーベージコレクション(GC)のジェネレーションのことを調べたことはあるでしょうか。
.NET FrameworkのGCは現在3つのジェネレーションがあります。
- 極めて短期的なオブジェクトを扱うジェネレーション0
- ある程度の期間に渡って保持されたオブジェクトのジェネレーション1
- 長期的に参照を保持されたものが到達するジェネレーション2
というわけですが、ジェネレーション0と1に関するGCの処理は実に実に高速です。
対してジェネレーション2に入り込んでしまったオブジェクトは、GCによって処理されるのにかなりの処理時間を要します*1。
問題はたったの1つ。85000バイトを超えるオブジェクトは、作られた当初からジェネレーション2に配置されます。なので、一時オブジェクトには本当に向いていません。大体は配列などのコレクションということになるでしょう。
ですから、生成されて即時廃棄されるオブジェクトのために、大きなテーブルを作ってはいけません。GCの稼働時になかなかのパフォーマンス劣化を生み出します。
対策はざっくりと以下のようになります。
- 大きなオブジェクトや配列自体は再利用可能なマネージメントを行う
- 大きなオブジェクトはアンマネージ領域に配置する
- 大きなオブジェクトを作らないためにLinkedListやSortedDictionaryを使用する
(ただし、速度面のコストは十分理解してください) - 頻度が高くなければGCに委ねることももちろん手段の1つ
とはいえ、実際にはオブジェクトで85000バイトなんてあっという間に使ってしまうものです。画像とかを扱えばこの10倍は大きいものなど頻繁に扱うこととなります。
すべてのオブジェクトに対してうまい対処はなかなかできないと思います。なので、この辺りは今後も長く続く課題、ということになるでしょう。
*1:もともと長期保持を目的としたオブジェクトなら別に問題ありません
値型に対する拡張メソッドは、値型のサイズを検討してから
PointとSizeとRectとVectorは業務がら大変高頻度で使うのですが、小さい構造体ながら彼らのIsNaNが馬鹿にならないほど圧迫してきます。とはいっても、10分起動して6億回程度・・・・。
double.IsNaNはRect使用時に2~4回程度、ちょっとした矩形の合成でもやはり数回使われています。何が言いたいかといえば一言で遅いのです。ちなみに演算そのものは最小限です。double値のアドレスをlong*にキャストしてlong値を取得し、ビット演算を2回。これ以上短くできようはずもありません。アセンブラ的には最短と言って良いレベルになります。
ただ、このRect群にはNaNは絶対に入っていないという保証がある場合、これらの処理は無駄なのです。そういうわけで、double.IsNaN等判定を全く省く拡張メソッドを作ってみました。
・・・・遅い。
理由はすぐにわかりました。
Rectに拡張メソッドを作ろうとしてみたら、呼び出すごとに第1パラメータとして32バイト(Rectのサイズ)の余計なスタックが生まれて過剰コピーに苦悩することになりました。
ソースを壊さないという前提で、非publicな メソッドは全部 ref で呼び出すという、これまた気持ちの悪いコードと、大量のRectをまとめて一括合成するメソッドなどを生成してしのぐ羽目となりました。
PointやSizeやVectorの場合、拡張メソッドにしても遅くなるという感じはありませんでした。どうも、16バイトあたりを目安として、大量のスタック転送というものを見直すのが良いようです。
半端にLINQを使う悪手の代表例
古式なC#ですと、ループして、条件を絞り込む書き方が一般的でした。
// 例:1
foreach( var item in Items ) {
if( item.Value > 10.0 ) {
// 何かの処理
}
}
いやぁ、懐かしい。
LINQの登場(というか、メソッドチェインとラムダ式の導入)によって書き方は激変し、このように書くことができます。
// 例:2
Items.Where(item=>item.Value>10.0)
.ForEach(item=> /* 何かの処理 */);
短くまとまって、ループ回数も最小でハッピーです。この書き方は今や当たり前というくらいに浸透しています。
ところで、先日LINQがIEnumerable<TSource>を最適化しているだのということを書きましたが、古い構文との相性はさほど良くないことは書いておかなければならないことを思い出しました。
// 例:3
foreach( var item in Items.Where( e => e.Value > 10.0) ) {
// 何かの処理
}
速度の順序では、特殊な事例でなければ普通では1→3→2となります。ただし、ForEachは実は書き方次第でWhereと組み合わせて高速なコードを書くことができるので、1には届きませんが、2と3の順位は実装次第です。2は.NET Frameworkのメソッドチェイン標準実装のWhere+Selectの工夫のように、高速化余地が多々あるのでまだ有望です。
しかし3については、古い文法と混在していると、そこはコード展開が、2か所で遅いほうのIEnumerable<TSource>になってしまい、最適化の恩恵も最小になってしまいます。
どう直してもまず1には及ばないのですから、3で書くくらいなら1で書いたほうが潔いとも言えます。
古い書き方との混在は、コンパイラによる最適化の余地をつぶしてしまう可能性があります。気を付けましょう。
LINQに慣れた(いまどき普通の)C#プログラマにとっては、この点は色々とコードレビューもあるかと思いますので、ちゃんとコメントで理由を付記することをお忘れなく。
enumはenum以外の用途で使うと遅いのは何故か
このEnumはenumの本分を尽くす限りにおいては高速です。
しかし、C/C++におけるenumとは根本的に異なっており、int等へのキャストは高速なのに、GetHashCode等のクリティカルなシーンにおいて非常に低速な実装を伴っています。具体的にどういうことかというと
Dictionary<TKey,TValue> のTKeyにenumを使うと低速で、TKeyをintにしておいてintにキャストしたenumを使うと高速ということです。
ええ、馬鹿な!と思います。しかし、速度には1桁程度の差が出ます。
アルゴリズム的に線形探索などを繰り返すコードは必要時以外は論外としまして、型によって何故だか速い辞書、遅いHashSetが生まれる理由があります。
遅いといわれるものの多くはGetHashCodeの速度の問題で、最近調べた事例では順位は以下の通り。
- GetHashCodeについては、32bit以下の値型が最速。
- 次いでGuidやTypeなどの値型で品質の良いGetHashCodeを実装するもの(GuidとTypeこの二つは厳密に測定してもほぼ等速です。決して遅くはありません。最適化時でintの4倍程度のコストです)。
- 具体的なGetHashCodeの実装があるクラス(遅い理由はILに展開されたところで callvirt になってしまうからです。惜しいですが。)
- 具体的なGetHashCodeの実装が無いクラス
- そして以下の実装を持つEnumのGetHashCodeは極め付けで低速です。
http://referencesource.microsoft.com/#mscorlib/system/enum.cs#836
それにしても、この実装はどうにかならなかったのでしょうか。何か古いコードが邪魔をしてここで破壊的な変更を行うことができなかったか、糖衣構文の仕様変更を嫌ったか。あと、具体的にintへのキャストで十分な速度を得られるというところも理由かもしれません。
Enumもジェネリックにするクラスデザインとか、個人的には賛成です。誰かこれをC#の糖衣構文化してくれないでしょうか。
もともとC/C++に馴染んだ者として、遅いenumは辛いですからね。
そういえば、enumは列挙も相当遅いので、コードとしては綺麗ではありませんが速度が必要な時はint等からenumへのキャストをしてください。
DependencyPropertyの急所を見つける
WPFに触れたことのある人ならバインディングの便利さを知らぬ人は居ないでしょう。これはその骨にあたる部分の話です。
DependencyObjectを継承したクラスにはDependencyPropertyを使用することができます。これは通常の依存関係プロパティとしてでなく、添付プロパティ、継承プロパティなどにも使用することができます。
そのほか値の有効性の判定や、変更時のコールバックやイベントなどの機能。デフォルト値から変更しなければメモリが節約されること、メタデータの設定に応じて様々な付加機能が使えるところなど、究極的に便利なプロパティです。本当に手厚いものです。
便利である反面、以下のような分かり易いボトルネックを持っています。
- DependencyPropertyは内部の情報保持はObjectであるため、値型を格納する際はボックス化、アンボックス化のコストを必ず持ちます。つまり、GCがフル稼働する要因となります。
- DependencyObject自体の構造はクラスインスタンスとプロパティ名(実際はそのプロパティ名に付された番号)に紐付いた辞書としてグローバルに配置されます。まず、GetHashCode()とEquals()がDependencyObjectでsealedされていることから、このDependencyPropertyはこの部分の出来に相当依存していることがうかがい知れます。
- DependencyPropertyの重要な要素、PropertyMetadataにはいくつかの姉妹版があります。FrameworkPropertyMetadataやUIPropertyMetadataなどです。
それぞれ、複雑さが異なります。FrameworkPropertyMetadataなど、この複雑さを知ってしまうと使うのにためらいが生じるほどです。
最も安価なのはPropertyMetadataです。
あと、基本的な事として、単純なGetterとSetterのコストを理解しておくのは良いでしょう。
Getterの動作
- クラスインスタンスと変数名(変数名は厳密には登録番号)の辞書からObject返します。これが速さを期待できない程度に高負荷の処理であることは想像できるでしょう。また、値型の場合はボックス化されています。
- 一般プロパティでGetValueを用いているなら、戻ってきた値はキャスト(値型の場合はアンボックス化)してプロパティの型に合わせて返します。
Setterの動作
- 設定しようとしている値がデフォルト値と同じ場合は値を削除してデフォルト値に戻して終了します。
-
値の正当性チェックを行います(この処理が実装されている場合、通常はアンボックス化が行われます)。
- Getterの1の動作を行い、現在値を取得します。
-
比較を行い、変更が必要ではない場合、ここで処理を中断します。
- 変更が生じた場合、辞書を書き換えます。
- PropertyMetadataの種類(FrameworkPropertyMetadata、UIPropertyMetadataなど)に応じた更新処理を経ます。
- PropertyMetadataのPropertyChangedCallbackを呼び出します。
- DependencyObjectのOnPropertyChangedを呼び出します。
どこをどうやっても、これだけの処理はSetValueとGetValue周辺で実行されます。Setter側はバインディングされている場合に直接SetValueが呼ばれてしまうため、もはや省略のしようもありません。
となれば、ここを軽量化するにはこのように書くしかありません。
class Hoge : DependencyObject
{
private int _foo = FooProperty.DefaultMetadata.DefaultValue;
public int Foo {
get { return _foo; }
set { SetValue( FooProperty, value ); }
}
static readonly DependencyProperty FooProperty = DependencyProperty.Register( ”Foo", typeof(int), typeof(Hoge), (d,e)=>{ ((Hoge)d)._foo = e.NewValue; });
}
この方法は、バインディングのみで使用するコードには効果がありませんので、コードから直接参照されるプロパティに限るものとします。
また、コーディングする側の原則論としても、普通のプロパティのように気軽にSetterを使用しないことを意味しています。
また、ここまで書いておきながら、_fooのキャッシュを持つことはメモリの無駄という考え方も存在します。少なくとも、グローバルな依存関係プロパティ辞書とクラス内に同一内容の情報を保持することにはなります。
それでも、コード側からの参照がある場合はこの手法は高速化に大きな効果があります。速度とメモリのどちらを選ぶか、それは業務上の様々なシーンによって異なってくるでしょう。
また個人的には、ジェネリックで、ボックス化に正しい配慮の為されたPropertyMetadataがあると、かなり速くなるのではないかと考えています。
Panel.Chidrenのボトルネックについて
Canvasにせよ、Gridにせよ、みんなPanel継承しています。
ですから、Childrenに子コントロールを追加していくことになります。ChildrenはUIElementCollectionです。UIElementCollectionの中身を知っておくことは重要です。中身はVisualCollectionなのですが、これが実は結構曲者です。
これがVisualCollection.Insert()の実装ですが、注目すべきはこの部分。
Visualに子を追加している様のソースを追跡すると、巡り巡ってこんな処理にたどり着きます。
OnVisualChildrenChangedは、VisualTreeが変化するごとに呼び出されます。Panel.ZIndexの変更時と、VisualTreeに対する子の追加が行われる都度、といえばわかりやすいでしょうか。
ともかく、1つのパネルに追加するコントロール数は極力抑えるべきです。*1
場合によっては、パネル内にZIndex単位の層のパネルを内包して、その中に子を追加するなどするのが良いでしょう。ただし、その場合Invalidate系の処理は複雑になることがありますが。*2
あと、無難なところでは仮想化などが現実解でしょうか。
いずれにしても、通常のパネルに1000もの要素を追加していることがあるとするならば、何やら応答が遅い理由はこのあたりにあるのかもしれません。
IEnumerableを扱う諸々について
IEnumerable<TSource> を返すメソッドだからといって、こんなことをしていると凄い遅いコードが出力されます。
yield return new TSource();
yield return new TSource();
yield return new TSource();
プログラムの大半はループで構成されているのですから、ループが速くて悪いという事はありません。
メソッドの内部は、最も効率の良い具象型を用いましょう。ちなみに、上記のコードの最速例は以下のようになります。
return new[] {
new TSource(),
new TSource(),
new TSource()
};
可読性の点では問題ありませんし、yield return を並べるよりは良い動きをします。外部からはIEnumerable<TSource>なので、インターフェース面の問題もありません。
また、MicrosoftはLINQは具象型の種類に応じた個別の最適化を実装しています。 おおまかには、TSource配列、List<TSource>、IEnumerable<TSource>の順で速い実装が本当にあるのです。
http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs#38
C#で高速なコードを書くには、配列を嫌いにならないことが結構肝心です。
List<T>の内部も他のコレクションも内部的にはほとんどが配列です。
遅延評価することが重要といわれる局面でのみ、本当の意味でのIEnumerableが必要となるわけです。
Canvas.LeftやCanvas.Topの動作について
パネルのうちで極めて自由度が高いといえばCanvasですが、使い込めば使い込むほど中身のことをしっかりと理解しておく必要を感じるはずです。
Canvas.Top/Leftはお馴染みですが、こんな風になってます。
- コントロールはUIElementを継承していないと効果がありません。
- VisualTreeHelperでの親がCanvasの場合だけ、InvalidateArrangeを実行します。
MSDNには特殊なシナリオでしか使わぬようにとあれだけはっきり書いてあった気がするのですが、InvalidateArrangeです。
FrameworkPropertyMetadataOption.AffectsParentArrangeではなくこちらを選択したのは、Canvas以外に対して無差別にInvalidateArrangeはしないようにするためだと考えられます。(他の理由もあるかもしれませんが。)
親の型に応じて処理を切り替える必要が多い添付プロパティにはこの種の処理が多いのです。つまり、パネルはMicrosoftにとっては特殊なシナリオなのだと言えるでしょう。
InvalidateArrangeは、Arrange処理中か、既にInvalidateArrangeしていなければ、ContextLayoutManagerのアレンジキューにUIElementを追加します。アレンジキュー自体は結構重い処理なので、これを多用しないようにというのはわからないでもありません。
しかし、1回アレンジキューに追加されれば、Arrange処理が走るまでは同じ処理は回避されます。すぐに処理から抜けるので、再描画が必要な状態においてInvalidateArrangeの利用自体を忌避する理由は実はそれほどありません。
InvalidateArrangeの観点からは、ボトルネックポイントになるのは、無駄に多くのUIElementをアレンジキューに追加してしまう事です。
つづく
callとcallvirtの違いとstructとinterfaceの関係
List<T>の話は具体的なILの話に続いていきます。
ILに変換された後にcallであるかcallvirtであるか、という違いは案外大きいようです。
callである場合、現時点の .NET Frameworkは比較的積極的な最適化を行ってくれます。一方callvirtになる場合の最適化は消極的です。
試しにすべてstruct(値型)でList<T>を実装してみました。
List<T>を実装するという事は大まかには struct StructList<T> : IList<T>というクラスを作成し、GetEnumeratorが返すものはstruct StructList<T>.Enumrator : IEnumerator<T> とするわけです。
そしてここが重要ですが、interfaceを単純に実装するだけでは実は callvirt に変換されるという罠が待っています。
interfaceのメソッドを明示的に実装し、同名で具象型を返す(ただし、具象型の側はinterfaceは実装している)メソッドやプロパティ一式を書きます。ここまでやって初めて、csc.exeはinterfaceメソッドをcallにすることを保証してくれます*1。
ビルド時に最適化を有効として、デバッガを介さずにプログラムを走らせると、通常のList<T>よりも1.2~2倍程度の速度*2、インデクサによるアクセスは最適化の恩恵で配列と同等という真に優れたList<T>の高速版が出来上がります。
足りない機能は、内部配列が変更された際に例外が出ないことと(少しリスクはありますが、デバッグ完了後にDEBUG定義の有無で実装を入れ替えると良いでしょう)、List<T>のように継承ができないことくらいでしょうか。
でも、残念なことにデバッガ上で実行すると、純然たるループの速度が通常のList<T>の2倍以上かかります。これは本当に、内部実装をDEBUG定義の有無で切り替える必要があることを意味します。最適化した後のビルドで速度計測しなければ意味がない、という意見も時々ありますが、それは完成品を使うユーザーの話です。私たち開発者にとって「デバッグ中にコードが遅いことも耐え難い」と私は思います。
コアコードには十分な量のユニットテストコードを書き、Debug版とRelease版の両方で確実に動くことを確認すべきです。十分な安全を確保していれば恐れるには足りません。List<T>の代替コードは200行に収まります。この程度ならば。
なお、列挙中のリストの変更に例外を出すなどの色気を出すとなると、標準の.NET Frameworkのコードには恐らく勝てません。
このあたりは塩加減が重要、という話です。
*1:厳密にはこれも保証ではありません。IEnumeratorの基底インターフェース IDisposableのDisposeは何をどうしてもcallvirtでした。interfaceが他のinterfaceを継承する場合、基底interfaceのメソッドはcallにはなりません。何たることでしょう。ILコードのレベルではここまでです。.NET Framework本体側の最適化に期待するしか無いようです。
*2:call命令で呼ばれる上、内部のILのサイズを28バイトまでは縮めることができるでしょう。これはインライン展開対象となり得ます
List<T>の話
困ったことにList<T>を最近使いたくありません。
List<T>の場合.NET Framework 4.5 時点でいまだに for と foreach では、 forが高速に組めます。
コンパイラやJITの最適化が進化すれば同じ速度になるかと思いきや、いつまで経っても foreachの方が遅いのです。
あっさり言うと理由は2つあります。
- foreachはILコード上は try~finallyで囲われており、Disposeが呼ばれます。IEnumeratorがIDisposableを持っているので仕方ありません。中身は空ですが、インターフェースに対するILのcallvirt(遅延バインディングのcall命令)はインライン展開も省略もしません。
- 列挙子でMoveNext()とCurrentをアクセスするより、List<T>のインデクサ1回アクセスの方が高速です。
興味深いのはList<T>のインデクサは callvirt なのに思いのほか高速なことです。(とはいえ、2回程度同じリストにアクセスする場合は ToArray()してアクセスした方が高速な場合が多いようです。配列とList<T>ですら、速度面ではそれだけの隔たりがあります。しかし、マクロな視点ではGCが効率化されない可能性もあるので、この辺りは丹念な計測で決定づけるべき要素です。)
また、List<T>には専用の struct List<T>.Enumerator が実装されており、それらのメソッドはIL上は call なので (structは継承しないためインターフェースが callvirtにならないので)インライン展開が容易な形になります。
それでも、インデクサより速くはなりません。理由は List<T>.Enumerator.MoveNext() の実装が ILで81バイトあり、インライン展開しないほどのサイズとなっているためです。(.NET Frameworkは通常、32バイトを超えるメソッドをインライン展開しません。*1)
いえ、ここで重要なのはインライン展開がどうのというよりは、ちょっと処理量が多いことでしょうか。どう見ても列挙中にリストが変更されたことを検知することに躍起です。
そのコードはここにあります。
http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs#1209
このあたりのコードを読ませていただきますと、実装方針としてcallにせよcallvirtにせよ、メソッドの呼び出しを減らす設計というものは常に大事です。
また、.NET Frameworkの各種クラスは、GCを強く信頼しながらメモリを最小限に扱うことと、不味い組み方に耐えることには長けていますが、動作が最も速いコードではないことを覚えておく必要があります。
独自のコレクションを作る際には、列挙子の各メソッドをILコード32バイト以下にするための独自実装を行う、というのも実は結構重要なポイントになります。
あと、列挙時にEnumeratorではなくインデクサを使うという最適化ヒントを与える属性でもあれば良いのですが・・・。ただ、foreach中にリストが変更された場合の扱いはやや難しいものになりますが。
これらの点は近いうちにもう少し掘り下げます。
常識とかセオリーには何度もだまされたのです
最後にブログを書いていたころのことを思い出すと、あれからずいぶん技術的な点では変化があったなと思います。あの当時は.NET FrameworkにLINQなんてありませんでしたし、DirectXと相互運用できるOSSもありませんでした。WPFもありませんでした。
ただ、C#登場以来ひたすらに取り組んでいることがありました。
それは、現時点では以下のような事になっています。
それはベンチマークとパフォーマン解析の連続でした。たくさんあるセオリーの組み合わせの工夫でした。そして他の部分は、Microsoftが提唱する常識やセオリーを一部覆すことでした。仕様から陥りがちな罠に対抗することでした。
でもおかげでいろいろなノウハウを獲得することができたと思います。
これができるようになったのも、.NET Frameworkのソースコードが公開されたことと、いろいろなサイトが山ほどの情報を提供してくれたこと、また業務上の機会にも大変恵まれていたことによります。
これらの事柄にはいつも感謝しています。
そして最近、また昔のように少し自分の得た知見を記事にしてみようと考えるようになりました。
慎みながら、根拠を開示しながら、細々とノウハウを書き綴っていきたいと思います。
誤りのご指摘や感想等いただけたらありがたいと思います。
また、当然どこかで既に書かれていることを書くこともあると思いますが、その場合はあたたかく見守っていただけたら幸いです。
職業上のコードを開示することは絶対にありません。ここに書くコードは引用のものを除きすべて私が記述したものとなります。コピーして使用する等、全く問題にしません。断らずに使用してください。
最近ともかく有難かった書籍を1つ紹介させていただきます。
- 作者: Sasha Goldshtein,Dima Zurbalev,Ido Flatow
- 出版社/メーカー: 翔泳社
- 発売日: 2013/11/20
- メディア: Kindle版
- この商品を含むブログ (1件) を見る