C # queued up faster than my own

Question

I tried to make the queue as fast as possible, and I planned to make it so that I could extract many functions, and you all know from the very beginning. This means that I will never try to add more elements than for the selected array.

Despite the fact that I only implemented what I need, I lose the built-in queue when I switch (~ 2000) read and write operations.

I was curious that this makes the built-in queue faster than mine, which is built on bare bone?

As you can see, the queue is based on a circular array, so I don't need to move any elements. I also just write on top of the data instead of creating a new node to save some time. (Despite the fact that in my test he made no big differences.)

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

My test code is executed with a built-in stopwatch, and everything is written out in ticks.

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

Conclusion:

My queue method ticks = 2416

Queue Method Key C # = 2320

Answer 1

The sheer cost that I see is the introduction of objects Node. This will be especially noticeable if you are actually using it as Queuevalue types, such as charbecause the inline implementation does not transfer values ​​to the reference type.

Here's how I would change your implementation:

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

This seems to be much better (Release build, Any CPU, win 8.1):

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