3

我正在做一个庞大的数字运算项目。从一开始我就一直在优化一切，因为我知道这很重要。进行性能分析时，我的代码几乎 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 的低级工作不是很了解，但这可能是这种情况吗？

4

3 回答 3

3

只是一些代码重写。它可能会有所帮助，因为它至少避免了两次跳跃。

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;

}
于 2013-05-14T22:17:26.973 回答
0

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

您可能在 null 检查中受到了打击，因为 CLR 必须进行强制转换才能检查您粘贴的密封类。检查 null 不一定是您所追求的。有很多方法可以修改该类，以便为您提供一个布尔值来检查它不需要太多的计算能力。老实说，我会走你的 ScTreeNode 类可以提供的东西的路线。

于 2013-05-14T22:31:22.930 回答
0

鉴于其他答案中关于缓存的要点，但与空检查无关，请尝试对BranchNodeData字段的引用进行排序，以便第一个引用允许将以下所有字段加载到缓存中。

也就是说，我假设 Jitter 或 CPU 不够聪明，无法“向后”加载到 cache SplitInputIndex，SplitValue并且在当前代码中首先引用了Child1when 。Child2

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

于 2013-05-22T07:58:08.267 回答