[解決済み] なぜ私のアプリケーションは動作時間の24％をNULLチェックに費やすのですか？

質問

私はパフォーマンスが重要な二分木を持っており、この質問を一行のコードに集中させたいと思います。バイナリ ツリー イテレータのコードは、それに対してパフォーマンス分析を実行した結果とともに、以下のとおりです。

        public ScTreeNode GetNodeForState(int rootIndex, float[] inputs)
        {
0.2%        ScTreeNode node = RootNodes[rootIndex].TreeNode;

24.6%       while (node.BranchData != null)
            {
0.2%            BranchNodeData b = node.BranchData;
0.5%            node = b.Child2;
12.8%           if (inputs[b.SplitInputIndex] <= b.SplitValue)
0.8%                node = b.Child1;
            }

0.4%        return node;
        }

BranchDataはプロパティではなく、フィールドです。 インライン化されないリスクを防ぐためにこうしました。

BranchNodeDataクラスは以下のようなものです。

public sealed class BranchNodeData
{
    /// <summary>
    /// The index of the data item in the input array on which we need to split
    /// </summary>
    internal int SplitInputIndex = 0;

    /// <summary>
    /// The value that we should split on
    /// </summary>
    internal float SplitValue = 0;

    /// <summary>
    /// The nodes children
    /// </summary>
    internal ScTreeNode Child1;
    internal ScTreeNode Child2;
}

ご覧のとおり、whileループとnullチェックはパフォーマンスに大きな打撃を与えています。ツリーは巨大なので、リーフを検索するのに時間がかかることは予想されますが、その1行に費やされる不釣り合いな時間を理解したいと思います。

試してみました。

• Null チェックと while を分離する - ヒットするのは Null チェックです。
• オブジェクトに boolean フィールドを追加し、それに対してチェックしても、違いはありませんでした。比較されるものは問題ではなく、比較することが問題なのです。

これは分岐予測の問題なのでしょうか。もしそうなら、どうしたらよいのでしょうか？何かあれば教えてください。

を理解したふりをするつもりはありません。 CIL を理解したふりをするつもりはありませんが、誰でもそこから情報をかき集められるように、それを掲載しておきます。

.method public hidebysig
instance class OptimalTreeSearch.ScTreeNode GetNodeForState (
    int32 rootIndex,
    float32[] inputs
) cil managed
{
    // Method begins at RVA 0x2dc8
    // Code size 67 (0x43)
    .maxstack 2
    .locals init (
        [0] class OptimalTreeSearch.ScTreeNode node,
        [1] class OptimalTreeSearch.BranchNodeData b
    )

    IL_0000: ldarg.0
    IL_0001: ldfld class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode> OptimalTreeSearch.ScSearchTree::RootNodes
    IL_0006: ldarg.1
    IL_0007: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode>::get_Item(int32)
    IL_000c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.ScRootNode::TreeNode
    IL_0011: stloc.0
    IL_0012: br.s IL_0039
    // loop start (head: IL_0039)
        IL_0014: ldloc.0
        IL_0015: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
        IL_001a: stloc.1
        IL_001b: ldloc.1
        IL_001c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child2
        IL_0021: stloc.0
        IL_0022: ldarg.2
        IL_0023: ldloc.1
        IL_0024: ldfld int32 OptimalTreeSearch.BranchNodeData::SplitInputIndex
        IL_0029: ldelem.r4
        IL_002a: ldloc.1
        IL_002b: ldfld float32 OptimalTreeSearch.BranchNodeData::SplitValue
        IL_0030: bgt.un.s IL_0039

        IL_0032: ldloc.1
        IL_0033: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child1
        IL_0038: stloc.0

        IL_0039: ldloc.0
        IL_003a: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
        IL_003f: brtrue.s IL_0014
    // end loop

    IL_0041: ldloc.0
    IL_0042: ret
} // end of method ScSearchTree::GetNodeForState

編集します。 分岐予測テストをしてみようと思い、whileの中に同一のifを追加してみました。

