# Single timer event dispatcher.

This topic is 2495 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a need to asynchronously execute many timed events (Could go over 1000 events). So the basic idea is that I have a priority queue of events and the timer should execute the first one and then wait for the next item and execute it when the time comes. Events can be inserted concurrently and must have a way to be removed. I'm not sure what the best design looks like in C#.

I'll describe my current implementation:
[source lang="csharp"]
public class TimeEvent : IComparable<TimeEvent>
{
public DateTime Time { get; set; }
public bool Enabled { get; set; }

public TimeEvent()
{
Enabled = true;
}

public int CompareTo(TimeEvent other)
{
return Time.CompareTo(other.Time);
}
}
[/source]

Then I have a derived TimeEvent class. As an example (not that important):
[source lang="csharp"]
internal class TimeEvent1 : TimeEvent
{
public Action<Packet> Callback { get; set; }

public SourceConnectionRequestTimeout(Action<Packet> callback, TimeSpan time)
{
Callback = callback;

Time = DateTime.Now + time;
}
}
[/source]

Ignoring the odd use of inheritance, the basic dispatcher uses a Timer instance. "timeEvents" is a basic heap implementation for a priority queue.
[source lang="csharp"]
TimeEventDispatcher = new Timer((o) =>
{
lock (TimeEventDispatcher)
{
var timeEvent = timeEvents.Pop();

if (timeEvent.Enabled)
{
if (timeEvent is TimeEvent1)
{
(timeEvent as TimeEvent1).Callback();
}
}

// Stop the timer if there are no other events in the priority queue. If there are events then wait for the next one.
if (!timeEvents.Empty)
{
timeEvent = timeEvents.Peek();
var delay = Math.Max(0, (int)(timeEvent.Time - DateTime.Now).TotalMilliseconds);
TimeEventDispatcher.Change(delay, Timeout.Infinite);
}
}
}, null, Timeout.Infinite, Timeout.Infinite);
[/source]
Now to add a TimeEvent instance I'm locking the timer so the code in the callback can't execute at the same time. Then I insert the new time event instance. If it happens to be the first item in the priority queue this means the timer needs to be changed to update at the new earlier time. (Basically if the item in the priority queue was set to expire 100 ms from now and we insert an item to execute 50 ms from now then we need to change the timer to 50 ms). This also conveniently starts the timer if it isn't already started.
[source lang="csharp"]
{
lock (TimeEventDispatcher)
{
timeEvents.Push(timeEvent);
if (timeEvents.Peek() == timeEvent)
{
var delay = Math.Max(0, (int)(timeEvent.Time - DateTime.Now).TotalMilliseconds);
TimeEventDispatcher.Change(delay, Timeout.Infinite);
}
}
}
[/source]
Removing an event is done by locking the timer and setting the Enabled property on the time event instance to false. So when it's processed it's removed without executing the item. Pretty simple solution.

Okay so the above solution seems like it would work. There's a race condition in the system where if a callback is execute and doesn't get to the lock statement by the time another time event is inserted before the most recent one the it'll execute the wrong one. But that can only happen if you insert an item that must be executed right away so it has no ill-effect on the algorithm. Also all the time events are very small so when they execute they don't block the system so they don't need to be executed asynchronously themselves (via tasks or somethings).

Is there a better algorithm in C# for handling this situation? (Mostly caring about performance). Anything my algorithm is missing assuming it should be design to handle possibly thousands of time events.

(Also if anyone is curious about the actual problem, this is a networking library timer like the one found in TCP that manages resend events and other timer events).

##### Share on other sites
You're going to run into a problem where the timer delay is long and then an event in a short period of time will cause the new event to be skipped.

Personally, a simple thread working on a ConcurrentQueue<Action> seems like a more robust solution. Have a flag that is set on insert and unset after the loop gets all 'sendable' events. For a networking library I'm not sure that I would even do so much time work... any thing like this will use a disproportionate amount of resources the less latency you want to induce between when the event was supposed to trigger and when it actually does.

##### Share on other sites

You're going to run into a problem where the timer delay is long and then an event in a short period of time will cause the new event to be skipped.

