105

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

        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

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

while (node.BranchData != null)

和

if (node.BranchData != null)

里面。然后我对此进行了性能分析，执行第一次比较所花费的时间是执行始终返回 true 的第二次比较所用时间的六倍。所以看起来这确实是一个分支预测问题——我猜我对此无能为力？！

另一个编辑

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

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

4

3 回答 3

182

树很大

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

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

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

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

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

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

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

于 2013-05-15T10:20:40.867 回答
10

为了补充 Hans 关于内存缓存效果的精彩回答，我添加了对虚拟内存到物理内存转换和 NUMA 效果的讨论。

对于虚拟内存计算机（所有当前计算机），在进行内存访问时，必须将每个虚拟内存地址转换为物理内存地址。这是由内存管理硬件使用转换表完成的。该表由操作系统为每个进程管理，它本身存储在 RAM 中。对于虚拟内存的每一页，此转换表中都有一个条目将虚拟页映射到物理页。请记住 Hans 关于昂贵的内存访问的讨论：如果每个虚拟到物理的转换都需要内存查找，那么所有内存访问的成本都会增加一倍。解决方案是为翻译表设置一个缓存，称为翻译后备缓冲区（简称TLB）。TLB 并不大（12 到 4096 个条目），x86-64 架构上的典型页面大小仅为 4 KB，这意味着TLB 命中最多可以直接访问 16 MB（可能甚至更少，Sandy桥的 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 “swap insanity” 问题和 NUMA 架构的影响中有更详细的解释，其中为 Linux 提供了一些解决方案（在所有 NUMA 节点上分散内存访问，在远程 NUMA 访问上咬紧牙关以避免交换）。我还可以考虑为套接字分配更多 RAM（24 和 8 GB 而不是 16 和 16 GB）并确保您的程序安排在更大的 NUMA 节点上，但这需要物理访问计算机和螺丝刀 ;-) .

于 2013-05-23T10:18:50.923 回答
4

这本身并不是一个答案，而是强调 Hans Passant 所写的关于记忆系统延迟的内容。

真正的高性能软件——比如电脑游戏——不仅是为了实现游戏本身而编写的，它还被改编成代码和数据结构可以充分利用缓存和内存系统，即将它们视为有限的资源。当我处理缓存问题时，我通常假设如果数据存在，L1 将在 3 个周期内交付。如果不是，我必须去 L2，我假设 10 个周期。对于 L3 30 个周期和 100 个 RAM 存储器。

还有一个额外的与内存相关的操作——如果你需要使用它——会施加更大的惩罚，那就是总线锁。如果您使用 Windows NT 功能，总线锁称为临界区。如果您使用本土品种，您可能会称其为自旋锁。无论名称如何，它都会在锁定到位之前同步到系统中最慢的总线主控设备。最慢的总线主控设备可能是以 33MHz 连接的经典 32 位 PCI 卡。33MHz 是典型 x86 CPU (@ 3.3 GHz) 频率的百分之一。我假设完成总线锁定至少需要 300 个周期，但我知道它们可能需要很多倍的时间，所以如果我看到 3000 个周期，我不会感到惊讶。

新手多线程软件开发人员会到处使用总线锁，然后想知道为什么他们的代码很慢。诀窍 - 就像与内存有关的所有事情一样 - 是节省访问。

于 2014-01-22T09:40:06.057 回答