为什么我的应用程序在执行null检查时要花费24%的时间？

Question

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

        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分开-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。因此看起来确实是一个分支预测问题 - 我猜想我无法解决这个问题？!

另一个编辑

如果节点.BranchData必须从RAM加载进行while检查，则会出现上述结果 - 然后将为if语句缓存。

---

这是我关于类似主题的第三个问题。 这次我重点关注单行代码。 我关于此主题的其他问题:

• 我可以使用比树更快的数据结构吗？
• 在C#中迭代树的微小优化

- Will Calderwood

---

请展示 BranchNode 属性的实现。请尝试将 node.BranchData != null 替换为 ReferenceEquals(node.BranchData, null)。这样做有什么区别吗？ - Daniel Hilgarth

你确定这里的24%是指while语句本身，而不是while语句中条件表达式的一部分吗？ - Rune FS

另一个测试：尝试像这样重新编写 while 循环：while(true) { /* current body */ if(node.BranchData == null) return node; }。它改变了什么吗？ - Daniel Hilgarth

稍作优化，代码如下：while(true) { BranchNodeData b = node.BranchData; if(ReferenceEquals(b, null)) return node; node = b.Child2; if (inputs[b.SplitInputIndex] <= b.SplitValue) node = b.Child1; } 这样可以只获取一次 node.BranchData。 - Daniel Hilgarth

请将执行时间最长的两行代码的执行次数相加。 - Daniel Hilgarth

Answer 1

这棵树非常巨大。

迄今为止，处理器所做的最昂贵的事情不是执行指令，而是访问内存。现代 CPU 的执行核心比内存总线快 多 倍。与 距离 有关的问题，电信号需要传输的距离越远，将信号传递到电线的另一端就越难，而且容易出现信号损坏。唯一的解决方法是使其变慢。连接 CPU 和 RAM 的电线存在一个大问题，在您的机器上，您可以弹出外壳并 看到 这些电线。

处理器有一种对策来解决这个问题，它们使用缓存，即存储RAM字节副本的缓冲区。其中一个重要的缓存是L1缓存，通常是16千字节用于数据和16千字节用于指令。它很小，可以靠近执行引擎。从L1缓存读取字节通常需要2或3个CPU周期。接下来是L2缓存，更大但速度较慢。高端处理器还具有L3缓存，更大但速度更慢。随着工艺技术的改进，这些缓冲区占用的空间越来越少，并且随着它们靠近核心而自动变得更快，这是新型处理器更好的重要原因，以及它们如何成功地使用越来越多的晶体管。

然而，这些缓存并不是完美的解决方案。如果数据在其中一个缓存中不可用，处理器仍然会在内存访问上停顿。它必须等到非常慢的内存总线提供数据才能继续。在单个指令上失去100个CPU周期是可能的。

树形结构是一个问题，它们不太适合缓存。它们的节点往往分散在地址空间中。访问内存最快的方式是从连续的地址读取。L1缓存的存储单位为64字节。换句话说，一旦处理器读取了一个字节，接下来的63个字节非常快，因为它们将存在于缓存中。

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

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

虽然不是一个简单的问题，但将树形结构转换为数组很可能不切实际。这主要是因为通常无法预测树的节点将以何种顺序被访问。红黑树可能有所帮助，但从问题描述中并不清楚。因此，可以得出一个简单的结论，即它已经以最快的速度运行了。如果需要更快的速度，则需要更好的硬件和更快的内存总线。DDR4 今年正式成为主流。

- Hans Passant

---

可能。它们很有可能已经相邻存储在内存中，因此在缓存中，因为你是一次性分配了它们。否则，GC堆压缩算法会对此产生不可预测的影响。最好不要猜测，而是应该进行测量，以便你知道一个事实。 - Hans Passant

线程不能解决这个问题。虽然可以提供更多的核心，但仍然只有一个内存总线。 - Hans Passant

也许使用B树可以限制树的高度，因此您需要访问较少的指针，因为每个节点都是单个结构，因此可以在缓存中有效地存储。另请参见此问题。 - MatthieuBizien

深入解释，提供广泛相关信息，像往常一样。 +1 - Tigran

