¿Cuál es la razón detrás de esta gran diferencia de rendimiento en .Net 4

Question

Yo sólo estaba haciendo una investigación sobre RedBlack árbol. Yo sabía que la clase SortedSet en .Net 4.0 utiliza RedBlack árbol. Así que tomé esa parte que está utilizando reflector y creé una clase RedBlackTree. Ahora estoy corriendo alguna prueba de Potencia en este RedBlackTree y SortedSet inserción de 40000 valores enteros secuenciales (comenzando por 0 hasta 39999), me sorprende ver que hay una enorme diferencia Potencia de la siguiente manera:

 RBTree    took 9.27208   sec to insert 40000 values 
 SortedSet took 0.0253097 sec to insert 40000 values

¿Cuál es la razón detrás de esto? Por cierto, me encontré en la prueba única configuración de lanzamiento y aquí está el pequeño código de prueba

            var stopWatch = new Stopwatch();
            var rbT = new RedBlackTree<int>();      
        stopWatch = new Stopwatch();
        stopWatch.Start();
        for (int i = 0; i < 40000; i++) {
            rbT.Add(i);
        }
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed);

        var ss = new SortedSet<int>();
        stopWatch = new Stopwatch();
        stopWatch.Start();
        for (int i = 0; i < 40000; i++) {
            ss.Add(i);
        }
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed);

Editar

Me gustaría compartir el código también para RBTree lo he extraído de manera que también se puede ejecutar el diagnóstico

public class Node<T>
    {
        public Node(){}

        public Node(T value)
        {
            Item = value;
        }       

        public Node(T value, bool isRed)
        {
            Item = value;
            IsRed = isRed;
        }

        public T Item;
        public Node<T> Left;
        public Node<T> Right;
        public Node<T> Parent;
        public bool IsRed;
    }

    public class RedBlackTree<T>
    {
        public RedBlackTree(){} 

        public Node<T> root;
        int count, version; 
        Comparer<T> comparer = Comparer<T>.Default;     

        public void Add(T item)
        {
            if (this.root == null)
            {
                this.root = new Node<T>(item, false);
                this.count = 1;
                this.version++;
                return;
            }

            Node<T> root = this.root;
            Node<T> node = null;
            Node<T> grandParent = null;
            Node<T> greatGrandParent = null;
            this.version++;

            int num = 0;
            while (root != null)
            {
                num = this.comparer.Compare(item, root.Item);
                if (num == 0)
                {
                    this.root.IsRed = false;
                    return;
                }
                if (Is4Node(root))
                {
                    Split4Node(root);
                    if (IsRed(node))
                    {
                        this.InsertionBalance(root, ref node, grandParent, greatGrandParent);
                    }
                }
                greatGrandParent = grandParent;
                grandParent = node;
                node = root;
                root = (num < 0) ? root.Left : root.Right;
            }
            Node<T> current = new Node<T>(item);
            if (num > 0)
            {
                node.Right = current;
            }
            else
            {
                node.Left = current;
            }
            if (node.IsRed)
            {
                this.InsertionBalance(current, ref node, grandParent, greatGrandParent);
            }
            this.root.IsRed = false;
            this.count++;
        }


        private static bool IsRed(Node<T> node)
        {
            return ((node != null) && node.IsRed);
        }

        private static bool Is4Node(Node<T> node)
        {
            return (IsRed(node.Left) && IsRed(node.Right));
        }

        private static void Split4Node(Node<T> node)
        {
            node.IsRed = true;
            node.Left.IsRed = false;
            node.Right.IsRed = false;
        }

        private void InsertionBalance(Node<T> current, ref Node<T> parent, Node<T> grandParent, Node<T> greatGrandParent)
        {
            Node<T> node;
            bool flag = grandParent.Right == parent;
            bool flag2 = parent.Right == current;
            if (flag == flag2)
            {
                node = flag2 ? RotateLeft(grandParent) : RotateRight(grandParent);
            }
            else
            {
                node = flag2 ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent);
                parent = greatGrandParent;
            }
            grandParent.IsRed = true;
            node.IsRed = false;
            ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, node);
        }

        private static Node<T> RotateLeft(Node<T> node)
        {
            Node<T> right = node.Right;
            node.Right = right.Left;
            right.Left = node;
            return right;
        }

        private static Node<T> RotateRight(Node<T> node)
        {
            Node<T> left = node.Left;
            node.Left = left.Right;
            left.Right = node;
            return left;
        }

        private static Node<T> RotateLeftRight(Node<T> node)
        {
            Node<T> left = node.Left;
            Node<T> right = left.Right;
            node.Left = right.Right;
            right.Right = node;
            left.Right = right.Left;
            right.Left = left;
            return right;
        }

        private static Node<T> RotateRightLeft(Node<T> node)
        {
            Node<T> right = node.Right;
            Node<T> left = right.Left;
            node.Right = left.Left;
            left.Left = node;
            right.Left = left.Right;
            left.Right = right;
            return left;
        }

        private void ReplaceChildOfNodeOrRoot(Node<T> parent, Node<T> child, Node<T> newChild)
        {
            if (parent != null)
            {
                if (parent.Left == child)
                {
                    parent.Left = newChild;
                }
                else
                {
                    parent.Right = newChild;
                }
            }
            else
            {
                this.root = newChild;
            }
        }
    }

