У меня есть бинарное дерево решений, критичное к производительности, и я хотел бы сосредоточить этот вопрос на одной строке кода. Ниже приведен код для итератора двоичного дерева с результатами анализа производительности.

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

Как видите, проверка цикла loop / null является огромным ударом по производительности. Дерево массивное, поэтому я ожидал бы, что поиск листа займет некоторое время, но я хотел бы понять непропорциональное количество времени, проведенного на этой одной линии.

Я пробовал:

Отделение проверки Null от времени - это проверка 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 из оперативной памяти - затем он будет кэширован для оператора if.

Это мой третий вопрос на аналогичную тему. На этот раз я сосредоточен на одной строке кода. Мои другие вопросы на эту тему:

Могу ли я использовать для этого более быструю структуру данных, чем дерево?Микрооптимизации, проходящие по дереву в C #