我有一个性能关键的二元决策树，我想将这个问题集中在一行代码上。下面是二叉树迭代器的代码以及对其运行性能分析的结果。

        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 检查对性能有很大的影响。这棵树很大，所以我预计搜索一片叶子需要一段时间，但我想了解在这一行上花费的时间不成比例。

我试过:

• 将空检查与 while 分开 - 命中的是空检查。
• 向对象添加一个 bool 字段并对其进行检查，没有任何区别。比较什么并不重要，问题在于比较。

这是分支预测问题吗？如果是这样，我该怎么办？如果有的话？

我不会假装理解 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

编辑:我决定做一个分支预测测试，我在这段时间内添加了一个相同的 if，所以我们有

while (node.BranchData != null)

和

if (node.BranchData != null)

里面。然后我针对它运行性能分析，执行第一次比较所花的时间是执行第二次比较(始终返回 true)所花时间的六倍。所以它看起来确实是一个分支预测问题 - 我猜我对此无能为力？!

另一个编辑

如果 node.BranchData 必须从 RAM 加载以进行 while 检查，也会出现上述结果 - 然后它会被缓存用于 if 语句。

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

• Could I use a faster data structure than a tree for this?
• Micro optimisations iterating through a tree in C#

最佳答案

The tree is massive

到目前为止，处理器所做的最昂贵的事情不是执行指令，而是访问内存。现代的执行核心CPU比内存总线快 很多 倍。与距离相关的问题是，电信号传输的距离越远，就越难将该信号传送到电线的另一端而不被破坏。解决这个问题的唯一方法是让它变慢。将 CPU 连接到机器中的 RAM 的电线有一个大问题，您可以打开机箱并查看电线。

处理器针对这个问题有一个对策，它们使用缓存，即在 RAM 中存储字节副本的缓冲区。一个重要的是 L1 cache ，通常 16 KB 用于数据，16 KB 用于指令。小，允许它靠近执行引擎。从 L1 缓存中读取字节通常需要 2 或 3 个 CPU 周期。接下来是二级缓存，更大更慢。高档处理器也有一个 L3 缓存，更大更慢。随着工艺技术的改进，这些缓冲区占用的空间更少，并且随着它们靠近内核而自动变得更快，这是新处理器更好以及它们如何设法使用越来越多的晶体管的一个重要原因。

然而，这些缓存并不是完美的解决方案。如果其中一个高速缓存中的数据不可用，处理器仍将在内存访问时停止。在非常慢的内存总线提供数据之前，它无法继续。一条指令可能会损失一百个 CPU 周期。

树结构是个问题，它们不缓存友好。它们的节点往往分散在整个地址空间中。访问内存的最快方法是从顺序地址读取。 L1缓存的存储单位是64字节。或者换句话说，一旦处理器读取了 一个 字节，接下来的 63 个字节就会非常快，因为它们将出现在缓存中。

这使得数组成为迄今为止最高效的数据结构。也是 .NET List<> 类根本不是列表的原因，它使用数组进行存储。其他集合类型也是如此，比如 Dictionary，在结构上与数组不相似，但在内部是用数组实现的。

因此您的 while() 语句很可能会遇到 CPU 停顿，因为它正在取消引用访问 BranchData 字段的指针。下一条语句非常便宜，因为 while() 语句已经完成了从内存中检索值的繁重工作。分配局部变量很便宜，处理器使用缓冲区进行写入。

否则这不是一个简单的问题，将树展平成数组很可能是不切实际的。一点也不，因为您通常无法预测访问树节点的顺序。一棵红黑树可能会有所帮助，但问题尚不清楚。因此，可以得出一个简单的结论是，它已经以您希望的速度运行。如果您需要它运行得更快，那么您将需要更好的硬件和更快的内存总线。 DDR4今年将成为主流。

关于c# - 为什么我的应用程序将 24% 的生命周期用于空值检查？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16561122/