---

Editar

---

Me corrió el mismo diagnóstico en alguna otra estructura de datos (algunos creados por mí *, algunos de .NET Framework **) y aquí es el resultado de interés

*AATree                 00:00:00.0309294
*AVLTree                00:00:00.0129743
**SortedDictionary      00:00:00.0313571
*RBTree                 00:00:09.2414156
**SortedSet             00:00:00.0241973

RBTree es el mismo que el anterior (quitó de la clase SortedSet). He intentado con 400000 valores también, pero parece RBTree teniendo SIEMPRE , realmente no sé qué.

Answer 1

tiene un error en su clase Node<T>. Cuando se llama al constructor que sólo toma un solo argumento de valor que debe estar fijándose IsRed a true.

supongo que la clase Node<T> fijo debe ser algo como esto:

public sealed class Node<T>
{
    public T Item { get; private set; }
    public bool IsRed { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }

    public Node(T value)
    {
        Item = value;
        IsRed = true;
    }

    public Node(T value, bool isRed)
    {
        Item = value;
        IsRed = isRed;
    }
}

Otra opción - mi preferencia - sería omitir ese constructor por completo y siempre requieren IsRed que se establezca explícitamente cuando se instancia un nuevo nodo:

public sealed class Node<T>
{
    public T Item { get; private set; }
    public bool IsRed { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }

    public Node(T value, bool isRed)
    {
        Item = value;
        IsRed = isRed;
    }
}

Y luego vuelva a colocar esta línea en su método Add ...

Node<T> current = new Node<T>(item);

... con esto ...

Node<T> current = new Node<T>(item, true);

Answer 2

1. invertir el orden de las pruebas y repetir la medición.
2. aleatorizar los datos. conjuntos ordenados comportan de manera extraña cuando se insertan datos preclasificados.

Answer 3

SortedSet incluye un href="http://msdn.microsoft.com/en-us/library/system.runtime.targetedpatchingoptoutattribute.aspx" rel="nofollow noreferrer"> TargetedPatchingOptOut atributo

[TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
public bool Add(T item)
{
    return this.AddIfNotPresent(item);
}

Answer 4

Si la diferencia no era tan grande que yo sugeriría que la causa es que los ensamblados .NET son NGen de opinión y por lo que ya se traducen a código nativo. En el caso de la clase el tiempo para compilar el código IL en código nativo se amortiza en el momento de la prueba. ¿Cómo aumentar el número de iteraciones del bucle afecta los tiempos?