通話料金

メソッドを呼び出して実行プロセスを編成するオーバーヘッドは、アプリケーションの実行時間の15％を超えてはならないと考えられています。そうしないと、アプリケーションのリファクタリングとロジックの最適化を真剣に検討する必要があります。 このような考えを持って、.Netで配列をソートするために使用される標準のArraySortHelper<T>クラスのArraySortHelper<T>メソッドに出会いました。

ここで興味深い点は、要素の比較です。柔軟性を確保するために、 IComparer<T>インターフェイスを実装する別のクラスによってレンダリングされます。 さまざまな考えとスタジオを用意して、そのような柔軟性のコストとそれで何ができるかを評価することにしました-カットの下には、QuickSortの操作中に要素を比較するコストの分析があります。



したがって、Hoarのクイックソートの標準実装があります。これは、 IComparer<T>インターフェイスを実装するオブジェクトのCompare(T x, T y)メソッドを使用して、配列要素を比較します。 実験では、リフレクターを使用して、ソート方法のコードを次の形式で取得します。

Copy Source | Copy HTML

1. static public void Sort <T、TValue>（T []キー、TValue []値、 int左、 int右、IComparer <T>比較器）
2. {
3. する
4. {
5. int index = left;
6. int num2 = right;
7. T y =キー[インデックス+（（num2-インデックス）>> 1 ）];
8. する
9. {
10. 試してみる
11. {
12. / * Cmp 1 * / while （comparer.Compare（keys [index]、y）< 0 ）
13. {
14. インデックス++;
15. }
16. / * Cmp 2 * / while （comparer.Compare（y、keys [num2]）< 0 ）
17. {
18. num2--;
19. }
20. }
21. catch （ IndexOutOfRangeException ）
22. {
23. 新しい ArgumentException （ null 、 "keys" ）をスローします。
24. }
25. catch （ 例外 ）
26. {
27. 新しい InvalidOperationException （）をスローします。
28. }
29. if （インデックス> num2）
30. {
31. 休憩 ;
32. }
33. if （インデックス<num2）
34. {
35. T local2 =キー[インデックス];
36. キー[インデックス] =キー[num2];
37. キー[num2] = local2;
38. if （値！= null ）
39. {
40. TValue local3 =値[インデックス];
41. 値[インデックス] =値[num2];
42. 値[num2] = local3;
43. }
44. }
45. インデックス++;
46. num2--;
47. }
48. while （インデックス<= num2）;
49. if （（num2-left）<=（right-index））
50. {
51. if （左<num2）
52. {
53. / * Call 1 * / Sort <T、TValue>（keys、values、left、num2、comparer）;
54. }
55. 左=インデックス。
56. }
57. 他に
58. {
59. if （インデックス<右）
60. {
61. / *呼び出し2 * /ソート<T、TValue>（キー、値、インデックス、右、比較子）;
62. }
63. right = num2;
64. }
65. }
66. while （左<右）;
67. }

比較操作の呼び出しのみを調査するため、この関数に対するすべての変更は、リストの識別コメントでマークされている行1、12、16、53、および61でのみ行われます。

パート1 数値の配列の実験（int）

まず、ソート処理の期間中に2つの数値を比較する操作を呼び出すオーバーヘッドの寄与を推定します。 これを行うには、上記の関数で、「 comparer.Compare(a, b) 」の呼び出しを「 a - b 」の形式の式に変更します。 両方のバージョンの実行時間を測定し、参照してください...恐ろしい画像が表示されます-時間のほぼ3分の2が、比較番号の述部の呼び出しの編成に費やされています。



何がそんなに遅くなるのでしょうか？ 明らかに、ポイントは比較プロセスの過度の複雑さです（これは、演算自体が2つの数値を減算することに削減されるという事実にもかかわらず！）：

1. comparerのnullチェック
2. オブジェクト仮想テーブルでのCompareメソッドの検索
3. comparerオブジェクトのCompareメソッドを呼び出す
4. CompareToメソッドを呼び出す
5. 実際に数字の比較

