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

输出为:

我的队列方法ticks = 2416

c#队列方法ticks = 2320

Answer 1

我看到的一个明显的开销是Node对象的引入。当您实际使用它作为值类型(如char)的Queue时，这将特别明显，因为内置实现没有将值包装到引用类型中。

这是我将如何改变你的实现:

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

这个似乎要好得多(发布版本，x64, win 8.1):

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