在C#中遍历树的微小优化

Question

我正在进行一项规模庞大的数字计算项目。从一开始就一直在优化每个细节，因为我知道这很重要。通过性能分析，我的代码中有将近40%的时间被耗费在一个函数上——二叉树迭代器。

        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;
        }

有没有 C# 优化专家有关于进一步优化的建议？所有比较都是浮点数。我知道理论上它不应该有影响，但我使用的是字段而不是属性来确保优化。在这里稍微节约一点时间可能会缩短几天的处理时间。

请不要回复“在实际情况中这些优化无关紧要”的话 - 因为在这种情况下它们很重要。 :-)

编辑：根据下面的评论，我已经更新了代码，并添加了每行代码的性能分析输出。正如您所看到的，主要的杀手是空值检查 - 为什么？我尝试在节点上使用布尔标志 IsLeaf 来替代空值检查，但是那一行的性能也受到了影响。

分支节点对象的代码如下：

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;
}

另一个编辑：在这里进一步思考...我在想为什么这行代码

BranchNodeData b = node.BranchData;

在执行过程中，注册处占0.2％，而空比较行占17.7％。我猜这是分支预测失败了？虽然该比较被多次击中，并且几乎总是返回true，但这使得CPU很难预测何时会返回false。我对CPU的低级工作原理不是很了解，但这可能是情况吗？

- Will Calderwood

---

仅从C++角度思考...我不知道在C#中有多少是可能的，但当你遍历一棵树时，你已经失去了缓存局部性。如果你所有的对象都散布在内存中，那么就没有局部性了。如果你的树是密集的，考虑将其存储为数组或使用内存池（如果你可以在C#中这样做）。在这里，你也会成为分支预测的受害者。不确定你能否对此做出多少改变。 - paddy

有个小细节可能是将 node.BranchData 存储在一个临时变量中，而不是在每次 while 循环迭代中加载该字段三次。 - Chris Sinclair

尝试用 node = node.BranchData.Children[(1 + Math.Sign(inputs[node.BranchData.SplitInputIndex] - node.BranchData.SplitValue))/2]; 替换掉 if 语句。 - Sergey Kalinichenko

@WillCalderwood由于这是一棵二叉树（我认为），是否有可能放弃“Children”集合，直接引用“Child1”和“Child2”，避免集合查找？ - Chris Sinclair

Chris，我按照你说的做了。确实提高了15%的速度。谢谢。 - Will Calderwood

Answer 1

只需简单地重写代码，这可能会有所帮助，因为它至少避免了两次跳转。

public ScTreeNode GetNodeForState(int rootIndex, float[] inputs)
{

    ScTreeNode node = RootNodes[rootIndex].TreeNode;

    while (node.BranchData != null)
    {
        BranchNodeData b = node.BranchData;
        node = b.Child2;
        if (inputs[b.SplitInputIndex] <= b.SplitValue))
            node = b.Child1;
    }

    return node;

}

- Zoran Horvat

---

谢谢你。我运行了最新的性能测试。在一个1GB的树中搜索每个叶子100次。我的代码花费了5190毫秒，而你的则花费了4827毫秒。虽然进展很小，但也是进步。 :-) - Will Calderwood

Answer 2

BranchNodeData看起来像是一个引用类型。它只占据了你运行时的0.2%，因为它只是指向已经存在的数据的指针，而不是实际复制或分配任何东西。

你可能会在空值检查上遇到问题，因为CLR需要进行强制转换才能检查你粘贴进去的密封类。在那里检查空值并不一定是你想要的。有很多方法可以修改那个类，以便给你一个布尔值来检查，这不需要太多的计算能力。我会诚实地选择让你的ScTreeNode类提供这样的功能。

- Jason M

---

我猜你没有读到这一段：“我尝试在节点上使用布尔标志IsLeaf而不是空检查，但在那一行上它的性能损失相等。”;-) - Will Calderwood

Answer 3

考虑到缓存的相关问题，但与空值检查无关，请尝试对BranchNodeData字段的引用进行排序，以便第一个引用允许所有以下字段加载到缓存中。

也就是说，我假设Jitter或CPU不足够聪明，无法在当前代码中首先引用Child2时“向后”缓存SplitInputIndex、SplitValue和Child1。

因此，要么更改BranchNodeData类中字段的顺序，要么将set; if ... overwrite;更改为if ... else。

- Mark Hurd