この場合、最初の2つのポイントは、CIL命令callvirtとcall違いです。 nullチェックの存在によりcallvirtは、仮想性に関係なく、 すべての非静的クラスメソッドを呼び出すために生成されることを思い出させてください。

さて、4番目のポイントは、比較器の標準実装によって呼び出されます（ T代わりにintを置換する場合、 nullすべてのチェックはJITコンパイラーによって自然に削除されnull ）。

Copy Source | Copy HTML

1. クラス GenericComparer < T >：IComparer < T > ここで、 T ： IComparable < T >
2. {
3. public int Compare（ T x、 T y）
4. {
5. if （x！= null ）
6. {
7. if （y！= null ）
8. {
9. return x.CompareTo（y）;
10. }
11. 1を 返します。
12. }
13. if （y！= null ）
14. {
15. return - 1 ;
16. }
17. 0を 返し ます 。
18. }
19. }

レイヤーを一度に1つずつ削除します。これは、 CompareToを呼び出すことから始めます。これは基本的に行われるためです。次の形式の比較CompareTo子を作成します。

Copy Source | Copy HTML

1. クラス IntComparer ： IComparer < int >
2. {
3. public int Compare（ int x、 int y）
4. {
5. return x-y;
6. }
7. }

測定では、15％の確率で勝っています。 そして、すべての構造体のすべてのメソッドに関して、整数の配列を検討し、それらに対してCompareToを呼び出すという事実にもかかわらず、これは非仮想的です。 次の層であるcallvirtとcallときのcall違いは、特にソート機能の柔軟性に関する同じ要件の範囲内で、検証がより困難です。 ただし、不可能なことは何もありません。構造体のインスタンスを操作する場合、インターフェイスから継承されたメソッドの実装を含め、 call操作を使用してすべての構造体のすべてのメソッドが呼び出されます。 これにより、次の最適化を行うことができます。

Copy Source | Copy HTML

1. static public void SortNoVirt <T、TValue、TCmp>（T []キー、TValue []値、 int left、 int right、TCmp comparer） ここで、 TCmp： IComparer <T>
2. {
3. // ...
4. }
6. struct IntComparerNoVirt ： IComparer < int >
7. {
8. public int Compare（ int x、 int y）
9. {
10. return x-y;
11. }
12. }

実際の型がソート関数に転送されるため、ジェネリックパラメーターが展開されると、実際の型の比較演算子が考慮され、より効率的なcall命令が使用されて比較演算が呼び出されます。 時間の測定では、「標準」コールの実行時間の約35％の生産性の向上が示されていますが、引き算によるCompareコールの後続の置き換えからの増加は18％です。

注： C ++のSTLライブラリでは、すべての述語がこの方法で送信されます-型はテンプレートパラメーターを通過します。 さらに、このトリックのおかげで、C ++コンパイラは型に関する完全な情報を取得し、原則として述語コードのインライン化を実行するため、メソッドを呼び出すコストが完全になくなります。 .Net JITの結果を分解した経験から、すべてのトリックとは異なり、ここでは展開が行われないことが示されました。 どうやら、これはジェネリックに関連するか、静的メソッドに対してのみ機能します。

注＃2：空の構造を使用して比較演算子の転送を保存することはできませんでした-C＃のフィールドのない構造のサイズ（ sizeof ）は1に等しいことが判明しました（必要に応じてゼロではありません）。 VC ++では、空の構造体のサイズも1に等しくなりますが、標準では、空のクラス（構造体）のサイズは0より大きい必要があるとされています。 これは、配列「 sizeof(array) / sizeof(array[0]) 」の長さを計算するための一般的な設計のために行われます。 C＃/。Netでは、これは明らかにC ++で書かれたコードとやり取りする際のバイナリ互換性のために行われます。

データを単一のダイアグラムに縮小すると、標準的な方法によるソートの実行時間の次の分布が得られます。



明らかな結論は、計算量の多いライブラリの開発では、頻繁に呼び出される述語構造を作成し、ジェネリックパラメーターを介してその型を転送することが理にかなっているということです。

パート2 そして、オブジェクトはどうですか？

