Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C# built in queue faster than my own [closed]

Tags:

performance

c#

I tried to make a queue that would be so fast as possible and I planned to make it so my taking out many features and you know everything from the beginning. That means I will never try to add more element than I have an array allocated for.

Even though I only implemented what I need, I lose to the built in queue when I get over (~2000) read and write operations.

I got curious what it is that makes the built in queue faster than my own that is built to the bare bone?

As you can see the queue is based on a circular array so I don't have to move any elements. I also just write over the data instead of creating a new node to save some time. (Even though in my test it didn't make any 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 testing code is done with the built in stop watch 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();
}

The output is:

My queue method ticks is = 2416

C# queue method ticks is = 2320

like image 820
Olof Avatar asked Jul 12 '15 20:07

Olof


1 Answers

One obvious overhead that I can see is the introduction of Node objects. This will be especially noticeable when you're actually using this as a Queue of value types such as char, because the built in implementation isn't wrapping the values into a reference type.

Here is 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 fare much better (Release build, x64, win 8.1):

My queue method ticks is = 582
C# queue method ticks is = 2166
like image 171
Asad Saeeduddin Avatar answered Oct 09 '22 01:10

Asad Saeeduddin