c# - ¿Por qué mi rendimiento se ralentiza? ¿Moví los métodos a una clase base?

performance inheritance

Question

Estoy escribiendo diferentes implementaciones de árboles binarios inmutables en C #, y quería que mis árboles heredasen algunos métodos comunes de una clase base.

Desafortunadamente, las clases que derivan de la clase base son abismalmente lentas. Las clases no derivadas funcionan adecuadamente. Aquí hay dos implementaciones casi idénticas de un árbol AVL para demostrar:

• AvlTree: http://pastebin.com/V4WWUAyT
• DerivedAvlTree: http://pastebin.com/PussQDmN

Los dos árboles tienen exactamente el mismo código , pero he movido el método DerivedAvlTree.Insert en la clase base. Aquí hay una aplicación de prueba:

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: inserta 5000 elementos en 121 ms
• DerivedAvlTree: inserta 5000 elementos en 2182 ms

Mi generador de perfiles indica que el programa pasa una cantidad de tiempo BaseBinaryTree.Insert en BaseBinaryTree.Insert . Cualquier persona que esté interesada puede ver el archivo de registro EQATEC que he creado con el código anterior (necesitará el perfil EQATEC para dar sentido al archivo).

Realmente quiero usar una clase base común para todos mis árboles binarios, pero no puedo hacer eso si el rendimiento se resiente.

¿Qué causa que mi DerivedAvlTree funcione tan mal y qué puedo hacer para solucionarlo?

Answer 1

No tiene nada que ver con la clase derivada que llama a la implementación original y luego también llama a Balance, ¿o sí?

Creo que probablemente deba mirar el código máquina generado para ver qué es diferente. Todo lo que puedo ver en el código fuente es que ha cambiado muchos métodos estáticos en métodos virtuales llamados polimórficamente ... en el primer caso el JIT sabe exactamente qué método se llamará y puede hacer una instrucción de llamada directa, posiblemente incluso en línea. Pero con una llamada polimórfica no tiene más remedio que hacer una búsqueda en la tabla v y una llamada indirecta. Esa búsqueda representa una fracción significativa del trabajo que se realiza.

La vida puede mejorar un poco si llama a ((TreeType) this) .Method () en lugar de this.Method (), pero es probable que no pueda eliminar la llamada polimórfica a menos que también declare que los métodos de anulación están sellados. Y aun así, puede pagar la penalidad de un control de tiempo de ejecución en esta instancia.

Poner tu código reutilizable en métodos genéricos estáticos en la clase base también podría ser útil, pero creo que seguirás pagando llamadas polimórficas. Los genéricos C # simplemente no optimizan tan bien como las plantillas C ++.

Answer 2

Nota : ahora hay una solución "limpia" aquí, así que salte a la edición final si solo quiere una versión que se ejecute rápido y no le importe todo el trabajo de detective.

No parece ser la diferencia entre las llamadas directas y virtuales lo que está causando la desaceleración. Tiene algo que ver con esos delegados; No puedo explicar exactamente qué es, pero un vistazo a la IL generada muestra una gran cantidad de delegados almacenados en caché que creo que podrían no estar siendo utilizados en la versión de la clase base. Pero la IL en sí misma no parece ser significativamente diferente entre las dos versiones, lo que me lleva a creer que el jitter en sí mismo es en parte responsable.

Eche un vistazo a esta refactorización, que reduce el tiempo de ejecución en aproximadamente un 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);
}

Esto debería (y aparentemente lo hace) garantizar que el delegado de inserción solo se crea una vez por inserción; no se crea en cada recursión. En mi máquina, corta el tiempo de ejecución de 350 ms a 120 ms (por el contrario, la versión de clase única se ejecuta en aproximadamente 30 ms, por lo que todavía no está cerca de donde debería estar).

Pero aquí es donde se vuelve aún más extraño: después de probar la refactorización anterior, pensé, hmm, tal vez todavía es lento porque solo hice la mitad del trabajo. Así que intenté materializar al primer delegado también:

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

Y adivina qué ... ¡esto hizo que fuera más lento otra vez! Con esta versión, en mi máquina, tomó algo más de 250 ms en esta ejecución.