しかし、私たちのアプリケーションは数字で生きているわけではありません:)影響の問題は、オブジェクトの配列を操作するコンテキストで発生しました。 簡単！ このような単純なクラスをプロトタイプとして使用します。

Copy Source | Copy HTML

1. クラス IntObj ： IComparable < IntObj >
2. {
3. パブリックint値 。
5. public int CompareTo（ IntObjその他）
6. {
7. 戻り値 -その他。 値 ;
8. }
9. }

そして、同様の単純な実験を行いますが、オブジェクトの配列を使用すると、結果としてわずかに異なる状況になります。



また、比較プロセスの各部分の比率が変わらない場合、合計時間への寄与は著しく減少します。 非常に幸運な質問が発生します。問題は何ですか、何が遅くなっていますか？ ソート関数のコードをひと目見れば、理解するのに十分です。コードの唯一の異なる部分の処理が遅くなりました-配列要素間の値の交換。 しかし、私たちは参照型を使用しており、ポインタのみが再配置され、それらは数字の「中心」にあります！ おもしろいので、そこで速度が低下し、CILを読んでもあまりメリットがないことが*.refます。交換コードは、数字には*.i4命令を、オブジェクトには*.i4使用する以外はまったく同じです。

CILは役に立たなかったので、JIT出口を意味するので、アセンブラーを見てみましょう:)ここで私たちは多くの問題に直面しています-構成（デバッグ/リリース）に関係なく、JITコンパイラーはその環境を見て、プロセスに接続されたデバッガーの存在に応じて別のコードを生成します。 したがって、[逆アセンブリ]ウィンドウから実際のコードにアクセスするには、デバッグせずにアプリケーションを起動し、 Debugger.Break();の呼び出しの形式でブレークポイントを設定しますDebugger.Break(); 。 以下は、配列の2つのセルの値を交換するために生成されるコードのリストです。

Copy Source | Copy HTML ; ================================================ ; int配列のスワップ ; 124：T local2 = keys [インデックス];

Copy Source | Copy HTML ; ================================================ ; IntObj配列のスワップ ; 124：T local2 = keys [インデックス];

00000142 movsxd rcx、ebx 00000145 mov rsi、qword ptr [rbp + 68h] 00000149 mov rax、qword ptr [rsi + 8] 0000014d cmp rcx、rax 00000150 jae 0000000000000275 00000156 mov edx、dword ptr [rsi + rcx * 4 + 10h] ; 125：キー[インデックス] =キー[num2]; 0000015a movsxd r8、edi 0000015d cmp r8、rax 00000160 jae 0000000000000275 00000166 mov eax、dword ptr [rsi + r8 * 4 + 10h] 0000016b mov dword ptr [rsi + rcx * 4 + 10h]、eax ; 126：キー[num2] = local2; 0000016f mov dword ptr [rsi + r8 * 4 + 10h]、edx

00000146 movsxd r12、ebx 00000149 mov rsi、qword ptr [rbp + 68h] 0000014d mov rax、qword ptr [rsi + 8] 00000151 cmp r12、rax 00000154 jae 0000000000000285 0000015a mov r14、qword ptr [rsi + r12 * 8 + 18h] ; 125：キー[インデックス] =キー[num2]; 0000015f movsxd r13、edi 00000162 cmp r13、rax 00000165 jae 0000000000000285 0000016b mov r8、qword ptr [rsi + r13 * 8 + 18h] 00000170 mov edx、ebx 00000172 mov rcx、rsi 00000175呼び出しFFFFFFFFEF5F7CB0 ; 126：キー[num2] = local2; 0000017a mov r8、r14 0000017d mov edx、edi 0000017f mov rcx、rsi 00000182呼び出しFFFFFFFFEF5F7CB0

リストでは、オブジェクトの配列に書き込む関数の呼び出しにすぐに気付き、CILを監視している間はこの呼び出しはありませんでした。 明らかに、この関数は単にアドレスをコピーするだけではなく、この呼び出しを整理するコストに加えて、何か他のものを取得します。つまり、詳細はCLRの実装にあります。 実際、パブリックバージョンのCLR 2.0（SSCLI 2.0パッケージ）のソースを読んだ後、次のコードが見つかりました。

