我有一个性能关键二元决策的树，我想集中这个问题上的一行代码。 对于二叉树迭代器的代码如下与反对它的运行性能分析的结果。
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;
}
正如你所看到的，而循环/ 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的第二比较执行第一比较。 所以看起来它确实是一个分支预测的问题 - 我猜有什么我可以做些什么？
另一个编辑
如果node.BranchData不得不从RAM的同时，检查装载也会出现上述结果 - 那么这将被缓存的if语句。
这是我在一个类似的话题第三个问题。 这一次，我专注于一个单一的代码行。 我对这个问题的其他问题有：
- 我可以用更快的数据结构比这树？
- 微的优化，通过C＃中的树遍历