That's what I was talking about with the race condition. It can't happen where the timer delay is long. Notice in the AddTimeEvent that it calls Change on the timer after inserting the item. So if for instance you have the timer currently going to timeout in 100 ms and you insert an item to timeout in 10 ms the timer will be changed to 10 ms. The race condition only exists when the item in the queue is at say 1 ms and you try to insert an item at 0 ms, but that case doesn't matter much since it's supposed to be implemented instantly anyway. Unless I misunderstood the situation you're thinking of. Could you describe it in more detail?

Personally, a simple thread working on a ConcurrentQueue<Action> seems like a more robust solution. Have a flag that is set on insert and unset after the loop gets all 'sendable' events. For a networking library I'm not sure that I would even do so much time work... any thing like this will use a disproportionate amount of resources the less latency you want to induce between when the event was supposed to trigger and when it actually does.

You would need to dequeue all events and reinsert them. For a thousand items this is not a trivial task. However, neither is a lock. I think I'll write a benchmark for each method.

Anymore suggestions?

##### Share on other sites
Not offhand without a better understanding of the problem
.

##### Share on other sites
Been busy lately. Okay so we have the two implementation. One is easy on the CPU but the resolution is < 15 ms using a timer. The other is a thread consuming version which is very accurate but keeps is rather "wasteful" with resources. Opinions? Technically the first option fits my needs for now and the accuracy is good enough for a networking library. The second option to me seems a bit naive.