while (node.BranchData != null)

と

if (node.BranchData != null)

の中にあります。最初の比較の実行には、常に true を返す 2 番目の比較の実行の 6 倍の時間がかかりました。つまり、これは本当に分岐予測の問題であり、私にはどうすることもできないと思います。

別の編集

上記の結果は、whileチェックのためにnode.BranchDataをRAMから読み込む必要があった場合にも発生します - そしてそれはif文のためにキャッシュされます。

これは、同様のトピックに関する私の 3 つ目の質問です。今回は1行のコードに焦点を当てます。 このテーマに関する私の他の質問は、次のとおりです。

• これには、ツリーよりも高速なデータ構造を使用できますか？
• C#でツリーを反復するマイクロ最適化

どのように解決するのですか？

ツリーが巨大化している

プロセッサが行うことの中で最もコストがかかるのは、命令を実行することではなく、メモリにアクセスすることです。最近の実行コアは CPU は 多く 倍速いです。に関連する問題 距離 電気信号が遠くなればなるほど、その信号を破損させることなく電線の反対側に届けるのが難しくなります。この問題を解決する唯一の方法は、信号の速度を遅くすることです。マシンのCPUとRAMをつなぐワイヤーに大きな問題があり、ケースを開けると を見る のワイヤーを見ることができます。

プロセッサはこの問題への対抗策として キャッシュ というバッファを使用し、バイトのコピーを RAM に保存します。重要なのは L1キャッシュ , データ用に通常16キロバイト、命令用に16キロバイトです。小さいので、実行エンジンの近くに置くことができます。L1キャッシュからバイトを読み取るには、通常2、3CPUサイクルが必要です。次はL2キャッシュで、より大きく、より低速です。アップスケールプロセッサーにはL3キャッシュもあり、こちらはさらに大きく低速です。プロセス技術の向上により、これらのバッファはより小さなスペースで済むようになり、コアに近づくにつれて自動的に高速化します。これは、新しいプロセッサがより優れており、増え続けるトランジスタの数をどのように使用するかの大きな理由です。

しかし、これらのキャッシュは完全な解決策ではありません。データがキャッシュのいずれかに存在しない場合、プロセッサはメモリ アクセスでストールします。非常に低速なメモリ バスがデータを供給するまで、処理を続行することはできません。1つの命令で何百ものCPUサイクルを失う可能性があるのです。

ツリー構造は問題であり、それらは ではなく キャッシュフレンドリーではありません。そのノードはアドレス空間全体に散らばる傾向があります。メモリにアクセスする最速の方法は、シーケンシャルアドレスから読み出すことである。L1キャッシュの記憶単位は64バイトである。言い換えれば、プロセッサが一度読み込んだ 1 バイトを読み取ると、次の63バイトはキャッシュに存在することになるため、非常に高速になります。

を作るのは 配列 が最も効率的なデータ構造です。.NET の List<> クラスがリストではなく、ストレージに配列を使用しているのもそのためです。辞書のような他のコレクションタイプについても同様で、構造的には配列とは似ても似つかぬものですが、内部的には配列で実装されています。

つまり、while() 文は BranchData フィールドにアクセスするためにポインタをデリファレンスしているため、CPU ストールに悩まされる可能性が非常に高いのです。while()ステートメントがすでにメモリから値を取得するという重い仕事をしたため、次のステートメントは非常に安上がりです。ローカル変数の代入は、プロセッサが書き込みのためにバッファを使用するため、安価です。

そうでなければ、解決するための簡単な問題ではなく、ツリーを配列に平らにすることは、非常に現実的でない可能性が高いです。少なくとも、ツリーのノードがどの順番で訪問されるかを一般的に予測できないからです。赤黒い木は役に立つかもしれませんが、問題からは明らかではありません。ですから、単純な結論として、それはすでにあなたが望むだけの速度で動いているのです。もし、もっと速くする必要があるなら、より高速なメモリバスを備えたより良いハードウェアが必要でしょう。 DDR4 は今年主流になりつつあります。