В чем причина такой огромной разницы в производительности .Net 4? - PullRequest
Новая
       11

В чем причина такой огромной разницы в производительности .Net 4?

18 голосов
/ 15 сентября 2010

Я просто занимался исследованиями RedBlack Tree.Я знал, что класс SortedSet в .Net 4.0 использует дерево RedBlack.Поэтому я взял эту часть, как при использовании Reflector, и создал класс RedBlackTree.Сейчас я провожу некоторые тесты перфорации на этом RedBlackTree и SortedSet, вставляя 40000 последовательных интегральных значений (от 0 до 39999), я удивлен, увидев, что существует огромная разница перфорирования следующим образом:причина этого?Кстати, я выполнил тест только в конфигурации выпуска, и вот небольшой тестовый код 

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

Edit

Я хотел бы поделиться кодом также для RBTree, что я извлек, чтобы вытакже может запускать диагностику 

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

Редактировать

Я выполнил ту же диагностику для некоторой другой структуры данных (некоторые созданы мной *, некоторые из .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). Я пробовал также с 400000 значений, но RBTree, кажется, принимает навсегда , я действительно не знаю, почему.

Ответы [ 4 ]

17 голосов
/ 15 сентября 2010

В вашем классе Node<T> есть ошибка. Когда вы вызываете конструктор, который принимает только один аргумент значения, вы должны установить IsRed в true.

Я полагаю, что фиксированный Node<T> класс должен выглядеть примерно так: 

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

Другой вариант - мое предпочтение - было бы вообще опустить этот конструктор и всегда требовать явной установки IsRed при создании нового узла: 

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

А затем замените эту строку в вашем Add методе ... 

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

... с этим ... 

Node<T> current = new Node<T>(item, true);
3 голосов
/ 15 сентября 2010
  1. изменить порядок испытаний и повторить измерение.
  2. рандомизируйте ваши данные. Сортированные наборы ведут себя странно при вставке предварительно отсортированных данных.
1 голос
/ 15 сентября 2010

SortedSet включает атрибут TargetedPatchingOptOut , включена ли в вашу скопированную версию? 

[TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
public bool Add(T item)
{
    return this.AddIfNotPresent(item);
}
0 голосов
/ 15 сентября 2010

Если бы разница не была такой большой, я бы предположил, что причина в том, что .NET-сборки имеют NGen-ed и поэтому они уже переведены на собственный код.В случае вашего класса время компиляции IL-кода в нативный код амортизируется во время вашего теста.Как увеличение количества итераций цикла влияет на время?

...