如果您知道树的访问模式，并且它遵循80/20规则（80％的访问总是在相同的20％节点上），那么像伸展树这样的自适应树也可能会更快。http://en.wikipedia.org/wiki/Splay_tree - Jens Timmerman

Answer 2

为了补充Hans关于内存缓存效应的回答，我会讨论虚拟内存到物理内存的转换和NUMA效应。

虚拟内存计算机（所有当前计算机）在进行内存访问时，每个虚拟内存地址都必须翻译成物理内存地址。这是由内存管理硬件使用转换表完成的。该表由操作系统为每个进程管理，并存储在RAM中。对于每个虚拟内存页，该转换表中都有一个条目，将虚拟页映射到物理页。记住汉斯(Hans)关于内存访问代价高昂的讨论：如果每个虚拟到物理的翻译都需要进行内存查找，那么所有内存访问成本都会增加一倍。解决方案是为转换表设置缓存，称为翻译后备缓存（TLB）。TLB不大（12至4096个条目），并且x86-64架构上的典型页面大小仅为4 KB，这意味着最多有16 MB可以直接通过TLB命中访问（实际上可能甚至少于此，Sandy Bridge的TLB大小为512项）。为减少TLB未命中次数，您可以使操作系统和应用程序合作使用更大的页面大小，例如2 MB，从而可通过TLB命中访问更大的内存空间。本页说明了如何在Java中使用大页面，这可以大大加速内存访问。

如果你的电脑有很多插口，那么它可能是一种NUMA架构。 NUMA代表非统一内存访问。在这些架构中，某些内存访问比其他访问更昂贵。例如，对于一个具有32 GB RAM的2插口计算机，每个插口可能有16 GB RAM。在这个例子的计算机上，本地内存访问比访问另一个插口的内存（远程访问比本地慢20％到100％，甚至更多）更便宜。如果在这样的计算机上，您的树使用了20 GB RAM，则您的数据中至少有4 GB位于另一个NUMA节点上，如果远程内存访问速度降低50％，则NUMA访问将使您的内存访问减慢10％。此外，如果您只在单个NUMA节点上有可用内存，则需要内存的所有进程都将从其他访问更昂贵的节点分配内存。更糟糕的是，操作系统可能认为将部分内存交换出去是个好主意，这将导致更昂贵的内存访问。这在MySQL“交换疯狂”问题和NUMA架构的影响中有更详细的解释，其中提供了一些Linux的解决方案（在所有NUMA节点上分散内存访问，在远程NUMA访问上咬紧牙关以避免交换）。我还可以考虑将更多RAM分配给插口（24和8 GB而不是16和16 GB），并确保您的程序安排在较大的NUMA节点上，但这需要物理访问计算机和螺丝刀 ;-）。

- jfg956

Answer 3

这并不是一个具体的答案，而是强调了Hans Passant关于内存系统延迟的内容。 高性能软件（如电脑游戏）不仅编写用于实现游戏本身，还要适应缓存和内存系统，即把它们作为有限资源来处理，以此来使代码和数据结构更充分利用。当我处理缓存问题时，我通常假设如果数据在L1中，它将在3个周期内被传输。如果数据不在L1中，我就会假设需要10个周期去到L2。对于L3，需要30个周期，对于RAM内存，则需要100个周期。还有一种与内存相关的操作，如果需要使用它，将会带来更大的惩罚，那就是总线锁定。如果你使用Windows NT功能，总线锁定也称为临界区。如果你使用自己编写的变体，你可能称之为自旋锁。无论名称如何，它都会在放置锁定之前同步到系统中最慢的总线主控设备。最慢的总线主控设备可能是连接在33MHz的经典32位PCI卡上。 33MHz是典型x86 CPU的频率（@ 3.3 GHz）的百分之一。我假设完成总线锁定需要不少于300个周期，但我知道它们可能需要更长的时间，所以如果我看到3000个周期，我不会感到惊讶。初学者多线程软件开发人员会在代码中大量使用总线锁定，然后想知道为什么他们的代码很慢。对于与内存有关的任何事情，诀窍就是要节省访问次数。

- Olof Forshell