微型优化迭代通过一棵树在C＃

我正在一个海量号码处理项目。我从一开始就一直在优化一切，因为我知道这很重要。做性能分析我的代码将其生命中几乎40％的时间花在一个函数中 - 二叉树迭代器。微型优化迭代通过一棵树在C＃

 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％。我猜这是分支预测失败？虽然这种比较被多次击中，并且几乎总是返回正确的，但它使CPU很难预测何时会返回错误。我并不是很了解CPU的低级工作，但是这可能是这种情况吗？

来源

2013-05-07 Will Calderwood

其中一个想法是预取状态（字典）并在数据更改时更新它们。这样，当需要获取节点的状态时，操作将在O（1） – 2013-05-07 09:57:48

中完成。从C++的角度来看......我不知道在C＃中有多少可能，但是当你走过一棵树时，你已经失去了缓存局部性。如果你的所有物体都是通过记忆分散的，那么局部性就消失了。如果你的树很密集，可以考虑将它存储为一个数组或者使用一个内存池（如果你可以用C＃来做）。你也会在这里成为分支预测的受害者。不知道你能否做得更多。 – paddy 2013-05-07 10:00:12

一个_minor_事情可能是将'node.BranchData'存储在一个临时变量中，而不是每次循环迭代加载该字段三次。 – 2013-05-07 10:01:55

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

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-14 22:17:26

感谢你的支持，我运行了我的最新性能测试。在一个1GB的树上100次我的代码花费了5190ms，你花了4827ms，它很小，但是进度很大:-) – 2013-05-14 23:04:39

BranchNodeData看起来像引用类型。它只有0.2％的运行时间，因为它只是指向已经存在的数据，而不是实际上复制或分配任何东西。

您可能会在空检查中受到如此的打击，因为CLR必须进行强制转换才能检查已粘贴的密封类。检查无效性并不一定就是您要的后。有很多方法可以修改该类，以便为您提供一个布尔值来检查该类是否需要尽可能多的计算能力。我真的会走的路线，这是你的ScTreeNode类可以提供的东西。

来源

2013-05-14 22:31:22

我猜你没看过这个位“我尝试在节点上使用布尔标志IsLeaf的空检查，但这是同样的表现击中该行。“;-) – 2013-05-14 22:35:35

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

也就是说，我假设抖动，或CPU，当Child2在当前代码首先引用的是没有足够的智慧加载“反向”缓存SplitInputIndex，SplitValue和Child1。

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

来源

2013-05-22 07:58:08

微型优化迭代通过一棵树在C＃

回答

相关问题