Speeding up System.Collection.Generic.Queue() possible?

Question

50\% of my simulation time is spent on the following code:

    internal double simWithdrawalFast(double t)
    {
        simarrivals.Enqueue(t + Leadtime);
        return simarrivals.Dequeue();
    }

where simarrivals is a System.Collection.Generic.Queue<double>.

If I write my own queue, will it be faster?

EDIT: note that there are doubles in the queue to begin with, i.e. the queue has about 200 elements when simwithdrawal is called. Each call adds and removes an element.

Answer 1

I wanted to know what could be achieved by combining these ideas, and inlining. I did not make explicit in the question that the length of the queue stays constant. So I can use a fixed array simarrivalsArray with length simS:

The below adaptation makes the function twice as fast (i.e. fraction of time spent in function drops from 50 to 33\%):

internal double simWithdrawalFast(double time)
{
    double returnValue = simarrivalsArray[head]; //Withdrawal
    simarrivalsArray[head] = time+leadtime; //Enqueue
    head = (head + 1) % simS;//simS is length of array/queue, which stays constant;
    return returnValue;
}

Now the crazy part: getting rid of modulus sign drops the fraction of time spent in this function to only 17\%. This means the function becomes about five times as fast as the original, or 2.5 times as fast as the version above (0.2/(1+0.2 ) is about 0.17).

internal double simWithdrawalFast(double time)
{
    double returnValue = simarrivalsArray[head]; //Withdrawal
    simarrivalsArray[head++] = time+leadtime; //Enqueue
    if(head==simS)//simS is length of array/queue, which stays constant;
    {
         head=0;
    }
    return returnValue;
}

EDIT: in response to HH, I wrote the some code to test the difference in isolation.

Output:

Own implementation: 7964
Queue: 23860

Factor of 3, but of course some time is spent in the loop itself. Profiling with slimtune gives me
Loop: 23%
Own implementation 11%
Queue: 65%
i.e. a factor 6.5.

I don't think it is the measuring overhead, as running the program while profiling gives me
Output:
Own implementation: 8795
Queue: 27863

Implementation:

class Tester
{
    int simS;
    Queue<double> simarrivals;
    double[] simarrivalsArray;
    int head = 0;
    double leadtime = 5.0;

    internal Tester()
    {
        this.simS = 300;
        simarrivalsArray = new double[simS];
        simarrivals = new Queue<double>(simS + 1);
        for (int i = 0; i < simS; i++)
        {
            simarrivals.Enqueue(0.0);
        }            
    }

    internal void TestQueues()
    {
        System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
        double withdrawals = 5.0E+8;
        for (double d = 0.0; d < withdrawals; d += 1.0)
        {
            simWithdrawalFast(d);
        }
        Console.WriteLine("Own implementation:  "+ sw.ElapsedMilliseconds);
        System.Diagnostics.Stopwatch sw2 = System.Diagnostics.Stopwatch.StartNew();
        for (double d = 0.0; d < withdrawals; d += 1.0)
        {
            simWithdrawalFast2(d);
        }
        Console.WriteLine("Queue:  "+sw2.ElapsedMilliseconds);
    }
    double simWithdrawalFast(double time)
    {
        double returnValue = simarrivalsArray[head]; //Withdrawal 
        simarrivalsArray[head++] = time + leadtime; //Enqueue 
        if (head == simS)//simS is length of array/queue, which stays constant; 
        {
            head = 0;
        }
        return returnValue;
    }
    double simWithdrawalFast2(double t)
    {
        simarrivals.Enqueue(t + leadtime);
        return simarrivals.Dequeue();
    }
}

Answer 2

Kirk's answer is great. However, if you really need to speed this up, you can.

Copy the functions Kirk generously showed to you, then remove the checks or management that you do not need. For example, if the code you posted is the only access to this queue, you could improve speed with something like the following.

private double[] array; // Initialize this appropriately.

public double Dequeue()
{
  // Assume you use these functions properly, and avoid the exception checks.
  double obj = this._array[this._head];

  // No need to clean up after ourselves if used appropriately...
  //this._array[this._head] = default (T);

  // Still need to adjust the position in the queue.
  this._head = (this._head + 1) % this._array.Length;

  // May not need these either.
  //--this._size;
  //++this._version;
  return obj;
}


public void Enqueue(T item)
{
  // Don't bother trying to resize if you know you don't ever need to.

  this._array[this._tail] = item;
  this._tail = (this._tail + 1) % this._array.Length;

  // Probably don't need these.
  //++this._size;
  //++this._version;
}

Also, if you really want to squeeze out performance, see if you can find a slightly faster set of operations to accomplish the same goal as the head and tail adjustments. You can also look at C#'s unchecked keyword to see if it is appropriate for your situation.

Answer 3

The implementations of these two methods seem pretty minimalist to me:

public T Dequeue()
{
  if (this._size == 0)
    ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);
  T obj = this._array[this._head];
  this._array[this._head] = default (T);
  this._head = (this._head + 1) % this._array.Length;
  --this._size;
  ++this._version;
  return obj;
}


public void Enqueue(T item)
{
  if (this._size == this._array.Length)
  {
    int capacity = (int) ((long) this._array.Length * 200L / 100L);
    if (capacity < this._array.Length + 4)
      capacity = this._array.Length + 4;
    this.SetCapacity(capacity);
  }
  this._array[this._tail] = item;
  this._tail = (this._tail + 1) % this._array.Length;
  ++this._size;
  ++this._version;
}

I have a hard time believing the semantics of a queue can be honored by code much more efficient than this. Therefore, your problem is probably at a higher level. Why is this method (simWithdrawalFast) getting called so much? You're probably going to have to find a way to make your overall algorithm more efficient rather than finding a more efficient data structure.

If the problem is frequent resizing of the queue, you might be able to improve the performance somewhat by specifying a capacity when constructing the queue. My hunch though is that this isn't your problem.