Qual è la ragione di questa enorme differenza di prestazioni in .Net 4

Question

Stavo solo facendo delle ricerche su RedBlack Tree. Sapevo che la classe SortedSet in .Net 4.0 utilizza l'albero RedBlack. Quindi ho preso questa parte come se stessimo usando Reflector e creato una classe RedBlackTree. Ora sto facendo funzionare alcune prove perf su questo RedBlackTree e SortedSet inserimento di 40000 valori interi sequenziali (a partire 0-39.999), io sono stupito di vedere che c'è grande differenza perf come segue:

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

Qual è la ragione Dietro? BTW Ho eseguito il test in unica configurazione di uscita ed ecco il piccolo codice di prova

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

Modifica

Vorrei condividere il codice anche per RBTree quello che ho estratto in modo che sia anche possibile eseguire il diagnostica

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

---

Modifica

---

mi corse lo stesso diagnostica su qualche altra struttura dati (alcuni creati da me *, alcuni da NET Framework **) e qui è i risultati interessanti

*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 è la stessa di cui sopra (spogliato fuori dalla classe SortedSet). Ho provato anche con 400000 valori, ma sembra che RBTree stia prendendo FOREVER, davvero non so perché.

Answer 1

Si è verificato un errore nella classe Node<T>. Quando chiami il costruttore che accetta solo un argomento a valore singolo, devi impostare IsRed su true.

Suppongo che il Node<T> classe fisso dovrebbe essere simile a questo:

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

Un'altra opzione - la mia preferenza - potrebbe essere quella di omettere quel costruttore del tutto e sempre richiedere IsRed essere impostato in modo esplicito quando si crea un'istanza un nuovo 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; 
    } 
} 

e quindi sostituire questa linea nel metodo Add ...

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

... con questo ...

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

Answer 2

Se la differenza non era così grande, suggerirei che la causa è che gli assembly .NET sono NGen-ed e quindi sono già tradotti in codice nativo. Nel caso della tua classe il tempo di compilare il codice IL in codice nativo viene ammortizzato nel tempo del tuo test. In che modo l'aumento del numero di iterazioni del ciclo influisce sui tempi?

Answer 3

SortedSet include un attributo TargetedPatchingOptOut, inclusa la versione copiata?

[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. invertire l'ordine delle prove e ripetere la misurazione.
2. randomize your data. Gli insiemi ordinati si comportano in modo strano quando si inseriscono dati pre-ordinati.