在C＃中迭代树的微优化
我正在做一个大规模的运算项目。 我从一开始就一直在优化所有内容，因为我知道它很重要。 进行性能分析我的代码在一个函数中花费了近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而不是null检查，但是在该行上它的性能相同。
分支节点对象的代码如下：
public sealed class BranchNodeData { /// /// The index of the data item in the input array on which we need to split /// internal int SplitInputIndex = 0; /// /// The value that we should split on /// internal float SplitValue = 0; /// /// The nodes children /// internal ScTreeNode Child1; internal ScTreeNode Child2; }
另一个编辑：在这里更多的思考…我想知道为什么这条线
BranchNodeData b = node.BranchData;
注册执行率为0.2％，空对比线注册17.7％。 我猜这是一个分支预测失败？ 虽然这种比较被多次击中，并且几乎总是返回true，但是CPU很难预测它什么时候会返回false。 我对CPU的低级工作情况不太了解，但情况可能就是这样吗？
只是一些代码重写。 它可能会有所帮助，因为它可以避免至少两次跳跃。
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; }
BranchNodeData看起来像一个引用类型。 它仅占运行时的0.2％，因为它只是指向已存在的数据，而不是实际复制或分配任何内容。
你可能会在空检查上受到这样的打击，因为CLR必须进行强制转换才能检查你粘贴的密封类。检查无效性并不一定是你所追求的。 有很多方法可以修改该类，为您提供一个布尔值来检查，这不需要那么多的计算能力。 老老实实地说，这是你的ScTreeNode类可以提供的东西。
鉴于关于缓存的其他答案中提出的观点，但与空检查无关，请尝试对BranchNodeData字段的引用进行排序，以便第一个引用允许将所有以下字段加载到缓存中。
也就是说，我假设在当前代码中首先引用SplitInputIndex ，Jitter或CPU不够智能地加载“向后”以缓存SplitInputIndex ， SplitValue和Child2 。
因此，要么更改BranchNodeData类中字段的顺序，要么更改set; if ... overwrite; set; if ... overwrite; if ... else 。