.NET queue ElementAt performance

Question

I'm having a hard time with parts of my code:

    private void UpdateOutputBuffer()
    {
        T[] OutputField = new T[DisplayedLength];

        int temp = 0;
        int Count = HistoryQueue.Count;
        int Sample = 0;

        //Then fill the useful part with samples from the queue
        for (temp = DisplayStart; temp != DisplayStart + DisplayedLength && temp < Count; temp++)
        {
            OutputField[Sample++] = HistoryQueue.ElementAt(Count - temp - 1);
        }

        DisplayedHistory = OutputField;
    }

It takes most of the time in the program. The number of elements in HistoryQueue is 200k+. Could this be because the queue in .NET is implemented internally as a linked list?

What would be a better way of going about this? Basically, the class should act like a FIFO that starts dropping elements at ~500k samples and I could pick DisplayedLength elements and put them into OutputField. I was thinking of writing my own Queue that would use a circular buffer.

The code worked fine for count lower values. DisplayedLength is 500.

Thank you,

David

Answer 1

Queue does not have an ElementAt method. I'm guessing you are getting this via Linq, and that it is simply doing a forced iteration over n elements until it gets to the desired index. This is obviously going to slow down as the collection gets bigger. If ElementAt represents a common access pattern, then pick a data structure that can be accessed via index e.g. an Array.

Answer 2

Yes, the linked-list-ness is almost certainly the problem. There's a reason why Queue<T> doesn't implement IList<T> :) (Having said that, I believe Stack<T> is implemented using an array, and that still doesn't implement IList<T>. It could provide efficient random access, but it doesn't.)

I can't easily tell which portion of the queue you're trying to display, but I strongly suspect that you could simplify the method and make it more efficient using something like:

T[] outputField = HistoryQueue.Skip(...) /* adjust to suit requirements... */
                              .Take(DisplayedLength)
                              .Reverse()
                              .ToArray();

That's still going to have to skip over a huge number of items individually, but at least it will only have to do it once.

Have you thought of using a LinkedList<T> directly? That would make it a lot easier to read items from the end of the list really easily.

Building your own bounded queue using a circular buffer wouldn't be hard, of course, and may well be the better solution in the long run.