[c#] 내 애플리케이션이 널 검사를 수행하는 데 24 %의 시간을 소비하는 이유는 무엇입니까?

성능에 중요한 이진 의사 결정 트리가 있으며이 질문을 한 줄의 코드에 집중하고 싶습니다. 이진 트리 반복기에 대한 코드는 성능 분석을 실행 한 결과와 함께 아래에 있습니다.

        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 검사와 동안 분리-히트 인 것은 Null 검사입니다.
• 객체에 부울 필드를 추가하고 이에 대해 확인해도 아무런 차이가 없습니다. 무엇을 비교하는지는 중요하지 않습니다. 비교가 문제입니다.

분기 예측 문제입니까? 그렇다면 어떻게해야합니까? 만약 있다면?

나는 CIL 을 이해하는 척 하지는 않겠지 만, 누구든지 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 (node.BranchData != null)

과

if (node.BranchData != null)

그 안에. 그런 다음 이에 대해 성능 분석을 실행했는데, 항상 참을 반환하는 두 번째 비교를 실행하는 것보다 첫 번째 비교를 실행하는 데 6 배 더 오래 걸렸습니다. 그래서 그것은 실제로 분기 예측 문제인 것 같습니다. 그리고 그것에 대해 내가 할 수있는 것이 아무것도 없다고 생각합니다?!

또 다른 편집

위의 결과는 node.BranchData가 while 검사를 위해 RAM에서로드되어야하는 경우에도 발생합니다. 그러면 if 문에 대해 캐시됩니다.

---

이것은 비슷한 주제에 대한 세 번째 질문입니다. 이번에는 한 줄의 코드에 집중하고 있습니다. 이 주제에 대한 다른 질문은 다음과 같습니다.

• 이를 위해 트리보다 빠른 데이터 구조를 사용할 수 있습니까?
• C #의 트리를 통해 반복되는 마이크로 최적화

---

---

답변