Queue vs List Performance In C#

I was recently investigating a piece of non-performant code that essentially boiled down to a loop that pulled items off a “working list”, and when the work was done, removed it from the list. Now even me describing this code now you’re probably thinking.. Well that sounds like a “Queue” type. And you would be right, it basically is a queue but written using a List object.

Maybe this sounds like a real rookie mistake, but there is definitely a common theme among C# developers (myself included), that use List as basically the catch all for any sort of collection. Arrays, queues, stacks and pipelines are all pretty much non-existent in any sort of business logic code I write, and as we’re about to find out, maybe that’s to my own detriment.

Back to the code I was talking about, it looked something like this :

//Somewhere in the code we add a bunch of items to the working list. 
var workingList = new List<object>();
workingList.Add(new object());

//And then later on we have a loop that looks like so : 
while(workingList.Any())
{
    var item = workingList.First();
    workingList.Remove(item);
    //do some work
}

Immediately looking at this code I realized it’s basically a makeshift queue built ontop of a list type, but with some clear performance issues in mind. Just how much performance can be squeezed out of this we will certainly delve into, but let’s look at the problems of this code in a nutshell.

1. We have a call to “Any()” to check if we have items. This is probably pretty fast, but we do this as an additional check rather than just trying to “pop” an item immediately.
2. We remove the item from the front of the list. This actually means that the list itself all shifts up 1 place, a much larger operation than I first thought.
3. Our removing code requires us to compare object references within the list rather than remove it by index (Although this is the least of our problems).

Just touching on number 3, we could instead change the remove line to be :

workingList.RemoveAt(0);

But that’s not our actual issue.

The problem is we are trying to use a List type for a job that is clearly suited to Queue. But how much faster would Queue actually be? What if we only have a hundred items? Is there actually any noticeable difference?

Well, there’s an easy way to solve this using BenchmarkDotNet.

Here’s my benchmark that I set up :

[SimpleJob(RuntimeMoniker.NetCoreApp31)]
public class QueueVsListBenchmark
{
    [Params(100, 1000, 10000)]
    public int size;

    private Queue<object> queue = new Queue<object>();
    private List<object> list = new List<object>();

    [IterationSetup]
    public void Setup()
    {
        queue = new Queue<object>();
        list = new List<object>();
    }

    [Benchmark]
    public void ComputeQueue()
    { 
        for(int i=0; i < size; i++)
        {
            queue.Enqueue(new object());
        }

        while(queue.TryDequeue(out var item))
        {
        }
    }

    [Benchmark(Baseline = true)]
    public void ComputeList()
    {
        for (int i = 0; i < size; i++)
        {
            list.Add(new object());
        }

        while(list.Any())
        {
            var item = list.First();
            list.Remove(item);
        }
    }
}

Not too complicated. We simply insert X amount of items, and then dequeue until we are done. We also have different sizes of queues to just compare how the size of the queue may affect the performance.

And the results?

|       Method |  size |          Mean | Ratio |
|------------- |------ |--------------:|------:|
| ComputeQueue |   100 |      4.080 us |  0.19 |
|  ComputeList |   100 |     21.917 us |  1.00 |
|              |       |               |       |
| ComputeQueue |  1000 |     28.066 us |  0.12 |
|  ComputeList |  1000 |    242.496 us |  1.00 |
|              |       |               |       | 
| ComputeQueue | 10000 |    205.809 us |  0.02 |
|  ComputeList | 10000 | 10,033.700 us |  1.00 |

So swapping a queue, even at a relatively small size of 100 items, is 5x faster. And the larger the queue, the more performance we can squeeze out of not using a list.

Now is this over thinking everything? Maybe. But it’s one I’m very comfortable with. Not only is performance that much better using a queue, but it’s actually the right data type anyway. We aren’t doing some “hack” to squeeze juice out of it. We are actually using the correct data type for the correct use. Anyone looking at our code and seeing a “Queue” type is going to know exactly what it’s doing.