Is .NET 6 PriorityQueue thread-safe?

Question

.NET 6 now has PriorityQueue<TElement,TPriority> which is very useful. The document is not very clear yet (granted at the time of the question the documentation is still for RC1) if it is thread-safe or not. Two things:

• It resides in System.Collections.Generic and there doesn't seem to be an equivalent in System.Collections.Concurrent.

• It does have method named TryDequeue and TryPeek. Granted they probably are just methods that do not throw exception when the queue is empty but it does give an impression of the concurrent collections.

Can I use it for multithreaded environment without wrapping/locking (for example in an ASP.NET Core website)? Any concurrent equivalent that I am not aware of (I try not to use 3rd-party package if possible)?

Goahead

That's a bit of an omission -- normally the MSDN docs are good at saying whether a type is thread-safe. Looking at the source however, it's abundantly clear that it's not thread-safe. You will need to use your own locking. – Erdmann

In my opinion, the easiest rule to follow with this is that if the type does not explicitly state that it is thread-safe (or has a name that implies it), you should assume it is not. – Ingravescent

It is not only your rule - it is the general way .NET is written. Thread safety is a RARE feature and comes with a cost. Unless it is explicitly mentioned, the default is that something is not thread safe. As such, the documentation is EXTREMELY clear on this not being thread safe. – Kochi

No. Keep your eye on the big picture, the point of PriorityQueue is iteration. You get the elements back in priority order. Iteration is never thread-safe. The safe collection classes fake it by having the enumerator copy the collection, which only keeps it logically safe. But is expensive and doesn't prevent elements that are no longer in the collection from showing up. Only the client code using lock can make it truly safe, beware the pain of locking an iterator loop. – Vixen

Answer 1

With a look at the source code for PriorityQueue.Enqueue, for instance, it is immediately apparent that the code is not thread-safe:

public void Enqueue(TElement element, TPriority priority)
{
    // Virtually add the node at the end of the underlying array.
    // Note that the node being enqueued does not need to be physically placed
    // there at this point, as such an assignment would be redundant.

    int currentSize = _size++; // <-- BOOM

Array

Answer 2

The document is not very clear yet

It actually is. Anything in .NET is NOT thread safe unless it is EXPLICITLY mentioned in the documentation. Period.

Thread safety comes with a (significant) performance overhead, particularly when done generically (i.e. not assuming specific uses). As such, it would be extremely stupid to make everything thread safe "just in case". Hence the general concept in .NET (since back in 1.0) that NOTHING is thread safe unless it is explicitly mentioned in the documentation.

As you say, the documentation has no mention of thread safety. As such, it is extremely clear on NOT being thread safe.

Kochi

If this is EXTREMELY clear by omission, how about all the types which have a "Thread Safety" section saying "This is not thread safe", e.g. the non-priority Queue<T> class? Since the overarching convention in the MSDN docs is to have a "Thread Safety" section regardless of whether the type is thread-safe or not, the lack of any such section is more an indication that the type is not thread-safe... – Erdmann

That requires extensive knowledge about the .NET documentation, I.E it's not very obvious. – Chic

Answer 3

It is not thread safe. Here is a very simple test:

PriorityQueue<int, int> queue = new PriorityQueue<int, int>();
Parallel.For(0, 10000, (id) => {
    queue.Enqueue(id, 0);
    queue.Dequeue();
});

The test crashes with an exception. It can be easily fixed using lock statements:

PriorityQueue<int, int> queue = new PriorityQueue<int, int>();
Parallel.For(0, 10000, (id) => {
    lock(queue)
    {
        queue.Enqueue(id, 0);
    }
    lock(queue)
    {
        queue.Dequeue();
    }
});

That might cause issues if the queue is being shared, but that can be fixed by using a wrapper class that extends PriorityQueue, overriding every method to include a lock.

Guv