What is the fastest collection in c# to implement a prioritizing queue?

I need to implement a FIFO queue for messages on a game server so it needs to as fast as possible. There will be a queue for each user.

The queue will have a maxiumem size (lets say 2000). The size won't change during runtime.

I need to prioritize me开发者_JAVA技巧ssages ONLY if the queue reaches its maximum size by working backwards and removing a lower priority message (if one exists) before adding the new message.

A priority is an int with possible values of 1, 3, 5, 7, 10.

There can be multiple messages with the same priority.

A message cannot change its priority once allocated.

The application is asynchronous so access to the queue needs to be locked.

I'm currently implementing it using a LinkedList as the underlying storage but have concerns that searching and removing nodes will keep it locked for too long.

Heres the basic code I have at the moment:

public class ActionQueue
{
    private LinkedList<ClientAction> _actions = new LinkedList<ClientAction>();
    private int _maxSize;

    /// <summary>
    /// Initializes a new instance of the ActionQueue class.
    /// </summary>
    public ActionQueue(int maxSize)
    {
        _maxSize = maxSize;
    }

    public int Count
    {
        get { return _actions.Count; }            
    }

    public void Enqueue(ClientAction action)
    {
        lock (_actions)
        {
            if (Count < _maxSize)
                _actions.AddLast(action);
            else
            {
                LinkedListNode<ClientAction> node = _actions.Last;
                while (node != null)
                {
                    if (node.Value.Priority < action.Priority)
                    {
                        _actions.Remove(node);
                        _actions.AddLast(action);
                        break;
                    }

                    node = node.Previous;

                }                    
            }
        }
    }

    public ClientAction Dequeue()
    {
        ClientAction action = null;

        lock (_actions)
        {
            action = _actions.First.Value;
            _actions.RemoveFirst();
        }

        return action;
    }

}

A vetted implementation of priority queue for C#/.NET can be found in the C5 Generic Collection Library in the C5.IntervalHeap<T> class.

So we have the following properties:

• Priorities are well-defined and bounded
• Needs to be thread-safe
• Queue size is fixed to 2000 messages, where enqueues beyond this drop the lowest item

Its very easy to write a priority queue which supports all of these properties:

public class BoundedPriorityQueue<T>
{
    private object locker;
    private int maxSize;
    private int count;
    private LinkedList<T>[] Buckets;

    public BoundedPriorityQueue(int buckets, int maxSize)
    {
        this.locker = new object();
        this.maxSize = maxSize;
        this.count = 0;
        this.Buckets = new LinkedList<T>[buckets];
        for (int i = 0; i < Buckets.Length; i++)
        {
            this.Buckets[i] = new LinkedList<T>();
        }
    }

    public bool TryUnsafeEnqueue(T item, int priority)
    {
        if (priority < 0 || priority >= Buckets.Length)
            throw new IndexOutOfRangeException("priority");

        Buckets[priority].AddLast(item);
        count++;

        if (count > maxSize)
        {
            UnsafeDiscardLowestItem();
            Debug.Assert(count <= maxSize, "Collection Count should be less than or equal to MaxSize");
        }

        return true; // always succeeds
    }

    public bool TryUnsafeDequeue(out T res)
    {
        LinkedList<T> bucket = Buckets.FirstOrDefault(x => x.Count > 0);
        if (bucket != null)
        {
            res = bucket.First.Value;
            bucket.RemoveFirst();
            count--;
            return true; // found item, succeeds
        }
        res = default(T);
        return false; // didn't find an item, fail
    }

    private void UnsafeDiscardLowestItem()
    {
        LinkedList<T> bucket = Buckets.Reverse().FirstOrDefault(x => x.Count > 0);
        if (bucket != null)
        {
            bucket.RemoveLast();
            count--;
        }
    }

    public bool TryEnqueue(T item, int priority)
    {
        lock (locker)
        {
            return TryUnsafeEnqueue(item, priority);
        }
    }

    public bool TryDequeue(out T res)
    {
        lock (locker)
        {
            return TryUnsafeDequeue(out res);
        }
    }

    public int Count
    {
        get { lock (locker) { return count; } }
    }

    public int MaxSize
    {
        get { return maxSize; }
    }

    public object SyncRoot
    {
        get { return locker; }
    }
}

Supports Enqueue/Dequeue in O(1) time, the TryEnqueue and TryDequeue methods are guaranteed to be thread-safe, and the size of the collection will never exceed the max size you specify in the constructor.

The locks on TryEnqueue and TryDequeue are pretty fine-grained, so you might take a performance hit whenever you need to bulk-load or unload data. If you need to load the queue with a lot of data up front, then lock on the SyncRoot and call the unsafe methods as needed.

If you have a fixed number of priorities, I'd just create a composite Queue class that wraps two or more private Queues.

A drastically simplified example follows although you could expand on it by adding a Priority enum and a switch to determine where to Enqueue an item.

class PriorityQueue {

    private readonly Queue normalQueue = new Queue();
    private readonly Queue urgentQueue = new Queue();

    public object Dequeue() {
        if (urgentQueue.Count > 0) { return urgentQueue.Dequeue(); }
        if (normalQueue.Count > 0) { return normalQueue.Dequeue(); }
        return null;
    }

    public void Enqueue(object item, bool urgent) {
        if (urgent) { urgentQueue.Enqueue(item); }
        else { normalQueue.Enqueue(item); }
    }
}

I'm assuming you can have duplicate priorities.

There's no container within .NET that allows duplicate keys akin to a C++ multimap. You could do this in a few different ways, either with a SortedList that had an array of values for each priority key (and grab the first item out of that array as the return value); the SortedList is a balanced tree underneath (IIRC) and should give you good insert and retrieval performance.

It really depends on the distribution of queue lengths you are likely to see. 2000 is the max but what's the average and what does the distribution look like? If N is typically small, a simple List<> with a brute force search for next lowest may be a fine choice.

Have you profiled your application to know this is a bottleneck?

          "Never underestimate the power of a smart compiler 
           and a smart CPU with registers and on-chip memory 
           to run dumb algorithms really fast"