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

Question

Estaba haciendo una investigación sobre RedBlack Tree. Sabía que la clase SortedSet en .Net 4.0 usa el árbol RedBlack. Así que saqué esa parte como está usando 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 eso? Por cierto, me encontré en la prueba de lanzamiento de configuración única 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

---

que corrieron el mismo diagnóstico en alguna otra estructura de datos (algunos creados por mí *, algunos de .NET Framework **) y aquí es los resultados interesantes

*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 (despojado de la clase SortedSet). Intenté con 400000 valores también, pero RBTree parece tomar FOREVER, realmente no sé por qué.

Answer 1

Tiene un error en su clase Node<T>. Cuando llame al constructor que solo toma un argumento de valor único, debe establecer IsRed en true.

supongo que la clase fija Node<T> debería 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 ejemplariza 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

Si la diferencia no fuera tan grande, sugeriría que la causa es que los ensamblados .NET son NGen-ed y por lo tanto ya están traducidos al código nativo. En el caso de su clase, el tiempo para compilar el código IL en el código nativo se amortiza durante el tiempo de su prueba. ¿Cómo afecta el aumento del número de iteraciones de bucle a los tiempos?

Answer 3

SortedSet incluye un atributo TargetedPatchingOptOut, ¿su versión copiada incluye eso?

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

Answer 4

1. invertir el orden de las pruebas y repetir la medición.
2. aleatorice sus datos. Los conjuntos ordenados se comportan de forma extraña cuando inserta datos preordenados.