Примечание - теперь есть «чистое» решение, поэтому перейдите к окончательному редактированию, если вам нужна только версия, которая работает быстро и не заботится обо всей детективной работе.
Кажется, что нет разницы между прямыми и виртуальными вызовами, которые вызывают замедление. Это как-то связано с этими делегатами; Я не могу точно объяснить, что это такое, но взгляд на сгенерированный IL показывает множество кэшированных делегатов, которые, я думаю, могут не использоваться в версии базового класса. Но сам 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, но помните, что это не само дерево, это просто одноразовый «работающий» экземпляр. Никто никогда не говорил, что перфект был хорош! Это единственный способ избежать создания нового 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, обычно на несколько миллисекунд меньше в сборке релиза.
Замедление очевидно из-за некоторой специфической комбинации виртуальных методов, анонимных методов и захвата переменных, которые каким-то образом мешают джиттеру провести важную оптимизацию. Я не настолько уверен, что он больше встроен, возможно, он просто кеширует делегатов, но я думаю, что единственные люди, которые действительно могли бы это уточнить, - это сами джиттеры.