为什么我的应用程序要花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检查从while中分离出来-这是Null检查，这是命中
• 向对象添加布尔字段并根据该字段进行检查，这没有什么区别。比较什么并不重要，比较本身才是问题所在。

这是分支预测问题吗?如果是这样，我该怎么办?如果有什么?

我不会假装理解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的第二次比较所花费的时间的6倍。所以看起来这确实是一个分支预测问题-我猜我对此无能为力?!

上述结果也会发生，如果节点。BranchData必须从RAM中加载用于while检查-然后它将被缓存用于if语句。

这是我对类似话题的第三个问题。这次我只关注一行代码。我对这个主题的其他问题是:

• 我可以使用比树更快的数据结构吗?
• c#中遍历树的微优化