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



performance inheritance (2)

Я пишу различные реализации неизменяемых бинарных деревьев в C #, и я хотел, чтобы мои деревья наследовали некоторые распространенные методы из базового класса.

К сожалению, классы, которые происходят из базового класса, ужасно медленны. Непроизводные классы работают адекватно. Вот две почти идентичные реализации дерева AVL для демонстрации:

Два дерева имеют одинаковый код , но я переместил метод DerivedAvlTree.Insert в базовый класс. Вот тестовое приложение:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using Juliet.Collections.Immutable;

namespace ConsoleApplication1
{
    class Program
    {
        const int VALUE_COUNT = 5000;

        static void Main(string[] args)
        {
            var avlTreeTimes = TimeIt(TestAvlTree);
            var derivedAvlTreeTimes = TimeIt(TestDerivedAvlTree);

            Console.WriteLine("avlTreeTimes: {0}, derivedAvlTreeTimes: {1}", avlTreeTimes, derivedAvlTreeTimes);
        }

        static double TimeIt(Func<int, int> f)
        {
            var seeds = new int[] { 314159265, 271828183, 231406926, 141421356, 161803399, 266514414, 15485867, 122949829, 198491329, 42 };

            var times = new List<double>();

            foreach (int seed in seeds)
            {
                var sw = Stopwatch.StartNew();
                f(seed);
                sw.Stop();
                times.Add(sw.Elapsed.TotalMilliseconds);
            }

            // throwing away top and bottom results
            times.Sort();
            times.RemoveAt(0);
            times.RemoveAt(times.Count - 1);
            return times.Average();
        }

        static int TestAvlTree(int seed)
        {
            var rnd = new System.Random(seed);

            var avlTree = AvlTree<double>.Create((x, y) => x.CompareTo(y));
            for (int i = 0; i < VALUE_COUNT; i++)
            {
                avlTree = avlTree.Insert(rnd.NextDouble());
            }

            return avlTree.Count;
        }

        static int TestDerivedAvlTree(int seed)
        {
            var rnd = new System.Random(seed);

            var avlTree2 = DerivedAvlTree<double>.Create((x, y) => x.CompareTo(y));
            for (int i = 0; i < VALUE_COUNT; i++)
            {
                avlTree2 = avlTree2.Insert(rnd.NextDouble());
            }

            return avlTree2.Count;
        }
    }
}
  • AvlTree: вставляет 5000 элементов в 121 мс
  • DerivedAvlTree: вставляет 5000 элементов в 2182 мс

Мой профилировщик указывает, что программа тратит чрезмерное количество времени в BaseBinaryTree.Insert . Любой, кто заинтересован, может видеть файл журнала EQATEC, который я создал с помощью кода выше (вам понадобится профилировщик EQATEC, чтобы понять смысл файла).

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

Что заставляет мой DerivedAvlTree работать так плохо, и что я могу сделать, чтобы исправить это?

https://ffff65535.com


Это не связано с производным классом, вызывающим первоначальную реализацию, а затем также вызывающим Баланс, не так ли?

Я думаю, вам, вероятно, придется посмотреть на сгенерированный машинный код, чтобы узнать, что другое. Все, что я вижу из исходного кода, это то, что вы изменили множество статических методов на виртуальные методы, называемые полиморфно ... в первом случае JIT точно знает, какой метод будет вызываться, и может выполнять инструкцию прямого вызова, возможно даже в очереди. Но с полиморфным вызовом у него нет выбора, кроме как выполнить поиск по v-таблице и косвенный вызов. Этот поиск представляет значительную часть выполняемой работы.

Жизнь может стать немного лучше, если вы вызовете ((TreeType)) .Method () вместо this.Method (), но, вероятно, вы не сможете удалить полиморфный вызов, если вы также не объявите переопределяющие методы как запечатанные. И даже тогда вы можете заплатить штраф за проверку времени выполнения этого экземпляра.

Включение вашего многоразового кода в общие статические методы в базовом классе может также помочь, но я думаю, вы все еще будете платить за полиморфные звонки. C # generics просто не оптимизируют, а также шаблоны C ++.


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

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

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 , как правило, на несколько миллисекунд меньше в сборке релизов.

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





inheritance