Timer implementation:
 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Test { using System; using System.Collections.Generic; using System.Threading; using System.Collections.Concurrent; public class Heap<T> where T : class, IComparable<T> { List<T> nodes = new List<T>(); public bool Empty { get { return nodes.Count == 0; } } public Heap() { } public Heap(T[] elements) { nodes = new List<T>(elements); for (int i = elements.Length / 2; i >= 0; --i) { SiftDown(i); } } public void Push(T value) { nodes.Add(value); SiftUp(nodes.Count - 1); } public T Pop() { T ret = nodes[0]; nodes[0] = nodes[nodes.Count - 1]; nodes.RemoveAt(nodes.Count - 1); SiftDown(0); return ret; } public T Peek() { return nodes[0]; } public void DecreaseKey(T value) { for (int i = 0; i < nodes.Count; ++i) { if (nodes == value) { SiftDown(i); break; } } } private void SiftUp(int i) { int parent = (i - 1) / 2; if (parent >= 0 && nodes[parent].CompareTo(nodes) > 0) { T tmp = nodes[parent]; nodes[parent] = nodes; nodes = tmp; SiftUp(parent); } } private void SiftDown(int i) { int left = i * 2 + 1; int right = i * 2 + 2; int smallest; if (left < nodes.Count && nodes.CompareTo(nodes) < 0) { smallest = left; } else { smallest = i; } if (right < nodes.Count && nodes

.CompareTo(nodes[smallest]) < 0) { smallest = right; } if (smallest != i) { T tmp = nodes; nodes = nodes[smallest]; nodes[smallest] = tmp; SiftDown(smallest); } } } public class TimeEvent : IComparable<TimeEvent> { public DateTime Time { get; set; } public bool Enabled { get; set; } public TimeEvent() { Enabled = true; } public virtual void Execute() { } public int CompareTo(TimeEvent other) { return Time.CompareTo(other.Time); } } public class TimeEvent1 : TimeEvent { public int Index { get; set; } public Action Callback { get; set; } public TimeEvent1(int index, TimeSpan time) { Index = index; Time = DateTime.Now + time; Test.ExpectedTime.Enqueue(Tuple.Create(index, (int)(Time - Test.StartTime).TotalMilliseconds)); } public override void Execute() { Test.ActualTime.Enqueue(Tuple.Create(Index, (int)(DateTime.Now - Test.StartTime).TotalMilliseconds)); } } public class Test { public static Timer TimeEventDispatcher { get; set; } public static Heap<TimeEvent> timeEvents = new Heap<TimeEvent>(); public static DateTime StartTime { get; set; } public static ConcurrentQueue<Tuple<int, int>> ExpectedTime = new ConcurrentQueue<Tuple<int, int>>(); public static ConcurrentQueue<Tuple<int, int>> ActualTime = new ConcurrentQueue<Tuple<int, int>>(); public static void StartDispatcher() { TimeEventDispatcher = new Timer((o) => { lock (TimeEventDispatcher) { var timeEvent = timeEvents.Pop(); if (timeEvent.Enabled) { timeEvent.Execute(); } if (!timeEvents.Empty) { timeEvent = timeEvents.Peek(); var delay = Math.Max(0, (int)(timeEvent.Time - DateTime.Now).TotalMilliseconds); TimeEventDispatcher.Change(delay, Timeout.Infinite); } } }, null, Timeout.Infinite, Timeout.Infinite); } public static void AddTimeEvent(TimeEvent timeEvent) { lock (TimeEventDispatcher) { timeEvents.Push(timeEvent); if (timeEvents.Peek() == timeEvent) { var delay = Math.Max(0, (int)(timeEvent.Time - DateTime.Now).TotalMilliseconds); TimeEventDispatcher.Change(delay, Timeout.Infinite); } } } public static void Main() { StartTime = DateTime.Now; StartDispatcher(); var random = new Random(); for (var i = 0; i < 100; ++i) { AddTimeEvent(new TimeEvent1(i, TimeSpan.FromMilliseconds(random.Next(10, 500)))); } Thread.Sleep(1000); var expectedTime = ExpectedTime.ToArray(); var actualTime = ActualTime.ToArray(); for (var i = 0; i < expectedTime.Length; ++i) { for (var j = 0; j < actualTime.Length; ++j) { if (expectedTime.Item1 == actualTime[j].Item1) { Console.WriteLine("Expected Time: " + expectedTime.Item2 + " Actual Time: " + actualTime[j].Item2 + " Error: " + (actualTime[j].Item2 - expectedTime.Item2)); } } } } } } 
Output:
 Expected Time: 299 Actual Time: 308 Error: 9 Expected Time: 264 Actual Time: 277 Error: 13 Expected Time: 494 Actual Time: 498 Error: 4 Expected Time: 75 Actual Time: 79 Error: 4 Expected Time: 272 Actual Time: 277 Error: 5 Expected Time: 276 Actual Time: 277 Error: 1 Expected Time: 466 Actual Time: 469 Error: 3 Expected Time: 123 Actual Time: 137 Error: 14 Expected Time: 123 Actual Time: 137 Error: 14 Expected Time: 262 Actual Time: 261 Error: -1 Expected Time: 428 Actual Time: 433 Error: 5 Expected Time: 284 Actual Time: 293 Error: 9 Expected Time: 170 Actual Time: 169 Error: -1 Expected Time: 175 Actual Time: 184 Error: 9 Expected Time: 128 Actual Time: 137 Error: 9 Expected Time: 197 Actual Time: 202 Error: 5 Expected Time: 218 Actual Time: 222 Error: 4 Expected Time: 57 Actual Time: 61 Error: 4 Expected Time: 309 Actual Time: 308 Error: -1 Expected Time: 229 Actual Time: 230 Error: 1 Expected Time: 110 Actual Time: 121 Error: 11 Expected Time: 218 Actual Time: 222 Error: 4 Expected Time: 114 Actual Time: 121 Error: 7 Expected Time: 390 Actual Time: 402 Error: 12 Expected Time: 191 Actual Time: 202 Error: 11 Expected Time: 131 Actual Time: 137 Error: 6 Expected Time: 332 Actual Time: 341 Error: 9 Expected Time: 54 Actual Time: 61 Error: 7 Expected Time: 319 Actual Time: 326 Error: 7 Expected Time: 282 Actual Time: 293 Error: 11 Expected Time: 338 Actual Time: 341 Error: 3 Expected Time: 227 Actual Time: 230 Error: 3 Expected Time: 318 Actual Time: 326 Error: 8 Expected Time: 114 Actual Time: 121 Error: 7 Expected Time: 34 Actual Time: 45 Error: 11 Expected Time: 162 Actual Time: 169 Error: 7 Expected Time: 266 Actual Time: 277 Error: 11 Expected Time: 78 Actual Time: 79 Error: 1 Expected Time: 201 Actual Time: 202 Error: 1 Expected Time: 62 Actual Time: 61 Error: -1 Expected Time: 21 Actual Time: 30 Error: 9 Expected Time: 92 Actual Time: 91 Error: -1 Expected Time: 114 Actual Time: 121 Error: 7 Expected Time: 39 Actual Time: 45 Error: 6 Expected Time: 285 Actual Time: 293 Error: 8 Expected Time: 62 Actual Time: 61 Error: -1 Expected Time: 285 Actual Time: 293 Error: 8 Expected Time: 180 Actual Time: 184 Error: 4 Expected Time: 42 Actual Time: 45 Error: 3 Expected Time: 374 Actual Time: 387 Error: 13 Expected Time: 250 Actual Time: 261 Error: 11 Expected Time: 389 Actual Time: 402 Error: 13 Expected Time: 322 Actual Time: 326 Error: 4 Expected Time: 363 Actual Time: 371 Error: 8 Expected Time: 124 Actual Time: 137 Error: 13 Expected Time: 94 Actual Time: 105 Error: 11 Expected Time: 162 Actual Time: 169 Error: 7 Expected Time: 116 Actual Time: 121 Error: 5 Expected Time: 387 Actual Time: 387 Error: 0 Expected Time: 154 Actual Time: 153 Error: -1 Expected Time: 447 Actual Time: 451 Error: 4 Expected Time: 424 Actual Time: 433 Error: 9 Expected Time: 306 Actual Time: 308 Error: 2 Expected Time: 343 Actual Time: 355 Error: 12 Expected Time: 426 Actual Time: 433 Error: 7 Expected Time: 213 Actual Time: 222 Error: 9 Expected Time: 468 Actual Time: 469 Error: 1 Expected Time: 68 Actual Time: 79 Error: 11 Expected Time: 154 Actual Time: 153 Error: -1 Expected Time: 469 Actual Time: 469 Error: 0 Expected Time: 434 Actual Time: 433 Error: -1 Expected Time: 153 Actual Time: 153 Error: 0 Expected Time: 358 Actual Time: 371 Error: 13 Expected Time: 260 Actual Time: 261 Error: 1 Expected Time: 221 Actual Time: 222 Error: 1 Expected Time: 31 Actual Time: 30 Error: -1 Expected Time: 116 Actual Time: 121 Error: 5 Expected Time: 87 Actual Time: 91 Error: 4 Expected Time: 118 Actual Time: 121 Error: 3 Expected Time: 142 Actual Time: 153 Error: 11 Expected Time: 348 Actual Time: 355 Error: 7 Expected Time: 164 Actual Time: 169 Error: 5 Expected Time: 24 Actual Time: 30 Error: 6 Expected Time: 448 Actual Time: 451 Error: 3 Expected Time: 44 Actual Time: 45 Error: 1 Expected Time: 452 Actual Time: 451 Error: -1 Expected Time: 407 Actual Time: 418 Error: 11 Expected Time: 458 Actual Time: 469 Error: 11 Expected Time: 492 Actual Time: 498 Error: 6 Expected Time: 443 Actual Time: 451 Error: 8 Expected Time: 14 Actual Time: 15 Error: 1 Expected Time: 163 Actual Time: 169 Error: 6 Expected Time: 194 Actual Time: 202 Error: 8 Expected Time: 61 Actual Time: 61 Error: 0 Expected Time: 119 Actual Time: 121 Error: 2 Expected Time: 101 Actual Time: 105 Error: 4 Expected Time: 290 Actual Time: 293 Error: 3 Expected Time: 275 Actual Time: 277 Error: 2 Expected Time: 117 Actual Time: 121 Error: 4 Expected Time: 86 Actual Time: 91 Error: 5 Press any key to continue . . . 

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; using System.Collections.Concurrent; namespace Test { public class TimeEvent { public DateTime Time { get; set; } public bool Enabled { get; set; } public TimeEvent() { Enabled = true; } public virtual void Execute() { } } public class TimeEvent1 : TimeEvent { public int Index { get; set; } public Action Callback { get; set; } public TimeEvent1(int index, TimeSpan time) { Index = index; Time = DateTime.Now + time; Test.ExpectedTime.Enqueue(Tuple.Create(index, (int)(Time - Test.StartTime).TotalMilliseconds)); } public override void Execute() { Test.ActualTime.Enqueue(Tuple.Create(Index, (int)(DateTime.Now - Test.StartTime).TotalMilliseconds)); } } class Test { public static Thread TimeEventDispatcher { get; set; } public static DateTime StartTime { get; set; } public static ConcurrentQueue<TimeEvent> timeEvents = new ConcurrentQueue<TimeEvent>(); public static ConcurrentQueue<Tuple<int, int>> ExpectedTime = new ConcurrentQueue<Tuple<int, int>>(); public static ConcurrentQueue<Tuple<int, int>> ActualTime = new ConcurrentQueue<Tuple<int, int>>(); public static void StartDispatcher() { TimeEventDispatcher = new Thread(new ThreadStart(() => { TimeEvent timeEvent; while (true) { if (timeEvents.TryDequeue(out timeEvent) && timeEvent.Enabled) { var now = DateTime.Now; if ((timeEvent.Time - now).TotalMilliseconds < 0) { timeEvent.Execute(); } else { timeEvents.Enqueue(timeEvent); } } Thread.Sleep(0); } })); TimeEventDispatcher.Start(); } public static void AddTimeEvent(TimeEvent timeEvent) { timeEvents.Enqueue(timeEvent); } static void Main(string[] args) { StartTime = DateTime.Now; StartDispatcher(); var random = new Random(); for (var i = 0; i < 100; ++i) { AddTimeEvent(new TimeEvent1(i, TimeSpan.FromMilliseconds(random.Next(10, 500)))); } Thread.Sleep(1000); TimeEventDispatcher.Abort(); var expectedTime = ExpectedTime.ToArray(); var actualTime = ActualTime.ToArray(); for (var i = 0; i < expectedTime.Length; ++i) { for (var j = 0; j < actualTime.Length; ++j) { if (expectedTime.Item1 == actualTime[j].Item1) { Console.WriteLine("Expected Time: " + expectedTime.Item2 + " Actual Time: " + actualTime[j].Item2 + " Error: " + (actualTime[j].Item2 - expectedTime.Item2)); } } } } } } 
Output:
 Expected Time: 493 Actual Time: 493 Error: 0 Expected Time: 345 Actual Time: 345 Error: 0 Expected Time: 453 Actual Time: 453 Error: 0 Expected Time: 247 Actual Time: 247 Error: 0 Expected Time: 27 Actual Time: 27 Error: 0 Expected Time: 113 Actual Time: 113 Error: 0 Expected Time: 43 Actual Time: 43 Error: 0 Expected Time: 89 Actual Time: 89 Error: 0 Expected Time: 226 Actual Time: 226 Error: 0 Expected Time: 414 Actual Time: 414 Error: 0 Expected Time: 205 Actual Time: 205 Error: 0 Expected Time: 187 Actual Time: 187 Error: 0 Expected Time: 463 Actual Time: 463 Error: 0 Expected Time: 46 Actual Time: 46 Error: 0 Expected Time: 440 Actual Time: 440 Error: 0 Expected Time: 389 Actual Time: 389 Error: 0 Expected Time: 68 Actual Time: 68 Error: 0 Expected Time: 370 Actual Time: 370 Error: 0 Expected Time: 290 Actual Time: 290 Error: 0 Expected Time: 195 Actual Time: 195 Error: 0 Expected Time: 245 Actual Time: 245 Error: 0 Expected Time: 461 Actual Time: 461 Error: 0 Expected Time: 372 Actual Time: 372 Error: 0 Expected Time: 430 Actual Time: 430 Error: 0 Expected Time: 243 Actual Time: 243 Error: 0 Expected Time: 73 Actual Time: 73 Error: 0 Expected Time: 78 Actual Time: 78 Error: 0 Expected Time: 261 Actual Time: 261 Error: 0 Expected Time: 259 Actual Time: 259 Error: 0 Expected Time: 264 Actual Time: 264 Error: 0 Expected Time: 79 Actual Time: 79 Error: 0 Expected Time: 449 Actual Time: 449 Error: 0 Expected Time: 485 Actual Time: 485 Error: 0 Expected Time: 304 Actual Time: 304 Error: 0 Expected Time: 435 Actual Time: 435 Error: 0 Expected Time: 93 Actual Time: 93 Error: 0 Expected Time: 21 Actual Time: 21 Error: 0 Expected Time: 145 Actual Time: 145 Error: 0 Expected Time: 60 Actual Time: 60 Error: 0 Expected Time: 308 Actual Time: 308 Error: 0 Expected Time: 384 Actual Time: 384 Error: 0 Expected Time: 138 Actual Time: 138 Error: 0 Expected Time: 417 Actual Time: 417 Error: 0 Expected Time: 328 Actual Time: 328 Error: 0 Expected Time: 441 Actual Time: 441 Error: 0 Expected Time: 131 Actual Time: 131 Error: 0 Expected Time: 438 Actual Time: 438 Error: 0 Expected Time: 145 Actual Time: 145 Error: 0 Expected Time: 175 Actual Time: 175 Error: 0 Expected Time: 422 Actual Time: 422 Error: 0 Expected Time: 267 Actual Time: 267 Error: 0 Expected Time: 496 Actual Time: 496 Error: 0 Expected Time: 408 Actual Time: 408 Error: 0 Expected Time: 371 Actual Time: 371 Error: 0 Expected Time: 432 Actual Time: 432 Error: 0 Expected Time: 45 Actual Time: 45 Error: 0 Expected Time: 475 Actual Time: 475 Error: 0 Expected Time: 35 Actual Time: 35 Error: 0 Expected Time: 16 Actual Time: 16 Error: 0 Expected Time: 455 Actual Time: 455 Error: 0 Expected Time: 47 Actual Time: 47 Error: 0 Expected Time: 283 Actual Time: 283 Error: 0 Expected Time: 331 Actual Time: 331 Error: 0 Expected Time: 464 Actual Time: 464 Error: 0 Expected Time: 346 Actual Time: 346 Error: 0 Expected Time: 258 Actual Time: 258 Error: 0 Expected Time: 203 Actual Time: 203 Error: 0 Expected Time: 170 Actual Time: 170 Error: 0 Expected Time: 113 Actual Time: 113 Error: 0 Expected Time: 359 Actual Time: 359 Error: 0 Expected Time: 379 Actual Time: 379 Error: 0 Expected Time: 425 Actual Time: 425 Error: 0 Expected Time: 321 Actual Time: 321 Error: 0 Expected Time: 483 Actual Time: 483 Error: 0 Expected Time: 313 Actual Time: 313 Error: 0 Expected Time: 119 Actual Time: 119 Error: 0 Expected Time: 56 Actual Time: 56 Error: 0 Expected Time: 55 Actual Time: 55 Error: 0 Expected Time: 490 Actual Time: 490 Error: 0 Expected Time: 123 Actual Time: 123 Error: 0 Expected Time: 137 Actual Time: 137 Error: 0 Expected Time: 434 Actual Time: 434 Error: 0 Expected Time: 98 Actual Time: 98 Error: 0 Expected Time: 339 Actual Time: 339 Error: 0 Expected Time: 498 Actual Time: 498 Error: 0 Expected Time: 84 Actual Time: 84 Error: 0 Expected Time: 52 Actual Time: 52 Error: 0 Expected Time: 126 Actual Time: 126 Error: 0 Expected Time: 373 Actual Time: 373 Error: 0 Expected Time: 402 Actual Time: 402 Error: 0 Expected Time: 120 Actual Time: 120 Error: 0 Expected Time: 488 Actual Time: 488 Error: 0 Expected Time: 140 Actual Time: 140 Error: 0 Expected Time: 107 Actual Time: 107 Error: 0 Expected Time: 273 Actual Time: 273 Error: 0 Expected Time: 112 Actual Time: 112 Error: 0 Expected Time: 308 Actual Time: 308 Error: 0 Expected Time: 454 Actual Time: 454 Error: 0 Expected Time: 483 Actual Time: 483 Error: 0 Expected Time: 195 Actual Time: 195 Error: 0 Press any key to continue . . . 

1. 1
2. 2
Rutin
21
3. 3
A4L
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633741
• Total Posts
3013624
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!