Most suitable .net Timer for a scheduler

Question

We've identified a hotspot in our code using CCR timers. It appears that if we enqueue many thousands of timers that the code suffers terminal slowdown.

The fix is to choose the soonest scheduled item and enqueue a timer for this event. When it fires, we repeat. In this way, we're only ever enqueueing one timer interval at a time.

What we're finding now is that the SortedList instance which we're using to manage the scheduled items is burning with the weight of the removals from the list.

Do all .net timers suffer from the problem of increased CPU usage with the number of items enqueued, or is there one that is more intelligently written.

Alternatively, is there a better suited data structure for keeping our scheduled items in ordered fashion, that supports fast insertion and fast removal from the front of the list?

Answer 1

To always get the soonest scheduled item you need to use Heap, rather than SortedList.

There's no heap in standard .Net library. You can download the implementation from here or roll your own.

Answer 2

Try using a LinkedList<T>, I'm sure you'll see a huge improvement in performance. It's well suited for quick adds and removes.

Answer 3

A sorted list uses an array underneath, so removal from the front of the list is one of it's slowest operations. Sorting in reverse order would reduce the time it takes to remove an item from a list, because you'd be removing from the end.

If all you care about is the next item, a Priority Queue is probably a good bet.

Answer 4

Sounds like you need to use a priority queue. Priority queues are often implemented with heaps, but I find that skip lists tend to work better. Unfortunately there is no priority queue builtin to the BCL so you will have to write your own or find one elsewhere. That SortedList is going to kill your performance. Even if you decide against the priority queue you could probably get a quick boost by moving to a SortedDictionary instead.

Edit: The reason why I would prefer a priority queue here as opposed to the SortedDictionary is because removals of the lowest key in a SortedDictionary are O(log(n)) as opposed to O(1) for the priority queue.

Answer 5

If you absolutely need the sorting feature you could consider using a SortedDictionary instead of a SortedList. SortedDictionary is O(log n) for insertion and remonal since internally it uses a tree.

http://msdn.microsoft.com/en-us/library/5z658b67(VS.80).aspx

Answer 6

For a quick fix that might (or might not) be enough, switch to a sorted dictionary.

A sorted list is going to cause problems because its underlying data structure is an array. As another poster pointed out, if you remove from the "top" ([0]) of the sorted list, all the other items have to be shifted down one in the array, so the more items you have in the list, the more expensive it is to remove one. (so the performance is O(n) or worse).

Conversly, insertion and removal on the sorted dictionary is O(log n), so your remove performance should be much less impacted when you have lots of items in the list.