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检查与一会儿分开-这就是Nul​​l检查。 向对象添加一个 bool 字段并进行检查，这没有什么区别。被比较的内容无关紧要，而是比较成为问题。 这是分支预测问题吗？如果是这样，我该怎么办？如果有什么？我不会假装理解CIL，但是我会把它发布给任何人，以便他们可以尝试从中获取一些信息。.method public hidebysiginstance 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)在里面。然后，我对此进行了性能分析，执行第一次比较所需的时间比执行总是返回true的第二次比较要花费六倍的时间。因此，看来这确实是一个分支预测问题-我猜我对此无能为力吗？ 另一个编辑如果必须从RAM加载while.check的node.BranchData，则也会发生上述结果-然后将其缓存为if语句。这是我关于类似主题的第三个问题。这次，我只关注一行代码。关于这个问题，我的其他问题是: Could I use a faster data structure than a tree for this? Micro optimisations iterating through a tree in C# 最佳答案 到目前为止，处理器执行的最昂贵的操作是不执行指令，而是访问内存。现代CPU的执行核心比内存总线快许多倍。与距离有关的问题是，电信号必须传播得越远，越难将信号传递到电线的另一端而不会被破坏。解决该问题的唯一方法是使其变慢。将CPU连接到计算机中RAM的电线存在很大问题，您可以弹出机箱并查看电线。处理器有一个针对此问题的对策，它们使用高速缓存，将字节的副本存储在RAM中的缓冲区。重要的是L1 cache，数据通常为16 KB，指令为16 KB。很小，允许它靠近执行引擎。从L1缓存读取字节通常需要2或3个CPU周期。接下来是更大更慢的L2缓存。高档处理器还具有L3高速缓存，更大，更慢。随着制程技术的改进，这些缓冲器占用的空间更少，并且随着距离内核的增加而自动变快，这是更新的处理器变得更好以及如何使用越来越多的晶体管的主要原因。但是，这些缓存不是完美的解决方案。如果其中一个缓存中的数据不可用，则处理器仍将在内存访问上停顿。直到非常慢的内存总线提供了数据，它才能继续。一条指令可能会丢失数百个CPU周期。树形结构是一个问题，它们对不友好，对缓存不友好。它们的节点往往分散在整个地址空间中。访问内存的最快方法是通过读取顺序地址。 L1高速缓存的存储单位为64字节。换句话说，一旦处理器读取一个字节，下一个63就会非常快，因为它们将出现在缓存中。到目前为止，这使数组成为最有效的数据结构。也是.NET List 类根本不是列表的原因，它使用数组进行存储。其他集合类型(例如Dictionary)的结构相同，在结构上与数组在远程上并不相似，但在内部使用数组实现。因此，您的while()语句很可能会遭受CPU停顿的困扰，因为它正在取消引用访问BranchData字段的指针。下一条语句非常便宜，因为while()语句已经完成了从内存中检索值的繁重工作。分配局部变量很便宜，处理器使用缓冲区进行写操作。要解决这个简单的问题不是很简单，将树展平为阵列很不切实际。至少因为您通常无法预测树的节点将以什么顺序访问。红黑树可能会有所帮助，这个问题尚不清楚。因此得出一个简单的结论是，它已经以您希望的速度运行。而且，如果您需要它更快地运行，那么您将需要具有更快内存总线的更好硬件。 DDR4今年将成为主流。