Copy Source | Copy HTML

1. / **************************************************** **************************** /
2. / *適切なチェックをすべて行った後、配列[idx]に「val」を割り当てます* /
4. HCIMPL3（ void 、JIT_Stelem_Ref_Portable、PtrArray *配列、符号なしidx、 Object * val）
5. {
6. if （！配列）
7. {
8. FCThrowVoid（kNullReferenceException）;
9. }
10. if （idx> = array-> GetNumComponents（））
11. {
12. FCThrowVoid（kIndexOutOfRangeException）;
13. }
15. if （val）
16. {
17. MethodTable * valMT = val-> GetMethodTable（）;
18. TypeHandle arrayElemTH = array-> GetArrayElementTypeHandle（）;
20. if （arrayElemTH！= TypeHandle（valMT）&& arrayElemTH！= TypeHandle（g_pObjectClass））
21. {
22. TypeHandle :: CastResult result = ObjIsInstanceOfNoGC（val、arrayElemTH）;
23. if （result！= TypeHandle :: CanCast）
24. {
25. HELPER_METHOD_FRAME_BEGIN_2（val、配列）;
27. //これはArrayStoreCheck（＆val、＆array）;と同等です。
28. #ifdef STRESS_HEAP
29. //ストレスレベルが十分に高い場合、すべてのjitでGCを強制します
30. if （g_pConfig-> GetGCStressLevel（）！= 0
31. #ifdef _DEBUG
32. &&！g_pConfig-> FastGCStressLevel（）
33. #endif
34. ）
35. GCHeap :: GetGCHeap（）-> StressHeap（）;
36. #endif
38. #if CHECK_APP_DOMAIN_LEAKS
39. //インスタンスがアジャイルの場合、またはアジャイルをチェックする
40. if （！arrayElemTH.IsAppDomainAgile（）&&！arrayElemTH.IsCheckAppDomainAgile（）&& g_pConfig-> AppDomainLeaks（））
41. {
42. val-> AssignAppDomain（array-> GetAppDomain（））;
43. }
44. #endif
45. if （！ObjIsInstanceOf（val、arrayElemTH））
46. {
47. COMPlusThrow（kArrayTypeMismatchException）;
48. }
50. HELPER_METHOD_FRAME_END（）;
51. }
52. }
54. //最適化されたJIT_Stelem_Refのパフォーマンスゲイン
55. // jitinterfacex86.cppは、主にJIT_WriteBarrierReg_Bufの呼び出しが原因です。
56. //ここで直接書き込みバリアを呼び出すことにより、
57. //インラインアセンブリをMSVCからgccに変換することを回避できます
58. //ほとんどのパフォーマンス向上を維持しながら。
59. HCCALL2（JIT_WriteBarrier、（ Object **）＆array-> m_Array [idx]、val）;
61. }
62. 他に
63. {
64. // NULLの書き込みバリアを通過する必要はありません
65. ClearObjectReference（＆array-> m_Array [idx]）;
66. }
67. }
68. HCIMPLEND

これからわか​​るように、オブジェクトの配列に要素を書き込む場合、配列の境界の標準チェックに加えて、型の互換性もチェックされ、必要に応じて適切な変換が実行されます。 文字列型であり、C＃自体にも型制御が含まれていることに注意する価値がありますが、情報はSystem.Objectの形式でCIL命令にすでに含まれているため、CLRは信頼性を再確認します。

パート3。 結論の類似性

このすべてからどのような結論を引き出すことができますか？ 筋金入りの最適化は提供しませんが、特にミニチュアの述語関数では、大きなループ内での仮想呼び出しを避けることは理にかなっています。 実際には、これはたとえば次のとおりです。

• クラスではなく構造の形式で述語を実装し、その後にジェネリックパラメーターを介して型情報を予測する
• 小さな実用的なクラスメソッドを静的拡張メソッドに置き換えます。静的拡張メソッドは、静的な性質のため、仮想テーブルをバイパスするために呼び出されます

もちろん、これらは唯一の可能な結論ではありませんが、読者は思考のために部屋を離れる必要があります:)