Как писать быстрый managed-код?

[george_u]

Пусть у нас есть некоторая функция, которая осуществляет рекурсивный обход некоторого довольно большого дерева.

private void VisitNode(ISnapShotNode node, IProgressIndicator indicator)
{
// doing something with node
// ...

foreach(ISnapShotNode child in node.Children)
VisitNode(child, indicator);
}

Мы увидели такое чудо в performance-critical коде, и нам это, естественно, захотелось соптимизировать. Первое, на что наткнулся взгляд - параметр indicator не меняется внутри рекурсивной функции (у него вызываются некоторые методы), поэтому его очевидно нужно вынести. Но это изменение нам кажется мелким, и мы решаем начать с более крупного изменения. Итак, во-первых, казалось бы, очевидное соображение - при рекурсивных вызовах в стеке помимо параметров сохраняется адрес возврата, а если рекурсию реализовать ручками, то на этом можно будет сэкономить. Как говорит наш опыт, в managed коде уменьшение параметров у глубокой рекурсивной функции всегда позволяет получить performance benefit, так что почему бы не попробовать сэкономить на адресе возврата?

Делаем контрольный замер производительности первого варианта функции (намеряли 17.4 секунд), и пишем второй вариант:

private void VisitNode(ISnapShotNode startNode, IProgressIndicator indicator)
{
ArrayList workNodes = new ArrayList(startNode.SubTreeSize);
workNodes.Add(startNode);

while(workNodes.Count > 0)
{
ISnapShotNode node = workNodes[workNodes.Count-1];
workNodes.RemoveAt(workNodes.Count-1);

// doing something with node
// ...

workNodes.AddRange(node.Children);
}
}

Прогоняем unit-тесты и готовимся замерить performance второго варианта. В предвкушении огромного benefit сжимается сердце. Проводим замер, и оказывается, что время второго варианта составляет... 27 секунд!

Чертыхаемся. Думаем. Профилируем. Осознаём, что дело должно быть в том, что нам для работы требуется большой непрерывный кусок памяти, на поиск которого могло и уйти драгоценное время. Смекаем, что раз коллекция node.Children в памяти уже есть, то можно в нашем случае создать сложную коллекцию, в которой хранить указатели на коллекции node.Children. При этом колоссально уменьшится размер требуемого непрерывного куска. Итак, пишем следующий класс

using System;
using System.Collections;

namespace JetBrains.dotTrace.Utils.DataStructures
{
///
/// ComplexEnumerable - array of pointers to enumerables; datastructure for fast
/// non-recursive tree walking.
///
public class ComplexEnumerable : IEnumerable
{
private readonly ArrayList mySubEnumerables = new ArrayList();

public void AddSubEnumerable(IEnumerable subEnumerable)
{
mySubEnumerables.Add(subEnumerable);
}

#region IEnumerable Members

class Enumerator : IEnumerator
{
private IEnumerator myCurrentItem;
private int myCurrentEnumerableNum;
private readonly ArrayList mySubEnumerables;

public Enumerator(ArrayList subEnumerables)
{
mySubEnumerables = subEnumerables;
Reset();
}

public bool MoveNext()
{
while(!myCurrentItem.MoveNext())
{
if(myCurrentEnumerableNum == mySubEnumerables.Count - 1)
return false;
else
{
myCurrentEnumerableNum ++;
myCurrentItem = ((IEnumerable) mySubEnumerables[myCurrentEnumerableNum]).GetEnumerator();
}
}

return true;
}

public void Reset()
{
if(mySubEnumerables.Count == 0)
throw new ArgumentOutOfRangeException("Underlying collection is empty");

myCurrentEnumerableNum = 0;

myCurrentItem = ((IEnumerable)mySubEnumerables[myCurrentEnumerableNum]).GetEnumerator();
}

public object Current
{
get { return myCurrentItem.Current; }
}
}

public IEnumerator GetEnumerator()
{
return new Enumerator(mySubEnumerables);
}

#endregion
}
}

И приводим функцию к следующему виду:

private void VisitNode(ISnapShotNode startNode, IProgressIndicator indicator)
{
ComplexEnumerable workStack = new ComplexEnumerable();
workStack.AddSubEnumerable(new ISnapShotNode[] { startNode } );

foreach (ISnapShotNode node in workStack)
{
//Doing something with node
//...

ISnapShotNode[] children = node.Children;
if(children.Length > 0)
workStack.AddSubEnumerable(children);
}
}

Замеряем быстродействие. Получаем 29 секунд...

Профиляция показывает, что время возрастает за счёт того, что возрастает количество вызываемых функций. Заставить в managed коде заинлайниться некоторые функции невозможно. А ведь на С++ при грамотной реализации, на указателях, картина была бы диаметрально противоположной - самым быстрым оказался бы последний вариант.

Выводы можно делать разные, но степень забавности ситуации потрясает.