Ответ 1
Примечание - здесь есть "чистое" решение, поэтому пропустите окончательное редактирование, если вам нужна только версия, которая работает быстро и не заботится обо всех детективных работах.
Кажется, это не разница между прямыми и виртуальными вызовами, которые вызывают замедление. Это как-то связано с этими делегатами; Я не могу полностью объяснить, что это такое, но посмотрите на сгенерированный IL, показывающий много кэшированных делегатов, которые, я думаю, не могут использоваться в версии базового класса. Но сам ИЛ не кажется существенно отличающимся между двумя версиями, что заставляет меня думать, что сам джиттер частично отвечает.
Взгляните на этот рефакторинг, который сокращает время работы примерно на 60%:
public virtual TreeType Insert(T value)
{
Func<TreeType, T, TreeType, TreeType> nodeFunc = (l, x, r) =>
{
int compare = this.Comparer(value, x);
if (compare < 0) { return CreateNode(l.Insert(value), x, r); }
else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); }
return Self();
};
return Insert<TreeType>(value, nodeFunc);
}
private TreeType Insert<U>(T value,
Func<TreeType, T, TreeType, TreeType> nodeFunc)
{
return this.Match<TreeType>(
() => CreateNode(Self(), value, Self()),
nodeFunc);
}
Это должно (и, по-видимому,) гарантировать, что делегат вставки создается только один раз для каждой вставки - он не создается на каждой рекурсии. На моей машине он сокращает время работы от 350 мс до 120 мс (в отличие от него однопроцессорная версия работает примерно через 30 мс, так что это все еще не так близко, где это должно быть).
Но здесь, где он становится еще более странным - попробовав вышеуказанный рефакторинг, я подумал, хм, может быть, он все еще медленный, потому что я сделал половину работы. Поэтому я попробовал материализовать и первого делегата:
public virtual TreeType Insert(T value)
{
Func<TreeType> nilFunc = () => CreateNode(Self(), value, Self());
Func<TreeType, T, TreeType, TreeType> nodeFunc = (l, x, r) =>
{
int compare = this.Comparer(value, x);
if (compare < 0) { return CreateNode(l.Insert(value), x, r); }
else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); }
return Self();
};
return Insert<TreeType>(value, nilFunc, nodeFunc);
}
private TreeType Insert<U>(T value, Func<TreeType> nilFunc,
Func<TreeType, T, TreeType, TreeType> nodeFunc)
{
return this.Match<TreeType>(nilFunc, nodeFunc);
}
И угадайте, что... это снова сделало его медленнее! С этой версией на моей машине в этом прогоне потребовалось чуть больше 250 мс.
Это игнорирует все логические объяснения, которые могут относить проблему к скомпилированному байт-коду, поэтому я подозреваю, что дрожание связано с этим заговором. Я думаю, что первая "оптимизация" выше может быть (ПРЕДУПРЕЖДЕНИЕ - спекуляция впереди), позволяющая вставить делегат вставки - это известный факт, что дрожание не может встроить виртуальные вызовы, - но есть еще что-то еще что не было встроено и что там, где я сейчас в тупике.
Следующим шагом было бы выборочно отключить встраивание определенных методов с помощью MethodImplAttribute и посмотреть, какое влияние оказывает на время выполнения, что поможет доказать или опровергнуть эту теорию.
Я знаю, что это не полный ответ, но, надеюсь, он, по крайней мере, дает вам что-то, с чем можно работать, и, возможно, некоторые дальнейшие эксперименты с этим декомпозицией могут привести к близким результатам к исходной версии.
Править: Ха, сразу после того, как я представил это, я наткнулся на другую оптимизацию. Если вы добавите этот метод в базовый класс:
private TreeType CreateNilNode(T value)
{
return CreateNode(Self(), value, Self());
}
Теперь время работы сокращается до 38 мс, чуть выше исходной версии. Это ударит мой разум, потому что ничего не ссылается на этот метод! Частный метод Insert<U> по-прежнему идентичен самому первому блоку кода в моем ответе. Я собирался изменить первый аргумент, чтобы ссылаться на метод CreateNilNode, но мне не пришлось. Либо джиттер видит, что анонимный делегат совпадает с методом CreateNilNode, и разделяет тело (возможно, снова встраивается), либо... или, я не знаю. Это первый экземпляр, который я когда-либо видел, когда добавление частного метода и никогда его не вызывает, может ускорить программу в 4 раза.
Вам нужно будет проверить это, чтобы убедиться, что я случайно не представил никаких логических ошибок - я уверен, что нет, код почти такой же, но если все будет проверено, то вот вы, этот работает почти так же быстро, как и не производный AvlTree.
ДОПОЛНИТЕЛЬНОЕ ОБНОВЛЕНИЕ
Мне удалось придумать версию базовой/производной комбинации, которая на самом деле работает немного быстрее, чем версия одного класса. Принял немного уговоров, но он работает!
Что нам нужно сделать, так это создать специальный вставщик, который может создавать все делегаты только один раз, не требуя каких-либо захватов переменных. Вместо этого все состояние сохраняется в полях-членах. Поместите это внутри класса BaseBinaryTree:
protected class Inserter
{
private TreeType tree;
private Func<TreeType> nilFunc;
private Func<TreeType, T, TreeType, TreeType> nodeFunc;
private T value;
public Inserter(T value)
{
this.nilFunc = () => CreateNode();
this.nodeFunc = (l, x, r) => PerformMatch(l, x, r);
this.value = value;
}
public TreeType Insert(TreeType parent)
{
this.tree = parent;
return tree.Match<TreeType>(nilFunc, nodeFunc);
}
private TreeType CreateNode()
{
return tree.CreateNode(tree, value, tree);
}
private TreeType PerformMatch(TreeType l, T x, TreeType r)
{
int compare = tree.Comparer(value, x);
if (compare < 0) { return tree.CreateNode(l.Insert(value, this), x, r); }
else if (compare > 0) { return tree.CreateNode(l, x, r.Insert(value, this)); }
return tree;
}
}
Да, да, я знаю, он очень неэффективен, используя это изменяемое внутреннее состояние tree, но помните, что это не само дерево, а просто случайный "runnable" экземпляр. Никто никогда не говорил, что perf-opt был хорош! Это единственный способ избежать создания нового Inserter для каждого рекурсивного вызова, что в противном случае замедляло бы это из-за всех новых распределений Inserter и его внутренних делегатов.
Теперь замените методы вставки базового класса на это:
public TreeType Insert(T value)
{
return Insert(value, null);
}
protected virtual TreeType Insert(T value, Inserter inserter)
{
if (inserter == null)
{
inserter = new Inserter(value);
}
return inserter.Insert(Self());
}
Я сделал общедоступный метод Insert не виртуальным; вся настоящая работа делегируется защищенному методу, который принимает (или создает свой собственный) экземпляр Inserter. Изменение производного класса достаточно просто, просто замените переопределенный метод Insert следующим образом:
protected override DerivedAvlTree<T> Insert(T value, Inserter inserter)
{
return base.Insert(value, inserter).Balance();
}
Что это. Теперь запустите это. Это займет почти то же самое время, что и AvlTree, как правило, на несколько миллисекунд меньше в сборке релизов.
Замедление, очевидно, связано с определенной комбинацией виртуальных методов, анонимных методов и захвата переменных, которые каким-то образом препятствуют тому, чтобы дрожание делало важную оптимизацию. Я не настолько уверен, что он вникнет больше, это может быть просто кеширование делегатов, но я думаю, что единственные люди, которые могли бы реально разработать, сами являются джиттер-людьми.