Почему моя производительность замедляется к проверке, я перемещаю методы в базовый класс?

Примечание - теперь здесь есть «чистое» решение, так что переходите к окончательному редактированию, если вам нужна только версия, которая работает быстро и не заботится обо всей детективной работе.

Кажется, нет разницы между прямыми и виртуальными вызовами, которые вызывают замедление. Это как-то связано с этими делегатами; Я не могу подробно объяснить, что это такое, но взгляд на сгенерированный 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 и посмотреть, как это повлияет на время выполнения - это поможет доказать или опровергнуть эту теорию.

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

Edit: Ха, сразу после того, как я отправил это, я наткнулся на другую оптимизацию. Если вы добавите этот метод к базовому классу:

private TreeType CreateNilNode(T value)
{
    return CreateNode(Self(), value, Self());
}

Теперь время работы упадет до 38 мс здесь, что чуть выше исходной версии. Это шокирует меня, потому что на самом деле ничего не ссылается на этот метод! Частный метод Insert по-прежнему идентичен самому первому блоку кода в моем ответе. Я собирался изменить первый аргумент для ссылки на метод CreateNilNode , но мне не пришлось этого делать. Либо дрожание заключается в том, что анонимный делегат совпадает с методом CreateNilNode и разделяет тело (вероятно, снова встраивается), либо ... либо, я не знаю.Это первый случай, который я когда-либо видел, когда добавление частного метода и , никогда не вызывающее его , может ускорить программу в 4 раза.

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

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

protected override DerivedAvlTree<T> Insert(T value, Inserter inserter)
{
    return base.Insert(value, inserter).Balance();
}