为什么我的应用程序花费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检查与时间分离 – 这是Null检查是否是命中。
- 给对象添加一个布尔型字段并检查它，没有什么区别。 不pipe比较什么，比较就是这个问题。
这是一个分支预测问题？ 如果是的话，我能做些什么呢？ 如果有什么？
我不会假装理解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
编辑：我决定做一个分支预测testing，我添加了一个相同的，如果在这段时间，所以我们有
while (node.BranchData != null)
和
if (node.BranchData != null)
在里面。 然后，我运行了性能分析，并且执行第一次比较的时间比执行第二次总是返回true的比较时间长6倍。 所以看起来这确实是一个分支预测问题 – 我猜我没有办法做到这一点？！
另一个编辑
上面的结果也会发生，如果node.BranchData不得不从RAM加载为while检查 – 它将被caching的if语句。
这是我的第三个类似的话题。 这一次我专注于一行代码。 我在这个问题上的其他问题是：
- 我可以使用比此树更快的数据结构吗？
- 微观优化在C＃中迭代树
树是巨大的
到目前为止，处理器所做的最昂贵的事情是不执行指令，而是访问内存。 现代CPU的执行核心比内存总线快许多倍。 与距离有关的问题，电信号必须传输得越远 ，越难将信号传送到线的另一端而不被损坏。 解决这个问题的唯一办法是让它变慢。 将CPU连接到机器内存的电线的一个大问题是，您可以popupshell并查看电线。
处理器有对这个问题的反措施，他们使用caching ，缓冲区，在RAM中存储的字节副本。 一个重要的是一级caching ，通常是16千字节的数据和16千字节的指令。 小，让它靠近执行引擎。 从L1高速caching读取字节通常需要2或3个CPU周期。 接下来是L2caching，越来越大。 高端处理器也有一个三级caching，越来越大。 随着工艺技术的提高，这些缓冲器占用更less的空间，并且随着接近内核而自动变得更快，这是新型处理器更好以及如何设法使用越来越多的晶体pipe的重要原因。
那些caching不是一个完美的解决scheme。 如果某个caching中的数据不可用，处理器仍然会在内存访问上停顿。 在非常慢的存储器总线提供数据之前，它不能继续。 单条指令可能会损失数百个CPU周期。
树结构是一个问题，他们不caching友好。 他们的节点往往分散在整个地址空间。 访问内存的最快方式是通过从连续地址读取。 L1caching的存储单位是64个字节。 换句话说，一旦处理器读取一个字节，接下来的63 个字节就会非常快，因为它们将会出现在caching中。
这是迄今为止最有效的数据结构。 也是因为.NET List <>类根本不是一个列表，所以它使用一个数组来存储。 对于像Dictionary这样的其他集合types也是如此，在结构上不是与数组类似，而是在内部使用数组来实现。
所以你的while（）语句很可能会受到CPU停顿的影响，因为它是取消引用访问BranchData字段的指针。 下一个语句非常便宜，因为while（）语句已经完成了从内存中检索值的繁重工作。 分配本地variables很便宜，处理器使用缓冲区进行写操作。
不是别的一个简单的问题来解决，扁平化你的树arrays是非常不切实际的。 一点也不，因为你通常无法预测树的节点将被访问的顺序。 红黑树可能会有所帮助，但问题并不清楚。 所以一个简单的结论就是，它已经运行得很快，你可以期待。 如果你需要更快的速度，那么你将需要更快的内存总线更好的硬件。 DDR4今年将成为主stream。
为了配合汉斯关于内存caching效果的很好的回答，我将虚拟内存的讨论添加到物理内存翻译和NUMA效果中。
使用虚拟内存计算机（所有当前的计算机）在进行内存访问时，必须将每个虚拟内存地址转换为物理内存地址。 这是由内存pipe理硬件使用转换表完成的。 该表由操作系统pipe理，每个进程都存储在RAM中。 对于虚拟内存的每个页面 ，在这个翻译表中有一个条目将虚拟映射到物理页面。 还记得汉斯关于内存访问的讨论：昂贵的内存访问：如果每个虚拟到物理的翻译需要内存查找，所有的内存访问将花费两倍的成本。 解决scheme是为翻译表提供一个caching，称为翻译旁视caching （简称TLB）。 TLB不是很大（12到4096个条目），x86-64体系结构上的典型页面大小只有4 KB，这意味着最多可以有16 MB的TLB命中 （可能甚至比Sandy更less） 具有512个项目的TLB大小的桥 ）。 为了减lessTLB未命中的数量，您可以让操作系统和应用程序一起使用，使用更大的页面大小（如2 MB），从而通过TLB命中可以访问更大的内存空间。 本页解释了如何使用Java的大页面， 这可以大大加快内存访问 。
如果你的电脑有多个sockets，那可能是NUMA架构。 NUMA意味着非一致的内存访问。 在这些架构中， 一些内存访问成本比其他更高 。 例如，使用32 GB RAM的双插槽计算机，每个插槽可能有16 GB的RAM。 在这个示例的计算机上，本地内存访问比访问另一个套接字的内存便宜（远程访问速度慢20到100％，甚至更多）。 如果在这样的计算机上，您的树使用20 GB的RAM，则至less有4 GB的数据位于另一个NUMA节点上。如果访问速度比远程内存低50％，则NUMA访问会减慢内存访问速度10％。 另外，如果在一个NUMA节点上只有空闲内存，那么饥饿的节点上所有需要内存的进程将被分配来自其他节点的内存，这些节点的访问会更加昂贵。 更糟糕的是，操作系统可能认为将饥饿节点的部分内存换掉是一个好主意， 这会导致更昂贵的内存访问 。 这在MySQL“swap insanity”问题以及NUMA体系结构的某些解决scheme（在所有NUMA节点上扩展内存访问，咬住远程NUMA访问的子弹以避免交换） 的影响中有更详细的解释。 我也可以考虑将更多的RAM分配给一个套接字（24和8 GB而不是16和16 GB），并确保您的程序安排在更大的NUMA节点上，但这需要物理访问计算机和螺丝刀;-) 。
这本身并不是一个答案，而是强调汉斯·帕斯特（Hans Passant）写的关于记忆系统延迟的问题。
真正高性能的软件 – 比如电脑游戏 – 不仅是为了实现游戏本身而编写的，它还适应于使代码和数据结构充分利用caching和内存系统，即将它们视为有限的资源。 当我处理caching问题时，我通常假设L1会在3个周期内发送数据。 如果不是，我必须去L2我假设10个周期。 对于L330周期和RAM存储器100。
还有一个额外的与内存相关的动作 – 如果你需要使用它 – 会带来更大的惩罚，这就是一个总线锁。 如果您使用Windows NTfunction，总线锁称为关键部分。 如果你使用本土品种，你可以称之为自旋锁。 无论名称如何，在locking到位之前，它会同步到系统中速度最慢的总线主控设备。 速度最慢的总线主控设备可能是连接@ 33MHz的传统32位PCI卡。 33MHz是典型x86 CPU（@ 3.3 GHz）频率的百分之一。 我假设不less于300个循环来完成一个公交车锁，但是我知道他们可以花很长时间，所以如果我看到3000个周期，我不会感到惊讶。
新手multithreading软件开发人员将使用遍布各处的总线锁，然后想知道为什么他们的代码很慢。 诀窍 – 就像所有与记忆有关的事情 – 就是节约访问。