Esto desafía todas las explicaciones lógicas que puedan relacionar el problema con el bytecode compilado, y es por eso que sospecho que el jitter está en esta conspiración. Creo que la primera "optimización" de arriba podría ser ( AVISO - especulación por delante ) permitiendo que el delegado de inserción esté incluido - es un hecho conocido que el jitter no puede alinear llamadas virtuales - pero todavía hay algo más que no está en línea y ahí es donde Actualmente estoy perplejo.

Mi próximo paso sería inhabilitar selectivamente la creación de líneas en ciertos métodos a través del MethodImplAttribute y ver qué efecto tiene en el tiempo de ejecución, lo que ayudaría a probar o refutar esta teoría.

Sé que esta no es una respuesta completa, pero afortunadamente al menos te da algo con lo que trabajar, y tal vez un poco más de experimentación con esta descomposición pueda producir resultados que estén cerca del rendimiento de la versión original.

Editar: Hah, justo después de enviar esto tropecé con otra optimización. Si agrega este método a la clase base:

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

Ahora el tiempo de ejecución se reduce a 38 ms aquí, apenas por encima de la versión original. Esto me sorprende, ¡porque en realidad nada hace referencia a este método! El método privado Insert<U> sigue siendo idéntico al primer bloque de código en mi respuesta. Iba a cambiar el primer argumento para hacer referencia al método CreateNilNode , pero no era necesario. O el jitter es ver que el delegado anónimo es el mismo que el método CreateNilNode y compartir el cuerpo (probablemente entrando de nuevo en línea), o ... o, no sé. Esta es la primera instancia que he visto en la que agregar un método privado y no llamarlo nunca puede acelerar un programa por un factor de 4.

Tendrás que verificar esto para asegurarte de que no haya introducido accidentalmente ningún error de lógica, estoy seguro de que no, el código es casi el mismo, pero si todo sale bien, entonces aquí estás, esto funciona casi como rápido como el AvlTree no derivado.

ACTUALIZACIÓN ADICIONAL

Pude encontrar una versión de la combinación base / derivada que realmente funciona un poco más rápido que la versión de una sola clase. Tomó algo de persuasión, ¡pero funciona!

Lo que tenemos que hacer es crear un insertador dedicado que pueda crear todos los delegados solo una vez, sin necesidad de realizar ninguna captura de variables. En cambio, todo el estado se almacena en los campos de miembros. Pon esto dentro de la clase 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;
    }
}

Sí, sí, lo sé, es muy poco funcional usar ese estado de tree interno mutable, pero recuerda que este no es el árbol en sí, es solo una instancia desechable "ejecutable". ¡Nadie dijo que perf-opt era bonita! Esta es la única forma de evitar la creación de un nuevo Inserter para cada llamada recursiva, que de lo contrario ralentizaría esto a causa de todas las nuevas asignaciones del Inserter y sus delegados internos.

Ahora reemplace los métodos de inserción de la clase base por esto:

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

He hecho que el método de Insert pública no sea virtual ; todo el trabajo real se delega en un método protegido que toma (o crea el suyo) instancia de Inserter . Alterar la clase derivada es bastante simple, simplemente reemplace el método de Insert anulado con esto:

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

Eso es. Ahora ejecuta esto. Tardará casi la misma cantidad de tiempo que el AvlTree , generalmente algunos milisegundos menos en una compilación de lanzamiento.

La desaceleración se debe claramente a una combinación específica de métodos virtuales, métodos anónimos y captura de variables que de alguna manera evita que la inestabilidad genere una optimización importante. No estoy tan seguro de que esté entrando más, podría estar guardando en el caché a los delegados, pero creo que las únicas personas que podrían elaborar realmente son los mismos.

Answer 3

Estás corriendo bajo VS IDE, ¿verdad? Se tarda unas 20 veces más, ¿verdad?

Envuelva un bucle alrededor para iterarlo 10 veces, por lo que la versión larga tarda 20 segundos. Luego, mientras se está ejecutando, presiona el botón "pausa" y mira la pila de llamadas. Verás exactamente cuál es el problema con un 95% de certeza. Si no crees lo que ves, pruébalo un par de veces más. ¿Por qué funciona? Aquí está la explicación larga , y esta es la breve .