.Net 4中这种巨大的性能差异背后的原因是什么？

我刚刚在RedBlack Tree上做了一些研究。 我知道.Net 4.0中的SortedSet类使用RedBlack树。 所以我使用Reflector取出了那部分并创建了一个RedBlackTree类。 现在我在这个RedBlackTree和SortedSet上运行一些perf测试，插入40000个顺序积分值（从0到39999开始），我惊讶地发现有很大的性能差异如下：

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

它背后的原因是什么？ 顺便说一句，我只在Release配置中运行测试，这里是一个小测试代码

  var stopWatch = new Stopwatch(); var rbT = new RedBlackTree(); 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(); stopWatch = new Stopwatch(); stopWatch.Start(); for (int i = 0; i < 40000; i++) { ss.Add(i); } stopWatch.Stop(); Console.WriteLine(stopWatch.Elapsed); 

编辑

我想为RBTree分享我提取的代码，以便您也可以运行诊断程序

 public class Node { public Node(){} public Node(T value) { Item = value; } public Node(T value, bool isRed) { Item = value; IsRed = isRed; } public T Item; public Node Left; public Node Right; public Node Parent; public bool IsRed; } public class RedBlackTree { public RedBlackTree(){} public Node root; int count, version; Comparer comparer = Comparer.Default; public void Add(T item) { if (this.root == null) { this.root = new Node(item, false); this.count = 1; this.version++; return; } Node root = this.root; Node node = null; Node grandParent = null; Node 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 current = new Node(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 node) { return ((node != null) && node.IsRed); } private static bool Is4Node(Node node) { return (IsRed(node.Left) && IsRed(node.Right)); } private static void Split4Node(Node node) { node.IsRed = true; node.Left.IsRed = false; node.Right.IsRed = false; } private void InsertionBalance(Node current, ref Node parent, Node grandParent, Node greatGrandParent) { Node 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 RotateLeft(Node node) { Node right = node.Right; node.Right = right.Left; right.Left = node; return right; } private static Node RotateRight(Node node) { Node left = node.Left; node.Left = left.Right; left.Right = node; return left; } private static Node RotateLeftRight(Node node) { Node left = node.Left; Node right = left.Right; node.Left = right.Right; right.Right = node; left.Right = right.Left; right.Left = left; return right; } private static Node RotateRightLeft(Node node) { Node right = node.Right; Node left = right.Left; node.Right = left.Left; left.Left = node; right.Left = left.Right; left.Right = right; return left; } private void ReplaceChildOfNodeOrRoot(Node parent, Node child, Node newChild) { if (parent != null) { if (parent.Left == child) { parent.Left = newChild; } else { parent.Right = newChild; } } else { this.root = newChild; } } } 

---

编辑

---

我对其他一些数据结构运行了相同的诊断（一些由我创建*，一些来自.net framework **），这里是有趣的结果

 *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与上面相同（从SortedSet类中删除）。 我也尝试了40万个值，但RBTree似乎没有了，我真的不知道为什么。

Answer 1

您的Node类中有一个错误。 当您调用仅接受单个值参数的构造函数时，您应该将IsRed设置为true 。

我想固定的Node类看起来像这样：

 public sealed class Node { public T Item { get; private set; } public bool IsRed { get; set; } public Node Left { get; set; } public Node Right { get; set; } public Node(T value) { Item = value; IsRed = true; } public Node(T value, bool isRed) { Item = value; IsRed = isRed; } } 

另一个选项 – 我的偏好 – 将完全省略该构造函数，并且在实例化新节点时始终要求显式设置IsRed ：

 public sealed class Node { public T Item { get; private set; } public bool IsRed { get; set; } public Node Left { get; set; } public Node Right { get; set; } public Node(T value, bool isRed) { Item = value; IsRed = isRed; } } 

然后在Add方法中替换此行…

 Node current = new Node(item); 

…有了这个…

 Node current = new Node(item, true); 

Answer 2

1. 颠倒测试的顺序并重复测量。
2. 随机化您的数据。 插入预排序数据时，排序集的行为很奇怪。

Answer 3

SortedSet包含TargetedPatchingOptOut属性，您的复制版本是否包含该属性？

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

Answer 4

如果差异不是那么大，我会建议原因是.NET程序集是NGen-ed，因此它们已经被翻译成本机代码。 对于您的类，将IL代码编译为本机代码的时间将在您的测试时间内分摊。 如何增加循环迭代次数会影响时间？