为什么我的应用程序花费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检查对性能造成了巨大冲击.树是巨大的,所以我希望寻找一片叶片需要一段时间,但我想了解花在这一行上的不成比例的时间.

我试过了:

• 将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 (node.BranchData != null)

和

if (node.BranchData != null)

在里面.然后,我对此进行了性能分析,执行第一次比较所需的时间长了六倍,执行第二次比较总是返回true.所以它看起来确实是一个分支预测问题 - 我猜我无能为力吗？!

另一个编辑

如果必须从RAM加载node.BranchData进行while检查,也会出现上述结果 - 然后将其缓存为if语句.

---

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

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

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今年将成为主流.

Answer 2

为了补充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,则在另一个NUMA节点上至少有4 GB的数据,如果远程内存的访问速度低50%,则NUMA访问会使您的内存访问速度降低10%.此外,如果您在单个NUMA节点上只有空闲内存,那么在饥饿节点上需要内存的所有进程将从另一个节点分配内存,访问更加昂贵.即便最糟糕的是,操作系统可能认为更换饥饿节点的部分内存是个好主意,这会导致更昂贵的内存访问.这在MySQL"交换疯狂"问题以及NUMA体系结构的影响中有更详细的解释,其中给出了Linux的一些解决方案(在所有NUMA节点上扩展内存访问,在远程NUMA访问中咬住子弹以避免交换).我还可以考虑为插槽分配更多的RAM(24和8 GB而不是16和16 GB)并确保您的程序安排在较大的NUMA节点上,但这需要物理访问计算机和螺丝刀;-) .