C＃内置队列比我自己的队列快

Question

我试图建立一个尽可能快的队列，并计划将其排成一列，这样我就可以使用许多功能，并且从一开始就了解所有内容。这意味着我将永远不会尝试添加比分配了数组更多的元素。

即使我只实现了我需要的东西，但是当我完成（〜2000）次读写操作时，我仍然迷失在内置队列中。

我很好奇是什么使内置队列比我的裸露队列快？

如您所见，队列基于圆形数组，因此我无需移动任何元素。我还只是覆盖数据，而不是创建新节点来节省时间。（即使在我的测试中，也没有太大的区别。）

class Queue<T> {

    private class Node {
        public T data;
        public Node(T data) {
            this.data = data;
        }
        public Node() {

        }
    }
    Node[] nodes;
    int current;
    int emptySpot;

    public Queue(int size) {
        nodes = new Node[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = new Node();
        }
        this.current = 0;
        this.emptySpot = 0;
    }

    public void Enqueue(T value){
        nodes[emptySpot].data = value;
        emptySpot++;
        if (emptySpot >= nodes.Length) {
            emptySpot = 0;
        }
    }
    public T Dequeue() {
        int ret = current;
        current++;
        if (current >= nodes.Length) {
            current = 0;
        }
        return nodes[ret].data;
    }
}

我的测试代码是使用内置秒表完成的，所有内容都以滴答作答。

static void Main(string[] args) {

    MinimalCollections.Queue<char> queue = new MinimalCollections.Queue<char>(5500);
    Queue<char> CQueue = new Queue<char>(5500);

    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int y = 0; y < 4; y++) {
        for (int i = 0; i < 5500; i++) {
            queue.Enqueue('f');
        }
        for (int i = 0; i < 5500; i++) {
            queue.Dequeue();
        }
    }
    sw.Stop();
    Console.WriteLine("My queue method ticks is = {0}", sw.ElapsedTicks);

    sw.Reset();

    sw.Start();
    for (int y = 0; y < 4; y++) {
        for (int i = 0; i < 5500; i++) {
            CQueue.Enqueue('f');
        }
        for (int i = 0; i < 5500; i++) {
            CQueue.Dequeue();
        }
    }
    sw.Stop();
    Console.WriteLine("C# queue method ticks is = {0}", sw.ElapsedTicks);

    Console.ReadKey();
}

输出为：

我的排队方法的滴答声是= 2416

C＃队列方法的滴答度= 2320

Answer 1

我可以看到的一个显而易见的开销是Node对象的引入。当您实际将其用作Queue诸如的值类型时，这一点尤其明显char，因为内置实现并未将这些值包装为引用类型。

这是我将如何更改您的实现的方法：

class Queue<T>
{
    T[] nodes;
    int current;
    int emptySpot;

    public Queue(int size)
    {
        nodes = new T[size];
        this.current = 0;
        this.emptySpot = 0;
    }

    public void Enqueue(T value)
    {
        nodes[emptySpot] = value;
        emptySpot++;
        if (emptySpot >= nodes.Length)
        {
            emptySpot = 0;
        }
    }
    public T Dequeue()
    {
        int ret = current;
        current++;
        if (current >= nodes.Length)
        {
            current = 0;
        }
        return nodes[ret];
    }
}

这似乎要好得多（发行版，Any CPU，win 8.1）：

My queue method ticks is = 582
C# queue method ticks is = 2166